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.