Operating Systems | Subject Wise Gate CS Questions

The Principle of Locality of Reference justifies the use of cache Memory.
In other words, Locality of Reference refers to the tendency of the computer program to access instructions whose addresses are near one another.

locality of reference. There are two ways with which data or instruction is fetched from main memory and get stored in cache memory. These two ways are the following:

Temporal Locality :
Temporal locality means current data or instruction that is being fetched may be needed soon.
In Temporal Locality The Least Recently Algorithm is Used (LRU)
Clustering in time: items referenced in the immediate past have a high probability of being re-referenced in the immediate future

Spatial Locality:
Spatial locality means instruction or data near to the current memory location that is being fetched, may be needed soon in the near future.
Clustering in space: items located physically near an item referenced in the immediate past have a high probability of being re-referenced in the immediate future  

Social network analysis use to Facebook api access Facebook data
API is the acronym for Application Programming Interface, which is a software intermediary that allows 2 applications to talk to each other.

• Time taken to switch between user and kernel models is LESS THEN the time taken to switch between two processes.
• Time taken to switch between 2 processes is very high as compared to time taken to switch between kernel and user mode of execution because
• We need to do a context switch when we switch processes and we need to save the previous process PCB(Process control Block) and its registers and then load the new process PCB and its registers
• But when you switch between Kernal and User mode is a very fast operation because(OS has to just change single bit at hardware level)
• However, context switch involves a switch to the kernel mode too But switching to kernel mode is not so fast. It is a system call.

option(A) In asymmetric multiprocessing, the processor are peers. - False
In asymmetric multiprocessing, processors are controlled by one central processor or master processor. CPUs are not self scheduling in AMP. In this, master slave approach is used.

option(B) In symmetric multiplexing, the processors are placed symmetrically on the motherboard - False
In this, all processors are self scheduling in nature. They share a common memory space. All have same precedence. These are useful for time sharing systems. So, given statement is incorrect as all processors can do the operating system task.

option(C) Clustered systems are used for high performance computing. - True
Clustered systems result in high performance as they contain two or more individual computer systems merged together. These work as a parallel unit and result in much better performance for the system.

option(D) All multiprocessor systems are multicore systems - False
A processor that has more than one core is called Multicore Processor while one with single core is called Unicore Processor or Uniprocessor
Two or more processors or CPUs present in same computer, sharing system bus, memory and I/O is called Multi Processing System. It allows parallel execution of different processors.
In a multicore system, we have only one CPU and multiple cores are present in that CPU. While in a multiprocessor system, we have more than one CPU.
If you want to run a single program then the multicore system will be faster. But if you are running multiple programs then the multiprocessor system will be faster.

Operating System maintains a small table called the open-file table. It containing information about all open files.
-----When a file operation is requested, the file is specified via an index into this table, so no searching is required.
------When the file is no longer being actively used, it is closed by the process, and the OS removes its entry from the open-file table.

Open-File table also has an open count associated with each file to indicate how many processes that have the file open.
Each close () decreases this open count, and when the open count reaches zero, the file is no longer in use, and the file's entry is removed from the open-file table.

Refer : http://boron.physics.metu.edu.tr/ozdogan/OperatingSystems/week11/node4.html

Given,
Hit ratio = H = 80 % = 0.8
Miss ratio = (1 – H) = 20 % = 0.2
TLB access time = 100ns
Main Memory access time = 400ns
Page is found = (T + M) = 100 ns
Page is not found = (T + 2 × M) = 400 ns

Formula:
Effective memory access time (EAT) =
TLB_Miss_Time * (1- hit_ratio) + TLB_hit_time * hit_ratio

Calculation:
EAT = 0.8*100+0.2*400
=80 + 80
= 160

So option(D) is correct Answer

When the disk drive is reading from cylinder 20 According to FCFS Scheduling it will server (20),10, 22, 20, 2, 40, 6 ,38 Total seek time= (10 + 12 + 2 + 18 + 38 + 34 + 32)*6
= 146*6
= 876 ms

Virtual address = 32 bit
Virtual address space = 2^​32 B
Physical address = 28 bit
Physical address space =  2​²⁸​ B
Page size = 2KB =2^​11​

Number of entries for virtual page number  
= 2​^{virtual address​} / Pages Size
= 2^​32​ /2^​11​ =2​²¹

Number of entries for physical page number
= 2^{​ physical address​} / Pages  Size
=2^​28​ /2​¹¹​ =2^​17

∴ Number bits for virtual page number =21.
∴ Number bits for physical page number = 17.

Page size = 100 records
Frame size = 100 records

