GATE CS & IT Engineering Operating System Syllabus

Operating System syllabus — full chapter and topic list

Expand any chapter to see its topics and sub-topics. This is the whole examinable outline for Operating System in GATE CS & IT Engineering, not a summary of it.

1. 1

   System calls

   overview

   Examined as a single unit within Operating System — no further topic split in the official outline.

2. 2

   Processes and Threads

   overview

   Examined as a single unit within Operating System — no further topic split in the official outline.

3. 3

   Inter-process Communication

   overview

   Examined as a single unit within Operating System — no further topic split in the official outline.

4. 4

   Concurrency and Synchronization

   overview

   Examined as a single unit within Operating System — no further topic split in the official outline.

5. 5

   Deadlock

   overview

   Examined as a single unit within Operating System — no further topic split in the official outline.

6. 6

   CPU and I/O Scheduling

   2 topics

   • CPU Scheduling
   • I/O Scheduling
7. 7

   Memory Management and Virtual Memory

   2 topics

   • Memory Management
   • Virtual Memory
8. 8

   File Systems

   1 topic

   • File Systems

Operating System flashcards for GATE CS & IT Engineering

20 of 51 cards from the Operating System deck — real questions with worked answers.

1. What is the difference between preemptive and non-preemptive CPU scheduling?

   In non-preemptive scheduling, once the CPU is allocated to a process it keeps the CPU until it terminates or switches to the waiting state. In preemptive scheduling, the CPU can be forcibly taken from a running process (e.g., when a higher-priority process arrives or a time quantum expires).

2. Define turnaround time, waiting time, and response time in CPU scheduling.

   Turnaround Time $= $ Completion Time $-$ Arrival Time. Waiting Time $= $ Turnaround Time $-$ Burst Time. Response Time $= $ Time of first CPU allocation $-$ Arrival Time.

3. What scheduling algorithm gives the provably minimum average waiting time, and is it preemptive or non-preemptive?

   Shortest Job First (SJF) gives the minimum average waiting time among all non-preemptive algorithms. Its preemptive version is Shortest Remaining Time First (SRTF).

4. Why can the FCFS scheduling algorithm cause the 'convoy effect'?

   In FCFS, if a long CPU-bound process arrives first, all shorter processes behind it must wait for it to finish, leading to poor average waiting time. This piling up of short processes behind one long process is the convoy effect.

5. In Round Robin scheduling, how does the time quantum value affect performance?

   If the time quantum is very large, RR degenerates into FCFS. If it is very small, context-switch overhead dominates and throughput drops. The quantum should be large relative to the context-switch time but small enough to keep response time low.

6. What is starvation in CPU scheduling and what technique solves it?

   Starvation is the indefinite postponement of a low-priority process because higher-priority processes keep arriving. It is solved by aging, which gradually increases the priority of a process the longer it waits.

7. For SJF, given processes with burst times, what is the formula used to predict the next CPU burst via exponential averaging?

   $$\tau_{n+1} = \alpha\, t_{n} + (1-\alpha)\,\tau_{n}$$ where $t_n$ is the actual length of the $n$th burst, $\tau_n$ is the previous prediction, and $0 \leq \alpha \leq 1$.

8. What is the difference between a priority scheduling algorithm and SJF?

   SJF is a special case of priority scheduling where the priority is the inverse of the predicted next CPU burst (shorter burst = higher priority). General priority scheduling can use any externally or internally defined priority criterion.

9. Compute the average waiting time for FCFS with processes P1, P2, P3 having burst times 24, 3, 3 (arriving at time 0 in that order).

   Waiting times: P1 $=0$, P2 $=24$, P3 $=27$. $$\text{Avg WT} = \frac{0 + 24 + 27}{3} = 17 \text{ ms}$$

10. In Multilevel Feedback Queue scheduling, how do processes move between queues?

    A process that uses too much CPU time is demoted to a lower-priority queue; a process that waits too long in a lower queue can be promoted (aged) to a higher queue. This favors short and I/O-bound processes while preventing starvation.

11. What is the formula for CPU utilization in terms of context-switch overhead with time quantum $q$ and context-switch time $s$?

    $$\text{CPU Utilization} = \frac{q}{q + s}$$ where $q$ is the time quantum and $s$ is the context-switch time.

12. Differentiate between the long-term, short-term, and medium-term schedulers.

    Long-term (job) scheduler selects which jobs enter the ready queue, controlling the degree of multiprogramming. Short-term (CPU) scheduler selects which ready process runs next and executes frequently. Medium-term scheduler handles swapping processes in and out of memory.

13. What is the goal of disk (I/O) scheduling, and what three components make up a disk access time?

    Disk scheduling aims to minimize total head movement / access time. Disk access time $= $ Seek Time $+$ Rotational Latency $+$ Transfer Time.

14. How does the SSTF (Shortest Seek Time First) disk scheduling algorithm work, and what is its main drawback?

    SSTF selects the pending request closest to the current head position (minimum seek). Its drawback is starvation of requests far from the head, and it is not optimal overall.

15. Describe the SCAN (elevator) disk scheduling algorithm.

    The disk head moves in one direction servicing all requests until it reaches the end of the disk, then reverses direction and services requests on the way back, like an elevator.

16. How does C-SCAN differ from SCAN, and why is it preferred?

    In C-SCAN, the head services requests in one direction to the end, then jumps back to the beginning without servicing on the return, treating the disk as circular. This gives a more uniform wait time than SCAN, which favors recently passed cylinders.

17. What is the difference between LOOK and SCAN disk scheduling?

    LOOK is like SCAN but the head only goes as far as the last request in each direction instead of all the way to the end of the disk, then reverses. C-LOOK is the circular variant of LOOK.

18. Calculate total head movement for FCFS servicing the request queue 98, 183, 37 starting at head position 53.

    Movement $= |98-53| + |183-98| + |37-183| = 45 + 85 + 146 = 276$ cylinders.

19. What is rotational latency, and what is its average value for a disk rotating at $r$ RPM?

    Rotational latency is the time for the desired sector to rotate under the head. On average it is half a rotation: $$\text{Avg Latency} = \frac{1}{2} \cdot \frac{60}{r} \text{ seconds} = \frac{30}{r}\text{ s}$$

20. Give the formula for data transfer time of one sector on a disk rotating at $r$ RPM with $N$ sectors per track.

    $$T_{transfer} = \frac{1}{r/60} \cdot \frac{1}{N} = \frac{60}{r \cdot N} \text{ seconds}$$ i.e., the time for one full rotation divided by the number of sectors per track.

See more Operating System flashcards →

Planning Operating System for GATE CS & IT Engineering

Operating System (GATE CS & IT Engineering) FAQ