OS

What is a Program Counter?|A CPU register that holds the memory address of the next instruction to be executed by the processor. As each instruction completes, the PC automatically updates to point to the subsequent instruction. During a context switch, the PC value must be saved so the process can resume exactly where it left off.

What is a Stack Pointer?|A CPU register that points to the top of the current process's stack in memory. The stack is essential for managing function calls, storing local variables, passing parameters, and saving return addresses. Each process has its own stack, and the stack pointer must be saved and restored during context switches.

What is PSW/FLAGS register?|The Program Status Word (or FLAGS register) contains critical status information about the processor's current state. This includes condition codes from arithmetic and logical operations (zero flag, carry flag, overflow flag, sign flag), and system state bits that control processor modes and interrupt handling.

What is Pseudoparallelism?|The illusion that multiple processes execute simultaneously on a single CPU. The OS rapidly switches between processes using context switching, giving each process a time slice. To users and applications, it appears as though all processes run concurrently, even though only one process actually occupies the CPU at any given moment.

What is Multiprogramming?|A technique where multiple programs reside in memory simultaneously, and the CPU switches between them. The goal is to maximize CPU utilization by ensuring the processor always has work to do. When one process becomes blocked (waiting for I/O), the CPU can immediately switch to another ready process.

What is Copy-on-Write?|An optimization technique where a parent and child process initially share the same physical memory pages after fork(). Pages are marked as copy-on-write in page tables. When either process attempts to write to a shared page, a page fault occurs, the OS creates a private copy of that page for the writing process, saving significant time and memory.

What is a Context Switch?|The process where the CPU stops running one process, saves its current state (registers, program counter, stack pointer, PSW), and loads the saved state of another process. This allows multiple processes to share the CPU effectively by rapidly switching between them.

What is a Critical Region?|Sections of code that contain access to shared resources that are shared across multiple processes. These regions must be protected to prevent race conditions. When one process executes in a critical region, no other process should simultaneously execute in a critical region accessing the same shared resource.

What is Mutual Exclusion?|The fundamental property that prevents multiple processes from simultaneously executing critical regions that access the same shared resource. It ensures that when one process is in a critical region, all other processes wanting to access that critical region must wait, preventing race conditions and maintaining data consistency.

What are Race Conditions?|A situation where the system's behavior depends on the relative timing or interleaving of process execution. The same program with the same inputs might produce different outputs depending on the unpredictable order in which the scheduler runs processes. Race conditions indicate insufficient synchronization around shared resources.

What is a Spin Lock?|A synchronization mechanism where a process wanting to enter a critical region continuously checks (spins on) a lock variable in a tight loop. When the lock becomes available, the process acquires it and enters the critical region. Spin locks waste CPU cycles during spinning but are appropriate for very short critical regions.

What is a Semaphore?|A synchronization primitive that uses a counter to control access to shared resources. Unlike simple locks, semaphores maintain a count representing resource availability. Semaphores solve the busy-waiting problem of spin locks by blocking processes when resources are unavailable, allowing them to be scheduled out.

What is a Thread?|The smallest unit of execution within a process, representing a sequence of instructions that can run independently. Multiple threads within the same process share the process's memory space (code, global variables, heap) but each thread maintains its own stack, program counter, and register set.

What is a Process?|The operating system's abstraction of a running program. It encompasses the executable program code, current values of variables (data), allocated resources (open files, network connections), and execution state (register values, program counter, stack pointer). Each process operates in its own protected memory space.

What is the Kernel?|The core component of an operating system that operates with the highest privileges and maintains complete control over system resources. It serves as the intermediary between hardware and user applications, providing abstraction layers that hide hardware complexity. The kernel runs in protected memory space (kernel mode).

What are the main jobs of the Kernel?|Process management, memory management, device management, file system management, CPU scheduling, system call handling, and inter-process communication (IPC). The kernel creates and terminates processes, allocates memory, manages I/O operations, implements file systems, decides which process runs, and facilitates process communication.

What data structures does the Xinu Kernel use to track processes?|An array-based process table called proctab where array indexes correspond to process IDs, and a ready list data structure to track processes ready to run. The proctab allows O(1) access to any process's information given its PID.

