CSS Computer Science Computer Architecture, Operating Systems & Networks Syllabus

What is a microinstruction and what does a microprogram represent?

A microinstruction is a set of control signals (micro-operations) issued in one clock; it may contain a next-address field. A microprogram is the sequence of microinstructions in control memory that implements one machine (macro) instruction.

Distinguish horizontal from vertical microprogramming.

Horizontal microinstructions are wide, with one bit per control signal, allowing high parallelism but large memory. Vertical microinstructions are narrow and encoded (decoded into signals), saving memory but allowing less parallelism and needing decoding.

State the memory hierarchy levels from fastest/smallest to slowest/largest.

Registers, L1 cache, L2/L3 cache, main memory (RAM), then secondary storage (SSD/HDD), and tertiary/offline storage. As you go down: capacity and access time increase, while cost per bit and speed decrease.

State the formula for average memory access time (AMAT).

AMAT = Hit Time + (Miss Rate x Miss Penalty). For multilevel caches it expands recursively, e.g., AMAT = HitTime_L1 + MissRate_L1 x (HitTime_L2 + MissRate_L2 x MissPenalty_L2).

Define temporal and spatial locality.

Temporal locality: recently accessed data/instructions are likely to be accessed again soon. Spatial locality: data near recently accessed addresses is likely to be accessed soon. Caches and block transfers exploit both.

Compare the three cache mapping techniques.

Direct-mapped: each block maps to exactly one cache line (simple, more conflict misses). Fully associative: a block can go in any line (flexible, expensive search). Set-associative: a block maps to one set of N lines (compromise, N-way).

List the three categories of cache misses (the 3 Cs).

Compulsory (cold) misses on first access to a block; Capacity misses because the cache cannot hold all needed blocks; Conflict (collision) misses due to too many blocks mapping to the same set in direct/set-associative caches.

Contrast write-through and write-back cache policies.

Write-through updates both cache and main memory on every write (simple, consistent, higher traffic). Write-back updates only the cache, marking the block dirty, and writes to memory only on eviction (less traffic, needs dirty bit).

What is instruction-level parallelism (ILP) and the main technique to exploit it?

ILP is the overlapping execution of multiple instructions from a single instruction stream. The primary technique is pipelining; further exploited by superscalar issue, out-of-order execution, and speculation.

List the classic 5 stages of a RISC instruction pipeline.

IF (Instruction Fetch), ID (Instruction Decode / register read), EX (Execute / ALU), MEM (Memory access), WB (Write Back to register). Each stage takes one cycle, ideally completing one instruction per cycle.

Name the three types of pipeline hazards.

Structural hazards (resource conflicts), Data hazards (dependence on a not-yet-computed result, e.g., RAW), and Control hazards (branches changing the instruction flow). Each can force stalls/bubbles unless mitigated.

How are data hazards mitigated without always stalling?

By forwarding/bypassing (routing an ALU result directly to a dependent instruction before write-back), and by compiler instruction scheduling. RAW dependences that cannot be forwarded (e.g., load-use) still require a stall/bubble.

What techniques reduce control (branch) hazards?

Branch prediction (static or dynamic), branch target buffers, delayed branches (branch delay slots), and speculative execution. Correct prediction avoids the pipeline flush that a mispredicted branch causes.

Define a superscalar processor and how it differs from a scalar pipeline.

A superscalar processor fetches, decodes, and issues multiple instructions per clock cycle to multiple execution units, achieving CPI < 1 (IPC > 1). A scalar pipeline issues at most one instruction per cycle.

Distinguish multicore from multiprocessor (SMP) systems.

A multicore chip has multiple CPU cores on one die, often sharing caches and the memory bus. A multiprocessor system has multiple separate CPU packages. SMP (symmetric multiprocessing) shares one main memory equally among all processors.

What is the difference between multiprogramming, multitasking, and multiprocessing?

Multiprogramming keeps several jobs in memory to keep the CPU busy. Multitasking (time-sharing) rapidly switches the CPU among tasks for interactivity. Multiprocessing uses two or more physical CPUs/cores executing in parallel.

Compare UMA and NUMA memory architectures.

UMA (Uniform Memory Access): all processors have equal access time to shared memory (typical SMP). NUMA (Non-Uniform Memory Access): memory is distributed; a processor accesses its local memory faster than remote memory, improving scalability.

Flynn's taxonomy: name and define the four classes.

SISD (Single Instruction Single Data - uniprocessor), SIMD (Single Instruction Multiple Data - vector/GPU), MISD (Multiple Instruction Single Data - rare), MIMD (Multiple Instruction Multiple Data - multiprocessors/multicore).

What are the primary roles/functions of an operating system?

Acts as resource manager (CPU, memory, I/O, files) and as an extended/virtual machine offering a convenient interface. Functions include process, memory, file, I/O, and security management plus providing system calls and a user interface.

Compare monolithic, layered, and microkernel OS structures.

Monolithic: all OS services in one kernel address space (fast, less modular). Layered: organized into hierarchical layers each using the one below. Microkernel: minimal kernel (IPC, scheduling, basic memory); other services run as user-space servers (modular, reliable, more overhead).

