Operating Systems

Paging in virtual memory

Paging is a memory-management scheme that divides the virtual (logical) address space into fixed-size blocks called pages and the physical memory into frames of the same size. A virtual address consists of a page number, which indexes the page table, and an offset, which passes unchanged into the physical address. The page table entry gives the frame number, so the physical address equals \text{frame number} \times \text{page size} + \text{offset}. Because the page size is a power of two, the offset is the low-order \log_2(\text{page size}) bits of the address.

Paging removes external fragmentation, because any free frame can hold any page, so the only waste is internal. Internal fragmentation occurs inside the last page of each process, and on average about half a page is wasted per process, so a smaller page size reduces internal fragmentation. The price of a small page size is a larger page table. Every process needs its own page table, and that table occupies memory, which is a basic memory overhead of paging.

The number of page table entries equals the number of pages in the logical address space, which is 2^{(\text{address bits} - \text{offset bits})}. For example, a 32-bit address with a 2 KB page has an 11-bit offset and a 21-bit page number, so the table has at most 2^{21} entries. The physical address width determines the size of each frame number, not the number of entries. The memory management unit (MMU) is hardware that performs this translation on every memory reference using the page table of the running process. The MMU raises a page fault trap when an entry is invalid and a protection trap when an access violates the permission bits, such as a write to a read-only page. The operating system kernel, not the MMU, allocates the page table when a process is created.

To keep page tables small, a multi-level scheme splits the page number into several levels. A table page holds p/e entries, where p is the page size and e is the entry size, so each level indexes \log_2(p/e) bits. The number of levels is L = \lceil \text{page number bits} / \text{bits per level} \rceil. For example, with 4 KB pages and 8-byte entries each table holds 512 entries and resolves 9 bits, so a 36-bit page number needs 4 levels. Multi-level paging exists to shrink the tables, and it is not a requirement for supporting pages of different sizes. In a two-level scheme, the outer table is allocated at process creation, while an inner table is allocated on demand only when it contains at least one valid entry. The outer index then has \text{address bits} - \text{offset bits} - \text{inner index bits} bits. The memory needed by a multi-level table is the sum of the table pages at every level, and for a three-level table each level's count is found by dividing the number of pages by the entries per table page, and adding the required higher-level tables.

A translation lookaside buffer (TLB) is a small associative cache of recent page-to-frame translations. The page number of the incoming address is compared in parallel with all valid entries. A TLB hit means the page is resident in main memory, so if the subsequent cache lookup misses, the word is fetched from main memory. A TLB entry stores a process identifier, a page number, a frame number and control bits, so the TLB size in bytes is the number of entries times the bits per entry, divided by 8. The TLB reach is the number of entries times the page size. An inverted page table has one entry per frame and is searched with hashing, so the number of entries examined depends on the address and on hash collisions, and the access time is not the same for all addresses.

To translate an address, compute the page number as the quotient of the address and the page size, and the offset as the remainder. The physical address is the base address of the frame that holds the page plus the offset. For example, with a 1 KB page, virtual address 3000 has page 2 and offset 952, so if page 2 is in frame 5 the physical address is 5 \times 1024 + 952.

When a referenced page is not resident, a page fault occurs, and the operating system must choose a victim frame. The optimal policy evicts the page whose next reference is farthest in the future, which yields the fewest faults but requires knowledge of future references. LRU evicts the page whose most recent use is oldest, and the page fault rate is the number of faults divided by the number of memory accesses. Comparing a fault sequence with the reference string identifies the policy in use: LRU, LFU (least frequently used) and MFU (most frequently used) each choose a victim by a different criterion, so a single replacement can rule out some policies. In a modified optimal policy that predicts only a limited window of future references, a page that does not appear within the window is treated as having an infinitely distant next use, and it becomes the victim. Finally, array access order matters. Under LRU, a cyclic sweep over more pages than there are frames faults on every new page in each sweep, because each page is evicted before it is referenced again. Row-major storage makes a column-wise traversal touch a different page on almost every reference.