• 0100−1 page fault       → Records Range [0100−0199 ]
• 0200−2  page faults  → Range[0200−0299]
• 0430−3  page faults. → Range[0400−0499]
• 0499−3  page faults. → Range[ 0400−0499]
• 0510−4  page faults. → Range[ 0500−0599 ]
• 0530−4  page faults → Range[ 0500−0599 ]
• 0560−4 page faults → Range[ 0500−0599 ]
• 0120−5  page faults → Range[ 0100−0199 ]
• 0220−6  page faults → Range[ 0200−0299 ]
• 0240−6  page faults → Range[ 0200−0299 ]
• 0260−6 page faults → Range[ 0200−0299 ]
• 0320−7  page faults → Range[ 0300−0399 ]
• 0370−7  page faults → Range[ 0300−0399 ]

Total number of page fault is 7.

The major functions or requirements for an I/O module fall into the following categories
1) Control and timing
2) Processor communication
3) Device communication
4) Data buffering
5) Error detection

Assign 1 thread for each image so that all images will load faster and performance of the browser will speed up

• A real-time operating system (RTOS) is an operating system (OS) intended to serve real-time applications that process data as it comes in, typically without buffer delays.
• Processing time requirements (including any OS delay) are measured in tenths of seconds or shorter increments of time.
• A real-time system is a time-bound system which has well-defined, fixed time constraints. Processing must be done within the defined constraints or the system will fail. They either are event-driven or time-sharing.
• Event-driven systems switch between tasks based on their priorities, while time-sharing systems switch the task based on clock interrupts.
• Most RTOS use a pre-emptive scheduling algorithm
• RTLinux is a hard realtime real-time operating system (RTOS) microkernel that runs the entire Linux operating system as a fully preemptive process.

A path is either relative or absolute.
An absolute path always contains the root element and the complete directory list required to locate the file.
Example:
/home/sally/statusReport is an absolute path. All of the information needed to locate the file is contained in the path string.
Linux absolute path example 2
/home/users/c/computerhope/public_html/cgi-bin
Internet URL absolute path
https://www.academyera.com/oh.htm

A relative path needs to be combined with another path in order to access a file. Example
joe/foo is a relative path. Without more information, a program cannot reliably locate the joe/foo directory in the file system.
Linux relative path
./public_html/cgi-bin
Internet URL relative path
oh.htm

• In contiguous memory allocation each process is contained in a single contiguous block of memory. Memory is divided into several fixed size partitions.
• Each partition contains exactly one process. When a partition is free, a process is selected from the input queue and loaded into it.
• The free blocks of memory are known as holes. The set of holes is searched to determine which hole is best to allocate.

A memory transaction is a sequence of read-write operations to memory that are performed atomically.
void update()
{
read/write memory
}

• Monolithic kernel means that the whole operating system runs in kernel mode (i.e. highly privileged by the hardware). That is, no part of the OS runs in user mode (lower privilege). Only applications on top of the OS run in user mode.
• In non-monolithic kernel operating systems, such as Windows, a large part of the OS itself runs in user mode.
• In either case, the OS can be highly module

-Throughput means total number of tasks executed per unit time.
-If the number of processors are increased then amount of work done is increased and time is decreased.
-In Shortest Job First scheduling algorithm has maximum throughput because in this scheduling technique the processor selects the process with the smallest execution time to execute next. Hence, maximum number of tasks are completed.

Note :

• Highest Response Ratio Next policy favors shorter jobs but it also limits the waiting time of longer jobs.
• Priority scheduling is a non-preemptive scheduling algorithm.
• Round-robin scheduling is a preemptive scheduling algorithm.
• Shortest job first scheduling results in maximum throughput.
• First come first serve scheduling algorithm is the simplest scheduling algorithm.

Refer this link for more information :
https://en.wikipedia.org/wiki/Object_Linking_and_Embedding

A major problem with the priority scheduling algorithm is indefinite blocking or starvation. This algorithm can leave some low priority processes waiting indefinitely.

The solution to the problem of starvation is aging. Aging is a technique of gradually increasing the priority of processes that wait in the system for a long time.

For example - If priorities range from 100 to 0(high), we could increase the priority of a waiting process by 1 every 15 minutes. Due to this, even a process with 100 priority would have the highest priority.

Threads are sometimes called lightweight processes because the threads share the common memory space.
The memory allocated to the main thread will be shared by all other child threads.
Whereas in case of Process, the child process are in need to allocate the separate memory space

• It clearly says "There is only one job" So, Round robin algorithm won't perform any context switch
• But according to their intention it may cause total 6 connected switches i.e initially started with 0 ( 0-2 | 2-4 | 4-6 | 6-8 | 8-10 | 10-12 | 12-14 )