What distinguishes user mode from kernel (supervisor) mode?

Kernel mode allows execution of all (privileged) instructions and direct hardware/memory access; user mode restricts these. A mode bit enforces this. The transition to kernel mode occurs via system calls, interrupts, or traps.

What is a system call and how does it transfer control to the OS?

A system call is the programmatic interface for a user program to request an OS service (e.g., read, fork). It triggers a software interrupt/trap that switches to kernel mode, runs the corresponding kernel routine, then returns to user mode.

Trace the evolution of operating systems through its major generations.

Serial/manual processing, then batch systems, then multiprogrammed batch, then time-sharing/multitasking, then personal/desktop and real-time systems, and finally distributed, networked, mobile, and cloud/virtualized operating systems.

Define a process and a process control block (PCB).

A process is a program in execution with its own address space, resources, and state. The PCB is the kernel data structure storing a process's metadata: PID, process state, PC, CPU registers, scheduling info, memory limits, and open files.

List the five states in the process state model.

New, Ready, Running, Waiting/Blocked, and Terminated. A process moves Ready->Running (dispatch), Running->Ready (timeout/preempt), Running->Waiting (I/O request), Waiting->Ready (I/O complete), and Running->Terminated (exit).

Differentiate a process from a thread.

A process has its own address space and resources; a thread is a lightweight unit of execution within a process. Threads of one process share its code, data, and files but have separate stacks, registers, and program counters, making context switches cheaper.

Compare preemptive and non-preemptive scheduling.

In non-preemptive scheduling a running process keeps the CPU until it blocks or terminates. In preemptive scheduling the OS can forcibly take the CPU (e.g., on a timer interrupt or higher-priority arrival), improving responsiveness but adding context-switch overhead.

Name common CPU scheduling algorithms and one key property of each.

FCFS (simple, convoy effect); SJF/SRTF (optimal average waiting time, needs burst prediction, can starve); Priority (starvation, fixed by aging); Round Robin (fair, time-quantum based, good response time); Multilevel Queue/Feedback (multiple queues by priority).

State the four necessary conditions for deadlock (Coffman conditions).

Mutual exclusion, Hold and wait, No preemption, and Circular wait. All four must hold simultaneously for deadlock; breaking any one prevents it.

What is the difference between logical (virtual) and physical address space?

A logical/virtual address is generated by the CPU/program; the physical address is the actual main-memory location. The Memory Management Unit (MMU) translates logical to physical addresses at run time, enabling protection and relocation.

Explain paging and the role of the page table.

Paging divides logical memory into fixed-size pages and physical memory into equal frames. The page table maps each page number to a frame number; a logical address splits into a page number (table index) and an offset, eliminating external fragmentation.

What is a TLB and why is it used?

The Translation Lookaside Buffer is a small, fast associative cache that stores recent page-number-to-frame-number translations. It avoids a slow main-memory page-table lookup on every access, greatly speeding virtual-to-physical address translation.

Distinguish internal from external fragmentation.

Internal fragmentation: allocated memory is larger than requested, wasting space inside a block (common in paging/fixed partitions). External fragmentation: free memory exists but is split into non-contiguous holes too small to use (common in segmentation/variable partitions).

What is demand paging and what triggers a page fault?

Demand paging loads a page into memory only when it is first referenced (lazy loading). A page fault occurs when a referenced page is not in memory (valid-invalid bit set invalid); the OS then fetches it from disk and updates the page table.

Name three page-replacement algorithms and identify the optimal/anomalous ones.

FIFO (simple, suffers Belady's anomaly), Optimal/OPT (replaces the page used farthest in future - theoretical minimum faults, unimplementable), and LRU (replaces least recently used - good approximation of OPT, no Belady's anomaly).

What is thrashing and how is it controlled?

Thrashing is excessive paging where the system spends more time swapping pages than executing, due to too high a degree of multiprogramming/insufficient frames. It is controlled using the working-set model or page-fault-frequency (PFF) control to adjust allocated frames.

Compare contiguous, linked, and indexed file allocation methods.

Contiguous: blocks stored consecutively (fast access, external fragmentation). Linked: each block points to the next (no fragmentation, slow random access, pointer overhead). Indexed: an index block holds all block pointers (supports direct access, needs index space).

What is an inode and what does it store?

An inode (index node) is a file's metadata structure in Unix-like file systems. It stores file attributes (type, permissions, owner, size, timestamps) and pointers to the data blocks, but not the file name (kept in the directory).

Differentiate programmed I/O, interrupt-driven I/O, and DMA.

Programmed I/O: CPU polls device status continuously (busy-waiting, wasteful). Interrupt-driven I/O: device interrupts the CPU when ready (no polling). DMA (Direct Memory Access): a controller transfers data directly between device and memory, interrupting the CPU only on completion.

What is the purpose of double buffering and spooling in I/O management?

Buffering smooths speed mismatches between producer and consumer (double buffering lets one buffer fill while the other drains). Spooling (Simultaneous Peripheral Operation On-Line) queues output (e.g., print jobs) on disk so a slow shared device serves multiple processes without blocking them.