Operating Systems

Summary of the CS2106 course

Get Started. It's Free
or sign up with your email address
Operating Systems by Mind Map: Operating Systems

1. Memory Management

1.1. Free Memory Management

1.1.1. Data Structures Bitmaps Linked lists

1.1.2. Policies Find first fitting block Find tightest fitting block Find loosest ftting block Buddy (Quick fit)

1.2. Virtual Memory

1.2.1. Pages and Frames

1.2.2. Mapping virtual addresses to physical addresses

1.2.3. Page fault remedy Free frames already available No free frames available Replacement scope Policies

1.2.4. Virtual table management All-in-memory Two-level Page Tables

1.2.5. Translation Lookaside Caches page tables Flush on context switch

2. CPU Management

2.1. Process Management

2.1.1. Create new process

2.1.2. Destroy process

2.2. Process Scheduling

2.2.1. Batch systems Fixed Priority FIFO Shortest Job First

2.2.2. Interactive systems Fixed priority Shortest Remaining Time Round Robin

2.2.3. Real-time Systems Fixed Priority Rate Monotonic Scheduling Earliest Deadline First

2.3. Process co-operation

2.3.1. Pre-emptive

2.3.2. Co-operative

2.3.3. Batch

2.4. UNIX

2.4.1. 140 priority levels Time quanta inversely proportional to priority 0-99 real-time 100-139 non-realtime

2.4.2. Dynamic priorities Base level Niceness level Other heuristics I/O boost CPU time consumed Interactive/background

3. Disk Management

3.1. Free Space Management

3.1.1. UNIX Free list maintained in superblock

3.1.2. DOS Free blocks marked in FAT

3.2. File management

3.2.1. UNIX Directories Kept as files inodes First level Second level Third level

3.2.2. DOS Directories Root directory kept just after FAT Sub-directories kept as files inside root or other sub-directories FAT Linked list Each entry:

4. Device Drivers

4.1. I/O Hardware Architecture

4.1.1. Memory mapped I/O devices can be accessed as pointers Eats memory addressing space

4.1.2. Direct mapped Special machine instructions to access I/O Separate addressing space

4.2. I/O Software Architecture

4.2.1. Polling Simple Expensive busy-waiting

4.2.2. Interrupts No busy-waiting Needs hardware support Frequent interrupts can incur significant overheads

4.2.3. DMA No busy waiting Fewer interrupts (only at end of transfer) Needs significant hardware support (DMAC) More complex to program correctly

5. Service Access

5.1. APIs

5.1.1. File system access File access open close lseek read write Directory access read search unlink add delete

5.1.2. Memory request _brk and _sbrk free

5.1.3. Access to scheduler nice surrender CPU

5.1.4. Interprocess communications services mutexes semaphores message passing

5.1.5. Process management services fork clone kill exec wait exit

6. Inter-process Communications

6.1. Race conditions

6.1.1. Non-critical sections with local variables

6.1.2. Critical sections caused by shared variables

6.2. Mutual Exclusion

6.2.1. Busy-wait approaches Expensive, wastes CPU cycles, can cause deadlocks in fixed priority systems Methods Lock variables Peterson's Solution

6.2.2. Wait/Signal Lost signals can cause deadlocks

6.2.3. Semaphores Can cause deadlocks and starvation Dining philosophers problem

6.3. Inter-process communications

6.3.1. Message passing

6.3.2. Pipes