This cheat sheet covers the core operating system ideas behind processes, scheduling, synchronization, deadlocks, memory management, and file systems. College students need these concepts to understand how programs share CPU time, memory, files, and devices safely. It is designed as a compact reference for exams, labs, and system design review.
Key Facts
- A typical process state flow is new -> ready -> running -> waiting -> ready -> terminated, with preemption moving a process from running back to ready.
- CPU utilization can be estimated as CPU utilization = busy CPU time / total elapsed time.
- Turnaround time is turnaround time = completion time - arrival time, and waiting time is waiting time = turnaround time - total CPU burst time.
- Round Robin scheduling gives each ready process a time quantum q, and a smaller q improves responsiveness but increases context switch overhead.
- A semaphore protects shared resources using wait() to decrement and block if needed, and signal() to increment and wake a waiting process.
- Deadlock requires all four Coffman conditions: mutual exclusion, hold and wait, no preemption, and circular wait.
- For paging, logical address = page number + offset, and physical address = frame number + offset after translation through the page table or TLB.
- Effective access time with a TLB is EAT = hit ratio * TLB hit time + (1 - hit ratio) * TLB miss time, using the full memory access cost for each case.
Vocabulary
- Process
- A process is a running program with its own address space, state, registers, and operating system control information.
- Context switch
- A context switch is the act of saving the current process state and loading another process state so the CPU can run a different process.
- Semaphore
- A semaphore is a synchronization variable controlled by wait() and signal() operations to manage access to shared resources.
- Deadlock
- A deadlock is a condition where processes wait forever because each holds a resource needed by another process in the same waiting cycle.
- Virtual memory
- Virtual memory is a memory abstraction that lets each process use logical addresses that the operating system maps to physical memory or storage.
- Page fault
- A page fault occurs when a process references a virtual page that is not currently loaded in physical memory.
Common Mistakes to Avoid
- Confusing waiting time with turnaround time is wrong because turnaround time includes all time from arrival to completion, while waiting time excludes actual CPU burst time.
- Treating blocked and ready as the same state is wrong because a ready process only needs CPU time, while a blocked process is waiting for an event such as I/O.
- Using wait() and signal() in the wrong order is wrong because entering a critical section before wait() can allow multiple processes to access shared data at once.
- Assuming deadlock happens whenever a process waits is wrong because deadlock requires a cycle of resource dependence plus the necessary deadlock conditions.
- Ignoring page fault cost is wrong because disk or SSD access is much slower than memory access and can dominate effective memory access time.
Practice Questions
- 1 Three processes have arrival times P1 = 0, P2 = 2, P3 = 4 and CPU bursts P1 = 6, P2 = 3, P3 = 1. Using FCFS scheduling, find each turnaround time and average waiting time.
- 2 A Round Robin scheduler has time quantum q = 4 ms and context switch cost = 0.5 ms. If 10 time slices occur, how much total time is spent only on context switches?
- 3 A system has a TLB hit ratio of 0.90, TLB lookup time of 5 ns, and memory access time of 100 ns. If a TLB hit takes 5 ns + 100 ns and a miss takes 5 ns + 100 ns + 100 ns, compute the effective access time.
- 4 Explain why preventing circular wait can prevent deadlock, and describe one practical way an operating system or program can enforce this rule.
Understanding Operating Systems Process and Memory
A process is more than the program file stored on a drive. It is a running job with its own CPU register values, memory map, open files, permissions, and accounting data. The operating system keeps this information in a process control block.
When the CPU changes from one process to another, it saves the current registers and restores the next set. This is a context switch. It makes multitasking possible, but it does no useful work for the user.
Students should distinguish a process from a thread. Processes have separate address spaces by default. Threads inside one process share much of the same memory, which makes communication fast but can make errors easier to create.
Scheduling is about choosing which ready job receives CPU time next. Different policies favor different goals. An interactive editor should react quickly after a key press.
A long scientific calculation may care more about total completion time. Fairness matters too, because a low priority process can otherwise wait for an extremely long time. This problem is called starvation.
Priority aging gradually raises the priority of jobs that have waited for a long period. Real systems often combine scheduling rules across several queues.
Measuring performance requires more than one number. Low average waiting time can still hide poor response for one unlucky user.
Shared memory creates race conditions when the result depends on the timing of operations. A bank balance update is a useful example. Two threads can both read the same old balance before either writes its new value.
One update is then lost. A critical section is the small part of code that touches shared data. Locks, semaphores, and monitors control entry to that section.
Correct programs must protect every path that changes the shared resource, including error paths. They must release a lock reliably. Deadlock is different from a slow program.
In deadlock, each blocked task is waiting for an event that another blocked task must cause. Designers reduce this risk by requiring resources to be requested in one fixed order or by avoiding long lock hold times.
Virtual memory gives each process the impression of having a large private memory space. Only recently needed pages usually stay in physical RAM. When a program references a page that is absent, the hardware raises a page fault.
The operating system finds the page on storage, loads it into a free frame or replaces another page, then restarts the instruction. Storage is far slower than RAM, so frequent page faults can make a computer feel frozen. This is thrashing.
Page replacement policies try to keep pages that will be used again soon. The TLB is a small fast cache for address translations, so its hit rate strongly affects memory speed. File systems extend these ideas to persistent data by mapping file names to blocks, tracking free space, enforcing permissions, and recovering after crashes.