CPU scheduling and average waiting time

CPU scheduling decides which ready process runs next. For each process, the arrival time is when it enters the ready queue, the burst time is the CPU time it needs, and the completion time is when it finishes. The turnaround time is the completion time minus the arrival time, and it includes the waiting time, so turnaround equals waiting time plus burst time. The waiting time is the total time spent in the ready queue. In non-preemptive scheduling, it equals the start time minus the arrival time. The average waiting time is the mean of these values over all processes.

The usual goals are to maximize CPU utilization and throughput, and to minimize turnaround, waiting and response times. Throughput is to be maximized, not minimized, so a statement that only minimizes throughput is wrong. The standard method is to draw a Gantt chart on a timeline, mark each start and completion, and then compute the three quantities for each process.

Shortest job first (SJF) in non-preemptive form picks the ready process with the shortest burst whenever the CPU is free. When all processes arrive together and their burst lengths are known in advance, SJF gives the minimum achievable average waiting time. For example, with bursts 3, 5 and 2 at time 0, the order is 2, 3, 5, the waits are 0, 2 and 5, and the average is 7/3. Shortest remaining time first (SRTF) is the preemptive form. A running process is preempted whenever a newly arrived process has a shorter remaining time than the remaining time of the running process. When processes arrive at different times, SRTF can give a lower average waiting time than non-preemptive SJF, because the short job that arrives later does not wait for a long job to finish. For example, a process with burst 8 is preempted at time 2 by a process with burst 6, and the preempted process resumes after it completes.

For processes that arrive together under non-preemptive priority scheduling, the waiting time of each process is simply the time at which it starts. On a system with several processors, whenever a processor becomes free it dispatches the highest-priority ready process, and each process may run on any free processor. The average waiting time is then the mean of the start times.

First come first served (FCFS) runs processes in arrival order. Each process starts at the later of its arrival time and the completion time of the previous process, and the CPU is idle when no process has arrived. A long burst that runs first makes all shorter processes wait, which is the convoy effect.

Round robin (RR) gives each process at most a fixed time quantum q per turn and puts a preempted process at the tail of the ready queue. A process with burst b receives \lceil b/q \rceil slices. Round robin does not need the burst times in advance, which is why it is used when the CPU demand is unknown. A context switch occurs whenever the running process changes, including the switch to a ready process after the current process terminates. To check whether a context switch count is consistent with given bursts, simulate the queue slice by slice and count each change of the running process.

Preemptive scheduling needs hardware support, because a timer interrupt must be able to take the CPU away from a running process.

Semaphores and race conditions

A semaphore is an integer variable that is accessed only through two atomic operations. The wait operation, also called P, decrements the value and blocks the caller while the value is not positive. The signal operation, also called V, increments the value and wakes one blocked thread if any are waiting. A binary semaphore takes only the values 0 and 1 and acts like a lock. A counting semaphore counts available units of a resource and allows up to its initial value of threads to pass at the same time.

The initial value decides the synchronization pattern. An initial value of 1 gives mutual exclusion, because only one thread can pass wait at a time. An initial value of 0 makes the first wait block until some other thread signals, which is used to order events. Each waiting thread consumes one unit when it passes, so a semaphore with a count of 0 leaves no units for later threads.

A race condition occurs when the result depends on the interleaving of threads. The statement x = x + 1 is a load, an add and a store. If two threads interleave, one may load a stale value and later store it, overwriting the other thread's update, so the final value can be smaller than the number of increments. A semaphore protects the critical section only if it covers the whole read-modify-write sequence. With a binary semaphore, updates are serialized and no update is lost. With a counting semaphore whose initial value allows two threads inside at once, lost updates are possible, and the minimum value that can be reached is bounded by the number of decrements that can be applied from a stale read.

A deadlock involving semaphores occurs when threads hold units while waiting for more units and the units run out. For example, if five threads each perform two waits on a semaphore that starts at 5, the schedule in which all five pass the first wait leaves the value at 0, and every thread then blocks on its second wait. A thread that waits on a second semaphore while still holding the first can also block the rest of the system. If signal is executed after the blocking wait instead of before it, the holder keeps the lock while waiting and other threads cannot enter.

