Revision approach
- OS roles and reasoning
- Resource sharing, protection, convenient services
- State changes and algorithms
- Scheduling/deadlock: explicit assumptions
- Policy names ≠ universal performance rankings
👁 Full explanation
An OS controls resource sharing, protects programs and provides convenient services. Learn the state changes and algorithms behind each term. Scheduling and deadlock questions require explicit assumptions; a policy name alone does not establish a universal performance ranking. - Scheduling calculation setup
- Process-state transitions and Gantt chart
- Arrivals and burst lengths
- Numeric priority convention
- Quantum and context-switch cost
👁 Full explanation
Draw process-state transitions and a Gantt chart before calculating scheduling metrics. Record arrivals, burst lengths, priority convention, quantum and switch cost. - Deadlock diagnosis
- Held resources and directed waits
- Prevention, avoidance, detection, recovery
- CPU preemption ≠ resource preemption
👁 Full explanation
For deadlock, identify held resources and directed waits; distinguish prevention, avoidance, detection and recovery. CPU preemption is not the same as resource preemption. - Memory and file tracing
- Address translation
- Page replacement
- File-block lookup
- Small-number traces
- Convenience, efficiency, evolution: concrete mechanisms
👁 Full explanation
Trace address translation, page replacement and file-block lookup with small numbers. Compare convenience, efficiency and ability to evolve using concrete mechanisms.
OS01
Objectives and resource management
[Exam Focus]- OS objectives and services
- CPU, memory, storage allocation
- Device and communication resources
- Convenience: interfaces, files, device abstractions
- Efficiency: effective resource use
- Efficiency ≠ every process’s fastest response
- Development tools use OS services
- Application development ≠ core resource management
👁 Full explanation
An OS allocates CPU time, memory, storage, devices and communication resources, and provides services to programs. Convenience means making tasks easy through consistent interfaces, files and device abstractions. Efficiency means using resources effectively; it is not synonymous with the fastest response for every process. Application development tools use OS services but application development itself is not a core resource-management function. - Evolution and related properties
- Maintainable interfaces/modules
- Hardware support, features, repairs
- Backward compatibility: supported older behavior
- Compatibility ≠ every old binary
- Scalability: greater workload/resources
- Portability: other platforms
- Fault tolerance: correct service despite failures
- Recovery: service restoration afterward
- Updates/monitoring: administrative help
- Automatic updates: not universally defining
👁 Full explanation
Ability to evolve means adding hardware support, features and repairs through maintainable interfaces/modules. Backward compatibility preserves supported older application behavior; it is not a promise that every old binary works. Scalability means handling greater workload/resources; portability means adapting to other platforms. Fault tolerance continues correct service despite specified failures; recovery restores service afterward. Updates and monitoring help administration, but automatic updates are not a defining property of every OS.
21 related practice questions
Blueprint: OS1, OS2 · Note references: OS-M, OS-N, OS-SOLARIS
- OS objectives and services
OS02
Batch, sharing and real time
[Exam Focus]- Execution organization
- Batch: little post-submission interaction
- Multiprogramming: CPU work during another job’s wait
- Several available jobs
- Multiprogramming ≠ fixed time slices
- Time-sharing: rapid scheduling/preemption, interaction
- Single CPU: interleaved execution
- Multiple CPUs: true parallelism
- Shared memory ≠ mandatory private memories
👁 Full explanation
Batch jobs run with little interaction after submission. Multiprogramming keeps several jobs available so another can use the CPU while one waits; it does not require fixed time slices. Time-sharing uses rapid scheduling/preemption to support interactive users. A single CPU interleaves execution; multiple CPUs can execute work truly in parallel. Shared-memory multiprocessors do not require each CPU to have private main memory. - System categories and timing
- Single/multiuser: concurrent users, not applications
- Network systems: remote services
- Distributed systems: coordinated machines
- Location hiding possible
- Real-time correctness: timing included
- Hard deadlines: mandatory
- Soft misses: degraded service
- Real time ≠ simply fast
- Spooling/multitasking: mechanisms, not generation proofs
👁 Full explanation
Single-user and multiuser describe concurrent user access, not the number of applications. Network systems expose remote services; distributed systems coordinate work across machines, sometimes hiding location. Real-time correctness includes timing: hard deadlines must be met, while soft deadline misses degrade service. “Real time” does not simply mean fast. Spooling and multitasking are mechanisms, not proof of a particular OS generation.
3 related practice questions
Blueprint: OS1, OS2 · Note references: OS-M, OS-N
- Execution organization
OS03
Kernel, shell, privilege and boot
[Exam Focus]- OS components and privilege
- Kernel: resources, protection, system calls
- Shell: command interpretation
- GUI: another interface
- Browsers, office tools, editors: applications
- Drivers: commonly kernel, sometimes user-space
- Kernel mode: privileged operations
- Supervisor/kernel mode: often synonyms
- Exclusive mode options: ambiguity
👁 Full explanation
The kernel implements core resource management, protection and system-call handling. A shell reads/interprets user commands; a GUI is another interface. Browsers, office tools and editors are applications. Device drivers are commonly kernel components, although user-space drivers also exist. Kernel mode has privileged operations; supervisor mode often means the same privileged mode, so offering both as exclusive answers is ambiguous. - Boot sequence and resident components
- Firmware/bootloader before kernel
- Kernel loaded into RAM
- First core OS component
- Kernel ≠ first power-on program
- Loadable modules: running-kernel driver additions
- Modular systems allow runtime loading
- Resident kernel: session-long activity
- Antivirus/disk tools: utilities
- User processes plus privileged components
👁 Full explanation
Firmware/bootloader stages execute before transferring control to a kernel loaded into RAM. The kernel is the first core OS component, not the first program ever executed at power-on. Loadable modules can add drivers to a running kernel; “kernel modules cannot be loaded while running” is false in modular systems. A resident kernel remains active through the session. Utilities such as antivirus and disk tools can combine user processes with privileged components.
16 related practice questions
Blueprint: OS1, OS2 · Note references: OS-M, OS-N
- OS components and privilege
OS04
APIs, system calls and virtualization
[Exam Focus]- System call versus library API
- System call: protected kernel-service request
- Process creation, file read, socket opening
- API/library wrappers
- Library function ≠ mandatory kernel entry
- Application API versus user/kernel boundary
- OS-service interface: scope required
👁 Full explanation
A system call requests a protected kernel service, such as creating a process, reading a file or opening a socket. A user-facing API/library may wrap that request; not every library function enters the kernel. Distinguish the application API from the direct user/kernel boundary when describing access to OS services. - Services and virtual machines
- Process control
- File/device management
- Information retrieval and communication
- Video editing: application operation
- write_database(): application-specific, not generic syscall
- Virtualization: virtual machine environment
- Hypervisor: guests on one host
- Virtual memory: process-address translation
- Kernel/shell/API/VM: distinct labels
👁 Full explanation
Process control, file/device management, information retrieval and communication are service categories. Video editing and a database-specific write_database() are application operations, not standard generic syscall categories/names. Virtualization presents a virtual machine environment, often allowing guest operating systems on one host through a hypervisor. It differs from virtual memory, which translates a process’s addresses. Kernel, shell, API and VM are not interchangeable labels.
7 related practice questions
Blueprint: OS1, OS2 · Note references: OS-M, OS-N
- System call versus library API
OS05
Processes, programs and context
- Program versus process
- Program: stored instructions
- Process: executing instance
- Address space and resources
- Process ≠ universal application manager/UI
- PCB: identity and state
- Saved PC/registers: resume execution
- Scheduling information
- Memory/accounting details
- I/O and open-resource state
👁 Full explanation
A program is stored instructions; a process is an executing instance with address space and resources. A process does not universally “manage applications” or “provide a user interface.” The PCB records identity, state, PC/registers, scheduling information, memory/accounting details and I/O/open-resource state. A saved PC identifies where execution resumes. - Context switch and task terminology
- Save one context, restore another
- Application-work interruption: overhead
- Interrupt/syscall: privilege-only switch possible
- Privilege switch ≠ process switch
- Task: OS-specific meaning
- Process/thread/schedulable entity
- Process-versus-task: no universal distinction
👁 Full explanation
A context switch saves one execution context and restores another; useful application work is interrupted by this overhead. An interrupt or system call can switch privilege without switching process. Task is OS-specific terminology: it may mean process, thread or schedulable entity. No universal process-versus-task distinction follows from the word alone.
6 related practice questions
Note references: OS-M, OS-N
- Program versus process
OS06
Process states, queues and schedulers
- Process-state transitions
- New: created/admitted
- Ready: eligible, not running
- Running: CPU in use
- Waiting/blocked: event required
- Terminated: execution ended
- Running→ready: quantum expiry/preemption
- Running→waiting: blocking I/O
- I/O completion: waiting→ready
- Completion ≠ immediate running guarantee
👁 Full explanation
New processes are created/admitted; ready means eligible for CPU but not currently running. Running uses a CPU. Waiting/blocked means unable to proceed until an event; terminated means execution has ended. Running→ready follows time-slice expiry or another preemption. Running→waiting follows blocking I/O. I/O completion normally gives waiting→ready, not a guaranteed immediate running state. - Queues and scheduling roles
- Ready queue: eligible work
- Device queues: blocked requests
- Job queue: system processes
- Admission queue: awaiting memory/admission
- Long-term: job admission
- Medium-term: suspension/swapping
- Short-term: ready-work selection
- Dispatcher: handoff/context restore
- Priority preemption: policy-dependent running→ready
👁 Full explanation
The ready queue contains eligible work; device queues hold blocked requests. The broad textbook job queue contains processes in the system, while an admission queue more narrowly holds jobs awaiting memory/admission. Long-term scheduling admits jobs; medium-term scheduling suspends/swaps them; short-term scheduling selects ready work. The dispatcher performs the handoff/context restore after selection. A bare “priority” causes running→ready only if a preemptive policy chooses another process.
14 related practice questions
Note references: OS-M, OS-N, OS-SCHED
- Process-state transitions
OS07
Creation, fork/exec and termination
- Process creation mechanisms
- Initialization, user requests, service requests
- Running process’s creation call
- POSIX fork(): child creation
- Child return: 0
- Parent return: child PID
- Success assumption
- Distinct address spaces
- Explicit resource sharing possible
- exec: current image replacement
- exec ≠ new process creation
👁 Full explanation
Processes arise during initialization, user requests, service requests or a running process’s creation call. In POSIX-style systems fork() creates a child: zero is returned in the child and the child PID in the parent on success. The two have distinct address spaces, although resources may be shared through explicit mechanisms. exec replaces the current process image; it does not itself create another process. - Termination categories
- Voluntary: normal completion/program-detected error
- Involuntary: unrecoverable fault/killing
- exit(): normal runtime termination
- abort(): abnormal termination request
- Nonexistent/protected memory: fatal fault
- Bad-input exit: application decision
- Terminate exit: imprecise category
- Parent exit ≠ universal descendant killing
👁 Full explanation
Normal completion and a program-detected error exit are voluntary; an unrecoverable fault or being killed is involuntary. exit() terminates normally through the runtime; abort() requests abnormal termination. A reference to nonexistent/protected memory is a fatal fault, unlike an application deciding to exit after bad input. “Terminate exit” is not a precise standard category. Parent termination does not universally kill all descendants.
6 related practice questions
Note references: OS-N, OS-FORK, OS-EXEC
- Process creation mechanisms
OS08
Threads and mapping models
- Thread ownership and sharing
- Own PC, registers, stack
- Shared code and address space
- Usually shared open files
- Process: potentially many threads
- Thread: one process at a time
- Threads ≠ group of processes
- Thread execution need not be sequential
- Independent versus cooperating processes
- Cooperation: communication/shared data
👁 Full explanation
A thread has its own PC, registers and stack. Threads in a process share code, address space and usually open-file resources. A process can contain many threads; a thread belongs to one process at a time. Threads are not a group of processes and need not execute sequentially. Independent processes can exist; cooperating ones communicate/share data. - Thread management and mappings
- User-level: library management
- Kernel threads: OS-known
- Many-to-one: blocking call blocks all
- One context: no simultaneous multi-CPU use
- One-to-one: another thread runs when blocked
- Many-to-many: users multiplexed over kernel threads
- Speed/reliability: implementation-dependent
- Management layer ≠ guarantees
- Browser/Excel names ≠ threading-model proof
👁 Full explanation
User-level threads are managed by a library; kernel threads are known to the OS. In many-to-one mapping, a blocking kernel call can block all user threads and one kernel execution context cannot use multiple CPUs simultaneously. One-to-one permits another kernel thread to run when one blocks. Many-to-many multiplexes user threads over several kernel threads. Speed and reliability depend on implementation; the management layer alone guarantees neither. Application names such as browser or Excel do not prove a particular version’s threading model.
7 related practice questions
Note references: OS-M, OS-N
- Thread ownership and sharing
OS09
IPC and blocking semantics
- IPC mechanisms
- Shared memory: common region
- Conflicting updates require synchronization
- Message passing: send/receive
- Pipes: streams
- Message queues: message boundaries
- Sockets: endpoints
- RPC: remote operation
- HTTP: application communication protocol
- HTTP can carry IPC
👁 Full explanation
Shared memory lets processes access a common region and requires synchronization for conflicting updates. Message passing exchanges data through send/receive operations. Pipes provide streams; message queues preserve messages; sockets connect endpoints; RPC requests a remote operation. HTTP is an application protocol over a communication mechanism and can carry interprocess communication, so it is not universally “not IPC.” - Blocking and nonblocking contracts
- Blocking send: API-defined wait condition
- Handoff, buffering or receipt
- Blocking receive: wait for message
- Nonblocking: prompt data/progress/would-block
- Rendezvous: sender waits until receipt
- File locks: access coordination
- Locks ≠ arbitrary payload transfer
- Locking: IPC synchronization
- Asynchronous messaging ≠ synchronization-free
👁 Full explanation
Blocking send waits for the required handoff/buffering/receipt condition defined by its API. Blocking receive waits for a message. Nonblocking operations return promptly with data, progress or a would-block result. “Sender blocked until received” identifies blocking send under rendezvous semantics. File locks coordinate access rather than transfer arbitrary payloads, though locking is synchronization within IPC. Do not equate asynchronous messaging with no synchronization ever.
5 related practice questions
Note references: OS-M, OS-N
- IPC mechanisms
OS10
Races and critical-section correctness
- Race and critical-section criteria
- Race: conflicting uncoordinated interleavings
- Critical section: protected shared-state code
- Critical section ≠ resource itself
- Mutual exclusion: safety property
- Progress
- Bounded waiting
- Stated correctness assumptions
- Failures: races, starvation, deadlock
👁 Full explanation
A race occurs when results depend on uncoordinated interleaving of conflicting accesses. A critical section is code accessing shared state that needs protection, not the resource itself. A correct exclusion solution requires mutual exclusion, progress and bounded waiting under stated assumptions. Mutual exclusion is a desired safety property; races, starvation and deadlock are possible failures. - Synchronization structure
- Small critical regions
- Same protection for every conflicting access
- Barrier: defined participants reach point
- Monitor: encapsulated protected operations
- Condition synchronization
- Inconsistent lock order: deadlock risk
👁 Full explanation
Keep critical regions small and ensure every conflicting access uses the same protection. A barrier waits until a defined set of participants reaches a point; a monitor encapsulates protected operations with condition synchronization. Locking can itself introduce deadlock if acquisition order is inconsistent. - Worked example Lost-update example
- Two reads: counter=0
- Each computes/stores 1
- Two increments → 1, not 2
- Entire read-modify-write under one lock
👁 Full explanation
Worked microexampleTwo threads read counter=0, each computes 1 and each stores 1. Two increments produce 1 instead of 2. Protecting the entire read-modify-write with one lock prevents that lost update.
8 related practice questions
Note references: OS-M, OS-N
- Race and critical-section criteria
OS11
Semaphores and resource counts
- Semaphore operations and models
- Atomic wait/P/down
- Atomic signal/V/up
- Nonnegative wait: consume token or block
- Signal: token supply, possible wakeup
- Negative counts: alternative waiter encoding
- State the count model
- Binary semaphore: one permit
- Counting semaphore: several permits
- Mutex: ownership rules
- General semaphore: no equivalent ownership requirement
👁 Full explanation
A semaphore provides atomic wait/P/down and signal/V/up operations. Under the nonnegative-token model, wait consumes one available token or blocks when none is available; signal supplies a token and may wake a waiter. Implementations using negative internal counts encode waiters differently, so state the model. A binary semaphore represents one permit; a counting semaphore tracks several. A mutex normally has ownership rules that a general semaphore lacks. - Worked example Semaphore and bounded-buffer example
- Mutex initial value: 1
- wait(m); critical work; signal(m)
- N slots: empty=N, full=0, mutex=1
- Producer: wait empty, then mutex
- Insert; unlock; signal full
- Holding mutex while waiting empty
- Consumer unable to free slot
👁 Full explanation
Worked microexampleInitialize a mutex semaphore to 1. Each thread does wait(m); critical work; signal(m). For a buffer of N slots use empty=N, full=0 and mutex=1: producer waits empty then mutex, inserts, unlocks then signals full. Waiting for empty while already holding mutex can prevent the consumer from freeing a slot.
6 related practice questions
Note references: OS-N, OS-SEM
- Semaphore operations and models
OS12
Turn variables and atomic primitives
- Strict alternation and lock-variable races
- turn=0/1
- Process i: wait while turn≠i
- Enter, then hand turn over
- Alternation enforces turns
- Outside peer: progress violation
- Separate test/set: race
- Both may observe free
👁 Full explanation
Strict alternation uses turn=0/1: process i waits while turn≠i, then enters and sets turn to the other process on leaving. It enforces turns but can violate progress if the other process stays outside its critical region. A naive lock-variable test followed by a separate set races because both processes can observe free before either sets it. - Atomic synchronization primitives
- Test-and-set; compare-and-swap
- Atomic check/update
- Ordinary check-then-write: non-atomic
- Peterson: flags plus turn
- Two processes; memory-model assumptions
- Semaphore: more than two possible
- Local interrupt disabling excludes no other CPUs
- Not general user-space locking
- Interrupts: event notification/synchronization
- Interrupt synchronization exclusions: overbroad
👁 Full explanation
Test-and-set and compare-and-swap combine checking/updating atomically; ordinary check-then-write does not. Peterson’s classic algorithm uses flags plus turn for two processes under its memory-model assumptions; a semaphore can coordinate more than two. Disabling local interrupts does not exclude other CPUs and is not a general user-space locking solution. Interrupts can notify/synchronize events, so they cannot be universally excluded from every synchronization-related classification.
2 related practice questions
Note references: OS-SYNC, OS-N
- Strict alternation and lock-variable races
OS13
Scheduling metrics and calculations
[Exam Focus]- Scheduling equations and goals
- A: arrival; S: start; C: completion
- Response=S−A
- Turnaround=C−A
- Single burst B, no I/O
- Waiting=C−A−B
- I/O: subtract CPU and blocked time
- Ready-queue waiting only
- Throughput=completed_jobs/elapsed_time
- CPU_utilization=busy_time/elapsed_time
- Goal-dependent response/turnaround/wait minimization
- Useful throughput/utilization maximization
👁 Full explanation
For arrival A, first start S and completion C, response=S−A and turnaround=C−A. For a single CPU burst B with no I/O, waiting=C−A−B. With I/O, subtract all CPU and blocked time to isolate ready-queue waiting. Throughput=completed jobs/elapsed time; CPU utilization=busy time/elapsed time. Minimize response/turnaround/waiting under the selected goal and maximize useful throughput/utilization. - Timeline-first calculation method
- Arrivals and idle gaps
- Preemptions and overhead
- Per-process values before averages
- First response ≠ final completion
👁 Full explanation
First construct a time line with arrivals, idle gaps, preemptions and overhead, then calculate per-process values before averages. Do not confuse first response with final completion. - Worked example Scheduling-metric example
- A=2; S=5; B=4; C=9
- Uninterrupted CPU burst
- Response=3; turnaround=7; waiting=3
- Six completions/two hours=3 jobs/hour
👁 Full explanation
Worked microexampleA job arrives at 2, starts at 5, uses 4 CPU units without interruption and finishes at 9: response=3, turnaround=7, waiting=3. Six completions in two hours means throughput=3 jobs/hour.
4 related practice questions
Blueprint: OS4 · Note references: OS-M, OS-N
- Scheduling equations and goals
OS14
Preemptive and non-preemptive decisions
[Exam Focus]- CPU scheduling variants
- Non-preemptive: completion/block/yield ends burst
- Preemptive: running→ready allowed
- Timer quantum or urgent arrival
- FCFS/non-preemptive SJF: non-preemptive
- RR/SRTF: preemptive
- Priority: either variant
- Cooperative: voluntary release
👁 Full explanation
Non-preemptive scheduling keeps a running CPU burst until completion, blocking or voluntary yielding. Preemptive scheduling can return running work to ready, usually after a timer quantum or a more urgent arrival. FCFS and non-preemptive SJF are non-preemptive; RR and SRTF are preemptive. Priority can be either, so its name alone cannot decide. Cooperative describes relying on voluntary release. - CPU versus resource preemption
- Save context, reallocate CPU time
- Occupied printer/lock: unsafe withdrawal possible
- Time-slicing ≠ removing no-resource-preemption
- Frequent switches: overhead
- Non-preemptive long bursts delay interaction
👁 Full explanation
CPU preemption saves a context and reallocates processing time; taking an occupied printer or lock may be unsafe. This is why time-slicing does not automatically remove the no-resource-preemption condition for deadlock. Frequent switches have cost; non-preemptive policies can delay interactive work behind long bursts.
5 related practice questions
Blueprint: OS4 · Note references: OS-M, OS-N, OS-SCHED
- CPU scheduling variants
OS15
FCFS and convoy effects
[Exam Focus]- FCFS behavior and limits
- Ready bursts: arrival order
- Ordinarily non-preemptive
- Idle CPU: jump to next arrival
- Convoy: long burst delays short jobs
- Finite work ahead: eventual start
- Eventual service ≠ small waiting
- FCFS ≠ universally worst turnaround
👁 Full explanation
FCFS runs ready bursts in arrival order and ordinarily does not preempt. If the CPU is idle, jump to the next arrival. Long CPU-bound work can make many short jobs wait: the convoy effect. A finite burst with finitely many jobs ahead eventually starts, but waiting can still be large. FCFS does not universally have the worst turnaround for every possible workload. - Worked example FCFS simultaneous-arrival example
- All arrive 0; P1=24,P2=3,P3=3
- Tie order: P1,P2,P3
- P1:0–24; P2:24–27; P3:27–30
- Waiting 0,24,27 → mean 17
- Turnaround 24,27,30 → mean 27
- Different arrivals: recompute actual times
👁 Full explanation
Worked microexampleAll ready at time 0, tie order P1=24,P2=3,P3=3: schedule 0–24 P1,24–27 P2,27–30 P3. Waiting times 0,24,27 average to 17. Turnarounds 24,27,30 average to 27. If arrivals are not simultaneous, recompute using their actual times.
3 related practice questions
Blueprint: OS4 · Note references: OS-M, OS-N
- FCFS behavior and limits
OS16
SJF/SJN and remaining time
[Exam Focus]- Shortest-job scheduling rules
- SJF/SJN: shortest ready next burst
- Non-preemptive selection
- SRTF: reconsider arrivals
- Shortest remaining work; newcomer may preempt
- Future bursts: estimates needed
- SJF minimum-average-wait theorem
- Fixed simultaneous ready set
- Known bursts; no preemption/switch cost
- Theorem ≠ universal preemptive-policy comparison
👁 Full explanation
Non-preemptive SJF/SJN chooses the shortest next burst among currently ready jobs. SRTF reconsiders on arrivals and selects the shortest remaining work; a shorter newcomer can preempt. Future burst lengths normally need estimates. SJF minimizes average waiting for the usual fixed simultaneous ready set with known bursts and no preemption/switch cost; that theorem is not a workload-independent comparison against every preemptive policy. - Shortest-job traps
- Repeated short arrivals: long-job starvation
- Original burst ≠ remaining burst
👁 Full explanation
Repeated short arrivals can starve a long job. The shortest total original burst is not necessarily the shortest remaining burst after execution has begun. - Worked example SRTF example
- P1: arrival 0, burst 8
- P2: arrival 1, burst 2
- P1:0–1; P2:1–3; P1:3–10
- Waiting: P1=2, P2=0
- Non-preemptive SJF: no P1 interruption
👁 Full explanation
Worked microexampleP1 arrives 0 with burst 8; P2 arrives 1 with burst 2. SRTF runs P1 0–1, P2 1–3, P1 3–10. P1 waiting=2 and P2 waiting=0. Non-preemptive SJF cannot interrupt P1 once it has started.
7 related practice questions
Blueprint: OS4 · Note references: OS-M, OS-N
- Shortest-job scheduling rules
OS17
Priority, starvation and aging
[Exam Focus]- Priority scheduling assumptions
- Highest-priority ready job
- Numeric convention: smaller or larger wins
- Arrival preemption: specify variant
- Continued high-priority load: low-priority starvation
- SJF: long-job starvation too
- Priority/SJF options: multiple valid answers
👁 Full explanation
Priority scheduling chooses the highest-priority ready job. Check whether a smaller or larger numeric value means higher priority. State whether a high-priority arrival preempts. Fixed-priority scheduling can starve low-priority jobs under continued high-priority load. SJF can also starve long jobs; starvation is not exclusive to fixed-priority scheduling. - Aging and priority inversion
- Aging: waiting raises effective priority
- Explicit aging rule
- Workload/priority scheme conditions
- Reduced indefinite postponement
- Aging ≠ deadlock cure
- Inversion: urgent waits on low-priority holder
- Inheritance: temporarily raise holder priority
👁 Full explanation
Aging increases waiting jobs’ effective priority according to a rule, reducing indefinite postponement when the priority scheme and workload permit. It is not a deadlock cure. Priority inversion occurs when urgent work waits on a resource held by lower-priority work; priority inheritance can temporarily raise the holder’s priority.
6 related practice questions
Blueprint: OS4 · Note references: OS-M, OS-N
- Priority scheduling assumptions
OS18
Round Robin and quantum bounds
[Exam Focus]- Round Robin queue behavior
- Cyclic ready queue
- At most q per turn
- Unfinished→tail; completed/blocked→leave
- Quantum-boundary arrival ordering
- Large q approaches FCFS
- Tiny q increases switch overhead
- Recurring opportunities ≠ equal total consumption
👁 Full explanation
RR serves a ready queue cyclically for at most quantum q per turn. Unfinished jobs return to the tail; completed/blocked jobs leave. Specify how arrivals at a quantum boundary enter the queue. A large quantum approaches FCFS; tiny quanta increase switch overhead. RR gives recurring opportunities, not identical total CPU consumption for jobs of different lengths. - RR next-turn waiting bound
- n continuously ready jobs
- No priority bypass; zero overhead
- Next-turn wait≤(n−1)q
- One interval, not lifetime waiting
- Unrestricted arrivals/blocking: bound limitations
- Include specified context-switch costs
👁 Full explanation
With n continuously ready jobs, no priority bypass and zero overhead, a just-requeued job waits at most (n−1)q for its next turn. This bounds one interval, not total lifetime waiting when arrivals or blocking are unrestricted. Include context-switch costs if given. - Worked example RR trace example
- P1=5,P2=3; arrivals=0; q=2
- P1:0–2; P2:2–4; P1:4–6
- P2:6–7; P1:7–8
- Completions: P1=8,P2=7
- Waiting: 8−5=3; 7−3=4
- Mean waiting=3.5
👁 Full explanation
Worked microexampleP1=5,P2=3, both arrive 0, q=2: P1 0–2,P2 2–4,P1 4–6,P2 6–7,P1 7–8. Completions 8,7; waiting=8−5=3 and 7−3=4; average 3.5.
7 related practice questions
Blueprint: OS4 · Note references: OS-M, OS-N
- Round Robin queue behavior
OS19
Multilevel queues and feedback
[Exam Focus]- Multilevel scheduling
- Separate foreground interactive/background batch classes
- Between-queue and within-queue selection
- Fixed interqueue priority: lower-queue starvation
- Class time shares: starvation avoidance
- Feedback queues: behavior-based movement
- CPU-intensive demotion
- Periodic priority boosting
👁 Full explanation
A multilevel queue separates classes, such as foreground interactive and background batch, and chooses both between queues and within them. Fixed interqueue priority may starve lower queues; allocating time shares between classes can avoid this. A multilevel feedback queue allows movement according to observed behavior, commonly demoting CPU-intensive jobs and periodically boosting priority. - Multilevel trace assumptions and traps
- Plain multilevel ≠ automatic movement
- Initial class
- Quantum per level
- Promotion/demotion rules
- Interqueue policy
- Binary search tree: implementation data structure
- Tree ≠ CPU selection policy
- Infinite: not standard policy category
👁 Full explanation
Do not infer movement from a simple multilevel-queue label. State initial class, quantum per level, promotion/demotion rules and interqueue policy before tracing. A binary search tree is a data structure that might implement a queue; it is not itself a CPU selection policy. “Infinite” is not a standard scheduling-policy category.
1 related practice question
Blueprint: OS4 · Note references: OS-M, OS-N
- Multilevel scheduling
OS20
Fair-share and proportional guarantees
[Exam Focus]- Fair-share allocation
- Stated weights
- Per-user/group versus per-process shares
- More processes under RR: aggregate advantage
- Proportional shares: policy choice
- Fair ≠ necessarily equal
👁 Full explanation
Fair-share scheduling allocates according to stated weights, potentially per user/group rather than per process. Equal per-process RR can let a user obtain more aggregate CPU by launching more processes. Proportional shares address that policy choice; fair need not mean equal. - Lottery, stride and guarantee limits
- Lottery: tickets and winning selection
- Weights 3:1 → expected 75%:25%
- Short-run variation
- Lottery ≠ deterministic starvation deadline
- Stride: deterministic share-progress tracking
- Guaranteed scheduling: specify guarantee/assumptions
- Finite FCFS/RR: no indefinite postponement possible
👁 Full explanation
Lottery scheduling assigns tickets and selects a winning ticket each turn. With weights 3:1, expected shares are 75% and 25%; short-run results vary and this is not a deterministic no-starvation deadline. Stride-style scheduling tracks progress toward shares deterministically. Any “guaranteed scheduling” answer needs the actual guarantee and assumptions; finite FCFS and RR can also avoid indefinite postponement. - Worked example User-share example
- A: four ready tasks; B: one
- Per-process RR: A≈80% overall
- Per-user halves: A=50%,B=50%
- Each A task≈12.5%
- B’s task=50%
👁 Full explanation
Worked microexampleIf user A runs four ready tasks and B runs one, plain RR gives A about 80% overall. A policy granting each user half the CPU instead gives A’s tasks about 12.5% each and B’s task 50%.
3 related practice questions
Blueprint: OS4 · Note references: OS-FAIR, OS-M
- Fair-share allocation
OS21
Evaluating scheduling claims
[Exam Focus]- Workload-dependent scheduling comparisons
- Response, waiting, fairness, throughput tradeoffs
- Workload and objective first
- Apply algorithm; compare measured results
- Burst times alone: insufficient maximum wait
- Unconstrained arrivals, priorities, overhead
- Finite workload versus open stream
- Open stream: potential starvation
👁 Full explanation
There is no universally best policy for response, waiting, fairness and throughput simultaneously. State the workload and objective, apply the algorithm and compare measured results. Maximum waiting at submission is not determined from burst times alone if future arrivals, priorities or overhead are unconstrained. Known finite workloads are different from an open stream with potential starvation. - Scheduling-question ambiguity
- FCFS and SJN: both non-preemptive
- Equal share: process/user/group scope
- Highest turnaround: concrete workload required
- FCFS worst: not absolute
- RR: conventional interactive choice
- Turns improve responsiveness
- Quantum and overhead conditions
👁 Full explanation
An item asking for one non-preemptive algorithm while offering FCFS and SJN has multiple answers. Equal share needs a process/user/group definition. “Highest average turnaround” requires a concrete workload; do not memorize FCFS as an absolute. RR is a conventional interactive choice because turns improve responsiveness, subject to quantum and overhead.
3 related practice questions
Blueprint: OS4 · Note references: OS-M, OS-N
- Workload-dependent scheduling comparisons
OS22
Deadlock and necessary conditions
[Exam Focus]- Deadlock versus blocking/starvation
- Every member waits on blocked peer
- Ordinary holder wait: normal blocking
- Starvation: unfair indefinite delay
- Starvation need not contain dependency cycle
- Mutual exclusion: one nonshareable-resource holder
- Hold-and-wait: retain while requesting
- No resource preemption: voluntary release only
- Circular wait: closed dependency chain
👁 Full explanation
A set is deadlocked when each member waits for an event/resource that only another blocked member can provide. Mere waiting for another holder is normal blocking; indefinite unfair delay can be starvation without a cycle of dependencies. Mutual exclusion allows at most one holder of a nonshareable resource. Hold-and-wait means retaining a resource while requesting another. No resource preemption means release must be voluntary. Circular wait forms a closed chain of such waits. - Four-condition interpretation
- Standard reusable-resource model
- All four necessary
- General policies ≠ current deadlock proof
- Inspect actual allocations and requests
- Prevent one condition: prevent class
- CPU preemption can coexist with deadlocks
👁 Full explanation
All four are necessary in the standard reusable-resource model. Their availability as general system policies does not prove a deadlock exists at this instant; inspect actual allocations/requests. Preventing any one condition prevents that class of deadlock. A preemptive CPU scheduler can coexist with deadlocked locks. - Worked example Two-lock deadlock example
- P1 holds A, requests B
- P2 holds B, requests A
- No release before acquisition
- Nonshareable locks
- Retained holdings
- No forced release
- Circular dependency
👁 Full explanation
Worked microexampleP1 holds lock A and requests B; P2 holds B and requests A. Neither releases before acquiring the other: nonshareable locks, retained holdings, no forced release and a cycle all occur.
14 related practice questions
Blueprint: OS3 · Note references: OS-N
- Deadlock versus blocking/starvation
OS23
Resource graphs and cycle tests
[Exam Focus]- Resource-allocation graph rules
- P→R: request
- R-instance→P: assignment
- Follow directed waits
- No cycle → no deadlock
- Single instance/type: cycle → deadlock
- Multiple instances: cycle insufficient
- Available instance may permit completion
- Wait-for graph: resource nodes replaced
- P→Q: P waits for Q
👁 Full explanation
In a resource-allocation graph, P→R is a request and an instance R→P is an assignment. Follow these directions to form waits. No cycle implies no deadlock; with one instance of every resource type, a cycle implies deadlock. With multiple instances a cycle alone is insufficient: another instance may permit completion. A wait-for graph replaces single-instance resource nodes with P→Q when P waits for Q. - Single-instance cycle example
- P0 holds R0, requests R1
- P1 holds R1, requests R0
- Wait-for edges: P0→P1, P1→P0
- Cycle: neither proceeds
- Multiple instances: inspect every assignment
- Check available instances before conclusion
👁 Full explanation
For a complete single-instance example, suppose P0 holds R0 and requests R1, while P1 holds R1 and requests R0. The wait-for edges P0→P1 and P1→P0 form a cycle, so neither can proceed. With multiple resource instances, inspect all assignments and available instances before concluding that a cycle is a deadlock.
3 related practice questions
Blueprint: OS3 · Note references: OS-N
- Resource-allocation graph rules
OS24
Prevention and removed conditions
[Exam Focus]- Deadlock prevention mechanisms
- Constrain resource requests
- Safe sharing removes mutual exclusion
- All-before-holding requests remove hold-and-wait
- Safe withdrawal/restart attacks no-preemption
- Global acquisition order removes circular wait
- Physical resources: sharing/preemption limitations
👁 Full explanation
Prevention constrains how requests are made. Share a resource where safe to remove mutual exclusion; request all needed resources before holding any to remove hold-and-wait; permit safe resource withdrawal/restart to attack no-preemption; impose a global acquisition order to remove circular wait. Not every physical resource is shareable or safely preemptable. - Release-and-retry interpretation
- Release all holdings when waiting
- Removes simultaneous holding and waiting
- Voluntary release versus forced preemption
- Reclaiming description: ambiguous condition target
- Prevention: utilization waste possible
- Prevention: starvation possible
- Deadlock freedom ≠ fairness
👁 Full explanation
“If waiting, release all held resources and try again” removes simultaneous holding while waiting. Distinguish voluntary resource release from forced preemption when describing resource reclamation. Prevention can waste utilization or cause starvation; avoiding deadlock is not the same as treating every process fairly.
2 related practice questions
Blueprint: OS3 · Note references: OS-N
- Deadlock prevention mechanisms
OS25
Banker avoidance and safety testing
[Exam Focus]- Banker safety algorithm
- Avoidance: resulting state remains safe
- Known maximum claims required
- Need=Max−Allocation
- Work=Available
- Find unfinished process: Need≤Work componentwise
- Simulate completion: Work+=Allocation
- Finish all → safe sequence
- Request≤Need and request≤Available
- Tentative grant requires successful safety test
- Unsafe ≠ already deadlocked
- Banker: avoidance, not scheduling/detection/prevention
👁 Full explanation
Avoidance allows requests only if the resulting state remains safe. Banker requires maximum claims. Compute Need=Max−Allocation. Set Work=Available and repeatedly find an unfinished process with Need≤Work componentwise; simulate completion by adding its Allocation to Work. Finishing all gives a safe sequence. Tentatively grant a request only if it is within Need and Available and the safety test succeeds. Unsafe does not mean already deadlocked. Banker is avoidance, not CPU scheduling, detection or prevention by breaking a condition. - Worked example One-resource safety example
- Available=1
- P1: allocation=1, remaining need=1
- P2: allocation=2, remaining need=2
- Finish P1 → Work=2
- Then finish P2
- Safe sequence: P1,P2
- Maximum claims known before testing
👁 Full explanation
Worked microexampleOne resource type: Available=1; P1 holds 1 and needs 1 more; P2 holds 2 and needs 2 more. P1 can finish, returning its allocation so Work becomes 2; P2 can then finish. Safe order P1,P2. A maximum claim must be known before testing.
4 related practice questions
Blueprint: OS3 · Note references: OS-DEAD
- Banker safety algorithm
OS26
Detection, recovery and ignoring
[Exam Focus]- Detection and recovery
- Detection: current-state deadlock
- Terminate selected processes
- Reclaim safely preemptable resources
- Roll back to checkpoint
- Termination/rollback: both recovery methods
- Recovery-choice questions require criterion
- Repeated victim selection: starvation
👁 Full explanation
Detection asks whether the current state is deadlocked. Recovery can terminate selected processes or reclaim safely preemptable resources and roll affected work back to a checkpoint. Termination and rollback are both possible recovery tools; choose according to the resource and process conditions. Repeatedly sacrificing the same victim can cause starvation. - Detection timing and intentional ignoring
- Every-request versus periodic checking
- Overhead versus detection-delay tradeoff
- No universal best interval
- Ostrich: ignore sufficiently rare problem
- Real systems: selected prevention/detection
- Deadlock acceptance: intentional ignoring possible
- Detection graph versus avoidance safety graph
- Scheduling queue: different problem
👁 Full explanation
Checking on every request versus periodically trades overhead against detection delay; no universal best interval exists. Ignoring a sufficiently rare problem is sometimes called the ostrich policy, but real systems still prevent or detect selected deadlocks. “Deadlock acceptance” can mean intentional ignoring, not necessarily an invalid approach. A detection graph, avoidance safety graph and ordinary scheduling queue solve different problems.
7 related practice questions
Blueprint: OS3 · Note references: OS-N, OS-DEAD
- Detection and recovery
OS27
Address binding, loading and linking
- Address-binding stages
- Compile-time: known placement, absolute addresses
- Load-time: relocation on placement
- Execution-time: runtime translation
- Movement requires hardware support
- Logical/virtual: process-generated addresses
- Physical: RAM addresses
- MMU: logical→physical
- Reverse-direction bank stem: malformed
👁 Full explanation
Compile-time binding uses absolute addresses if placement is known. Load-time binding relocates when placed into memory. Execution-time binding translates while running and permits movement with hardware support. Logical/virtual addresses are generated for a process; physical addresses select RAM. An MMU translates logical addresses to physical addresses, not the reverse. - Loading, linking and swapping
- Dynamic loading: routine on demand
- Dynamic linking: external references load/runtime
- Suitable library pages shared
- Static linking: executable code copies
- Traditional swapping: whole process→backing store
- Paging: individual pages
- Context switch: execution-state change
👁 Full explanation
Dynamic loading brings a routine in when needed. Dynamic linking resolves references to external libraries at load/runtime, allowing suitable library code pages to be shared; static linking copies selected code into the executable. Swapping traditionally moves a whole process to backing store; paging moves individual pages. These differ from a context switch, which primarily changes execution state.
6 related practice questions
Note references: OS-M, OS-N
- Address-binding stages
OS28
Contiguous allocation and fit policies
- Contiguous base/limit translation
- One continuous process region
- Base: process physical start
- Limit: permitted length
- Check 0≤logical_offset<limit
- Physical=base+offset
- Relocation register ≠ normally OS base
- Last-valid-offset limit: changed inequality
- Specify limit convention
👁 Full explanation
A contiguous allocation gives a process one continuous region. In the standard base/limit model, base is that process’s physical starting address and limit is its permitted length. Check 0≤logical_offset<limit, then physical=base+offset. The relocation register does not normally hold the OS base. If limit instead means last valid offset, the inequality changes; specify the convention. - Hole-selection policies
- First-fit: first adequate hole
- Next-fit: resume previous search
- Best-fit: smallest adequate hole
- Worst-fit: largest hole
- Search time versus future utilization
- No universally optimal policy
- Binary-fit: not standard listed policy
👁 Full explanation
First-fit selects the first adequate hole; next-fit continues from the previous search position; best-fit selects the smallest adequate hole; worst-fit selects the largest. No policy universally optimizes both search time and future storage utilization. Binary-fit is not one of these standard names. - Worked example Fit and boundary examples
- Holes 100,500,200,300; request 180
- First-fit=500; best-fit=200; worst-fit=500
- Base=4000; length=100
- Offset 99→4099
- Offset 100: trap
👁 Full explanation
Worked microexampleHoles 100,500,200,300 and request 180: first-fit selects 500, best-fit 200, worst-fit 500. For base=4000,length=100, logical offset 99 maps to 4099; offset 100 traps.
6 related practice questions
Note references: OS-M, OS-N
- Contiguous base/limit translation
OS29
Internal and external fragmentation
- Fragmentation and consolidation
- Internal: unused allocated-unit space
- External: free total split inadequately
- Contiguous request cannot fit holes
- Coalescing: adjacent free holes joined
- Compaction: move allocated regions
- Consolidate free space
- Compaction requires relocation support
👁 Full explanation
Internal fragmentation is unused space inside an allocated unit. External fragmentation is sufficient total free space split into holes that cannot satisfy a required contiguous allocation. Coalescing joins adjacent free holes; compaction moves allocated regions to consolidate free space and requires relocation support. - Allocation-model fragmentation limits
- Fixed-frame paging: no external frame fragmentation
- Final page: possible internal waste
- Variable segmentation/contiguous partitions: external fragmentation
- Paging OS ≠ every allocator fragmentation-free
- Track units; round allocations upward
- Requests need not fill blocks
👁 Full explanation
Basic fixed-frame paging avoids external fragmentation of page-frame allocation but can waste the final page internally. Variable-length segmentation/contiguous partitions can fragment externally. This is not a statement that every allocator inside a paging OS is fragmentation-free. Track units and round allocations up rather than assuming all requests exactly fill blocks. - Worked example Fragmentation examples
- 10 KiB object; 4 KiB pages
- ceil(10/4)=3 pages
- Allocate 12 KiB; waste 2 KiB
- Two 3 KiB holes: total 6 KiB
- Contiguous 5 KiB request fails
👁 Full explanation
Worked microexampleA 10 KiB object in 4 KiB pages needs ceil(10/4)=3 pages: 12 KiB allocated and 2 KiB unused. Two 3 KiB free holes cannot serve one contiguous 5 KiB request although 6 KiB is free.
2 related practice questions
Note references: OS-M, OS-N
- Fragmentation and consolidation
OS30
Paging, page tables and TLB
- Paging translation
- Equal fixed page/frame size P
- Page=floor(v/P)
- Offset=v mod P
- Page table: frame plus protection/status
- Physical=frame×P+offset
- TLB: translation cache
- TLB miss: possible table walk
- TLB miss ≠ nonresident page
👁 Full explanation
Pages and physical frames have equal fixed size P. Divide virtual address v into page=floor(v/P) and offset=v mod P. The page table maps a page to a frame and protection/status flags. Physical address=frame×P+offset. A TLB caches translations; a TLB miss may require a table walk while the page is already resident. - Page-table sizing and validation
- Virtual-page count and entry size
- Table size ≠ physical RAM alone
- Check protection and present bits
- Table lookup ≠ CPU scheduling
👁 Full explanation
Table size depends on the number of virtual pages and entry size, not just physical RAM. Protection and present bits must be checked before access. A page-table lookup is not a CPU scheduling operation. - Worked example Paging calculation example
- P=1024; v=2053
- Page=2; offset=5
- Frame=7 → physical=7173
- 16-bit virtual space; 1 KiB pages
- 64 virtual pages
- Page number: 6 bits
👁 Full explanation
Worked microexamplePage size 1024, v=2053: page 2, offset 5. If page 2 maps to frame 7, physical address=7173. With 16-bit virtual addresses and 1 KiB pages, there are 64 virtual pages and a 6-bit page number.
4 related practice questions
Note references: OS-M, OS-N
- Paging translation
OS31
Segmentation versus paging
- Segment translation
- Variable logical units: code/stack/arrays
- Segment table: base/limit/permissions
- Address pair: segment,offset
- Validate segment and bound
- Physical=base+offset
- Out-of-range offset: trap
- No spill into next segment
👁 Full explanation
Segmentation uses logical variable-length units such as code, stack and arrays. A segment-table entry provides base, limit and permissions. For (segment,offset), validate the segment and check the bound, then add base+offset. An out-of-range offset traps; it must not spill into the next segment. - Basic paging/segmentation contrasts
- Paging: fixed units, page tables
- Paging: internal waste
- Segmentation: variable units, segment tables
- Segmentation: external fragmentation
- Segments reflect program structure
- Ordinary pages: largely application-transparent
- A/B/C contrasts all true
- Multiple true contrasts: no unique choice
👁 Full explanation
Under the basic models, paging uses fixed units/page tables and can waste space internally; segmentation uses variable logical units/segment tables and can fragment externally. Segments reflect program structure whereas ordinary pages are largely transparent to applications. Apply all three contrasts when comparing paging and segmentation. - Worked example Segment boundary example
- Segment 1: base=8000, length=500
- Offset 120→8120
- Offset 500: invalid
- Length-based limit convention
👁 Full explanation
Worked microexampleSegment 1 has base 8000 and length 500. Offset 120 maps to 8120; offset 500 is invalid under the length convention.
4 related practice questions
Note references: OS-M, OS-N
- Segment translation
OS32
Virtual memory and page faults
- Virtual-memory purpose and fault sequence
- Translated, protected address spaces
- Nonresident portions: storage backing
- No added physical RAM
- Capacity constraints remain
- Demand paging: load on access
- Nonresident access: trap
- Validate mapping/permissions
- Find frame or select victim
- Save dirty victim if needed
- Obtain contents; update mapping; restart
👁 Full explanation
Virtual memory provides translated, protected address spaces and allows nonresident portions of a program to be backed by storage. It does not add physical RAM or remove all capacity constraints. Demand paging brings a page in when accessed. On a nonresident access: trap, validate mapping/permissions, find a frame or choose a victim, save a dirty victim if needed, obtain contents, update mapping and restart. - Fault exceptions and thrashing
- Page fault ≠ mandatory disk read
- Zero-filled pages; shared mappings
- Illegal access: reject, not load
- Excess active-page demand: thrashing
- Repeated faults dominate computation
- Reduce active load
- Add suitable memory
👁 Full explanation
Not every fault reads a disk: some allocate zero-filled pages or establish shared mappings. An illegal access is rejected, not automatically loaded. Excessive active-page demand can cause thrashing: repeated faults dominate useful computation. Reducing active load or adding suitable memory can help. - Worked example Page-fault cost example
- Access: 100 ns
- Additional page-in: 5 ms
- Fault probability: 10^−4
- Added delay≈500 ns/access
- Rare long delays matter
👁 Full explanation
Worked microexampleIf access costs 100 ns and an additional page-in costs 5 ms, a fault probability of 10^−4 adds roughly 500 ns per access; rare long delays still matter.
5 related practice questions
Note references: OS-M, OS-N
- Virtual-memory purpose and fault sequence
OS33
Page-replacement traces
- Replacement policy rules
- Victim needed: no suitable free frame
- FIFO: earliest loaded page
- FIFO hit: insertion time unchanged
- LRU: least recently accessed
- LRU recency: every access
- Optimal: farthest future use
- Optimal: offline lower bound
- LFU: reference counts
- LFU tie/aging rules required
👁 Full explanation
Replacement chooses a victim when no suitable free frame is available. FIFO evicts the earliest loaded page; a hit does not refresh insertion time. LRU evicts the least recently accessed and updates recency on every access. Optimal evicts the page used farthest in the future, serving as an offline lower bound. LFU uses reference counts and needs tie/aging rules. - Replacement trace method and properties
- One row per reference
- Identify hits before eviction
- Initial loads count as faults
- Belady’s anomaly: more frames, more faults
- FIFO may exhibit anomaly
- LRU/optimal: stack property
- Page buffering: useful free/modified pages retained
- Reduced effective fault cost
👁 Full explanation
Write a row per reference, identify hits before evicting, and count initial loads as faults. FIFO may exhibit Belady’s anomaly when more frames cause more faults; LRU and optimal have the stack property. Page buffering retains useful free/modified pages to reduce effective fault cost. - Worked example FIFO versus LRU example
- Three empty frames
- References: 1,2,3,1,4,1
- FIFO: faults 1,2,3,4,last 1
- FIFO total: five faults
- LRU: refresh 1 on hit
- Evict 2 for 4
- Last 1: hit
- LRU total: four faults
👁 Full explanation
Worked microexampleThree empty frames, references 1,2,3,1,4,1: FIFO faults at 1,2,3,4 and the last 1: five faults. LRU updates page 1 on its hit, evicts 2 for 4, and ends with a hit on 1: four faults.
1 related practice question
Note references: OS-M, OS-N
- Replacement policy rules
OS34
Controllers, drivers and I/O services
- I/O hardware and software roles
- Controller: hardware status/control/data registers
- Driver: OS requests→device operations
- Device independence and uniform naming
- Hide brand-specific details
- Error handling: supported reports/retries
- Polling: repeated readiness checks
- Interrupts: CPU attention requests
- DMA: setup then block transfer
- No per-byte CPU work
👁 Full explanation
A controller is device hardware exposing status, control and data registers. A driver converts OS requests into device-specific operations. Device independence and uniform naming hide brand-specific details; error handling reports/retries supported failures. Polling checks readiness repeatedly; interrupts request CPU attention; DMA transfers blocks after setup without CPU work for every byte. - I/O responsibility boundaries
- Kernel/driver answer: abstraction scope required
- Plug-and-play: compatible hardware discovery/configuration
- Driver may still be needed
- Input/output/storage/NIC: managed hardware
- Accounts: identities
- Paper/network errors: report/handle
- Total power loss: hardware support required
- OS software alone insufficient
👁 Full explanation
Both the kernel and drivers participate in I/O; specify the abstraction level being discussed. Plug-and-play discovers/configures compatible new hardware but may still require a driver. Input/output/storage/NIC devices are OS-managed hardware; user accounts are identities. Printer-paper and network errors can be handled/reported, but continued operation during total power loss requires hardware support, not OS software alone.
9 related practice questions
Note references: OS-M, OS-N
- I/O hardware and software roles
OS35
Buffering, caching, spooling and clocks
- Buffering versus caching versus spooling
- Buffer: temporary in-transit data
- Absorb speed/transfer-size differences
- Cache: copies for faster reuse
- Spool: queued device jobs
- Printer jobs: usually disk-backed
- Producers avoid continuous device ownership
- Combined implementation, different purposes
👁 Full explanation
Buffering temporarily holds data in transit to absorb speed/transfer-size differences. Caching retains copies to accelerate reuse. Spooling queues jobs for a device such as a printer, usually on disk, so producers need not own it throughout job creation. These have different purposes even if one implementation combines them. - Timers, monitoring and disk responsibilities
- Timer: timekeeping and timeouts
- Accounting and preemptive scheduling
- Monitor: CPU/memory/storage/network usage
- Measurement ≠ resource creation
- Disk initialization/filesystem creation: OS/tools
- Boot begins: firmware
- Bad-sector remapping: drive firmware possible
- OS-all-disk-functions claim: scope boundaries
👁 Full explanation
The clock/timer supports timekeeping, timeouts, accounting and preemptive scheduling. A system monitor reports CPU, memory, storage and network usage; it measures rather than directly creating more resources. Disk initialization/filesystem creation is OS/tool work, firmware begins boot, and drive firmware may remap bad sectors. A broad “OS does all disk functions” claim needs these responsibility boundaries.
4 related practice questions
Note references: OS-M, OS-N
- Buffering versus caching versus spooling
OS36
Files, descriptors and operations
- File content, metadata and handles
- Metadata: name, size, owner
- Permissions and timestamps
- open: obtain reference
- read/write: byte transfer
- seek: offset change
- close: release reference
- truncate: size change
- unlink: name removal
- Descriptor: process-local integer handle
- Open-file state: offset/access mode
- Descriptor ≠ offset
👁 Full explanation
A file has content and metadata such as name, size, owner, permissions and timestamps. open obtains an open-file reference, read/write transfer bytes, seek changes an offset, close releases a reference, truncate changes size and unlink removes a name. A file descriptor is a process-local integer handle; the associated open-file state contains the current offset and access mode. Descriptor and offset are not synonyms. - Read semantics and filesystem formats
- Seekable read: offset advances
- Short reads possible
- Zero read: normally EOF
- Sockets: ordinary read/write supported
- socket/connect/send: socket operations
- read ≠ uniquely non-network call
- FAT32/NTFS/ext4: filesystem formats
- HTTP: application communication protocol
👁 Full explanation
Read advances the offset on seekable files and may return fewer bytes than requested; zero normally indicates end-of-file. Sockets also support ordinary read/write, alongside socket/connect/send operations, so read is not uniquely “not a network call.” FAT32, NTFS and ext4 are filesystem formats; HTTP is an application communication protocol.
9 related practice questions
Note references: OS-M, OS-N, OS-READ
- File content, metadata and handles
OS37
Directories, mounts and links
- Directory organizations
- Single-level: unique names, one namespace
- Two-level: users separated
- Tree: nested directories
- Absolute and relative paths
- Links: shared graphs
- Modern systems: commonly hierarchical
- Feature label ≠ excluding simpler arrangements
👁 Full explanation
A single-level directory requires unique names in one namespace. Two-level directories separate users. A tree allows nested directories and absolute/relative paths; links can create shared graphs. Modern general-purpose systems commonly present hierarchical namespaces, but a feature name alone does not prove that every system excludes simpler arrangements. - Links and filesystem attachment
- Hard link: same file, another name
- Usually within one filesystem
- Symlink: stored pathname
- Cross-filesystem targets; dangling links possible
- Unlink one name ≠ content deletion
- Remaining names/open references retain content
- Mount: attach filesystem at mount point
- Mount ≠ format
- NFS: remote filesystem access
- FTP: transfer, not itself mounting
👁 Full explanation
A hard link is another name for the same underlying file object, usually within one filesystem; a symbolic link stores a pathname and can point across filesystems or become dangling. Removing one hard link does not erase content while other names/open references retain it. Mounting attaches a filesystem at a mount point; it does not format the device. NFS provides remote filesystem access; FTP transfers files rather than itself mounting a local filesystem.
7 related practice questions
Note references: OS-M, OS-N
- Directory organizations
OS38
File-block allocation methods
- Contiguous, extent and linked allocation
- Contiguous: consecutive blocks
- Logical block i→start+i
- Direct access
- Growth and external fragmentation problems
- Extents: several contiguous runs
- Linked: block chains
- Growth without whole-file contiguous reservation
- Block i: traverse preceding links
- FAT: chains in table
- Cached FAT ≠ direct arithmetic mapping
👁 Full explanation
Contiguous allocation uses consecutive blocks; logical block i is start+i and supports direct access, but growth and external fragmentation are problems. Extents allow several contiguous runs. Linked allocation chains blocks and supports growth without reserving a complete contiguous file; locating block i requires traversing preceding links. FAT stores chains in a table; caching that table does not change the chain into a direct arithmetic mapping. - Indexed allocation and inode lookup
- Per-file pointer array/tree
- Direct lookup; metadata overhead
- Unix inode: direct and indirect pointers
- Pointer size and block size
- Index capacity
- Metadata-read caching assumptions
👁 Full explanation
Indexed allocation uses a per-file array/tree of block pointers and supports direct lookup with metadata overhead. A Unix inode can combine direct pointers with indirect levels. Check pointer size, block size, index capacity and whether metadata reads are cached. - Worked example Index-capacity example
- 1024-byte index; 4-byte pointers
- 1024/4=256 block addresses
- Data blocks: 1024 bytes
- One level: 256 KiB data
- Exclude metadata/reserved entries
👁 Full explanation
Worked microexampleA 1024-byte index block with 4-byte pointers holds 256 block addresses. With 1024-byte data blocks, one such index level addresses 256 KiB of file data, excluding metadata and any reserved entries.
4 related practice questions
Note references: OS-M, OS-N
- Contiguous, extent and linked allocation
OS39
Protection, authentication and threats
- Identity and access control
- Authentication: verify identity
- Authorization: permitted operations
- ACL: principals and rights
- Owner/group/other: simpler bit model
- Owner full access: not universal
- Everyone read: not universal
- Read/write/execute/append/delete: distinct rights
- Filesystem-specific permission rules
👁 Full explanation
Authentication verifies identity; authorization checks permitted operations. An ACL lists principals and rights; owner/group/other bits are a simpler policy model, not universal defaults granting all owners full access or everyone read. Read, write, execute, append and delete are different rights, with filesystem-specific rules. - Security controls, threats and interfaces
- Least privilege: limited damage
- Password hashing: no stored plaintext
- One-time passwords: expire after use
- Encryption: confidentiality with correct keys
- Encryption ≠ automatic integrity
- Trojan: useful-software disguise
- Worm: independent propagation
- Virus: attached host
- DoS: availability harm
- Cryptography/authentication/firewalls: product-dependent support/configuration
- Interfaces: CLI, GUI, speech/natural language, VR
- Interface list: not closed
👁 Full explanation
Least privilege limits damage. Password hashing verifies secrets without storing plaintext; one-time passwords expire after use. Encryption protects confidentiality under correct key use but does not automatically provide integrity. Trojans masquerade as useful software, worms propagate independently and viruses attach to hosts; denial of service harms availability. Modern OS families can support cryptography, authentication and firewalls, but support/configuration depends on product. CLI, GUI, speech/natural language and VR are possible interfaces, not a closed list excluding the last two.
4 related practice questions
Note references: OS-M, OS-N
- Identity and access control
OS40
Linux, Android and history limits
- Kernel, distributions and product licensing
- Linux: Unix-compatible, written from scratch
- Linus Torvalds
- Distribution: kernel/userland/libraries/tools
- Android base kernel: Linux
- Framework/applications: higher layers
- AOSP: open source
- Devices: proprietary apps/services possible
- Windows/macOS: proprietary products
- macOS: open-source components too
- Both proprietary options: ambiguous answer
- Microsoft Office: application suite
👁 Full explanation
Linux is a Unix-compatible kernel written from scratch by Linus Torvalds; a distribution combines it with userland, libraries and tools. Android’s base kernel layer is Linux; its framework and applications are higher layers. AOSP is open source, while a shipped device can include proprietary applications/services. Windows and macOS are both proprietary products, although macOS contains open-source components, so “which is not open source?” offering both is ambiguous. Microsoft Office is an application suite. - Product and historical-claim limits
- Windows: Microsoft, after MS-DOS desktop era
- Solaris: Sun origin
- First widely used: definition/evidence required
- First multitasking: definition/evidence required
- UNIX ≠ first ever multitasking
- Generation/function pairing: historical evidence
- Mobile majority: population/date required
- Architecture facts ≠ market-share proof
👁 Full explanation
Windows is the Microsoft family commonly described as succeeding the MS-DOS desktop era; Solaris originated at Sun. “First widely used OS,” “first multitasking OS,” and generation/function pairings require a definition and historical evidence; UNIX was not the first system ever to multitask. “Most mobile devices” needs a population and date; architecture facts do not prove market share.
10 related practice questions
Note references: OS-M, OS-N, OS-AOSP, OS-LINUX, OS-SOLARIS
- Kernel, distributions and product licensing
OS41
Repairing ambiguous bank questions
- Missing or multiple answer concepts
- Requested concept omitted
- Several valid examples: reject uniqueness
- System call: kernel-service request
- Process: executing program
- CPU/memory/I/O: multiple managers
- Device/process/file/security choices: missing umbrella
- Virtual memory: isolation, translated space
- Virtual memory ≠ unlimited memory
👁 Full explanation
Check whether the stated conditions support one answer or several before selecting a response. A general system-call purpose should say requesting a kernel service; a process purpose should say executing a program. CPU, memory and I/O management span multiple managers; device, process, file and security management describe particular responsibilities. Virtual memory provides isolation and translated space; it does not remove every memory constraint. - Minimal wording repairs
- Specify OS versus API
- Scheduling variant
- Arrivals and quantum
- Exact process/resource graph
- Base-limit convention
- Comparison scope
- Marked answer ≠ evidence
- Missing edges: unrecoverable from theory
👁 Full explanation
Specify the OS/API, scheduling variant, arrivals/quantum, exact graph, base-limit convention or scope of comparison needed to answer the question. Support the answer with the relevant operating-system rule and stated assumptions. A process/resource graph question requires its actual edges; theory alone cannot reconstruct a missing diagram.
9 related practice questions
Note references: OS-M, OS-N
- Missing or multiple answer concepts
No matching topics. Clear the search or change the filter.
Blueprint learning outcomes
- OS1 · Explain the objectives and functions of modern operating systems
OS01, OS02, OS03, OS04 - OS2 · Describe the functions of a contemporary operating system with respect to convenience, efficiency, and the ability to evolve.
OS01, OS02, OS03, OS04 - OS3 · Explain conditions that lead to deadlock
OS22, OS23, OS24, OS25, OS26 - OS4 · Compare and contrast the common algorithms used for both preemptive and non-preemptive scheduling of tasks in operating systems, such as priority, performance comparison, and fair-share schemes.
OS13, OS14, OS15, OS16, OS17, OS18, OS19, OS20, OS21