ST-CS130: Operating Systems

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/上下文交換

• 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

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

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
• Readers-Writers
  • https://blog.csdn.net/ValDC_Morning/article/details/73434006
• dining philosopher
  • 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