# Operating System

## Context Switch:

It's a prcedure that a computer's CPU follows to change from one task(process) to another while ensuring that the tasks do not conflict.

> How:
>> 1. Before switching, it stores the state of a task(process or thread).
>> 2. Restored the state of process you gonna resume execution.

>Pros:
>>1. Allows multi-processes to share a single CPU and it's >essential feature for a multi-tasking operating system.

>Cons:
>>1. Switching from one to another requires a certain amount of time for doing administration - saving and loading registers and memory maps, updating various tables and lists, etc.

>Performance:
>>It has a cost in performace due to running that task scheduler, memory cache and indirectly due to sharing the CPU cache between multi-tasks.

>> Switching between threads of a single process can be faster than between two separate processes. Because threads share the same virtual memory maps.

Q&A:
1. How a context switch occurs?
Process makes system call or interrupt occurs.
2. What's done by hardware?
* Switch from user to kernel mode
* Go to fixed kernel location
3. What's done by software(Kernel)?
* Save context of current process
* Select a process that is ready and restore its context.
* RTI

> RTI: Return from interrupt/trap
> Trap: causes entry into kernel

---

## Kernel

It's a computer program at the core of a computer's operating system with complete control over everything in the system. Besides, it takes responsibility for deciding at any time which of the many running programs should be allocated to the processors.


>Code within kernel that supports processes:
>>1. System calls: fork(), exit(), read(), write(), ...
>>2. Management: Context Switching, Scheduling, ...

Q&A:
1. When does the kernel run?
* System call or hardware interrupt occurs

---

## Time Sharing
* Running: making process, using CPU
* Ready: able to make progress, but not using CPU
* Blocked: not able to make progress, can't use CPU


* Dispatch: allocate the CPU to a process
* Preempt: take away CPU from process
* Sleep: process gives up CPU to wait for event
* Wake up: event occurred, make process ready

---

## Process vs. Threads

### Process (No shared memory):
It's a program in execution, assumed a single path of execution. In a memory composed of text, data and stack.

Q&A:
What if we want multiple paths of execution?
* **Single text**, but multiple executions in parallel
* **Single data**, any execution can see other's execution
* **Need separate stacks**, one per ongoing execution

### Threads (Shared memory spaces):
Single sequential path of execution, part of process, allows multi-threads in a process. It's **a unit of schedulability to the kernel**.

---

## Scheduling

### RR: Round Robin (Take turns)
Finished specific amount of work and switch to the next task in queue.

### Multi-Level Feedback Queues
1. Priority queues: 0 (high), ..., N (low)
2. New processes enter queue 0
3. Finish 2^k quantums(work) each time and move to next lower queue

### Fair Share (Proportional Share)

### Stride Scheduling
* R: request, S = 1/R: strides, P: pass
* Pick small P first


## Real-Time Scheduling
> **Periodic** vs. **Aperiodic**


> C = CPU burst
> T = Period
> U = C/T = Utilization

### Earlist Deadline First (EDF)

### Rate Monotonic Scheduling (RMS)
* Prioritize based on rates = 1/T

### Summary

| Algorithm | Property |Pre-emptive |
| ----------------------- |:---------------------------------------------:|:----------:|
| First come first served | Simple, no starvation | N |
| Round robin | Simple, no starvation | Y |
| Shortest process next | Optimal for non-preemptive, allows starvation | N |
| Shortest remaining time | Optimal for non-preemptive, allows starvation | Y |
| Multi-level feedback | Adaptive, Responsive, Complex, Favors shorter over longer, possible starvation||
| Priority sched | External Criteria ||
| Fair share | Proportional Allocation (Select process with min actual/request ratio) ||
| Stride sched || N |
| Earlist deadline first | Works for periodic and aperiodic, 100% utilization, high overhead due to ordering by deadlines | Y |
| Rate monotonic sched | Prioritize based on rates (1/T) < 100% util, low overhead, Optimal for static priority algorithms | Y if necessary |

**Preemption**: CPU is forcibly taken away before task finished.

**Synchronization** (blocks, costly) vs. **Asynchronization**

> Synchronization operation **blocks** a process till the operation completes. Asysnchronization operation is **non-blocking** and only initiates the operation. Note that Synchronization/Asynchronization implies blocking/non-blocking but not vice versa. **Asynchronization allows more parallelism**.

---

## Lock

### Mutex (Mutual Exclusion) vs. Semaphores