Threads of the same process share global variables, so each thread operates on the same copy of a global. Local variables declared inside a function are kept separately for each call, so each thread has its own copy. Processes have separate address spaces, so two processes each hold their own copy of a global variable and updates by one process do not affect the other.

To count the possible outcomes of two threads whose statements are atomic, note that the statements of each thread keep their program order. If one thread has m statements and the other has n, there are \binom{m+n}{m} interleavings. Enumerating these interleavings gives the set of final values.

Semaphores can also enforce an order of output. A thread can pass a token to the next thread by signaling a semaphore that the next thread waits on. With a single token in circulation, the threads take turns in a fixed cycle. A thread that reaches a counter threshold can signal a waiting semaphore to release the others one at a time, each released thread passing the signal along, so the printed pattern depends on where the signals occur relative to the mutual exclusion.

Process and thread states

A process passes through five standard states. In the new state the process is being created. In the ready state it waits for the CPU, in the running state it executes on a CPU, in the waiting (blocked) state it waits for an event such as the completion of an I/O request, and in the terminated state it has finished. The transitions are: new to ready when the process is admitted; ready to running when the scheduler dispatches it; running to ready when it is preempted, for example when its time slice expires; running to waiting when it requests I/O or waits for an event; waiting to ready when the event completes; and running to terminated when it exits.

A waiting process cannot move directly to running, because it must first become ready and then be dispatched by the scheduler. A ready process cannot move directly to waiting, because a process enters the waiting state only from the running state, when it itself requests an event or I/O. A running process may move to ready when it is preempted, and to terminated when it finishes.

The operating system switches the CPU away from a process only when the process cannot continue or when the scheduler decides to preempt it. A blocking system call, such as a read of a disk block, always moves the caller to the waiting state, so the operating system must dispatch another process. A page fault on a page held in swap space likewise requires a disk read, so the faulting process blocks and a context switch always follows. An interrupt from a device that delivers data for another process only runs the interrupt handler, and the interrupted process continues unless the scheduler chooses to switch. A timer interrupt causes a switch only when the time quantum has expired and another process is ready.

Threads follow the same state model, but threads of one process share the address space and global data, so one thread can block while other threads of the same process continue to run.

Some questions in this section test formal language theory rather than operating system state models. A subset of a recursively enumerable language need not be recursive, because the halting language is recursively enumerable but not recursive, so the statement that every subset of a recursively enumerable language is recursive is false. By Post's theorem, if both a language and its complement are recursively enumerable, then the language is recursive. Every context-free language is recursive, and recursive languages are closed under complement, so the complement of a context-free language is recursive. The regular languages are closed under union and intersection, and every regular language is deterministic context-free.

Disk geometry and capacity calculation

A hard disk stores data in concentric tracks on each surface, and each track is divided into sectors. A cylinder is the set of tracks at the same radius across all surfaces, so the number of cylinders equals the number of tracks on each surface. The total capacity is \text{surfaces} \times \text{cylinders} \times \text{sectors per track} \times \text{bytes per sector}. In GATE questions, 1\,\text{K} = 2^{10}, 1\,\text{M} = 2^{20} and 1\,\text{G} = 2^{30} bytes, so the capacity is often a power of two and the number of cylinders can be found by division. For example, a disk of 2^{39} bytes with 32 surfaces, 4096 sectors per track and 1 KB sectors has 2^{39} / (2^5 \times 2^{12} \times 2^{10}) = 2^{12} cylinders.

The rotation period is 60/\text{RPM} seconds. The average rotational latency is half of a rotation, because on average the wanted sector is half a revolution away from the head. The time to transfer one sector is the rotation period divided by the number of sectors per track, so the sector size in bytes does not change the transfer time when the number of sectors per track is given. For example, at 7200 RPM the rotation period is about 8.33 ms and the average rotational latency is about 4.17 ms.