• Volatile and Non-Volatile Memory are both types of computer memory.
• Volatile Memory is used to store computer programs and data that CPU needs in real time and is erased once computer is switched off. RAM and Cache memory are volatile memory.
• Non-volatile memory is static and remains in the computer even if computer is switched off. ROM and HDD are non-volatile memory.

In order to avoid deadlock minimum number of resources required is "n+1" If there are "n" process.
Given n = 3
so minimum we require (3+1=4) resources In order to avoid deadlock.

If we give 1 resource to 1 process then total resource = 1 + 1 + 1 = 3 but in this case deadlock will definitely occur because each process hold 1 unit resource and waiting for another resource so if we increase 1 more resource (3+1=4) then deadlocks will ever arise i.e., when process 1 complete their execution then it free 2 resource and this 2 resource will used by another process.

Correct answer is External fragmentation

Virtual memory is a memory management scheme that allows the execution of processes that may not be completely in main memory. In other words, virtual memory allows execution of partially loaded processes. As a consequence user programs can be larger than the physical memory.

Bélády’s anomaly is the name given to the phenomenon where increasing the number of page frames results in an increase in the number of page faults for a given memory access pattern.
This phenomenon is commonly experienced in following page replacement algorithms
First in first out (FIFO)
Second chance algorithm
Random page replacement algorithm

Banker’s Algorithm is a deadlock avoidance algorithm. It is also used for deadlock detection. This algorithm tells that if any system can go into a deadlock or not by analyzing the currently allocated resources and the resources required by it in the future.
Refer this link for more information : https://afteracademy.com/blog/what-is-bankers-algorithm

***Question setter may be drunk while framing the question*****
Semaphores main job is to provide Mutual exclusion to ensure process synchronization and Race condition is the problem and to solve that problem we need to do Mutual exclusion and Process Synchronization

S1: A small page size causes large page tables - True
Smaller page size means more pages required per process. It means large page tables are needed.

S2: internal fragmentation is increased with small pages- False
Internal fragmentation means when process size is smaller than the available space. When pages are small, then available space becomes less and there will be less chances of internal fragmentation.

S3: I/O transfers are more efficient with large pages- True
An I/O system is required to take an application I/O request and send it to the physical device. Transferring of I/O requests are more efficient with large pages.

In  c-scan disk scheduling algorithm, the disk head moves from one end to other end of the disk, serving the requests along the way.
When the head reaches the other end, it immediately returns to the beginning of the disk without serving any requests on the return trip.
Refer : http://www.cs.iit.edu/~cs561/cs450/disksched/disksched.html

Given file sizes,
F1=150 KB,
F2 = 225 KB,
F3 =75 KB,
F4= 60 KB,
F5 =275 KB,
F6 =65 KB.

For access time optimization sort the files in increasing order of file size.

F4= 60 KB, F6 =65 KB, F3 =75 KB, F1=150 KB,F2 = 225 KB, F5 =275 KB.

(F4,F6)=125 KB
((F4,F6),F3)=200 KB
(((F4,F6),F3),F1)=350 KB
(F2,F5)= 500 KB
Finally (F4,F6,F3,F1) (F2,F5) = 700 KB
So order will be F4,F6,F3,F1,F2,F5

Dispatcher is the module that gives control of the CPU to the process selected by the short-term scheduler. It receives control in kernel mode as the result of an interrupt or system call.

The functions of a dispatcher are :

• Context switches in which the dispatcher saves the state (also known as context) of the process or thread that was previously running; the dispatcher then loads the initial or previously saved state of the new process.
• Switching to user mode.
• Jumping to the proper location in the user program to restart that program indicated by its new state.

In Bitmap, I bit is required to store the information about the block. If the block is in use then its set as 1 else it set as 0.
Given data,
Total Memory(Hard Disk capacity) = 1 TB= (10^12) bytes
Block size = 1KB = (10^3) bytes
Number of Block = (10^12/10^3)= (10^9)
So, we need 10^9 bit to store all the information about bitmap,
Size of the bit vector = 10^9 bits

Note:
K = 10^3
M=10^6
G=10^9
T=10^12

Statement I  - A function of a linker is to combine several object modules into a single load module - True
linker or link editor is a computer system program that takes one or more object files (generated by a compiler or an assembler) and combines them into a single executable file, library file, or another "object" file

Statement II -  A function of a linker is to replace absolute references in an object module by symbolic - False
linker always generate relocatable address 

Given,
There are three processes P1, P2 and P3
Initial value of semaphore S = 1