What is the process table (proctab) in Xinu?|An array that contains process entries, where each index represents a process ID and contains the process entry structure for that process. The null process always occupies index 0 (NULLPROC). This design allows constant-time access to process information.

What fields are in a process entry structure in Xinu?|Name (human-readable identifier), priority (scheduling precedence), parent's PID (tracks process hierarchy), and state (current execution state like READY, RUNNING, BLOCKED). Additional fields may include stack pointer, memory protection registers, CPU time accounting, and pointers to message queues.

What are the two implementations of threads?|Threads in kernel space (managed by the OS kernel - kernel maintains thread tables, performs thread scheduling; slower but can utilize multiple CPUs) and threads in user space (managed by user-level thread libraries - extremely fast to create/switch but entire process blocks if one thread blocks; cannot use multiple CPUs).

How do you access the null process entry in Xinu?|proctab[NULLPROC], proctab[0], or proctab[currpid] (only if the currently running process is the null process). These are all equivalent ways to access the process entry for the null process which always has PID 0.

How do you retrieve the currently running process entry in Xinu?|proctab[currpid] where currpid is a global variable maintained by the kernel that holds the PID of the process currently executing on the CPU. This allows O(1) access to the running process's information.

What does the READY state mean?|A process has all the information needed to execute on the CPU and is waiting to be selected by the scheduler. READY processes wait in the ready list. The only thing preventing execution is that another process currently occupies the CPU.

What does the BLOCKED state mean?|The process does not have all the information it needs or is waiting for some external event. Common reasons include waiting for I/O completion, waiting on a semaphore, waiting for a message, or sleeping for a specified time. BLOCKED processes do not occupy CPU time and are not considered by the scheduler.

What does the RUNNING state mean?|The process currently has access to the CPU and is actively executing instructions. Only one process can be RUNNING on a single-core CPU at any given time. The RUNNING process's state is reflected in the CPU's registers.

What is the Ready List in Xinu?|A data structure that contains all processes in the system that have their state set to READY and would like to run. Typically implemented as a priority queue where processes are ordered by priority. The scheduler selects the highest-priority process from this list.

When might a process transition FROM the RUNNING state? (Name 3 reasons)|1) A higher priority process enters the system and requires the CPU (preemption). 2) The process becomes blocked as it needs more information (voluntary blocking). 3) The process has run for a time period that exceeds its maximum run time/quantum (time slice expiration).

What are the required steps during a Context Switch?|1) Push the current process's register contents onto that process's stack. 2) Update the current process's entry in the process table (save stack pointer, update state). 3) Select next process via scheduler. 4) Load new process state from process table. 5) Repopulate CPU registers by popping from new process's stack. 6) Jump to instruction pointed to by the new program counter.

What problems can badly timed context switches cause?|Incorrect output, race conditions, damaged variable contents (if the shared resource is a variable), and undesirable execution sequences when processes use shared resources without proper synchronization. This occurs when context switches happen while processes access shared resources.

What is an Atomic Action?|An operation that executes as a single, indivisible unit, meaning it completes entirely or not at all, and cannot be interrupted by other processes. From the perspective of other processes, atomic actions appear to occur instantaneously. Essential for implementing synchronization primitives and ensuring data consistency.

What does the fork() function do?|Creates a nearly identical copy of the calling process (parent). The newly created process is the child. After fork() completes, two processes exist, both continuing execution from the instruction immediately following the fork() call. Both have the same code but receive different return values.

