GATE CSE Operating Systems Formula Sheet: Paging, EAT, Deadlock

Operating systems numerical questions in GATE CSE come from a short list of formulas: scheduling times, effective access time, paging arithmetic, deadlock counts, inode sizes and fork counts. This sheet goes deeper than the general GATE CSE formula sheet. Each formula comes with a one-line worked example and the trap that costs marks.

Key takeaways

• Scheduling questions use three subtractions: turnaround is completion minus arrival, waiting is turnaround minus burst, and response is first dispatch minus arrival.
• The TLB formula charges a miss one memory access per page-table level plus the data access, so a two-level table costs $3t_m$ on a miss.
• Demand-paging effective access time is dominated by the fault term, so convert milliseconds to nanoseconds before you multiply.
• Deadlock is impossible only with $n(k - 1) + 1$ units; $n(k - 1)$ units can still deadlock.
• An inode's double indirect pointer reaches $p^2$ blocks, never $2p$.
• Most operating systems marks lost in revision come from units and conventions, not from the formulas themselves.

The terms this sheet uses

Every formula below is built from a few quantities. Learn them once and the formulas read like sentences.

• Arrival time ($A$) is when a process enters the ready queue. Burst time is the CPU time it needs. Completion time ($C$) is when it finishes.
• A page is a fixed-size block of virtual memory, and a frame is a block of physical memory of the same size. The offset is the part of an address that selects a byte inside a page, so offset bits $o = \log_2(\text{page size})$.
• A page-table entry (PTE) holds a frame number plus flag bits. The TLB is a small cache of recent translations, and the hit ratio $h$ is the fraction of lookups it answers.
• The page-fault rate $p$ is the fraction of memory references whose page is not in memory.
• An inode stores a file's block pointers: $d$ direct pointers and one single, one double and one triple indirect pointer.

Logs are base 2 throughout, and KB means $2^{10}$ bytes unless a question says otherwise.

Scheduling formulas, from timeline to averages

Every scheduling question ends in the same three subtractions. Draw the Gantt chart first, read off completion times, then apply the table.

Two conventions decide many timelines. In round robin, a new arrival joins the queue before the preempted process when both happen at the same instant. In SRTF, a new arrival preempts only if its burst is strictly less than the running process's remaining time.

Trap: A quantum larger than every remaining burst turns round robin into FCFS. Count context switches only when the running process changes. The CPU scheduling question guide works through these timelines.

Paging arithmetic: entries, table size and levels

Single-level paging needs one idea: the page-number bits decide how many entries the table has. Multi-level paging adds a second idea: each inner table must fit in one page.

Remember: When you count the memory a sparse process uses for its page tables, the outer table always costs one full page, and every partly used inner table also costs a full page.

Effective access time with a TLB

The average time is the hit case weighted by its probability, plus the miss case weighted by its own. On a hit you pay one TLB lookup and one memory access. On a miss you pay the lookup, one access per page-table level, and then the data access:

Here $h$ is the TLB hit ratio, $t_{TLB}$ the lookup time, $t_m$ one memory access and $L$ the number of page-table levels.

Worked example. Take $t_{TLB} = 10$ ns, $t_m = 100$ ns, $h = 0.9$ and a single-level table:

With a two-level table the miss term grows to $10 + 300 = 310$ ns, so the EAT becomes $99 + 31 = 130$ ns.

If the question says the TLB is searched in parallel with memory, the hit term is just $t_m$ and the miss term stays $t_{TLB} + (L + 1)\,t_m$. The page-table walk always goes to memory.

Effective access time with page faults

Demand paging uses the same weighting, with the page-fault rate $p$ in place of the miss ratio:

Here $d$ is the fraction of victim pages that are dirty and must be written back.

Worked example. With $t_m = 100$ ns, $t_{\text{fault}} = 8$ ms $= 8 \times 10^{6}$ ns and $p = 10^{-6}$, the fault term adds $10^{-6} \times 8 \times 10^{6} = 8$ ns. The EAT is about $100 + 8 = 108$ ns.

Trap: Multiplying $p$ by 8 instead of $8 \times 10^{6}$ gives an answer a million times too small. Write the unit next to every number before you substitute.

The page-replacement traces that feed these fault rates are covered in page replacement questions for GATE CSE.

The book's last-minute revision sheet gives the full operating systems formula table, with symbols, when each formula applies and its typical trap, alongside the same tables for the other nine subjects. It is part of the GATE CSE 2027 book.

Deadlock: the minimum number of resources

The worst case for one resource type is that every process holds one unit fewer than it needs. If one more unit exists, some process can finish and release everything. So deadlock is impossible exactly when:

File-system formulas: inode size and disk accesses

A block of $B$ bytes holds $p = B / \text{pointer size}$ pointers. The single indirect pointer reaches $p$ blocks, the double $p^2$ and the triple $p^3$, so:

Worked example. With $B = 1$ KB, 4-byte pointers and $d = 10$, $p = 256$. The sum is $10 + 256 + 65536 + 16777216 = 16843018$ blocks of 1 KB, a little over 16 GB.

In one line: Pointers per block is $p$, each extra level of indirection multiplies the reach by $p$, and each level costs one more disk access.

Process and semaphore counts

Two small formulas cover most counting questions on fork() and semaphores.

The operating systems important topics guide shows which of these families past papers have asked most, and the common mistakes guide lists the convention slips subject by subject.

More formula sheets: all of GATE CSE · Computer Networks · COA · Engineering Mathematics

Quick revision

1. $\text{TAT} = C - A$, $\text{WT} = \text{TAT} - \text{burst}$, $\text{RT} = \text{first dispatch} - A$.
2. TLB: $\text{EAT} = h(t_{TLB} + t_m) + (1 - h)(t_{TLB} + (L + 1)t_m)$; one level gives $t_{TLB} + 2t_m$ on a miss.
3. Demand paging: $\text{EAT} = (1 - p)t_m + p\,t_{\text{fault}}$, with milliseconds converted to nanoseconds.
4. Levels $= \lceil (v - o) / \log_2(\text{entries per page}) \rceil$; count the outer table as a full page.
5. Deadlock-free needs $n(k - 1) + 1$ units; the largest $n$ is $\lfloor (R - 1)/(k - 1) \rfloor$.
6. Inode: $(d + p + p^2 + p^3) \times B$, with 1 to 4 disk accesses by pointer level.
7. $n$ forks give $2^n$ processes and $2^n - 1$ children.