Operating Systems - Complete Study Guide for Flashcards

Operating Systems - Ultra-Simple Flashcard Version

DEFINITIONS

Program Counter (PC)

Points to the NEXT instruction to execute. Like a bookmark showing which line of code to run next. Must be saved during context switch so process knows where to continue.

Stack Pointer (SP)

Points to the top of the process's stack. Stack holds function calls, local variables, and return addresses. Each process has its own stack.

PSW/FLAGS Register

Status flags showing results of last CPU operation. Zero flag (was result zero?), Carry flag (number overflow?), Sign flag (negative result?). Used for if statements and loops.

Pseudoparallelism

FAKE simultaneous execution. CPU switches between processes so fast it LOOKS like they run at the same time, but only one actually runs at any moment. Real parallelism = multiple CPUs running processes truly simultaneously.

Multiprogramming

Multiple programs loaded in memory. When one waits (for I/O), CPU runs another. Goal: keep CPU busy, never idle.

Copy-on-Write

After fork(), parent and child SHARE memory pages initially. Only when one tries to WRITE does OS make a copy. Saves time and memory since many pages never get modified.

Context Switch

Switching CPU from one process to another. Save current process state (registers, PC, SP, FLAGS). Load next process state. Jump to where new process left off.

Critical Region

SECTION OF CODE that accesses shared resources. Only one process should execute this code at a time. If multiple processes run it simultaneously, data gets corrupted.

Mutual Exclusion

Rule: Only ONE process in critical region at a time. Forces processes to take turns. Prevents race conditions.

Race Condition

When output depends on unpredictable timing/order of execution. Same inputs might give different outputs based on who goes first. Hard to debug because happens randomly.

Spin Lock

Loop that keeps checking "is lock free yet?". Wastes CPU by constantly checking. Good only for very short waits.

Semaphore

Integer counter for managing resources. wait() decrements count, blocks if negative. signal() increments count, wakes waiting process if any. Blocks processes instead of spinning (saves CPU).

THEORY

Kernel

Core of OS with full control over everything. Connects hardware and software. Runs in privileged kernel mode.

Kernel Jobs

Process management, Memory management, Device/I/O management, File system management, CPU scheduling, System calls.

Program

Static code on disk. Just instructions sitting there. Like a recipe book.

Process

Program in execution. Includes: code, data, stack, CPU state, open files. Like actually cooking from the recipe. Multiple processes can run same program.

Thread

Lightweight execution unit within a process. Multiple threads share code, globals, heap but each has own stack, PC, registers. Like workers in same office with shared files but own desks.

Process State: READY

Has everything needed to run. Waiting in ready list for CPU. Just needs to be selected by scheduler.

Process State: RUNNING

Currently executing on CPU. Only ONE process running at a time (single CPU).

Process State: BLOCKED

Waiting for something (I/O, semaphore, message). Can't proceed. Not on ready list.

READY to RUNNING

Scheduler picks this process. Your turn to use CPU.

RUNNING to READY

Time slice expired OR higher priority process arrived. Kicked off CPU but still capable of running.

RUNNING to BLOCKED

Process needs something it doesn't have. Waiting for I/O, semaphore, message, timer. Voluntary - process chooses to wait.

BLOCKED to READY

Whatever was waited for arrived. I/O completed, semaphore signaled, message received. Goes to READY first, NOT directly to RUNNING.

Context Switch Steps

(1) Save registers to stack (2) Update process table with stack pointer and state (3) Scheduler picks next process (4) Load new process state (5) Restore registers from stack (6) Jump to new PC.

Bad Context Switch Problems

If switch happens while modifying shared data: race conditions, corrupted variables, incorrect output, inconsistent data structures.

Process Abstraction

OS makes each process think it owns the entire computer. Each gets virtual memory space, protected from others, scheduled fairly. Hides that you're sharing CPU with hundreds of processes.

Thread Abstraction

Multiple execution paths in one process. Threads share memory and resources but each has own stack and execution state. Cheaper than processes, easier communication through shared memory.

XINU SPECIFIC

Process Table (proctab)

Array where index = PID. proctab[0] = null process. proctab[5] = process with PID 5. Fast O(1) lookup.

Current Process

Access with proctab[currpid] where currpid = global variable = PID of running process.

Ready List

Queue of all READY processes waiting for CPU. Invariant: On ready list if and only if state = READY.

Semaphore in Xinu

Has count (integer) and queue (waiting processes).

wait() Operation

Decrement count. If count goes negative, add process to queue and BLOCK.

signal() Operation

Increment count. If count still ≤ 0, wake one waiting process (make it READY).

Semaphore Count Meaning

Positive = resources available. Zero = no resources, no waiters. Negative = number of waiting processes. Count = -3 means 3 processes waiting.

receive()

BLOCKING message receive. If no message, wait forever until one arrives.

recvclr()

NON-BLOCKING message receive. If no message, return immediately without blocking. Clears buffer.

recvtime()

Message receive with TIMEOUT. Wait for message but give up after specified time.

Killing SLEEPING Process

Remove from sleep queue FIRST. Otherwise zombie pointer remains, causes crash when timer expires.

Killing READY Process

Remove from ready list FIRST. Otherwise scheduler tries to run dead process, causes crash.

Killing WAITING Process

Remove from semaphore queue AND increment semaphore count. Increment compensates for the wait() it did but will never signal().

Process Entry Fields

Name, Priority, Parent PID, State, Stack pointer, Program counter, plus memory info and scheduling data.

Invariants

Rules always true. Sleep queue invariant: on sleep queue ↔ state = PR_SLEEP. Ready list invariant: on ready list ↔ state = PR_READY. currpid invariant: currpid points to process ↔ state = RUNNING.

User-Level Threads

Managed by library, not kernel. Kernel sees one process. FAST to create/switch. BIG PROBLEM: One thread blocks, ALL block. Can't use multiple CPUs.

Kernel-Level Threads

Managed by kernel. Kernel sees each thread. SLOWER to create/switch. One thread blocks, others keep running. Can use multiple CPUs.

fork() Function

Creates copy of calling process. Parent and child both continue from same point but get different return values. Returns 0 to child, child PID to parent, -1 if fails.

Atomic Action

Operation that completes entirely without interruption. Can't be split up. Other processes can't observe partial completion. Essential for locks and synchronization.

Why Race Conditions Hard to Debug

Timing-dependent. Non-deterministic. Might work 1000 times, fail once. Not reproducible. Adding debug code changes timing and hides bug.

Spin Lock vs Semaphore

Spin lock: continuously checks in loop, wastes CPU, fast for very short waits. Semaphore: blocks process when unavailable, no CPU waste, good for longer waits, maintains queue.

Blocking and I/O

I/O takes long time (milliseconds). Process goes BLOCKED during I/O so CPU can run other processes. When I/O completes, process goes back to READY. Enables multiprogramming.

Preemption

Higher priority process arrives. Current RUNNING process saved to READY. Higher priority process gets CPU immediately. Ensures important processes run quickly.

Quantum (Time Slice)

Maximum time process can run before forced off CPU. Prevents monopolization. When expires, RUNNING → READY. Ensures fairness.

Priority Scheduling

Ready list organized by priority. Highest priority runs first. Critical processes get CPU before less important ones.

Total cards: 60+ definitions

Study tip: Make one flashcard per section above. Front = term, Back = simple definition.