Comprehensive review
Overview
Content
OS-02 Functions and Structures
OS-03 Process
OS-04 Threads & Concurrency
OS-05 CPU Scheduling
OS-06 Process Synchronization
OS-07 Deadlocks
OS-08: main memory
OS-09: Virtual Memory
OS-10: storage
OS-11: File System
OS-12: I/O Systems
OS-13: Virtual Machine
OS-14: Distributed System
Resources
Introduction
Functions and Structures
Process
Thread
CPU scheduling
Process synchronization
Deadlocks
Main Memory
Virtual Memory
Storage
File System
IO System
Virtual Machine
Distributed System
Review
Process Management
Process
- Concepts (PCB, memory, process states)
- Process scheduling (long-term, short-term), context switching
- Process operations: fork() exec() wait() exit()
- IPC: shared memory, message passing
Threads & Concurrency
- Concepts (compared with processes)
- Parallelism vs. Concurrency
- Kernel threads vs. user threads (thread libraries) mapping models
- pthreads: tid attr init create join
CPU Scheduling
- Scheduling criteria: CPU utilization, throughput, turnaround time, waiting time, response time
- Scheduling algorithms: FCFS, SJF, RR, Priority, multilevel (feedback) queue scheduling
- thread scheduling: PCS vs. SCS
Process Synchronization
- The critical-section problem
- Peterson’s algorithm; breaks under instruction reordering
- Atomic operations
- Semaphores: wait() signal()
- mutex lock: acquire() release()
Deadlocks
- Mutual exclusion, hold and wait, no preemption, circular wait
- Prevention: break one of the conditions
- Avoidance: Banker’s algorithm, resource-allocation graph
- Detection: resource-allocation graph
Others
A process consists of the program, its data and the PCB; a thread consists of the TCB, the program counter, the stack space and the register set. The process is the basic unit of resource allocation and CPU scheduling. Threads share the process’s address space but have their own private register set and stack space.
Waiting time does not include I/O time; turnaround time does include I/O time.
Memory Management
Main Memory
- Low memory: OS High memory: user processes
- MMU: address translation; protection mechanism: base and limit registers
- Contiguous memory allocation: (1) first fit, (2) best fit, and (3) worst fit.
- Internal fragmentation vs. External fragmentation
- paging: physical frames, logical pages page number + page offset
- TLB: a “cache”
- swapping
The size of a page table entry has nothing to do with the page number; it is related to the page size and the offset.
Virtual Memory
- Demand paging: page fault
- COW: copy-on-write (copy when writing/modifying)
- Page replacement algorithms:
- FIFO, LRU,
- Optimal (stack, second chance)
- counting (LFU)
Storage Management
Storage
- Disk structure: cylinder, track, sector
- Disk scheduling algorithms: FCFS, SSTF, SCAN, C-SCAN, LOOK, C-LOOK (C means jump back to the start; SCAN goes all the way to the end)
- Mounting, swap-space
- RAID: 0 (striping) 1 (mirroring) 4 (block-interleaved parity) 5 (4 + distributed parity)
File System
- Access methods: sequential, direct
- Disk partition + file system = volume
- Directories:
- single-level, two-level, tree-structured, acyclic graph
- file descriptor: inode
I/O Systems
- Interrupts, polling, DMA
Advanced Topics
Virtual Machines
- VCPU: Trap-and-emulate (privileged instructions), Binary translation (translating special instructions)
- Type: 0 - hardware, 1 - software, 2 - application
Distributed Systems
- Network OS vs. Distributed OS: whether the user is aware of it
- Distributed File System: client-server, cluster-based
Algorithms
- CPU Scheduling
- FCFS, SJF, RR, Priority
- MQS, MFQS (with or without movement between queues)
- Banker’s Algorithm
- Memory allocation(Fit algorithms)
- Page replacement
- FIFO, LRU, Optimal
- Second chance, counting
- Disk scheduling
- FCFS, SSTF, SCAN, C-SCAN, LOOK, C-LOOK
- File allocation: I-node
Quiz
Producer-Consumer Problem
Threads
Answer: child process 5, parent process 0
Banker’s Algorithm
Main Memory
Answer:
Second chance algorithm
Translated from the Chinese original.
