# ST-CS130: Operating Systems

[](https://hackmd.io/sZl5W01XTyCsfOZngy4IFg)

## Basic Concepts
操作系统起着分离运行、幻象（抽象层？）、粘合（高级）的作用
- Process
- Program state
- PC, reg, Execution flag, Stack
- Address Space
- Virtual mem <-> Physical mem
- Thread
- Protect
- Multi
- Run one another one based on virtual address on CPU
- Frequently switch instead of real multiprocessing
- Dual-mode
- user mode and priviliged mode
- Isolation

## Process Management

### Diff between thread and process
- 线程共享 static 区
- 进程切换会更改 static 和 regs
- 进程是线程的超集

### Content Switch
https://zh.wikipedia.org/zh-cn/%E4%B8%8A%E4%B8%8B%E6%96%87%E4%BA%A4%E6%8F%9B

- low cost (compated to endless load addr and save word )

一般来说，进程有三个状态, running, waiting, terminated
在操作系统执行的过程中，进程在进程池中等待，当一个进程在 running 的时候，可以发出 interrupt 信号，此时进程被放回 waiting 或者 terminated

而在现实的场景中，对于一块架构良好的 computer, 在 aaa ~ xxx KB 的位置有一块 RoM， 其中写入了固定数据，也就是 bootloader， 从 bootloader 启动操作系统。现代机器会用 UEFI 或者 ACPH 提供一层抽象

而对于操作系统的终止，通过一个电路将 CPU 的某个 reg (可能是 EFREG ) 改值， 寄存器归零，从而让操作系统从 PC = 0 的地方重新执行， 或者接从启动内存处通过 bootloader 重新启动

### Thread-init
之前所说, Thread 有三个状态，在 time interupt 的时候通过检查 cpu-time-ticks 来切换 thread 的三个状态


- 注意资源锁
- 倒数计数
- 中断 (interupt) -> context switch
- thread scheduling: FIFO /

### Concurrency
- Isolated and run one after another, there's no hazard and race in CPU and Address
- Issues in synchronization (the order of excecution)
- The operation is atomic
- Run -> Choose -> Store old -> Load new
- Let system et control of the CPU
- yield (volunteerly)
- exit it
- All process will see itself as running even if the system has suspended it.

### Fork
It could be better to understand by
[Fork Bomb](https://zh.wikipedia.org/zh-hans/Fork%E7%82%B8%E5%BC%B9)

1）在父进程中，fork返回新创建子进程的进程ID；

2）在子进程中，fork返回0；

3）如果出现错误，fork返回一个负值；
### Creation of a New Thread
- `ThreadFork()` create a new thread and places it on ready queue
- Point to application routine (fcnPtr)
- Pointer to array of arguments (FcnArgPtr)
- Size of stack to allocate
- Allocate new Stack and TCB
- Initialize thr registers field
- Update `PC` and `ra`
- `run_new_thread()` will select this TCB and return into beginning of `ThreadRoot()`

### Concurrency
- Independent Threads
- Scheduling doesn't matter
- Cooperating Threads
- Many to one: 阻塞 / 空间利用率高
- One-to-One: 效率高，overhead大
- Many-to-Many: difficult
- 2-Level Model
- pthreads

### Thread Pool
- alloc exsiting (pre-allocated) threads to programmes in the pool

### Atomic Operations
- Mutex
- Socket

### Lock
lock the critical section and do the critical section, then unlock the section, so that others can access the section
No one can access unless the **lock release** (when leaving)
- Procesure
- lock
- unlock
- wait if locked
- Only mem r/w are atomic
- Hardware support: disable the interupt (e.g. Intel 486 https://blog.csdn.net/qq_43401808/article/details/86592677)
- 原子操作
- 上锁的过程也是原子的，因此需要 disable interupt

milklock.Acquire();
if (nomik)
    buymilk();
milklock.Lock();

### Create a thread

### Switch a thread
- deadlock: a thread stucked in the wait list
- Busy waiting
- Pros: works and no race
- Cons:
- inefficient
- Waiting thread may take cycles away from thread holding lock (no one wins!)
- **Priority Inversion**: If busy-waiting thread has higher priority than thread holding lock if no progress!

- Spin locks:
- when leave, release the lock
- ...

- Semaphore
- P(): wait => wait() => 等红灯
- if (>0) -1 and dosomething
- V(): wake a P => signal() => 绿灯
- +1
- initialized value: how many processes run at once
- 优先级捐赠: https://github.com/Yefancy/Pintos/issues/4 and https://blog.terrychan.me/2016/pintos-1-3

### Deadlock and Starvation
- Deadlock means a Starvation, starvation doesn't mean there's a deadlock
- 死锁的发生是由于资源的争抢 (resource contention)
#### Banker's Algorithm
- Request resources: Wait
- Get resources: release after a certain time
- 记录有多少个进程
- 一共有多少资源 （e.g. `vcpu`）
- 记录每个资源有多少
- 记录每个资源的总量 （const）
- 记录每个进程分配了什么资源
- 记录每个进程需要什么资源
- https://zh.wikipedia.org/wiki/银行家算法
- `If Request[i] <= Need[i]: Raise ERROR`
- `If Request[i] > Available[i]: Wait()`
-

     if Request[i] <= Available[i] :
         Available[i] -= Request[i];
         Allocation[i] += Request[i];
         Need[i] -= Request[i];

- 这样可以避免死锁 （资源没有争抢），同时便于资源回收与调度
- 前提假设是，每个资源都会自我了解，否则这个系统就是不安全的 (这样排队的 （Need Matrix）就永远等不到了)

### Scheduling Algorithms


- Waiting Time
- Average WaitingTime
- Average Completion Time (Burst time + waiting time)
- Goals
- minimize Response Time
- Maximize Throughput (reduce context switch)
- Fair
#### FIFO
- The process won't be interupted, run one until done.
- Non-preemptive algorithm
- Convoy Effect: short process behind long process cause big avg completion time
- **Bad for small jobs**
#### Round-Robin
- Each run a small time, do A then switch to do B
- When time spilit $q$ is large, its limitation is FCFS
- When $q$ is small, a hardware called Hyper Threading will support, Interleaved (CPU do context-switch and cause large overhead)
- so $q$ should be a medium value
- Pros: Fair, Fair and Fair
- Cons: overhead for context switch, with the increasement of jobs
#### Priority
Problem:
- Starvation
- Deadlock

Solution:
- Dynamic priorities
- Adjust base-level priority up or down based on heuristics about
- 意思就是长时间不动就降优先级

- [SRTF](https://en.wikipedia.org/wiki/Shortest_remaining_time)
#### Multilevel Queue
- queues (e.g. system processes) with own scudule
- Scheduling done between the queues
- fixed priority
- possibility of starvation

- MultiLevel Feedback Queue
- a process can move between queues
- 
- 
- 

#### Real-Time scheduling

## 期中复习
- basic knowleage about OS
- Process (include preseduo code, Concurrency, Scheduling)

### 同步
- deadlock

       wait(A)
       wait(B)
       // do something
       // release both

       wait(B)
       wait(A)
       // do something
       // release both

Then Programme A hold lock A wait B.
Programme B hold B wait A.
They can't cotinue.
- starvation

And
- bound buffer
- [https://en.wikipedia.org/wiki/Producer%E2%80%93consumer_problem](https://en.wikipedia.org/wiki/Producer%E2%80%93consumer_problem)
- Readers-Writers
- [https://blog.csdn.net/ValDC_Morning/article/details/73434006](https://blog.csdn.net/ValDC_Morning/article/details/73434006)
- dining philosopher
- [https://en.wikipedia.org/wiki/Dining_philosophers_problem](https://en.wikipedia.org/wiki/Dining_philosophers_problem)
- Basic solution is use **Monitor** to **periodly** check or pick down

### Process
- Create

## Address Space
- Seg:
- 0: code
- 1: data
- 2: shared
- 3: stack
- Offset:偏移
- Base:对应的物理内存底端
- Limit:对应的物理内存顶端
- Valid/N:
- Error:不能超过 Limit
- Physical Address: 物理内存-虚拟内存是物理内存的抽象
- Access Error:

So, a 32-bit operating system means that it has the reg which len 32, and address space of a maximum $2^{32}$B


### Memory Sharing
Using Page table to map the virtual address to the same physical address

### Multi-step Processing of a Program for Execution
Compile -> Load -> Execute
### Prevent from multi-programming
Use **Base_addr** and **Limit_addr** to ensure the range of vmem.
### Translation box (Memory Management Unit or MMU) converts between the two views
### B&B Method
- Not every process is same size → memory becomes fragmented over time
- Missing support for sparse address space
- Would like to have multiple chunks/program (Code, Data, Stack, Heap, etc)
- Hard to do inter-process sharing
- Want to share code segments when possible
- Want to share memory between processes
- Helped by providing multiple segments per process
### More Flexible Segmentation
- Each segment (Stack, Heap, Code, Data ...) is given region of contiguous memory
- 
- 
### Example
### Paging
### 2-Level Paging
### Multi-Level Paging

## Cacheing TLB
### PTE
#### Demand Paging
- Keep only active pages in memory
- Place others on disk and mark their PTEs invalid
#### Copy on Write
- UNIX fork gives copy of parent address space to child
- Address spaces disconnected after child created
- How to do this cheaply
- Make copy of parent’s page tables (point at same memory)
- Mark entries in both sets of page tables as read-only
- Page fault on write creates two copies
#### Zero Fill On Demand
- New data pages must carry no information (say be zeroed)
- Mark PTEs as invalid; page fault on use gets zeroed page
- Often, OS creates zeroed pages in background

### Caching Applied to Address Translation

## Demand Paging

## File System
### FAT

### iNode