<table>
<tr>
<td></td>
<td>Mutex</td>
<td>Semaphores</td>
</tr>
<tr>
<td>Mechanism</td>
<td>Locking</td>
<td>Signaling</td>
</tr>
<tr>
<td>Acquire (Wait)</td>
<td>Only one task can acquire the mutex (access critical section) at a time </td>
<td>Multi-Task can acquire the resources</td>
</tr>
<tr>
<td>Ownership</td>
<td>Ownership associated with mutex</td>
<td>No ownership</td>
</tr>
<tr>
<td>Release (Signal)</td>
<td>Only the owner can release the lock</td>
<td>Process in queue waiting for the signal that you can use the resource</td>
</tr>
<tr>
<td>Atomicity</td>
<td>Critical section is surrounded by wait and signal</td>
<td>Wait and Signal must be atomic, thus requiring lower-level mutex (Peterson's, TSL)</td>
</tr>
<tr>
<td>Note</td>
<td colspan="2" style="text-align:center">Mutex &#8800 Binary Semaphores</td>
</tr>
<tr>
<td>Ref</td>
<td colspan="2" style="text-align:center">
<a href="https://www.geeksforgeeks.org/mutex-vs-semaphore/">Mutex vs. Semaphores
</a>
</td>
</tr>
</table>

**Atomicity**
An operation done by a computer is considered atomic if it is guaranteed to be isolated from other operations that may be happening at the same time. Atomic operations are indivisible.

### Peterson's Solution
Get in critical section when you have **Intention** and it's your **Turn**.


### Test-and-Set Lock Instruction (TSL)

It's an instruction used to write 1 (set) to a memory location and return its old value as a single atomic (i.e., non-interruptible) operation. If multiple processes may access the same memory location, and if a process is currently performing a test-and-set, no other process may begin another test-and-set until the first process's test-and-set is finished.

> 1. Record the old value
> 2. Set the value to indicate available
> 3. Return the old value

* Mutex using TSL: Suffer from busy waiting.

**Interrupt**
Interrupt is a signal from a device attached to a computer or from a program within the computer that requires the operating system to stop and figure out what to do next.
* Interrupt generated when hardware timer expires
* Interrupt forces control to go to kernel
* While kernel running, resets timer for the next time

**Interrupt handler**
Interrupt handler prioritizes the interrupts and saves them in a queue if more than one is waiting to be handled.

**Scheduler**
It figures out which program to give control to next.

### Spin Lock (keep requesting, busy waiting)

A spin lock is a lock which causes a thread trying to acquire it to simly wait in a loop (spin) while repeatedly checking if the lock is available. Since the thread remains active but is not performing a usefull task, the use of such a lock is a kind of busy waiting.

**Busy Waiting (Busy Looping, Spinning)**

It's a technique in which a process repeatedly checks to see if a condition is true, such as whether keyboard input or a lock is available.

**Overhead (Kill chicken using a BIG knife)**
Overhead is any combination of excess of indirect computing time, memory, bandwidth, or other resources that are required to perform a specific task.
In computer science, sometimes we use cars to go down the street because we don't have a better way, or it's not worth our time to "learn how to work".

### Inter-Process Communication (IPC)

IPC is a mechanism which allows processes to communicate each other and synchronize their actions. The communication between these processes can be seen as a method of co-operation between them. Process can communicate with each other using these two ways
1. Shared Memory
2. Message Passing

Requires
* Data Transfer
* Synchronization

### Monitor

**Monitor is a synchronization construct that allows threads to have both mutual exclusion and the ability to wait (bock) for a certain condition to become false**. Monitors also have a mechanism for signaling other threads that their condition has been met. **A monitor consists of a mutex (lock) object and condition variables**.

**Only one process can be active**

### Deadlock

Deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process.

Deadlock can arise if following four conditions hold simultaneously (Necessary Conditions)
1. Mutex: Only one process can use at a time
2. Hold and Wait: Process holds resource while waiting for another
3. No preemption: A resource cannot be taken from a process unless the process releases the resource.
4. Circular Wait: The waiting processes form a cycle.

#### Methods for handling deadlock
1. Deadlock Prevention: Make deadlock impossible by removing condition
2. Deadlock Avoidance: Avoid getting into situations that lead to deadlock (Avoid deadlock using banker's algorithm)
3. Deadlock detection and recovery: Let deadlock occur, then **do preemption to handle it once occurred**.
4. Ignore the problem all together: If the deadlock is rare, then let it happen and reboot the system. This is the approach that both Windows and UNIX take.

#### Banker's Algorithm

* This is a safe state.
* Which process can run to completion? P2
* After P2 completes, its resources are returned.
* Next select P1, then P3, and then P4.

---

## Memory

### Process Memory (User Space)
* **Text**: Program instructions (Execution-only, fixed size)
* **Data**: Variables (static, heap)
* Dynamic allocation by request
* **Stack**: Automatic variables, activation records (auto)
* Automatic growth/shrinkage
* Other: Shared memory regions


### Physical Memory

* **Hole**: Physical memory without getting allocated
* **Block**: Area in physical memory gets allocated

#### Internal fragmentation
* Unused space within (allocated) blocks
* Cannot be allocated to others
* Can come in handy for growth

#### External fragmentation
* Unused space outside any blocks (within holes)
* Can be allocated

##### How to deal with No Holes?
* **Compaction**: Simple but Time Consuming
* **Break block into sub-blocks**: Easier to fit but complex


##### How many holes are there when there is n blocks?
###### 50% Rule: Number of holes = Number of blocks/2

##### How many wasted memory are there?
###### Unused memory rule (wasted memory rate) f:
* b = average size of blocks
* h = average size of holes
* k = h/b ratio of average hole-to-block size
* **f = k/(k+2)** is fraction space lost to holes

#### Buddy System

#### Logical vs. Physical addressing
* Logical addresses
* **Assumes separate memory starting at 0**
* **Compiler generated**
* Independent of location in physical memory
* Convert logical to physical
* Via software: at load time
* Via hardware: at access time

#### Hardware for logical addressing and protection
* **Base register** filled with starting logical address
* Achieves relocation
* To move process, change base
* **Bound register** works with vase register for protection
* Is address < bound?
* Yes: Add to base
* No: Invalid address, TRAP


##### Memory registers part of context
* On every Context Switch
* Load base/bound registers for selected process
* Only kernel does loading of these registers
* Kernel must be protected from all processes
* Benefit
* Allows each process to be separated located
* Protect each process from all others

### Segmented address vs. Paged address
#### Fitting process into memory
1. **Segmented address** space
a. Partition into segments
b. Segments can be different sizes to fit any contents
c. Segment is good "Logical" unit of information
d. Makes sense to **share** (code, data...)
e. Can be protected according to contents (Permission)
2. **Paged address** space
a. Partition into pages
b. Pages are the same size
c. Paged is good "Physical" Unit of information
d. **Simple** memory management


### Segmented

#### Segment Table (One per process)
Location of segment table is given by STBR (hardware) and STSR (hardware).


* V: Valid bit
* Base: Segment location
* Bound: Segment size
* Perm: Permissions
* STBR: Segment table base register
* STSR: Segment table size register

**Do following checks first:**
* If Segment s is within range (s < STSR)
* If Segment Entry s is valid (V == 1)
* If offset i is within bounds (i < Bound)
* If operation is permitted (Perm(op))

**Pros and Cons of Segmentation**
* Pros: Each segment can be
* Located independently
* Separately protected
* Grownn/shrunk independently
* Shared by processes
* Cons: Variable-size allocation
* Difficult to find holes in physical memory
* External fragmentation

### Paged

#### Paged Table
Location of page table is given by PTBR (hardware) and PTSR (hardware) and update when context switch.
* V: Valid bit
* DPB: Demand paging bits
* Frame: Page location in physical memory
* PTBR: Page table base register
* PTSR: Page table size register


**Do following checks first:**
* If Page p is within range (P < PTSR)
* If Page Table Entry P is valid (V == 1)
* If operation is permitted (Perm(op))

### Translation Look-aside Buffer (TLB) (Cache):

Combination of pros of Segmented and Paged


* TLB hit: Key matches
* TLB miss: No key matches and wait for normal translation (in parallel)
* The larger the TLB
* The higher the hit rate
* The slower the response
* The greater the expense
* Must be **flushed on context switches** (update buffer list)

---

## Virtual Memory: Illusion of large memory
* Keep only portion of logical memory in physical
* Rest is kept on desk (large, slower, cheaper)

### Page Faults (Valid bit is off, trap into kernel)
* Find page on disk (kept in kernel data structure)
* Read it into a free frame
* May need to make room: **Page Replacement**
* Record frame number in page table entry
* Set valid bit (and other fields)

**Thrashing: Busy dealing with page fault, barely do thins.**

### Page Replacement Algorithms
OPT >= LRU (assuming locality) >= FIFO
* FIFO: Select page that is oldest
* Optimal Page Replacement (OPT): Select page to be used furthest in future
* Optimal, but requires future knowledge
* LRU: Select page that was least recently used
* Predict future based on past; works given locality
* Costly: To keep track of frame with LRU page
* Clock Algorithm (approximating LRU)
* Denning's Working Set Model W(t, $\Delta$)
1. Working set: Pages referenced during this window of $\Delta$ time units
2. When a process is active its entire working set must always be in memory; never execute a thread whose working set is not resident
3. The collections of active processes is called the **balanced set**.
4. There is a mechanism for gradually processes into and out of the balance set

**Locality**
* **Temporal Locality**:
Temporal locality refers to the **reuse of specific data, and/or resources, within a relatively small time duration**.
* **Spatial Locality**:
Spatial locality (data locality) refers to the **use of data elements within relatively close storage locations. Sequential locality**, a special case of spatial locality, occurs when data elements are arranged and accessed linearly, such as, traversing the elements in a one-dimensional array.

### Faults under Segmentation/Paging
* Virtual address: <segment s, page p, offset i>
* Use s to index segment table (get page table)
* May get a segment fault
* Check bound (Is p < bound?)
* May get a segmentation violation
* Use p to index into page table (get frame f)
* May get a page fault (very expensive due to time costing)
* Physical address: concatenate f and offset i

---

## File System