更新于 

现代操作系统CS2310 （上）进程管理

操作系统基础

  • 关于抽象abstaction
    • （计算机组成的重要概念）
    • 层次化抽象
    • 将系统划分成多个层次，每个层次都对下层屏蔽了具体实现细节，只向上层提供了一组简单的接口，从而简化了系统的设计和维护。
    • 对于计算机系统结构，可以抽象为硬件层、操作系统层、系统程序层、应用程序层、用户层。每个层次都对下层屏蔽了具体实现细节，只提供了一组简单的接口。

  • 虚拟机 (Vitural machines)
    • ==virtualization layer==
      • vitural cpu & memory & devices
  • 什么是计算机操作系统 (Operating system / OS) ？
    • 一种介于计算机用户与计算机应用间的“程序”
    • 一个系统资源的分配者、其它程序的控制者

  • 提供服务

    • GUI
    • program execution
    • IO operations
    • File-system manipulation
    • communications
    • error detection
    • resource allocation
    • accouting
    • protection & security

  • 系统调用 (System Call)

    • OS提供的可编程接口
      • 比如 fork() exit() wait() (unix) 等
    • 比起使用系统调用，OS也向各类服务提供应用程序接口 ( Application program interface / Api) -> 可以视为一种对系统调用的封装和抽象
      • 简单，易移植
      • eg. Win32 API, POSIX API(UNIX, Linux, Mac OS), Java API(JVM)

  • Outline

    • 进程管理
      • 进程/线程/同步/死锁
    • 内存管理
      • 内存/虚拟内存
    • 存储管理
      • 文件系统/大容量存储结构/IO系统
    • 分布式系统结构

进/线程调度

并发 & 并行

  • 并发 Concurrency
    • 时分复用：多个任务在同一时段内共享资源，交替运行

  • 并行 Parallelism (multi-core system)
    • 多个任务在（通过多个处理单元）同一时刻同时执行，互相独立

进程 & 线程

进程 process 线程 threads
独立存在 作为进程子集存在
携带更多状态信息 共享内存.系统资源
独立地址空间 共享地址空间
仅通过IPC通信交互 更多方式
上下文切换比较慢 同进程内切换速度很快
  • 线程是进程内的执行单元，不能独立于进程存在，而只能在进程中产生。
  • 每个线程都共享了进程的地址空间、文件描述符表和其他系统资源。
  • 可以认为正因为线程之间共享了部分资源，如代码段、数据段和文件描述符表等，因此在线程之间进行切换时，不需要像进程切换那样复制和恢复整个地址空间，这使得线程切换速度更快。
  • 同时，由于线程之间共享了相同的地址空间，因此线程之间的通信更加容易和高效。线程可以直接访问同一进程内的共享内存，无需通过进程间通信（IPC）的方式进行数据传递，这减少了通信的开销和复杂性。

用户线程 (user threads) & 核线程 (kernel threads)

  • Many-to-one
    多个用户线程对核隐藏，映射到一个内核级线程上，由内核级线程来执行
    单个用户线程出现问题会导致同组线程都出问题；不能并行运行

  • One-to-one
    高并行支持
    创建kernel thread有开销
    Linux, windows NT/XP/2000, Solaris 9+

  • Many-to-many
    操作系统重构一定数量核线程
    Windows NT with the ThreadFiber package
  • Two-level
    在Many-to-many的基础上运行用户线程与核线程1对1绑定

进程 process

  • 进程 process ( = job 作业)

    • program becomes process when the exe file is loaded into memory
      • 开始运行的程序被载入内存，成为进程（此处的“内存”、之后的“组分”与虚拟内存有关）
    • 1 program can be several processes
      • 一个程序可以产生多个进程

  • 一个进程的组成部分 conposition:

    • 栈 stack
    • …
    • 堆 heap
      • memroy dynamically allocated during run time
    • 数据 data
    • 文本 text
      • programme code

  • PCB (Process control block)

    • state
    • num
    • counter
    • registers
    • mem limits
    • list of open files
    • …
      —> 包含进程的状态;控制;上下文切换;通信和同步;优先级管理信息

  • 进程的状态 process state

  • 一个新的进程的一生：
    • 创建 (new)
    • 就绪 (ready)
      • 进程就绪，等待处理器分配资源
      • 比如CPU正在忙着处理别的进程，可能新的进程就要等待
    • 运行 (run)
      • 执行指令
    • 等待 (wait)
      • 进程未就绪，等待事件的发生或完成
      • 比如等待键盘输入字符
    • 终止 (terminated)
  • CPU的进程切换过程

  • 保存当前进程的上下文(->PCB0)
  • 切换到新进程的上下文(<-PCB1)
  • …更新控制信息，开始执行新进程
  • 结束执行新进程
  • 保存新进程的上下文(->PCB1)
  • 切换到原进程的上下文(<-PCB0)
  • …