What are the key differences between parent and child after fork()?|Process ID (PID) - child gets a new unique PID; Parent Process ID (PPID) - child's PPID is set to parent's PID; Return value from fork(); Resource accounting (child starts fresh); Pending signals (child typically doesn't inherit them).

What does fork() return in the child process?|0 - This return value indicates the code is executing in the newly created child process, allowing the child to identify itself and potentially execute different code from the parent.

What does fork() return in the parent process?|A positive integer - the PID of the newly created child process. This allows the parent to know the child's PID for future communication or control operations.

What does fork() return if it fails?|−1 - Indicates process creation failed. This might occur due to system resource limits (maximum processes reached, insufficient memory, permission issues, etc.).

What does a semaphore entry contain in Xinu?|A count (integer value representing resource availability - positive means resources available, negative magnitude often indicates number of waiting processes) and a queue ID (identifier for retrieving the semaphore's queue of waiting processes).

What does the wait operation (wait.c) do on a semaphore?|Decrements the semaphore's count. If the resulting count is non-negative, the process continues execution (resource was available). If the count becomes negative, no resources are available, so the process is added to the semaphore's waiting queue and blocked until another process signals the semaphore.

What does the signal operation (signal.c) do on a semaphore?|Increments the semaphore's count. If the resulting count is ≤ 0, processes were waiting, so the kernel removes one waiting process from the semaphore's queue and transitions it to READY state. If the count becomes positive, no processes were waiting and the resource is now available.

What does receive.c implement in Xinu?|The receive() function that allows a process to receive a message. If a message is already waiting in the process's message buffer, it returns immediately. If no message is available, the process blocks until a message arrives, preventing CPU waste from polling.

What does recvclr.c implement in Xinu?|Non-blocking message reception with clearing. If a message is available, it returns the message immediately and clears the buffer. If no message is available, it returns immediately without blocking (with a special value) and ensures the message buffer is cleared.

What does recvtime.c implement in Xinu?|Message reception with timeout. The calling process specifies a maximum time to wait. If a message arrives within the timeout, it returns immediately. If timeout expires before a message arrives, it returns (typically with error code) without blocking indefinitely, preventing permanent blocking.

What are invariants in an operating system?|Crucial conditions or properties that must always hold true during system operation. They represent fundamental consistency requirements that, if violated, indicate a serious kernel bug. Essential for reasoning about system correctness and verified during debugging and testing.

What is the sleep queue invariant in Xinu?|A process is on the sleep queue if and only if its state is set to blocked with sleep-related status (PR_SLEEP or PR_RECTIM). This bidirectional relationship means every process on the sleep queue must have sleep state, and every process with sleep state must appear on the sleep queue.

What is the currpid invariant in Xinu?|A process's PID is stored in currpid if and only if its state is set to running (PR_CURR). At any given time, exactly one process (on single-core) should have running state, and currpid must point to that process's entry in the process table.

What is the ready list invariant in Xinu?|A process is on the ready list if and only if its state is set to ready (PR_READY). Every ready process must appear on the ready list (so scheduler can find it), and every process on the ready list must have ready state.

What must happen when killing a sleeping process in Xinu?|The terminated sleeping process must be removed from the sleep queue before finalizing termination. Otherwise, the sleep queue will contain a pointer to a freed process entry, and when the sleep timer expires, the kernel might attempt to wake a non-existent or wrong process.

What must happen when killing a ready process in Xinu?|The terminated ready process must be removed from the ready list before reclaiming resources. Otherwise, the scheduler might select a terminated process for execution, attempting to restore the state of a freed process entry, likely causing a crash.

What must happen when killing a waiting process in Xinu?|The terminated waiting process must be removed from the semaphore's waiting queue AND the semaphore count must be incremented. Incrementing compensates for the fact that this process will never complete its wait operation and signal the semaphore, preventing potential deadlock.

What mechanisms allow processes to communicate in Xinu?|Message passing (via receive.c, recvclr.c, recvtime.c for direct data transfer between processes) and semaphores (via wait.c, signal.c for coordination and mutual exclusion when accessing shared resources). These can be combined for complex communication patterns.

Describe the complete lifecycle of a process from creation to termination.|Process created (via fork or create) → Enters READY state and added to ready list → Scheduler selects it → Context switch to RUNNING state → May transition to BLOCKED (waiting for resource) → Returns to READY when resource available → May be preempted back to READY by higher priority process → May exhaust quantum and return to READY → Eventually terminates → Removed from all data structures → Resources released → Process entry freed.

How does Copy-on-Write improve fork() efficiency?|Instead of immediately copying all parent memory pages (expensive), parent and child initially share pages marked as copy-on-write. Both can read shared pages. Only when either writes to a page does a page fault occur, triggering the OS to create a private copy for the writing process. Only modified pages are copied, saving time and memory, especially important since many children immediately exec a new program.

Why are badly timed context switches dangerous?|If a context switch occurs while a process is in the middle of modifying a shared data structure, another process might observe the data in an inconsistent state (partially modified). This leads to race conditions where output depends on unpredictable timing, and shared variables can become corrupted when multiple processes interleave read-modify-write operations without synchronization.

Compare spin locks vs semaphores for synchronization.|Spin locks: Process continuously checks lock variable in loop (wastes CPU cycles); Simple to implement; Good for very short critical regions or multiprocessor systems. Semaphores: Process blocks and is descheduled when resource unavailable (no CPU waste); More complex; Good for longer waits or when resources are frequently contended; Uses a count to track resources and maintains queue of waiting processes.

Explain the relationship between process states and kernel data structures.|The kernel maintains strict consistency between a process's state field and its presence in data structures (captured by invariants): READY processes must be on ready list, BLOCKED processes must be on appropriate waiting queue, RUNNING process must be referenced by currpid. During state transitions, kernel must atomically update both state field and data structure membership.

What happens during preemption by a higher priority process?|1) Higher-priority process becomes READY (enters system or unblocks). 2) Scheduler detects higher priority process. 3) Context switch initiated. 4) Current RUNNING process's state saved. 5) Current process transitioned to READY and added to ready list. 6) Higher-priority process's state loaded. 7) Higher-priority process begins execution in RUNNING state. Ensures important processes receive CPU time promptly.

