Operating System GATE 2018 Solved Questions

Ques 1: 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.

GATE 2018 Q no 10

Which one of the following is the correct expression for the page fault rate experienced by the process?

(A) (D – M) / (X – M)

(B) (X – M) / (D – M)

(C) (D – X) / (D – M)

(D) (X – M) / (D – X)

Ans: (B) (X – M) / (D – M)

Solution: Let P be the page fault rate.

Average memory access time

 =(1− page fault rate)× memory access time when no page fault  +  Page fault rate  × Memory access time when page fault.

X=(1−P)M+P D

X=M -PM +PD

X=M+P(D−M)

P=(X−M)/(D−M)

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

GATE 2018 Q no 24

Ans: 2

Solution: Number of processes =3

Number of Resources =4

Let’s distribute each process one less than maximum demand (K−1)resources. i.e. 3(K−1)

Provide an additional resource to any of three processes for deadlock avoidance.

Total resources =3(K−1)+1=3K−2

Now, this 3K−2 should be less than or equal to the number of resources we have right now.

3K−2≤4

3K≤6

K≤2

So, largest value of K=2

Ques 3 :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.

GATE 2018 Q no 39

From the perspective of deadlock avoidance, which one of the following is true?

(A) The system is in safe state.

(B) The system is not in safe state, but would be safe if one more instance of E were available

(C) The system is not in safe state, but would be safe if one more instance of F were available

(D) The system is not in safe state, but would be safe if one more instance of G were available

Ans: (A) The system is in safe state.

Solution: Available Resource  (3,3,0)

With (3,3,0) we can satisfy the request of either P0 or P2.

Let’s assume request of P0  satisfied.

After execution, it will release resources.

Available Resource =(3,3,0)+(1,0,1)=(4,3,1)

Give (0,3,0) out of (4,3,1)unit of resources to P2 and P2 will complete its execution.

After execution, it will release resources.

Available Resource =(4,3,1)+(1,0,3)=(5,3,4)

Allocate (1,0,2) out of (5,3,4) unit of resources to P1 and P1 will completes its execution.

After execution, it will release resources.

Available Resource =(5,3,4)+(1,1,2)=(6,4,6)

And finally, allocate resources to P3

So, we have one of the possible safe sequence: P0⟶P2⟶P1⟶P3

Ques 4 :Consider the following solution to the producer-consumer synchronization problem. The shared buffer size is 𝑁. Three semaphores empty, full and mutex are defined with respective initial values of 0, 𝑁 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().

GATE 2018 Q no 40

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

Which one of the following assignments to P, Q, R and S will yield the correct solution?

(A) P: full, Q: full, R: empty, S: empty

(B) P: empty, Q: empty, R: full, S: full

(C) P: full, Q: empty, R: empty, S: full

(D) P: empty, Q: full, R: full, S: empty

Ans: (C) P: full, Q: empty, R: empty, S: full

Solution: Empty denotes number of Filled slots.

Full denotes number of empty slots.

So, Producer must deal with Empty and Consumer must deal with Full

Producer must checks Full i,e. decrease Full by 1 before entering and

Consumer must check Empty i.e. decrease Full by 1 before entering

So, (C) must be answer.

Click here to read more about Producer Consumer Problem in Operating System.

Ques 5 :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:

GATE 2018 Q no 53

[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 _______________.

Ans: 85

Solution: Shortest Seek Time First (SSTF), selects the request with minimum to seek time first from the current head position.

In the given question disk requests are given in the form of ⟨sectorNo, cylinderNo, platterNo⟩⟨sectorNo, cylinderNo, platterNo⟩. 

Cylinder Queue :72,134,20,86,116,16

Head starts at :80

Total head movements in SSTF =(86−80) + (86−72) + (116-72) + (134−116) + (134-20) + (20−16)=200

Power dissipated in moving 100 cylinder =20mW

Power dissipated by 200 movements (say P1)=0.2∗200=40mW

Power dissipated in reversing head direction once =15mW

Number of times head changes its direction =3

Power dissipated in reversing head direction (say P2)=3∗15=45mW

Total Power Consumption is P1+P2=85mW