1. P2 needs to access So we are allocating the critical section to P2 So, decreases semaphore value by 1, now S value became 0 (no one is waiting)
2. P1 needs to access decreases semaphore by 1, now S value became -1 (but processor is not available because p2 is accessing. So, one process is waiting)
3. P3 needs to access decreases semaphore value by 1, new S value became -2 ( Still processor not available so p1 and p3 process are waiting total 2 process are waiting)
4. P2 exits critical section increases semaphore value by 1, new S value will be -1 ( one process is waiting now p1 entered the critical section)
5. P1 exits critical section increases semaphore by 1, new S value will be 0 ( now p3 entered critical section So no process is waiting)

Effective memory access(EMA) =
Hit ratio * (TLB access time + Main memory access time) + (1-Hit ratio) * (TLB access time + (L+1) * main memory time)
Where,
L = Number of levels of page table
Miss Rate = (1-Hit ratio)
Note : This formula is valid only when there are no page faults

Given,
Number of levels of page table (L) = 1
TLB access time = 30 ns
Main memory access time = 90 ns
TLB Hit ratio = 70% = 0.7
EMA = ?
EMA =Hit ratio*(TLB access time + Main memory access time) +(1-Hit ratio) * (TLB access time + 2 * main memory time)
EMA=0.7*(30+90)+0.3(30+(2*90))
=0.7*120 + 0.3(30+(180))
=0.7*120 + 0.3*210
= 84 + 63
= 147 ns

Starvation occurs when a low priority process is requesting for a system resource but the resource is never allocated to this process because a higher priority process is utilizing that resource for an extended period.

Round Robin Scheduling: Each process is served by the CPU for a fixed time quantum, so all processes are given the same priority. Starvation doesn't occur because for each round robin cycle, every process is given a fixed time to execute. No process is left behind.

First-come, first-served (FCFS) scheduling is the simplest scheduling algorithm and FCFS can cause short processes to wait for very long processes. but it is clear that other process will definitely get their chance to execute, so it will not suffer from starvation.

In Priority based scheduling if higher priority process keep on coming then low priority process will suffer from starvation.

In Shortest Job First(SJF) if process with short process time keep on coming continuously then process with higher burst time will do wait and suffer from starvation.

As the Shortest remaining time first(SRTF) scheduling is a preemptive version of shortest job scheduling. It may cause starvation as shorter processes may keep coming and a long CPU burst process never gets CPU.

• A distributed system is a collection of independent computers that appear to the users of the system as a single computer.
• A Distributed operating system is usually defined as running on more loosely coupled hardware .
• There is no shared memory, but provides the “feel” of a single memory by Tightly-Coupled software.
• There is one single Operating System, the goal of Distributed system is to make the collection of machines behave more like a single machine. So that means there is tightly coupled OS running on a loosely coupled hardware.

P1 requires 2, P2 requires 5, P3 requires 7
In worst case, The number of units that each process holds = One less than its maximum demand

• Process P1 holds 1 units of resource R
• Process P2 holds 4 units of resource R
• Process P3 holds 6 units of resource R

Maximum number of units of resource R that ensures deadlock = 1 + 4 + 6 = 11
Minimum number of units of resource R that ensures no deadlock = 11 + 1 = 12
So, any number of units greater than 11 will ensure no deadlock.
Note : Given key is option(B) but it satisfies option-A,B,C

In "Shortest job first scheduling" Average response time is minimum. Assuming x = 4, Shortest job first scheduling sequence shall be C(3), E(4), D(5), B(6) and A(9)

Let,
P = Process
BT = Burst or Execution time
CT = completion time
AWT = Average Waiting Time
AT = Arrival time
WT = Waiting time

BT = Burst or Execution time
P = Process
AT = Arrival time

P1 to P2 = 1 switch
P2 to P1 =2nd switch
P1 to P3 =3rd switch

The given scheduling algorithm works as round robin with Time quantum equals to T units, after a process is scheduled it gets executed for T time units, its waiting time becomes least and its turn comes again after every other process has completed T time units.

• Normal instruction takes 1 micro second i.e., 10^-6 sec
• Instruction with page fault takes 2001 micro seconds so page fault will take 2000 microsecond
• The given program takes 60 sec to run and  In that program there were 15000 page fault
• so time taken by 1 page faults 2000 micro seconds
• so time taken by 15000 page faults = 15000x2000 microseconds = 30 sec
• Out of overall  Given 60 seconds of the program time remaining 30 sec are consumed by program execution
• If memory is doubled than the mean interval between the page faults is also doubled
• Hence page fault rate will be reduced by half
• So when Earlier 30 sec were needed by program instructions and 30 sec for page fault
• Now program execution takes 30 sec  and page fault will take 15 sec given by (15000x2000x10^-3)/2
• So Total Time = 30+15 =45 sec.

