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

1.1.1.1. Bitmaps

1.1.1.2. Linked lists

1.1.2. Policies

1.1.2.1. Find first fitting block

1.1.2.2. Find tightest fitting block

1.1.2.3. Find loosest ftting block

1.1.2.4. 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

1.2.3.1. Free frames already available

1.2.3.2. No free frames available

1.2.3.2.1. Replacement scope

1.2.3.2.2. Policies

1.2.4. Virtual table management

1.2.4.1. All-in-memory

1.2.4.2. Two-level Page Tables

1.2.5. Translation Lookaside

1.2.5.1. Caches page tables

1.2.5.2. 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

2.2.1.1. Fixed Priority

2.2.1.2. FIFO

2.2.1.3. Shortest Job First

2.2.2. Interactive systems

2.2.2.1. Fixed priority

2.2.2.2. Shortest Remaining Time

2.2.2.3. Round Robin

2.2.3. Real-time Systems

2.2.3.1. Fixed Priority

2.2.3.2. Rate Monotonic Scheduling

2.2.3.3. 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

2.4.1.1. Time quanta inversely proportional to priority

2.4.1.2. 0-99 real-time

2.4.1.3. 100-139 non-realtime

2.4.2. Dynamic priorities

2.4.2.1. Base level

2.4.2.2. Niceness level

2.4.2.3. Other heuristics

2.4.2.3.1. I/O boost

2.4.2.3.2. CPU time consumed

2.4.2.3.3. Interactive/background

3. Disk Management

3.1. Free Space Management

3.1.1. UNIX

3.1.1.1. Free list maintained in superblock

3.1.2. DOS

3.1.2.1. Free blocks marked in FAT

3.2. File management

3.2.1. UNIX

3.2.1.1. Directories

3.2.1.1.1. Kept as files

3.2.1.2. inodes

3.2.1.2.1. First level

3.2.1.2.2. Second level

3.2.1.2.3. Third level

3.2.2. DOS

3.2.2.1. Directories

3.2.2.1.1. Root directory kept just after FAT

3.2.2.1.2. Sub-directories kept as files inside root or other sub-directories

3.2.2.2. FAT

3.2.2.2.1. Linked list

3.2.2.2.2. Each entry:

4. Device Drivers

4.1. I/O Hardware Architecture

4.1.1. Memory mapped

4.1.1.1. I/O devices can be accessed as pointers

4.1.1.2. Eats memory addressing space

4.1.2. Direct mapped

4.1.2.1. Special machine instructions to access I/O

4.1.2.2. Separate addressing space

4.2. I/O Software Architecture

4.2.1. Polling

4.2.1.1. Simple

4.2.1.2. Expensive busy-waiting

4.2.2. Interrupts

4.2.2.1. No busy-waiting

4.2.2.2. Needs hardware support

4.2.2.3. Frequent interrupts can incur significant overheads

4.2.3. DMA

4.2.3.1. No busy waiting

4.2.3.2. Fewer interrupts (only at end of transfer)

4.2.3.3. Needs significant hardware support (DMAC)

4.2.3.4. More complex to program correctly

5. Service Access

5.1. APIs

5.1.1. File system access

5.1.1.1. File access

5.1.1.1.1. open

5.1.1.1.2. close

5.1.1.1.3. lseek

5.1.1.1.4. read

5.1.1.1.5. write

5.1.1.2. Directory access

5.1.1.2.1. read

5.1.1.2.2. search

5.1.1.2.3. unlink

5.1.1.2.4. add

5.1.1.2.5. delete

5.1.2. Memory request

5.1.2.1. _brk and _sbrk

5.1.2.2. free

5.1.3. Access to scheduler

5.1.3.1. nice

5.1.3.2. surrender CPU

5.1.4. Interprocess communications services

5.1.4.1. mutexes

5.1.4.2. semaphores

5.1.4.3. message passing

5.1.5. Process management services

5.1.5.1. fork

5.1.5.2. clone

5.1.5.3. kill

5.1.5.4. exec

5.1.5.5. wait

5.1.5.6. 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

6.2.1.1. Expensive, wastes CPU cycles, can cause deadlocks in fixed priority systems

6.2.1.2. Methods

6.2.1.2.1. Lock variables

6.2.1.2.2. Peterson's Solution

6.2.2. Wait/Signal

6.2.2.1. Lost signals can cause deadlocks

6.2.3. Semaphores

6.2.3.1. Can cause deadlocks and starvation

6.2.3.1.1. Dining philosophers problem

6.3. Inter-process communications

6.3.1. Message passing

6.3.2. Pipes