Why must process termination (kill) inspect process state?|Different states require different cleanup: SLEEPING processes must be removed from sleep queue; READY processes must be removed from ready list; WAITING processes must be removed from semaphore queue AND semaphore must be incremented. Only after proper state-specific cleanup can the process entry be freed for reuse. Skipping cleanup causes data structure corruption.

How do kernel-level and user-level threads differ in blocking behavior?|Kernel-level threads: When one thread blocks (e.g., I/O), kernel can schedule another thread from same or different process. Kernel sees individual threads. User-level threads: When one thread makes blocking system call, entire process blocks since kernel only sees the process, not individual threads. All threads in that process stop executing until system call completes.

Explain how semaphores prevent the busy-waiting problem.|Spin locks waste CPU by continuously checking lock variable. Semaphores avoid this: when a process calls wait() and resource is unavailable (count becomes negative), the process is added to semaphore's waiting queue and BLOCKED. The process is descheduled and doesn't consume CPU. When another process calls signal(), a waiting process is moved to READY state to be scheduled later.

What is the purpose of the quantum in time-sharing systems?|The quantum (time slice) is the maximum time a process can run before being preempted, even if it could continue executing. Prevents any single process from monopolizing the CPU. When quantum expires, RUNNING process transitions to READY and is placed at end of its priority level in ready list. Ensures fair CPU distribution among processes of equal priority and maintains system responsiveness.

How does priority-based scheduling work in Xinu?|The ready list is organized by priority (typically a priority queue). Scheduler selects the highest-priority READY process for execution. Higher-priority processes run before lower-priority ones, even if lower-priority processes have been waiting longer. Ensures critical system tasks and important processes receive CPU time promptly, though must balance against fairness to prevent starvation.

Describe the complete context switch register operations.|Save phase: Push all general-purpose registers onto current process's stack → Push program counter → Push stack pointer → Push PSW/FLAGS register. Switch phase: Update process table entry with saved stack pointer and new state → Select next process via scheduler. Restore phase: Load new process's stack pointer → Pop PSW/FLAGS → Pop general-purpose registers → Pop and jump to program counter (execution begins at saved location).

Why is atomicity important for synchronization primitives?|Synchronization primitives like test-and-set or compare-and-swap must execute without interruption. If a process could be interrupted mid-operation while checking and setting a lock, another process might also pass the check, and both would enter the critical region simultaneously, defeating mutual exclusion. Hardware-level atomic instructions provide the foundation for building higher-level synchronization mechanisms that guarantee correctness.

What information does the PSW/FLAGS register contain and why is it critical?|Contains condition codes from operations (zero flag - result was zero, carry flag - arithmetic carry occurred, overflow flag - signed overflow, sign flag - result is negative) and system state bits (interrupt enable/disable, privilege level). Critical for conditional branching (if statements, loops) and system operation. Must be saved during context switches or conditional logic will fail when process resumes.