Given,
Bytes per track = 16384
Rotational Time = 16 msec
Average Seek Time = 40 msec
Time in msec to read a block of 1024 bytes from this disk = ?
If there are 16384 bytes per track there are 1024/16384 tracks to be read for this block.
Transfer Time(TT) = ((1024 bytes * 16 ms) / (16384 bytes )) = 1 msec
Rotational Latency = 16 msec / 2 = 8 msec
Total time = Seek time + Rotational Latency + Transfer time
= 40 msec + 8 msec +1 msc
= 49 msec

• Option(A) : What is the maximum number of cells possible in the base cuboid ?
  pⁿ.
  This is the maximum number of distinct tuples that you can form with p distinct values per dimensions.
• Option(B) : What is the minimum number of cells possible in the base cuboid?
  p.
  You need at least p tuples to contain p distinct values per dimension. In this case no tuple shares any value on any dimension.
• Option(C) : What is the minimum number of cells possible in the data cube, C?
  (2ⁿ-1)×p+1.
  The minimum number of cells is when each cuboid contains only p cells, except for the apex, which contains a single cell.
• Option(D): What is the maximum number of cells possible (including both base cells and aggregate cells) in the data cube, C?
  (p+1)ⁿ.
  The argument is similar to that of part (a), but now we have p+1 because in addition to the p distinct values of each dimension we can also choose ∗.

SSTF : The movement of disk head from 143 to others is as shown in diagram.

So, total head movement = 02+14+04+04+38+08=70 cylinders.
Seek time = 70 X 6 = 420 msec
= 420/1000 msec= 0.42 sec
Note : 1 sec = 1000 msec

For a concurrent execution there should be no read-write ,write-write or write-read conflict
Option (A) : It violates concurrent execution of two process Pi and Pj because it performs Read and Write operation
Option (B) : It violates concurrent execution of two process Pi and Pj because it performs Write and Read operation
Option (C) : It not violates concurrent execution of two process Pi and Pj because it performs Read and Read operation. Moreover Two process can read the data simultaneously.
Option (D) : It violates concurrent execution of two process Pi and Pj because it performs Write and Write operation

The directory can be viewed as symbol table that translates filenames into their directory entries. The symbol table is created by the compiler front-end as a stand-alone file. The purpose of the table is to provide information that the linker and the debugger need to perform their respective functions

Refer :
https://www3.physnet.uni-hamburg.de/physnet/Tru64-Unix/HTML/APS31DTE/DOCU_014.HTM

The two-level CPU scheduling is used when memory is too small to hold all the ready processes because it facilitates putting some set of processes into memory and a choice is made from that.
Refer : https://en.wikipedia.org/wiki/Two-level_scheduling

Given,
Program Text = 200 K
Initial stack = 15 K
Initialized data=50 K
Bootstrap code=70 K
Number of editors = 5
physical memory is needed if shared text is used = ?
Since 5 editors started simultaneously On 200k of program text along with 15 K of initial stack, 50 K of initialized data, and 70 K of bootstrap code.
Total physical memory needed = Program Text + Initial stack + Initialized data + Bootstrap code
Total physical memory needed = = 200k + 15 K + 50 K + 70 K.
Total physical memory needed = = 335 k

In Critical section problem:

• No assumptions may be made about speeds or the number of CPUs.
• No two processes may be simultaneously inside their critical sections.
• Processes running outside its critical section can’t block other processes getting enter into critical section or not it is not going to effect the processes which are running inside the critical section anyway.
• Processes do not wait forever to enter its critical section.

Refer : http://www2.cs.uregina.ca/~hamilton/courses/330/notes/synchro/node2.html

Time to serve page fault if frame is empty or page replaced is not modified = 8 m.sec
Time to serve page fault if page is modified = 20 m.sec
Frequency of Page modification = 70% = 70/100 = 0.7
Frequency when page is not modified or frame is empty = (100-70)% = 30% = 0.3
Average access time = (Not modified*Time to serve page fault) + (Modified time * percentage of page modification)
Average access time = (0.3 * 8) + (0.7 * 20)
= 2.4 + 14
= 16.4 m.sec

Given,
Total Number of Resources (R) Available = 12
Maximum need for each resource (N) = 4

Deadlock-free condition :
R ≥ P(N − 1) + 1

Where,
R is total number of resources available,
P is the number of processes,
N is the maximum need for each resource.
12 ≥ P(4 − 1) + 1
11 ≥ 3P
11/3 ≥ P
P ≤ 3.66
P=3
∴Maximum value of n for which the system never enters into deadlock is 3

Note :
-Floor value for maximum
-Ceil value for minimum

Mutual execution means only one process can enter into the critical section at a time so when Process Q is in critical section then no other process can enter into the critical section.

 

Indirect	1 bit
Address	Given Address 256kB    28 (256kB) * 210 (1024 bytes/kB) = 218 == 18 bits
Registers	Total 64 registers = 26 = 6 bits
OP-code	32 - 1 - 18 - 6 bits = 7 bits

