GATE Operating System previous year questions

With respect to deadlocks in an operating system, which of the following statements is/are FALSE?

1. (A)Banker's algorithm is used to prevent deadlocks
2. (B)Deadlock formation can be prevented by ensuring that the hold and wait condition is not allowed
3. (C)An assignment edge in a resource allocation graph is marked from a process to a resource
4. (D)A safe state guarantees that all processes can finish without formation of a deadlock

Consider a system consisting of k instances of a resource R, being shared by 5 processes. Assume that each process requires a maximum of two instances of resource R and a process can request or release only one instance at a time. Further, a process can request the second instance of the resource only after acquiring the first instance. The minimum value of k for the system to be deadlock-free is ________. (answer in integer)

Consider a hard disk with a rotational speed of 15000 rpm. The time to move the read/write head from a track to its adjacent track is 1 millisecond. Initially, the head is on track 0. The number of sectors per track is 400. The sector size is 1024 bytes. It is necessary to transfer data from 10 randomly located sectors in each of the following tracks in the order: 5, 12 and 7. The total time for the data transfer (in milliseconds) from the hard disk is _________. (rounded off to one decimal place)

Consider the following program snippet. Assume that the program compiles and runs successfully. Further, assume that the fork() system call is always successful in creating a process. The total number of times that the printf statement gets executed is ________. (answer in integer)

int main () {
    int i;
    for (i = 0; i < 3; i++){
        if (fork() == 0){
            continue;
        }
        break;
    }
    printf("Hello!");
    return 0;
}

Consider a CPU that has to execute two types of processes. The first type, Actuators (A), requires a CPU burst of 6 seconds. The second type, Controllers (C), requires a CPU burst of 8 seconds. A new process of type A arrives at time t = 10, 20, 30, 40, and 50 (in seconds). Similarly, a new process of type C arrives at time t = 11, 22, 33, 44, and 55 (in seconds). The CPU scheduling policy is First Come First Serve (FCFS). The first process of type A starts running at t = 10 seconds. The average waiting time (in seconds) for the 10 processes is ___________. (rounded off to one decimal place)

Which one of the following CPU scheduling algorithms cannot be preemptive?

1. (A)Shortest Remaining Time First (SRTF) Scheduling
2. (B)First Come First Serve (FCFS) Scheduling
3. (C)Round Robin Scheduling
4. (D)Priority Scheduling

Consider three processes P1, P2, and P3 running identical code, as shown in the pseudocode below. A and B are two binary semaphores initialized to 1 and 0, respectively. X is a shared variable initialized to 0. Each line in the pseudocode is executed atomically. Assume that any of the three processes can start to execute first and context switching can happen between these processes at any arbitrary time and in any arbitrary order. Which of the following patterns is/are possible to be generated as an outcome of the execution of these three processes?

Wait(A);
Print(*);
X = X+1;
If (X == 2)
   {
      Print($);
      Signal(B);
   }