How do message passing and semaphores differ in purpose?|Message passing: Designed for data transfer between processes. Processes explicitly send/receive data (messages). Provides communication channel. Example: one process sends computed results to another. Semaphores: Designed for synchronization and coordination. Control access to shared resources via counting mechanism. Provide mutual exclusion. Example: ensuring only one process accesses a shared data structure at a time. Can be combined for complex patterns.

Explain why the ready list must be efficiently implemented.|The ready list is accessed during every context switch (potentially thousands per second) for both insertion (when process becomes READY) and removal (when scheduler selects next process). Scheduler must quickly find highest-priority process. Inefficient implementation (like unsorted list requiring linear search) would add significant overhead to every context switch, dramatically reducing system performance. Priority queue provides O(log n) or O(1) operations.

What is the significance of the return value from fork() for process behavior?|The different return values allow parent and child to execute different code despite having identical code sections. Common pattern: if (fork() == 0) { /* child-specific code / } else { / parent-specific code */ }. Child (returns 0) might execute a new program via exec(), while parent (returns child PID) might wait for child completion or continue other work. This enables process creation with role differentiation.

Describe the relationship between blocking and I/O operations.|I/O operations (disk reads, network receives) take much longer than CPU operations (milliseconds vs nanoseconds). If a process waited for I/O while RUNNING, CPU would be idle (wasting time). Instead, when process initiates I/O, it transitions to BLOCKED state and relinquishes CPU. Scheduler runs other processes. When I/O completes (interrupt), kernel transitions process back to READY. This is fundamental to multiprogramming efficiency.

Why must invariants be maintained atomically during state transitions?|If state field is updated but data structure membership isn't (or vice versa), the system is temporarily inconsistent. If a context switch or interrupt occurs during this inconsistency, kernel code might observe: a READY process not on ready list (scheduler can't find it - process starves), a process on ready list not marked READY (scheduler might run wrong process), or currpid pointing to non-RUNNING process (system corruption). Atomic updates prevent observable inconsistency.

How does Xinu's array-based process table differ from linked-list implementations?|Array-based (Xinu): O(1) access given PID (direct index), fixed maximum processes (array size), simple implementation, potential memory waste if many PIDs unused, PID reuse when process terminates. Linked-list: Dynamic size (grows/shrinks), O(n) access requiring traversal, more complex memory management, no fixed maximum (limited only by system memory), efficient memory use. Xinu chooses simplicity and speed over flexibility.

Explain the complete semaphore workflow for resource management.|Initialization: Semaphore created with count = number of available resources. Process requests resource: Calls wait() → count decremented → if count ≥ 0, continue (got resource) → if count < 0, add to queue and block. Process releases resource: Calls signal() → count incremented → if count ≤ 0, wake one waiting process (move to READY) → if count > 0, resource now available for future requests. Count reflects: positive = available resources, zero = no resources/no waiters, negative = number of waiters.

What makes race conditions particularly difficult to debug?|Race conditions depend on precise timing of context switches, which is non-deterministic (depends on scheduler decisions, interrupts, system load). Same program with same input might work correctly 99.9% of time but fail rarely when unlucky timing occurs. Failures are non-reproducible - running again might not trigger the bug. Adding debugging code changes timing and may hide the bug (Heisenbug). Require careful analysis of concurrent access patterns and proper synchronization.

Compare blocking vs non-blocking message reception in Xinu.|receive() - Blocking: If message available, return immediately. If no message, process blocks (transitions to BLOCKED state) until message arrives. Process doesn't waste CPU but cannot do other work while waiting. recvclr() - Non-blocking: If message available, return it and clear buffer. If no message, return immediately with indicator (no blocking). Process can check for messages and continue other work if none available. Useful for polling pattern or when process has alternative work.

Why is the process hierarchy (parent-child relationships) important?|Resource inheritance: Child may inherit open files, environment variables from parent. Process cleanup: When parent terminates, kernel must decide child fate (orphan adoption or termination). Wait operations: Parent can wait for child completion and retrieve exit status. Signal propagation: Some signals sent to parent may affect children. Resource limits: Children may inherit or be constrained by parent's resource limits. Job control: Shells use hierarchy for job management (process groups).