Q1➡| GATE 2021 Set-1 Consider a linear list based directory implementation in a file system. Each directory is a list of nodes, where each node contains the file name along with the file metadata, such as the list of pointers to the data blocks.Consider a given directory foo. Which of the following operations will necessarily require a full scan of foo for successful completion?
Q2➡| GATE 2021 Set-1 Which of the following standard C library functions will always invoke a system call when executed from a single-threaded process in a UNIX/linux operating system?
Q4➡| GATE 2021 Set-1 Three processes arrive at time zero with CPU bursts of 16, 20 and 10 milliseconds. If the scheduler has prior knowledge about the length of the CPU bursts, the minimum achievable average waiting time for these three processes in a non-preemptive scheduler (rounded to nearest integer) is _______ milliseconds.
Q5➡| GATE 2021 Set-1 There are 6 jobs with distinct difficulty levels, and 3 computers with distinct processing speeds. Each job is assigned to a computer such that: • The fastest computer gets the toughest job and the slowest computer gets the easiest job. • Every computer gets at least one job. The number of ways in which this can be done is ____
Q6➡|GATE 2021 Set-1 Consider the following pseudocode, where S is a semaphore initialized to 5 in line#2 and counter is a shared variable initialized to 0 in line#1. Assume that the increment operation in line#7 is not atomic. If five threads execute the function parop concurrently, which of the following program behaviour(s) is/are possible?
i ➥ The value of counter is 0 after all the threads successfully complete the execution of parop.
ii ➥ The value of counter is 5 after all the threads successfully complete the execution of parop.
iii ➥ There is a deadlock involving all the threads.
iv ➥ The value of counter is 1 after all the threads successfully complete the execution of parop.
Q8➡| GATE 2021 Set-2 Consider a computer system with multiple shared resource types, with one instance per resource type. Each instance can be owned by only one process at a time. Owning and freeing of resources are done by holding a global lock (L). The following scheme is used to own a resource instance:
i ➥ The scheme may lead to starvation.
ii ➥ The scheme ensures that deadlocks will not occur.
iii ➥ The scheme may lead to live-lock.
iv ➥ The scheme violates the mutual exclusive property.
Q10➡| GATE 2021 Set-2 Consider a three-level page table to translate a 39-bit virtual address to a physical address as shown below: The page size is 4KB (1KB = 210bytes) and page table entry size at every level is 8 bytes. A process P is currently using 2GB (1GB = 230bytes) virtual memory which is mapped to 2GB of physical memory. The minimum amount of memory required for the page table of P across all levels is_______ KB.
Q11➡| GATE 2020 Consider the following statements about process state transitions for a system using preemptive scheduling. I. A running process can move to ready state. II. A ready process can move to running state. III. A blocked process can move to running state. IV. A blocked process can move to ready state. Which of the above statements are TRUE?
Q12➡|GATE 2020 Consider allocation of memory to a new process. Assume that none of the existing holes in the memory will exactly fit the process’s memory requirement. Hence, a new hole of smaller size will be created if allocation is made in any of the existing holes. Which one of the following statements is TRUE?
i ➥ The hole created by next fit is never larger than the hole created by best fit.
ii ➥ The hole created by worst fit is always larger than the hole created by first fit.
iii ➥ The hole created by first fit is always larger than the hole created by next fit.
iv ➥ The hole created by best fit is never larger than the hole created by first fit.
Q13➡| GATE 2020 Consider the following five disk access requests of the form (request id, cylinder number) that are present in the disk scheduler queue at a given time. (P, 155), (Q, 85), (R, 110), (S, 30), (T, 115) Assume the head is positioned at cylinder 100. The scheduler follows Shortest Seek Time First scheduling to service the requests. Which one of the following statements is FALSE?
i ➥ Q is serviced after S, but before T.
ii ➥ R is serviced before P.
iii ➥ T is serviced before P.
iv ➥ The head reverses its direction of movement between servicing of Q and P.
Q14➡| GATE 2020 Each of a set of n processes executes the following code using two semaphores a and b initialized to 1 and 0, respectively. Assume that count is a shared variable initialized to 0 and not used in CODE SECTION P. What does the code achieve?
i ➥ It ensures that no process executes CODE SECTION Q before every process has finished CODE SECTION P.
ii ➥ It ensures that at most two processes are in CODE SECTION Q at any time.
iii ➥ It ensures that at most n-1 processes are in CODE SECTION P at any time.
iv ➥ It ensures that all processes execute CODE SECTION P mutually exclusively.
Q15➡|GATE 2020 Consider the following set of processes, assumed to have arrived at time 0. Consider the CPU scheduling algorithms Shortest Job First (SJF) and Round Robin (RR). For RR, assume that the processes are scheduled in the order P1,P2,P3,P4. If the time quantum for RR is 4 ms, then the absolute value of the difference between the average turnaround times (in ms) of SJF and RR (round off to 2 decimal places) is ________.
Q16➡|GATE 2020 Consider a paging system that uses a 1-level page table residing in main memory and a TLB for address translation. Each main memory access takes 100 ns and TLB lookup takes 20 ns. Each page transfer to/from the disk takes 5000 ns. Assume that the TLB hit ratio is 95%, page fault rate is 10%. Assume that for 20% of the total page faults, a dirty page has to be written back to disk before the required page is read in from disk. TLB update time is negligible. The average memory access time in ns (round off to 1 decimal places) is _______.
Q18➡| GATE 2019 Assume that in a certain computer, the virtual addresses are 64 bits long and the physical addresses are 48 bits long. The memory is word addressable. The page size is 8 kB and the word size is 4 bytes. The Translation Look-aside Buffer (TLB) in the address translation path has 128 valid entries. At most how many distinct virtual addresses can be translated without any TLB miss?
Q19➡| GATE 2019 The index node (inode) of a Unix-like file system has 12 direct, one single-indirect and one double-indirect pointers. The disk block size is 4 kB, and the disk block address is 32-bits long. The maximum possible file size is (rounded off to 1 decimal place) ________ GB.
Q20➡| GATE 2019 Consider the following four processes with arrival times (in milliseconds) and their length of CPU bursts (in milliseconds) as shown below: These processes are run on a single processor using preemptive Shortest Remaining Time First scheduling algorithm. If the average waiting time of the processes is 1 millisecond, then the value of Z is _______.
Q21➡| GATE 2019 Consider the following snapshot of a system running n concurrent processes. Process i is holding Xi instances of a resource R, 1 ≤ i ≤ n. Assume that all instances of R are currently in use. Further, for all i, process i can place a request for at most Yi additional instances of R while holding the Xi instances it already has. Of the n processes, there are exactly two processes p and q such that Yp = Yq = 0. Which one of the following conditions guarantees that no other process apart from p and q can complete execution?
i ➥ Xp + Xq < Min {Yk | 1 ≤ k ≤ n, k ≠ p, k ≠ q}
ii ➥ Min (Xp, Xq) ≤ Max {Yk | 1 ≤ k ≤ n, k ≠ p, k ≠ q}
iii ➥ Min (Xp, Xq) ≥ Min {Yk | 1 ≤ k ≤ n, k ≠ p, k ≠ q}
Q22➡| GATE 2018 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 _.
Q23➡| GATE 2018 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?
Q24➡| GATE 2018 In a system, there are three types of resources: E, F and G. Four processes P0, P1, P2 and P3 execute concurrently. At the outset, the processes have declared their maximum resource requirements using a matrix named Max as given below. For example, Max[P2, F] is the maximum number of instances of F that P2 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. From the perspective of deadlock avoidance, which one of the following is true?
i ➥ The system is in safe state.
ii ➥ The system is not in safe state, but would be safe if one more instance of E were available.
iii ➥The system is not in safe state, but would be safe if one more instance of F were available.
iv ➥ The system is not in safe state, but would be safe if one more instance of G were available.
Q25➡|GATE 2018 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:
Currently 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 __ .
Q26➡| GATE 2017 Set-1 Consider the following CPU processes with arrival times (in milliseconds) and length of CPU bursts (in milliseconds) as given below: If the pre-emptive shortest remaining time first scheduling algorithm is used to schedule the processes, then the average waiting time across all processes is _________ milliseconds.
Q27➡| GATE 2017 Set-1 A multithreaded program P executes with x number of threads and used y number of locks for ensuring mutual exclusion while operating on shared memory locations. All locks in the program are non-reentrant, i.e., if a thread holds a lock l, then it cannot re-acquire lock l without releasing it. If a thread is unable to acquire a lock, it blocks until the lock becomes available. The minimum value of x and the minimum value of y together for which execution of P can result in a deadlock are:
Q28➡| GATE 2017 Set-1 Recall that Belady’s anomaly is that the page-fault rate may increase as the number of allocated frames increases. Now, consider the following statements: S1: Random page replacement algorithm (where a page chosen at random is replaced) suffers from Belady’s anomaly S2: LRU page replacement algorithm suffers from Belady’s anomaly
Q29➡| GATE 2017 Set-2 In a file allocation system, which of the following allocation scheme(s) can be used if no external fragmentation is allowed? I. Contiguous II. Linked III. Indexed
Q30➡| GATE 2017 Set-2 Which of the following is/are shared by all the threads in a process? I. Program counter II. Stack III. Address space IV. Registers
Q31➡| GATE 2017 Set-2 A system shares 9 tape drives. The current allocation and maximum requirement of tape drives for three processes are shown below: Which of the following best describe current state of the system?
Q32➡|GATE 2017 Set-2 Consider the set of processes with arrival time (in milliseconds), CPU burst time (in milliseconds), and priority (0 is the highest priority) shown below. None of the processes have I/O burst time. The average waiting time (in milliseconds) of all the processes using preemptive priority scheduling algorithm is ________.
Q33➡| GATE 2016 Set-1 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?
i ➥ Highest priority first with priority proportional to CPU burst length
ii ➥ Uniform random
iii ➥Round-robin with time quantum less than the shortest CPU burst
Q34➡|GATE 2016 Set-1 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.
Q35➡|GATE 2016 Set-1 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 __________.
Q36➡|GATE 2016 Set-1 Consider a computer system with ten physical page frames. The system is provided with an access sequence (a1,a2,…,a20,a1,a2,…,a20), where each ai 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 ____________.
Q37➡| GATE 2016 Set-1 Consider the following proposed solution for the critical section problem. There are n processes: P0…P(n-1). In the code, function pmax returns an integer not smaller than any of its arguments. For all i, t[i] is initialized to zero. Code for Pi: Which one of the following is TRUE about the above solution?
i ➥ At most one process can be in the critical section at any time
Q38➡| GATE 2016 Set-2 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?
Q39➡|GATE 2016 Set-2 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 The average turn around time of these processes is _________ milliseconds.
Q40➡|GATE 2016 Set-2 Consider the following two-process synchronization solution. The shared variable turn is initialized to zero. Which one of the following is TRUE?
i ➥ This is a correct two-process synchronization solution.
ii ➥ This solution violates mutual exclusion requirement.
iii ➥ This solution violates progress requirement.
iv ➥ This solution violates bounded wait requirement.
Q41➡|GATE 2016 Set-2 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 _________.
Q42➡| GATE 2016 Set-2 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. The smallest cache size required to ensure an average read latency of less than 6 ms is ________ MB.
Q43➡| GATE 2015 Set-1 Consider a system with byte-addressable memory, 32-bit logical addresses, 4 kilobyte page size and page table entries of 4 bytes each. The size of the page table in the system in megabytes is___________.
Q44➡| GATE 2015 Set-1 The following two functions P1 and P2 that share a variable B with an initial value of 2 execute concurrently. The number of distinct values that B can possibly take after the execution is
Q45➡| GATE 2015 Set-1 Consider a uniprocessor system executing three tasks T1, T2 and T3, each of which is composed of an infinite sequence of jobs (or instances) which arrive periodically at intervals of 3, 7 and 20 milliseconds, respectively. The priority of each task is the inverse of its period and the available tasks are scheduled in order of priority, with the highest priority task scheduled first. Each instance of T1, T2 and T3 requires an execution time of 1, 2 and 4 milliseconds, respectively. Given that all tasks initially arrive at the beginning of the 1st millisecond and task preemptions are allowed, the first instance of T3 completes its execution at the end of ___________ milliseconds.
Q46➡| GATE 2015 Set-1 Suppose the following disk request sequence (track numbers) for a disk with 100 tracks is given: 45, 20, 90, 10, 50, 60, 80, 25, 70. Assume that the initial position of the R/W head is on track 50. The additional distance that will be traversed by the R/W head when the Shortest Seek Time First (SSTF) algorithm is used compared to the SCAN (Elevator) algorithm (assuming that SCAN algorithm moves towards 100 when it starts execution) is _________ tracks.
Q47➡|GATE 2015 Set-1 Consider a main memory with five page frames and the following sequence of page references: 3, 8, 2, 3, 9, 1, 6, 3, 8, 9, 3, 6, 2, 1, 3. Which one of the following is true with respect to page replacement policies First-In-First Out (FIFO) and Least Recently Used (LRU)?
Q49➡| GATE 2015 Set-2 A system has 6 identical resources and N processes competing for them. Each process can request atmost 2 resources. Which one of the following values of N could lead to a deadlock?
Q50➡| GATE 2015 Set-2 Consider six memory partitions of sizes 200 KB, 400 KB, 600 KB, 500 KB, 300 KB and 250 KB, where KB refers to kilobyte. These partitions need to be allotted to four processes of sizes 357 KB, 210KB, 468 KB and 491 KB in that order. If the best fit algorithm is used, which partitions are NOT allotted to any process?