Ignoring search time with in the cache statement tells us to use parallel access( simultaneous access ).

By default we consider hierarchical access - because that is the common implementation and simultaneous access cache has great practical difficulty
but in this question they given ignore search time within the cache usually search is applicable for an associative cache but here no such information given. So, may be they are telling to ignore the search time for L1 and just consider the time for L2 for an L1 miss and similarly just consider memory access time for L2 miss. This is nothing but simultaneous access.

Access time for hierarchical access
=h1×t1+ (1-h1) h2(t1+t2) +(1-h1)(1-h2)(t1+t2+tm)

Access time for simultaneous access
=h1×t1+(1−h1)h2×t2+(1−h1)(1−h2)tm
where,
H1 = Hit rate of level 1 cache = 0.7
T1 = Access time for level 1 cache = 0.5 ns
H2 = Hit rate of level 2 cache = 0.8
T2 = Access time for level 2 cache = 5 ns
Hm = Hit rate of Main Memory = 1
Tm = Access time for Main Memory = 100 ns
=h1×t1+(1−h1)h2×t2+(1−h1)(1−h2)tm
= 0.7(0.5) + 0.3(0.8)(5) + 0.3(0.2)(100)
= 7.55 ns

Given,
Number of surfaces = 32(2⁵)
Number of tracks per surface = 64(2⁶)
Number of sectors per track = 512(2⁹)
Number of bytes per sector = 256 bytes(2⁸)
Total number of sectors
= Total number of surfaces  * Number of tracks per surface  * Number of sectors per track
=32 * 64 * 512
=(2⁵) * (2⁶)  * (2⁹)
=5+6+9
=20 bits
To identify each sector uniquely  we require 20 bits

Dirty bit

• A dirty bit or modified bit is a bit that is associated with a block of computer memory and indicates whether or not the corresponding block of memory has been modified.
• The dirty bit is set when the processor writes to (modifies) this memory. The bit indicates that its associated block of memory has been modified and has not been saved to storage yet.
• When a block of memory is to be replaced, its corresponding dirty bit is checked to see if the block needs to be written back to secondary memory before being replaced or if it can simply be removed.
• Dirty bits are used by the CPU cache and in the page replacement algorithms of an operating system.
• Example : When a page is modified inside the cache and the changes need to be stored back in the main memory, the valid bit is set to 1 so as to maintain the record of modified pages.

A new process is created by fork() system call in UNIX. fork() system call returns a process ID which is generally the process id of the child process created.

A process residing in main memory and ready and waiting for execution, is kept on Ready Queue

Effective memory access(EMA) = Hit ratio * (TLB access time + Main memory access time) + (1-Hit ratio) * (TLB access time + (L+1) * main memory time)
Where,
L = Number of levels of page table
Miss Rate = (1-Hit ratio)
Note : This formula is valid only when there are no page faults

Given,
Number of levels of page table = 1
TLB access time = 20 ns
Main memory access time = 100 ns
TLB Hit ratio = 80% = 0.8
TLB Miss ratio= 1 – 0.8= 0.2

Effective Memory Access Time
= 0.8 x { 20 ns + 100 ns } + 0.2 x { 20 ns + (1+1) x 100 ns }
= 0.8 x 120 ns + 0.2 + 220 ns
= 96 ns + 44 ns
= 140 ns

• Block size = 256 KB
• Size of one address = 2Bytes
• Each indirect block stores 256/2 =128 pointers.
• Double indirect block can point 128 x 128 blocks
• Maximum file size = 128 x 128 x 256 = 4194304 B= 4096 KB =4MB

Given,
Counting Semaphore value (S) = 10
P operations = 12
V operations = x
Final Semaphore value (S) = 7

P operation also called as wait operation decrements the value of semaphore variable by 1.
V operation also called as signal operation increments the value of semaphore variable by 1.

Initially  value of a counting semaphore  S= 10
After 12 P operation are performed "S" Value became = -2
“x” V operations are performed on this semaphore S
now Final value of counting semaphore S = 7
x + (-2) = 7
x -2 = 7
x = 7+2
x = 9.

Given,
Page Hit Ratio is = 0.40
Secondary Memory Access Time=120 ns
Primary Memory Access Time=15 ns
Miss Ratio =1 – hit ratio
Average access time= ?

Average access time = hit ratio * primary memory access time + (1 – hit ratio) * secondary memory access time

Average access time = 0.4 * 15 + 0.6 * 120
Average access time = 6 + 72
Average access time = 78.

Statement(A) : False
External Fragmentation exists where there is enough total memory space to satisfy a request but available space is not contiguous.