Signal(A);
Wait(B);
Print(#);
Signal(B);

1. (A)**$*###
2. (B)**$#*##
3. (C)**$##*#
4. (D)***$###

To keep track of free blocks in a file system, one of the two approaches is generally used - using bitmaps (bit vectors) or using linked lists. Consider that the linked list approach is used to keep track of free blocks in a file system. Assume that the disk size is 16 GB, block size is 2 KB, and block numbers used are 32-bit long. A single pointer of size 4 bytes is used in each block of the list to point to the next block of the list. The number of blocks required to hold the free disk block numbers is ____________. (answer in integer) Note: 1K = 2¹⁰ and 1G = 2³⁰

A system has a Translation Lookaside Buffer (TLB) that has a reach of 1 MB. TLB reach is defined as the total amount of physical memory that can be accessed through the TLB entries. The paging system uses pages of size 4 KB. The virtual address space is 64 GB and physical address space is 1 GB. If each TLB entry stores a 4-bit process id, page number, frame number, and a 2-bit control field, then the size of the TLB (in bytes) is ___________. (answer in integer) Note: 1K = 2¹⁰, 1M = 2²⁰, 1G = 2³⁰

Consider contiguous allocation of physical memory to processes using variable partitioning scheme. Suppose there are 8 holes in the memory of sizes 20 KB, 4 KB, 25 KB, 18 KB, 7 KB, 9 KB, 15 KB, and 12 KB. Assume that no two holes are adjacent. Two processes P1 of size 16 KB and P2 of size 9 KB arrive in that order, and they are allocated memory using the best-fit technique. After allocating space to P1 and P2, the number of holes of size less than 8 KB is ____________. (answer in integer) Note: 1K = 2¹⁰

Consider a demand paging memory management system with 32-bit logical address, 20-bit physical address, and page size of 2048 bytes. Assuming that the memory is byte addressable, what is the maximum number of entries in the page table?

1. (A)2²¹
2. (B)2²⁰
3. (C)2²²
4. (D)2²⁴

Suppose in a multiprogramming environment, the following C program segment is executed. A process goes into I/O queue whenever an I/O related operation is performed. Assume that there will always be a context switch whenever a process requests for an I/O, and also whenever the process returns from an I/O. The number of times the process will enter the ready queue during its lifetime (not counting the time the process enters the ready queue when it is run initially) is _______. (Answer in integer)

int main()
{
    int x=0,i=0;
    scanf("%d",&x);
    for(i=0; i<20; i++)
    {
        x = x+20;
        printf("%d\n",x);
    }
    return 0;
}

A computer has two processors, M1 and M2. Four processes P1, P2, P3, P4 with CPU bursts of 20, 16, 25, and 10 milliseconds, respectively, arrive at the same time and these are the only processes in the system. The scheduler uses non-preemptive priority scheduling, with priorities decided as follows: - M1 uses priority of execution for the processes as, P1 > P3 > P2 > P4, i.e., P1 and P4 have highest and lowest priorities, respectively. - M2 uses priority of execution for the processes as, P2 > P3 > P4 > P1, i.e., P2 and P1 have highest and lowest priorities, respectively. A process Pi is scheduled to a processor Mk, if the processor is free and no other process Pj is waiting with higher priority. At any given point of time, a process can be allocated to any one of the free processors without violating the execution priority rules. Ignore the context switch time. What will be the average waiting time of the processes in milliseconds?

1. (A)9.00
2. (B)8.75
3. (C)6.50
4. (D)7.50

A disk of size 512M bytes is divided into blocks of 64K bytes. A file is stored in the disk using linked allocation. In linked allocation, each data block reserves 4 bytes to store the pointer to the next data block. The link part of the last data block contains a NULL pointer (also of 4 bytes). Suppose a file of 1M bytes needs to be stored in the disk. Assume, 1K = 2¹⁰ and 1M = 2²⁰. The amount of space in bytes that will be wasted due to internal fragmentation is ______. (Answer in integer)

In optimal page replacement algorithm, information about all future page references is available to the operating system (OS). A modification of the optimal page replacement algorithm is as follows: The OS correctly predicts only up to next 4 page references (including the current page) at the time of allocating a frame to a page. A process accesses the pages in the following order of page numbers: 1, 3, 2, 4, 2, 3, 1, 2, 4, 3, 1, 4. If the system has three memory frames that are initially empty, the number of page faults that will occur during execution of the process is ________. (Answer in integer)

Processes P1, P2, P3, P4 arrive in that order at times 0, 1, 2, and 8 milliseconds respectively, and have execution times of 10, 13, 6, and 9 milliseconds respectively. Shortest Remaining Time First (SRTF) algorithm is used as the CPU scheduling policy. Ignore context switching times. Which ONE of the following correctly gives the average turnaround time of the four processes in milliseconds?

1. (A)22
2. (B)15
3. (C)37
4. (D)19

Consider a demand paging system with three frames, and the following page reference string: 1 2 3 4 5 4 1 6 4 5 1 3 2. The contents of the frames are as follows initially and after each reference (from left to right): Reference: - 1* 2* 3* 4* 5* 4 1 6* 4 5 1* 3* 2* Frame 1: - 1 1 1 1 1 1 1 6 6 6 6 6 2 Frame 2: - - 2 2 4 4 4 4 4 4 4 1 1 1 Frame 3: - - - 3 3 5 5 5 5 5 5 5 3 3 The *-marked references cause page faults (replacements once the frames are full). Which one or more of the following could be the page replacement policy/policies in use?

1. (A)Least Recently Used page replacement policy
2. (B)Least Frequently Used page replacement policy
3. (C)Most Frequently Used page replacement policy
4. (D)Optimal page replacement policy

P = {P1, P2, P3, P4} consists of all active processes in an operating system. R = {R1, R2, R3, R4} consists of single instances of distinct types of resources in the system. The resource allocation graph has the following assignment and claim edges. Assignment edges: R1 → P1, R2 → P2, R3 → P3, R4 → P4 (the assignment edge R1 → P1 means resource R1 is assigned to process P1, and so on for others). Claim edges: P1 → R2, P2 → R3, P3 → R1, P2 → R4, P4 → R2 (the claim edge P1 → R2 means process P1 is waiting for resource R2, and so on for others). Which of the following statement(s) is/are CORRECT?

1. (A)Aborting P1 makes the system deadlock free.
2. (B)Aborting P3 makes the system deadlock free.
3. (C)Aborting P2 makes the system deadlock free.
4. (D)Aborting P1 and P4 makes the system deadlock free.

A computer system supports a logical address space of 2³² bytes. It uses two-level hierarchical paging with a page size of 4096 bytes. A logical address is divided into a b-bit index to the outer page table, an offset within the page of the inner page table, and an offset within the desired page. Each entry of the inner page table uses eight bytes. All the pages in the system have the same size. The value of b is ___________. (Answer in integer)

Which of the following statements about threads is/are TRUE?

1. (A)Threads can only be implemented in kernel space
2. (B)Each thread has its own file descriptor table for open files
3. (C)All the threads belonging to a process share a common stack
4. (D)Threads belonging to a process are by default not protected from each other

Which of the following process state transitions is/are NOT possible?

1. (A)Running to Ready
2. (B)Waiting to Running
3. (C)Ready to Waiting
4. (D)Running to Terminated

Consider the following two threads T1 and T2 that update two shared variables a and b. Assume that initially a = b = 1. Though context switching between threads can happen at any time, each statement of T1 or T2 is executed atomically without interruption. T1: a = a + 1; b = b + 1; T2: b = 2 * b; a = 2 * a; Which one of the following options lists all the possible combinations of values of a and b after both T1 and T2 finish execution?

1. (A)(a = 4, b = 4); (a = 3, b = 3); (a = 4, b = 3)
2. (B)(a = 3, b = 4); (a = 4, b = 3); (a = 3, b = 3)
3. (C)(a = 4, b = 4); (a = 4, b = 3); (a = 3, b = 4)
4. (D)(a = 2, b = 2); (a = 2, b = 3); (a = 3, b = 4)

Consider a 512 GB hard disk with 32 storage surfaces. There are 4096 sectors per track and each sector holds 1024 bytes of data. The number of cylinders in the hard disk is _________

Consider the following code snippet using the fork() and wait() system calls. Assume that the code compiles and runs correctly, and that the system calls run successfully without any errors. The total number of times the printf statement is executed is _______

int x = 3;
while(x > 0) {
  fork();
  printf("hello");
  wait(NULL);
  x--;
}

Consider a memory management system that uses a page size of 2 KB. Assume that both the physical and virtual addresses start from 0. Assume that the pages 0, 1, 2, and 3 are stored in the page frames 1, 3, 2, and 0, respectively. The physical address (in decimal format) corresponding to the virtual address 2500 (in decimal format) is _________

Which of the following tasks is/are the responsibility/responsibilities of the memory management unit (MMU) in a system with paging-based memory management?

1. (A)Allocate a new page table for a newly created process
2. (B)Translate a virtual address to a physical address using the page table
3. (C)Raise a trap when a virtual address is not found in the page table
4. (D)Raise a trap when a process tries to write to a page marked with read-only permission in the page table

Consider a process P running on a CPU. Which one or more of the following events will always trigger a context switch by the OS that results in process P moving to a non-running state (e.g., ready, blocked)?

1. (A)P makes a blocking system call to read a block of data from the disk
2. (B)P tries to access a page that is in the swap space, triggering a page fault
3. (C)An interrupt is raised by the disk to deliver data requested by some other process
4. (D)A timer interrupt is raised by the hardware

Consider a single processor system with four processes A, B, C, and D, represented as given below, where for each process the first value is its arrival time, and the second value is its CPU burst time. A (0, 10), B (2, 6), C (4, 3), and D (6, 7). Which one of the following options gives the average waiting times when preemptive Shortest Remaining Time First (SRTF) and Non-Preemptive Shortest Job First (NP-SJF) CPU scheduling algorithms are applied to the processes?

1. (A)SRTF = 6, NP-SJF = 7
2. (B)SRTF = 6, NP-SJF = 7.5
3. (C)SRTF = 7, NP-SJF = 7.5
4. (D)SRTF = 7, NP-SJF = 8.5

Consider a multi-threaded program with two threads T1 and T2. The threads share two semaphores: s1 (initialized to 1) and s2 (initialized to 0). The threads also share a global variable x (initialized to 0). The threads execute the code shown below. Which of the following outcomes is/are possible when threads T1 and T2 execute concurrently?

// code of T1        // code of T2
wait(s1);            wait(s1);
x = x+1;             x = x+1;
print(x);            print(x);
wait(s2);            signal(s2);
signal(s1);          signal(s1);

1. (A)T1 runs first and prints 1, T2 runs next and prints 2
2. (B)T2 runs first and prints 1, T1 runs next and prints 2
3. (C)T1 runs first and prints 1, T2 does not print anything (deadlock)
4. (D)T2 runs first and prints 1, T1 does not print anything (deadlock)

Consider a disk with the following specifications: rotation speed of 6000 RPM, average seek time of 5 milliseconds, 500 sectors/track, 512-byte sectors. A file has content stored in 3000 sectors located randomly on the disk. Assuming average rotational latency, the total time (in seconds, rounded off to 2 decimal places) to read the entire file from the disk is _________

Consider a 32-bit system with 4 KB page size and page table entries of size 4 bytes each. Assume 1 KB = 2¹⁰ bytes. The OS uses a 2-level page table for memory management, with the page table containing an outer page directory and an inner page table. The OS allocates a page for the outer page directory upon process creation. The OS uses demand paging when allocating memory for the inner page table, i.e., a page of the inner page table is allocated only if it contains at least one valid page table entry. An active process in this system accesses 2000 unique pages during its execution, and none of the pages are swapped out to disk. After it completes the page accesses, let X denote the minimum and Y denote the maximum number of pages across the two levels of the page table of the process. The value of X+Y is ________

Which one or more of the following need to be saved on a context switch from one thread (T1) of a process to another thread (T2) of the same process?

1. (A)Page table base register
2. (B)Stack pointer
3. (C)Program counter
4. (D)General purpose registers

Which one or more of the following options guarantee that a computer system will transition from user mode to kernel mode?

1. (A)Function Call
2. (B)malloc Call
3. (C)Page Fault
4. (D)System Call

Consider the two functions incr and decr shown below. There are 5 threads each invoking incr once, and 3 threads each invoking decr once, on the same shared variable X. The initial value of X is 10. Suppose there are two implementations of the semaphore s, as follows: I-1: s is a binary semaphore initialized to 1. I-2: s is a counting semaphore initialized to 2. Let V1, V2 be the values of X at the end of execution of all the threads with implementations I-1, I-2, respectively. Which one of the following choices corresponds to the minimum possible values of V1, V2, respectively?

incr(){
    wait(s);
    X = X+1;
    signal(s);
}

decr(){
    wait(s);
    X = X-1;
    signal(s);
}

1. (A)15, 7
2. (B)7, 7
3. (C)12, 7
4. (D)12, 8

Consider the following two-dimensional array D in the C programming language, which is stored in row-major order: int D[128][128]; Demand paging is used for allocating memory and each physical page frame holds 512 elements of the array D. The Least Recently Used (LRU) page-replacement policy is used by the operating system. A total of 30 physical page frames are allocated to a process which executes the following code snippet. The number of page faults generated during the execution of this code snippet is ________.

for (int i = 0; i < 128; i++)
    for (int j = 0; j < 128; j++)
        D[j][i] *= 10;

Consider a computer system with 57-bit virtual addressing using multi-level tree-structured page tables with L levels for virtual to physical address translation. The page size is 4 KB (1 KB = 1024 B) and a page table entry at any of the levels occupies 8 bytes. The value of L is .

Consider the following threads, T1, T2, and T3 executing on a single processor, synchronized using three binary semaphore variables, S1, S2, and S3, operated upon using standard wait() and signal(). The threads can be context switched in any order and at any time. Which initialization of the semaphores would print the sequence BCABCABCA....?

T1                    T2                    T3
while(true){          while(true){          while(true){
   wait(S3);             wait(S1);             wait(S2);
   print("C");           print("B");           print("A");
   signal(S2); }         signal(S3); }         signal(S1); }

1. (A)S1 = 1; S2 = 1; S3 = 1
2. (B)S1 = 1; S2 = 1; S3 = 0
3. (C)S1 = 1; S2 = 0; S3 = 0
4. (D)S1 = 0; S2 = 1; S3 = 1

Which of the following statements is/are TRUE with respect to deadlocks?

1. (A)Circular wait is a necessary condition for the formation of deadlock.
2. (B)In a system where each resource has more than one instance, a cycle in its wait-for graph indicates the presence of a deadlock.
3. (C)If the current allocation of resources to processes leads the system to unsafe state, then deadlock will necessarily occur.
4. (D)In the resource-allocation graph of a system, if every edge is an assignment edge, then the system is not in deadlock state.

Which one of the following statements is FALSE?

1. (A)The TLB performs an associative search in parallel on all its valid entries using page number of incoming virtual address.
2. (B)If the virtual address of a word given by CPU has a TLB hit, but the subsequent search for the word results in a cache miss, then the word will always be present in the main memory.
3. (C)The memory access time using a given inverted page table is always same for all incoming virtual addresses.
4. (D)In a system that uses hashed page tables, if two distinct virtual addresses V1 and V2 map to the same value while hashing, then the memory access time of these addresses will not be the same.

Consider four processes P, Q, R, and S scheduled on a CPU as per round robin algorithm with a time quantum of 4 units. The processes arrive in the order P, Q, R, S, all at time t = 0. There is exactly one context switch from S to Q, exactly one context switch from R to Q, and exactly two context switches from Q to R. There is no context switch from S to P. Switching to a ready process after the termination of another process is also considered a context switch. Which one of the following is NOT possible as CPU burst time (in time units) of these processes?

1. (A)P = 4, Q = 10, R = 6, S = 2
2. (B)P = 2, Q = 9, R = 5, S = 1
3. (C)P = 4, Q = 12, R = 5, S = 4
4. (D)P = 3, Q = 7, R = 7, S = 3

Consider two files systems A and B, that use contiguous allocation and linked allocation, respectively. A file of size 100 blocks is already stored in A and also in B. Now, consider inserting a new block in the middle of the file (between 50th and 51st block), whose data is already available in the memory. Assume that there are enough free blocks at the end of the file and that the file control blocks are already in memory. Let the number of disk accesses required to insert a block in the middle of the file in A and B are nA and nB, respectively, then the value of nA + nB is_________.

Consider a demand paging system with four page frames (initially empty) and LRU page replacement policy. For the following page reference string 7, 2, 7, 3, 2, 5, 3, 4, 6, 7, 7, 1, 5, 6, 1 the page fault rate, defined as the ratio of number of page faults to the number of memory accesses (rounded off to one decimal place) is_________.

Consider a process executing on an operating system that uses demand paging. The average time for a memory access in the system is M units if the corresponding memory page is available in memory, and D units if the memory access causes a page fault. It has been experimentally measured that the average time taken for a memory access in the process is X units. Which one of the following is the correct expression for the page fault rate experienced by the process?

1. (A)(D - M) / (X - M)
2. (B)(X - M) / (D - M)
3. (C)(D - X) / (D - M)
4. (D)(X - M) / (D - X)

Consider a system with 3 processes that share 4 instances of the same resource type. Each process can request a maximum of K instances. Resource instances can be requested and released only one at a time. The largest value of K that will always avoid deadlock is ____.

In a system, there are three types of resources: E, F and G. Four processes P₀, P₁, P₂ and P₃ execute concurrently. At the outset, the processes have declared their maximum resource requirements using a matrix named Max as given below. For example, Max[P₂,F] is the maximum number of instances of F that P₂ would require. The number of instances of the resources allocated to the various processes at any given state is given by a matrix named Allocation. Consider a state of the system with the Allocation matrix as shown below, and in which 3 instances of E and 3 instances of F are the only resources available. Allocation Max E F G E F G P₀ 1 0 1 4 3 1 P₁ 1 1 2 2 1 4 P₂ 1 0 3 1 3 3 P₃ 2 0 0 5 4 1 From the perspective of deadlock avoidance, which one of the following is true?

1. (A)The system is in safe state.
2. (B)The system is not in safe state, but would be safe if one more instance of E were available
3. (C)The system is not in safe state, but would be safe if one more instance of F were available
4. (D)The system is not in safe state, but would be safe if one more instance of G were available

Consider the following solution to the producer-consumer synchronization problem. The shared buffer size is N. Three semaphores empty, full and mutex are defined with respective initial values of 0, N and 1. Semaphore empty denotes the number of available slots in the buffer, for the consumer to read from. Semaphore full denotes the number of available slots in the buffer, for the producer to write to. The placeholder variables, denoted by P, Q, R, and S, in the code below can be assigned either empty or full. The valid semaphore operations are: wait() and signal(). Which one of the following assignments to P, Q, R and S will yield the correct solution?

Producer:                     Consumer:

do{                           do{
    wait(P);                      wait(R);
    wait(mutex);                  wait(mutex);
    //Add item to buffer          //Consume item from buffer
    signal(mutex);                signal(mutex);
    signal(Q);                    signal(S);
}while(1);                    }while(1);

1. (A)P: full, Q: full, R: empty, S: empty
2. (B)P: empty, Q: empty, R: full, S: full
3. (C)P: full, Q: empty, R: empty, S: full
4. (D)P: empty, Q: full, R: full, S: empty

Consider a storage disk with 4 platters (numbered as 0, 1, 2 and 3), 200 cylinders (numbered as 0, 1, ..., 199), and 256 sectors per track (numbered as 0, 1, ..., 255). The following 6 disk requests of the form [sector number, cylinder number, platter number] are received by the disk controller at the same time: [120, 72, 2], [180, 134, 1], [60, 20, 0], [212, 86, 3], [56, 116, 2], [118, 16, 1] Currently the head is positioned at sector number 100 of cylinder 80, and is moving towards higher cylinder numbers. The average power dissipation in moving the head over 100 cylinders is 20 milliwatts and for reversing the direction of the head movement once is 15 milliwatts. Power dissipation associated with rotational latency and switching of head between different platters is negligible. The total power consumption in milliwatts to satisfy all of the above disk requests using the Shortest Seek Time First disk scheduling algorithm is _______.

Consider an arbitrary set of CPU-bound processes with unequal CPU burst lengths submitted at the same time to a computer system. Which one of the following process scheduling algorithms would minimize the average waiting time in the ready queue?

1. (A)Shortest remaining time first
2. (B)Round-robin with time quantum less than the shortest CPU burst
3. (C)Uniform random
4. (D)Highest priority first with priority proportional to CPU burst length

Consider a computer system with 40-bit virtual addressing and page size of sixteen kilobytes. If the computer system has a one-level page table per process and each page table entry requires 48 bits, then the size of the per-process page table is ________ megabytes.

Consider a disk queue with requests for I/O to blocks on cylinders 47, 38, 121, 191, 87, 11, 92, 10. The C-LOOK scheduling algorithm is used. The head is initially at cylinder number 63, moving towards larger cylinder numbers on its servicing pass. The cylinders are numbered from 0 to 199. The total head movement (in number of cylinders) incurred while servicing these requests is ________.

Consider a computer system with ten physical page frames. The system is provided with an access sequence (a₁, a₂, ..., a₂₀, a₁, a₂, ..., a₂₀), where each aᵢ is a distinct virtual page number. The difference in the number of page faults between the last-in-first-out page replacement policy and the optimal page replacement policy is ________.

Consider the following proposed solution for the critical section problem. There are n processes: P₀ ... Pₙ₋₁. In the code, function pmax returns an integer not smaller than any of its arguments. For all i, t[i] is initialized to zero. Which one of the following is TRUE about the above solution?

Code for Pi:
do {
    c[i]=1; t[i] = pmax(t[0],...,t[n-1])+1; c[i]=0;
    for every j ≠ i in {0,...,n-1} {
        while (c[j]);
        while (t[j] != 0 && t[j]<=t[i]);
    }
    Critical Section;
    t[i]=0;
    Remainder Section;
} while (true);

1. (A)At most one process can be in the critical section at any time
2. (B)The bounded wait condition is satisfied
3. (C)The progress condition is satisfied
4. (D)It cannot cause a deadlock

In which one of the following page replacement algorithms it is possible for the page fault rate to increase even when the number of allocated frames increases?

1. (A)LRU (Least Recently Used)
2. (B)OPT (Optimal Page Replacement)
3. (C)MRU (Most Recently Used)
4. (D)FIFO (First In First Out)

Consider the following processes, with the arrival time and the length of the CPU burst given in milliseconds. The scheduling algorithm used is preemptive shortest remaining-time first. Process Arrival Time Burst Time P1 0 10 P2 3 6 P3 7 1 P4 8 3 The average turn around time of these processes is ______ milliseconds.

Consider the following two-process synchronization solution. The shared variable turn is initialized to zero. Which one of the following is TRUE?

Process 0                          Process 1
---------                          ----------
Entry: loop while (turn == 1);     Entry: loop while (turn == 0);
  (critical section)                 (critical section)
Exit:  turn = 1;                   Exit:  turn = 0;

1. (A)This is a correct two-process synchronization solution.
2. (B)This solution violates mutual exclusion requirement.
3. (C)This solution violates progress requirement.
4. (D)This solution violates bounded wait requirement.

Consider a non-negative counting semaphore S. The operation P(S) decrements S, and V (S) increments S. During an execution, 20 P(S) operations and 12 V (S) operations are issued in some order. The largest initial value of S for which at least one P(S) operation will remain blocked is ______.

A file system uses an in-memory cache to cache disk blocks. The miss rate of the cache is shown in the figure. The latency to read a block from the cache is 1 ms and to read a block from the disk is 10 ms. Assume that the cost of checking whether a block exists in the cache is negligible. Available cache sizes are in multiples of 10 MB. Miss rate from the figure: Cache size (MB): 10 20 30 40 50 60 70 80 Miss rate (%): 80 60 40 35 30 25 20 15 The smallest cache size required to ensure an average read latency of less than 6 ms is ______ MB.

Suppose a disk has 201 cylinders, numbered from 0 to 200. At some time the disk arm is at cylinder 100, and there is a queue of disk access requests for cylinders 30, 85, 90, 100, 105, 110, 135 and 145. If Shortest-Seek Time First (SSTF) is being used for scheduling the disk access, the request for cylinder 90 is serviced after servicing ____________ number of requests.

A system contains three programs and each requires three tape units for its operation. The minimum number of tape units which the system must have such that deadlocks never arise is _________.

An operating system uses shortest remaining time first scheduling algorithm for pre-emptive scheduling of processes. Consider the following set of processes with their arrival times and CPU burst times (in milliseconds): Process Arrival Time Burst Time P1 0 12 P2 2 4 P3 3 6 P4 8 5 The average waiting time (in milliseconds) of the processes is _________.

Consider a paging hardware with a TLB. Assume that the entire page table and all the pages are in the physical memory. It takes 10 milliseconds to search the TLB and 80 milliseconds to access the physical memory. If the TLB hit ratio is 0.6, the effective memory access time (in milliseconds) is _________.