CPU调度 cpu scheduling

抢占 preemptive 和 非抢占 nonpreemptive

  • 一个处于Run状态的进程是否可根据调度规则在运行过程中被其它进程中断？
    • 能 -> 抢占式：允许中断
    • 不能 -> 非抢占式：除非进程结束或者进入等待状态，即释放CPU资源，不允许另一个进程获取其CPU资源

什么是CPU调度

在进程的状态发生以下变化时，CPU可能作“调度”决策

  1. run -> wait
  2. run -> ready
  3. wait -> ready (I/O完成等event发生，等待资源分配)
  4. terminates

在1.4时做决策 -> 非抢占 (处理进程的等待和结束)
在2.3时做决策 -> 抢占 (处理新的ready进程)

调度器 Dispatcher

  • 控制CPU

    • 切换上下文
    • 切换进程
    • 切换用户/管理员权限
    • 用户程序重启

  • 调度延迟 Dispatch latency

time it takes for the dispatcher to stop one process and start another running.

调度算法

均为人为定义，可能会有版本差别。
可以将一切调度理解为队列的设计、出入队规则的设计。
一般不标注可抢占时，认为不可抢占。

先有四种基础决策。

FCFS (First-Come, First-Served）

  • Convoy effect - short process behind long process
  • 非常基础和朴素的安排方法
  • 短进程不友好

SJF (P/NP)
Shortest-Job-First

  • 先处理（预估的）总耗时最短的工作
    • SJF(P)
      • -> 先处理（预估的）剩余耗时最短的工作
      • 小心地处理新进程和被抢占的进程的顺序
  • 理论最优解
  • 事实上，难点在于很难预测到底耗时多久（ -> 预测方案）

  • 会导致饥饿

    • 等电梯。你住在高楼层。电梯总优先服务低楼层的人下楼。
    • 低楼层总有人按电梯。
    • 你永远等不到电梯。
    • 类似地，优先级调度也会导致饥饿。

  • Example of SJF (NP)

  • Example of SJF (P)

优先级调度 PS (P/NP)
Priority Scheduling (高度类似SJF，仅更改判断条件)

  • 先处理高优先级进程
  • 注意同优先级进程的处理方式

时间片轮转调度 RR (P/NP)
Round-Robin Scheduling
在RR(quatum=q)算法下，每个进程获得一个时间片time slice，长度为q。

  • 关于q

    • 当取quatum为一个极大的值，相当于FCFS，对短进程不友好
    • 当取quatum为一个极小的值，符合RR的意图，但是会消耗大量时间用于进程切换
    • 需要一个较为合适的取值

  • Example of RR

关于饥饿

  • FCFS 不会导致饥饿
  • SJF, PS均会导致饥饿
  • RR 可以有效避免饥饿

以下为混合决策，更加自定义化，请认真查看题目说明。

多级队列调度 Multilevel Queue Scheduling
multiques, eg. foreground & background

  • each queue has own scheduling algo 每个队列都有独立的出队规则
  • schedule between queues:
    • eg1. fixed prority 规定出队优先级
      • serve all from queue1, then 2
      • may cause starvation
    • eg2. time slice 轮转从两个队列调取进程
      • each queue has a time slice
        …

多级反馈队列 Multilevel Feedback Queue Scheduling
a kind of ↑

  • structure:
    • queues 多少队列
    • each queue’s sche algo 每个队列的出队规则
    • method
      • when to upgrade/demote jobs 任务的转移规则
      • which queue a process will enter when that process needs service 进入时的初始队列
  • classic example:
    Q1(RR(8))->Q2(RR(16))->Q3(FCFS)
    In Q1/Q2, not completed -> degrade and queue
    If not used up and not degrade, requeue ( & get a new time slice)

  • Example of MFQ

锁管理（进程同步）

进程同步 Process Synchronization

  • producer - consumer problem

  • Critical Section Problem

    • 临界资源：每个进程的访问互斥
      (When one process is in critical section, no other processes may be in its critical section)
    • find protocol to solve 防止竞争的==协议==

  • Critical Section

    do {  
    entry section  // 资源保护开始
    	== critical section ==
    exit section  //资源保护结束
    	remainder section  
    } while (TRUE)

  • To solve this

    • Mutual Exclusion 互斥
    • Progress
      • work when OK and don’t postpone indefinitely
    • Bounded Waiting 有限等待
      • Sequential Access 顺序访问

如何实现同步

原语 / 原子操作 Atomic

  • 硬件支持：atomic hardware instructions （原语）
    • Atomic = non-interruptable 不可中断

Test&Set (TAS)
Either test memory word and set value: TestAndSet ()

  • Definition (由硬件实现)

    boolean TestAndSet (boolean *target)  
    {  
    	boolean rv = *target;  
    	*target = TRUE;  
    	return rv:  
    }

  • Example (share bool Lock(False))

    Solution:
    do {
    	while ( TestAndSet ( &lock ))
    	;   // do nothing
    	//    critical section
    	lock = FALSE;
    	//    remainder section
    } while (TRUE)

->(Add bounded-waiting) ：
每个进程在一段时间内只能获取一定次数的testandset操作资源，如果达到阈值，就等待一定时间后再尝试获取

do {  
	waiting[i] = TRUE;  
	key = TRUE;  
	while (waiting[i] && key)  
		key = TestAndSet(&lock);  
	waiting[i] = FALSE;  
		// critical section  
	j = (i + 1) % n;  
	while ((j != i) && !waiting[j])  
		j = (j + 1) % n;  
	if (j == i)  
		lock = FALSE;  
	else  
		waiting[j] = FALSE;  
		// remainder section  
} while (TRUE);

Swap
安全地交换两个内存单元内的数据

  • Example
    do {  
    	key = TRUE;  
    	while ( key == TRUE)  
    		Swap (&lock, &key );  
    			// critical section  
    		lock = FALSE;  
    			// remainder section  
    } while (TRUE);

Mutex

  • 一种轻量级的同步机制
  • 实现两种基本操作：lock和unlock。
  • 在lock()和unlock()之间的临界区域内同一时间只有一个进程可以访问共享资源，其他进程必须等待锁被释放才能进入临界区域。
#include <pthread.h>
pthread_mutex_t mutex;
void *thread_function(void *arg) {
	pthread_mutex_lock(&mutex); // 加锁Mutex 
	// ... critical part
	pthread_mutex_unlock(&mutex); // 解锁Mutex
	// ... remainder 
}

Samophore

  • 一种用于线程同步的机制，可以用于多线程编程中控制访问共享资源。
  • 维护一个计数器和等待队列

Semaphore提供了两个主要的操作：wait（等待）和signal（发信号）。Semaphore的值为整数，初始值可以是任意的正整数，表示可用的资源数目。Semaphore的值只能在wait和signal操作中改变，且改变是原子的，所以可以避免竞态条件。

在C语言中，Semaphore是通过系统提供的sem_t类型来表示的。

  1. wait（等待）：当一个线程想要使用Semaphore代表的共享资源时，它需要调用wait操作。

如果Semaphore的值为正数，则该线程可以使用该资源，同时Semaphore的值减1；
如果Semaphore的值为0，则该线程将被阻塞，直到有其他线程释放资源并增加Semaphore的值为止。

int sem_wait(sem_t *sem);

  1. signal（发信号）：当一个线程使用完Semaphore代表的共享资源时，它需要调用signal操作。

这将增加Semaphore的值，并唤醒等待该Semaphore的线程，以便它们可以继续使用资源。

int sem_post(sem_t *sem);

Semaphore还有其他一些操作，例如初始化、销毁等。在使用Semaphore时，需要注意避免死锁等问题，通常需要仔细考虑线程的同步关系，避免资源竞争等问题。

死锁问题 Deadlock

Deadlock Characterization

  • Mutual exclusion 资源互斥
    同一时间仅有一个进程可以使用某资源
  • Hold and wait
    享有资源的进程等待其它资源
  • No preemption
    不允许抢占其它进程享有的资源
  • Circular wait
    互相等待形成环

哲学家吃饭都拿左边筷子

Resource-Allocation Graph algorithm

-> DEADLOCK AVOIDANCE

通过画资源分配图，检查是否存在死锁，以及确定导致死锁的进程和资源，进而解除死锁 (avoidance) ; 也可以用于避免死锁（在分配前检查是否可能导致死锁）

  • 用资源分配图可以表示当前的资源和进程关系

  • 常用于每个资源仅有1instance的情况（多个instance时，环路和死锁未必相关）

  • V:

    • P: P1,P2… (process list)
    • R: R1,R2… (resource list)
  • E:
    • request edges 请求边 ( process -> resource )
    • assignment edges 分配边 ( resource -> process )

  • 通过图判断死锁

    • 无环 -> no deadlock
    • 有环 ->
      • 1 instance / resource type -> 死锁
      • ->1 instance / … -> 死锁可能性

  • 升级的资源分配图

    • Each process must a priori claim maximum use
    • claim edge 有向虚线：进程P可能请求资源R （P->R）
    • request edge 实线（P->R）
    • assignment edge 实线 （R->P）

  • 只有当将需求边转换为分配边不会导致分配图中环的形成时，这个请求才会被允许。

Safe mode & safe sequence

Safe mode

  • 在分配请求发生时检查是否这一请求是否使得系统处于安全模式（存在安全队列）以预防死锁

  • Defination:

  • 系统中每个进程都能够按照它所需的顺序获得资源，执行完自己的任务并释放资源，而不会发生死锁。

    • If Pi’s resource needs are not immediately available, then Pi can wait until all Pj have finished
    • When all Pj are finished, Pi can obtain needed resources, execute, return allocated resources, and terminate
    • When Pi terminates, Pi+1 can obtain its needed resources, and so on
    • Otherwise, system is in unsafe state

  • 安全模式 -> 无死锁

  • 非安全模式 -> 有可能死锁
    • starvation 饥饿 …
  • Avoidance -> 确保系统不会进入非安全状态

    Safe sequence 安全队列

  • eg: available resource = 3
    | |maximum needs|holds|needs|
    |—|—|—|—|
    |P0|10|5|5|
    |P1|4|2|2|
    |P2|9|2|7|
Avai P1+ P1- P0+ P0- P2+ P2-
3 1 5 0 10 3 12

P1 -> P0 -> P2
每一步寻找可运行的process，完成后释放process和它的所有资源。
如果找不到可运行的process，则出现unsafe state。

The banker’s algorithm

  • 适用于资源有mutiple instances的情况

  • Defination
    n = number of processes
    m = number of resources types.

  • Available: Vector of length m. 

    If available\[j] = k, there are k instances of resource type Rj available
  • Max: n x m matrix. 
    If Max\[i,j] = k, then process Pi may request at  most k instances of resource type Rj
  • Allocation: n x m matrix. 
    If Allocation\[i,j] = k then Pi is currently allocated k instances of Rj

  • Need: n x m matrix. 

    If Need\[i,j] = k, then Pi may need k more instances of Rj to complete its task 
Need\[i,j] = Max\[i,j] – Allocation\[i,j]**

  • The algorithm

    1. work := available, finish[i] = false
    2. find i that
      • finish[i] = false
      1. need[i] <= work
      2. if i = -1, go to 4
    3. work = work + allocation[i], finish[i] = true, go to 2
    4. if finish[i] = true for all i -> ok, else !ok

Simulation
+P1->[2,1,0]->-P1->[5,3,2]
+P3->[5,2,1]->-P3->[7,4,3]
+P0->[0,0,0]->-P0->[7,5,3]
+P2->[1,5,3]->-P2->[10,5,5]
+P4->[12,2,4]->-P4->[10,5,7]

Sum up: deadlock handling

PREVENTION

-> restrain the ways request can be made
shown in [deadlock characterization]

AVOIDANCE

入职检查
Whenever a process requests a resource, the request is granted only if the allocation leaves the system in a safe state.

Help system to add priori info

  • Prepare for checking: each process declare max of resources needed
  • Dynamically check if there’ll be circular-wait condition
    • be defined by available/allocated resourvces, max demands of processes
    • safe state checking (bank algo/…) ; circle check
DETECTION

similar to avoidance

RECOVERY

  • precess termination 进程终结

    • 一次终结所有/逐个终结直至死锁解除

  • resource preemption 资源抢占

    • 允许从一个或多个死锁进程中抢占资源
    • selecting a victim / rollback 回滚
    • 可能导致饥饿

评论区仅供交流~