Statement(B) : True
Memory Fragmentation can be internal as well as external.

Statement(C) : True
One solution to external Fragmentation is compaction or shuffle memory contents.
Best Fit Block Search is the solution for internal fragmentation

• Page information in memory is also called as Page Table
• A page table entry must contain Page frame number.
• Virtual page number is typically used as index in page table to get the corresponding page frame number.

Given String,
1, 2, 3, 2, 4, 2, 5, 2, 3, 4
Total number of page faults are 7

• Unicode-enabled functions are described in Conventions for Function Prototypes.
• These functions use UTF-16 (wide character) encoding, which is the most common encoding of Unicode and the one used for native Unicode encoding on Windows operating systems.
• Each code value is 16 bits wide, in contrast to the older code page approach to character and string data, which uses 8-bit code values.
• The use of 16 bits allows the direct encoding of 65,536 characters.
• In fact, the universe of symbols used to transcribe human languages is even larger than that, and UTF-16 code points in the range U+D800 through U+DFFF are used to form surrogate pairs, which constitute 32-bit encodings of supplementary characters

• In Priority scheduling technique, we assign some priority to every process we have and based on that priority, the CPU will be allocated and the process will be executed. Here, the CPU will be allocated to the process that is having the highest priority
• higher priority processes keep on coming and the CPU is allocated to that higher priority processes and the low priority process keeps on waiting for its turn is called Starvation
• To avoid starvation, we use the concept called Aging.
• In Aging, after some fixed amount of time quantum, we increase the priority of the low priority processes. By doing so, as time passes, the lower priority process becomes a higher priority process.

• Segmentation is free of internal fragmentation but Suffers from external fragmentation.
• In Paging There is no external fragmentation but internal fragmentation exists.
• Swapping is a mechanism in which a process can be swapped temporarily out of main memory (or move) to secondary storage and make that memory available to other processes. At some later time, the system swaps back the process from the secondary storage to main memory.

• Relocation is the process of assigning load addresses for position-dependent code and data of a program and adjusting the code and data to reflect the assigned addresses
• Relocation is typically done by the linker at link time, but it can also be done at load time by a relocating loader, or at run time by the running program itself.
• Some architectures avoid relocation entirely by deferring address assignment to run time; this is known as zero address arithmetic.
• A linker usually performs relocation in conjunction with symbol resolution, the process of searching files and libraries to replace symbolic references or names of libraries with actual usable addresses in memory before running a program.

Virtual Address = 32 bits
Page size = 4 KB = 2¹² Bytes
Number of bits needed to address the page frame = 32-12=20 bits
Translation Look-aside Buffer (TLB) can hold 64 page table entries with 4-way set associative
Number of sets = 64/4 = 16(16=2⁴ bits.)
Therefore 4 bits are needed to address a set
So Tag bits = 20 - 4 = 16 bits.

Disk Size: 1.3 G bytes = 1.3 * 2³⁰ bytes
Block Size: 512 bytes = 2⁹ bytes

Number of Blocks = disk size / block size
= 1.3 * 2³⁰ bytes / 2⁹ bytes = 1.3 * 2²¹

In Bitmap We need a bit for each block
Number of entries in bit table = Number of blocks
= 1.3 * 2²¹

Size of bit table in bits
= 1.3 * 2²¹ bits

Size of bit table in bytes
= size in bits / (8 bits/byte)
= 1.3 * 2²¹ / 8 bytes
= 1.3 * 2²¹ / 2³ bytes
= 1.3 * 2¹⁸ bytes
= 1.3 * 2⁸ * 2¹⁰ bytes
= 1.3 * 256 * K bytes
= 332.8 K bytes
= 332.8K bytes

Refer : https://en.wikipedia.org/w/index.php?title=Scheduling_(computing)

• In preemptive scheduling tasks are usually assigned with priorities.
• The tasks are prioritized and the task with the highest priority among all other tasks gets the CPU time
• If a task with a priority higher than the currently executing task becomes ready to run, the kernel saves the context of the current task and switches to the higher priority task by loading its context.
• Usually, the highest priority task runs to completion or until it becomes non-computable
• Therefore, the running task is interrupted for some time and resumed later when the priority task has finished its execution. This is called preemptive scheduling.
• In non-preemptive scheduling, a running task is executed till completion. It cannot be interrupted.

• Dijikstra banking algorithm in an operating system, solves the problem of Deadlock avoidance
• The Banker's algorithm is a resource allocation & deadlock avoidance algorithm developed by Edsger Dijkstra
• Banker's algorithm tests for safety by simulating the allocation of pre-determined maximum possible amounts of all resources, and then makes a "safe-state" check to test for possible deadlock conditions for all other pending activities, before deciding whether allocation should be allowed to continue.
• In Banker's algorithm we have 4 data structures are used
  1) Available
  2) Max
  3) Allocation
  4) Need

****We know that page and frame both have the same size***

Physical Memory have 32 frames = 2⁵
Size of word 1024 = 2¹⁰
Size of physical address space = Number of frames × Frame size
Size of physical address space =2⁵× 2¹⁰= 2¹⁵
»» Number of required bits in the physical address =15

Logical Memory have 8 pages = 2³
Size of word = 2¹⁰
Size of logical address space = 2^m
= Number of pages × page size
= 2³ × 2¹⁰ = 2¹³
»» m=13 bit
»» Number of required bits in the logical address = 13 bits

The only state transition that is initiated by the user process itself is block. Whenever a user process initiates an I/O request it goes into block state unless and until the I/O request is not completed.

• In a single file program, while producing the object file, all references to labels are replaced by their corresponding addresses by the assembler.
• Incase of multi-file program, if there are any references to labels defined in another file, the assembler marks these references as "unresolved".
• When these object files are passed to the linker, the linker determines the values for these references from the other object files, and patches the code with the correct values.

• Spooler is a software which works on creating a typical request queue where data, instructions and processes from multiple sources are accumulated for execution later on.
• Spooler is maintained on computer’s physical memory, buffers or the I/O device-specific interrupts.
• The spool is processed in FIFO manner i.e. whatever first instruction is there in the queue will be popped and executed.
• How does printer spooling happen ? Whichever computer you printed from will handle all of the spooling.
• However, if you’re using a printer that’s shared over your network, the network server may handle it.
• A “spooler program” is what manages all of the print jobs in queue. It’ll send the line of documents in the order they were received to the printer (when available).
• It may seem a bit frustrating at first, but this functionality is actually designed to improve speed and efficiency, even though you may commonly see this term when your printer isn’t doing anything at all.

External subroutines are routines that are created and maintained separately from the program that will be calling them.

They are 5 states in Process States State Diagram
1) New
2) Ready
3) Running
4) Waiting
5) Terminated

The minimum number of states is 5 when the process from its creation to completion, passes through various states.

Refer slide 12 : http://web.cs.ucla.edu/~ani/classes/cs111.08w/Notes/Lecture%2016.pdf

sort <in> temp; head - 30 <temp; rm temp

• Head command prints the first N number of data of the given input. By default, it prints first 10 lines of each given file.
  head-30 means so 30 lines are to be read
• sort sorts the contents of a text file, line by line.
   sort <in> temp means Sort, taking the input from "in" and writing the output to "temp"
• rm command removes a file
  rm temp means temp is removed
• The symbol > used to redirection of output and symbol < used to redirect the input

• Processes that interact with each by cooperating to achieve a common goal are called concurrent processes.
• Concurrent processes are processes that share the CPU and memory. They do overlap in time while execution. At a time CPU entertain only one process but it can switch to other process without completing it as a whole.

• Source code is  programming statements that are created by a programmer with a text editor or a visual programming tool and then saved in a file.
• Object code generally refers to the output, a compiled file, which is produced when the Source Code is compiled with a C compiler.
• The object code file contains a sequence of machine-readable instructions that is processed by the CPU in a computer.

Windows is a multi user system. In task manager we can see processes belonging to multiple users and It is also preemptive.

WINDOWS is specified, no specific version or anything is given. If you consider windows 3.x, it was cooperative and non-preemptive. But windows 95,NT and 2000 are preemptive. Windows 3.x was not multi-user. But windows NT,2000 are multi-user. Again windows 3.x cannot be categorized as a real time operating system also. Since the question itself has got some ambiguity

Swapping is one of the memory management techniques used by the operating system. Since the size of the RAM is limited and finite, all the processes or programs to be executed cannot be made to fit in it. So the disk is also treated as an extension of the memory and is referred to as virtual memory. The page making process from main memory to disk is called swapping.

• Deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process.
• Deadlock is an undesirable condition but is a definite waiting process

• In an absolute loading scheme, Loading function is accomplished by the loader
• Loader loads the executable code into memory, program and data stack are created and registers will initialized
• Reallocation change relocatable address into absolute address

Note:
P operation also called as wait operation decrements the value of semaphore variable by 1.
V operation also called as signal operation increments the value of semaphore variable by 1.

• Round Robin(RR) is the preemptive process scheduling algorithm.
• Shortest Job Next(SJN) is a non-preemptive, pre-emptive scheduling algorithm
• First Come First Serve (FCFS) is a non-preemptive, pre-emptive scheduling algorithm.
• Priority Based Scheduling is a non-preemptive algorithm and also preemptive algorithm
• Shortest remaining time (SRT) is the preemptive version of the SJN algorithm.