2

Transcription

1 操作系统 2. 进程 (Processes) 和线程 (Threads) 任课教师 : 熊焰 黄 文超

2 进程是什什么? 需求 矛盾 : 需要在 一台电脑上 同时 执 行行多个任务 但 一个 CPU 同 一时刻只能 一个任务 如果让 用户 自 己去切换任务, 太难

3 进程是什什么? 进程是程序执 行行时的 一个实例例 A process is just an instance of an executing program 它包括 程序计数器器 (Program Counter, PC) 寄存器器 (Registers) 相关的变量量 (Variables) 所以, 看起来, 每个进程都拥有 一个虚拟的 CPU

4 进程是什什么? 进程的简单切换 One program counter A B C Process switch A Four program counters B C D Process D C B A D Time (a) (b) (c) Figure 2-1. (a) Multiprogramming four programs. (b) Conceptual model of four independent, sequential processes. (c) Only one program is active at once.

5 进程是什什么? 进程与程序的区别? 进程 是 一个动态的概念, 而程序是 一个静态的代码 块 不不同的进程可以执 行行同 一个程序 每 一个进程都有 自 己的 生命期 等等

6 进程的创建 哪些事件会触发进程的创建? System initialization. Execution of a process-creation system call by a running process. A user request to create a new process. Initiation of a batch job.

7 查看进程的 方法 进程的创建 tips Windows: 任务管理理器器 Unix: ps 命令 创建进程的系统调 用 Unix: fork( ) Windows: CreateProcess()

8 进程的创建 创建之后 一个 父进程, 一个 子进程 两个进程各 自维护 自 己的地址空间 ( 相互独 立 ) 无法共享可写的内存 ( 有的系统共享可读内存, 如程序的内容 )

9 进程的终 止触发终 止的条件 Normal exit (voluntary). exit(0), ExitProcess() Error exit (voluntary). exit(n) 例例 : 试试 cc foo.c Fatal error (involuntary). Killed by another process (involuntary).

10 进程的层次结构 Unix 由 父进程 生成 子进程..., 形成 一个进程组 Windows 没有进程组的概念, 为每个 生成的进程分配 一个 Handle 作为标识

11 进程的状态 运 行行状态 Running Blocked 阻塞状态 4 Ready 就绪状态

12 进程的状态 Processes 0 1 n 2 n 1 Scheduler

13 进程的实现 进程控制块 (Process Control Blocks, PCB), 里里 面包含 一系列列需维护的 数据 : program counter (PC) stack pointer (SP) memory allocation status of its open files 等等 作 用 :After each interrupt the interrupted process returns to precisely the same state it was in before the interrupt occurred

14 进程的实现 Process management Memory management File management Registers Pointer to text segment info Root directory Program counter Pointer to data segment info Wor king director y Program status word Pointer to stack segment info File descriptors Stack pointer User ID Process state Group ID Pr ior ity Scheduling parameters Process ID Parent process Process group Signals Time when process started CPU time used Children s CPU time Time of next alarm

15 CPU 的利利 用率 CPU utilization = 1 p n CPU utilization (in percent) % I/O wait 50% I/O wait 80% I/O wait Degree of multiprogramming

16 线程 进程 每个进程控制着 一块独 立的地址空间 可不不可能有多个 进程 ( 线程 ) 来控制同 一块地址空间? 需要线程的理理由 : 有些是 用多进程所 无法描述的 更更轻量量级 创建 切换 撤销 运 行行效率 多 CPU 并 行行的 支持

17 线程 Four score and seven years ago, our fathers brought forth upon this continent a new nation: conceived in liberty, and dedicated to the proposition that all men are created equal. Now we are engaged in a great civil war testing whether that nation, or any nation so conceived and so dedicated, can long endure. We are met on a great battlefield of that war. We have come to dedicate a portion of that field as a final resting place for those who here gave their lives that this nation might live. It is altogether fitting and proper that we should do this. But, in a larger sense, we cannot dedicate, we cannot consecrate we cannot hallow this ground. The brave men, living and dead, who struggled here have consecrated it, far above our poor power to add or detract. The world will little note, nor long remember, what we say here, but it can never forget what they did here. It is for us the living, rather, to be dedicated here to the unfinished work which they who fought here have thus far so nobly advanced. It is rather for us to be here dedicated to the great task remaining before us, that from these honored dead we take increased devotion to that cause for which they gave the last full measure of devotion, that we here highly resolve that these dead shall not have died in vain that this nation, under God, shall have a new birth of freedom and that government of the people by the people, for the people Keyboard Kernel Disk Figure 2-7. A word processor with three threads.

18 线程 Web server process Dispatcher thread Worker thread User space Web page cache Kernel Kernel space Network connection

19 线程 while (TRUE) { while (TRUE) { get next request(&buf); wait for work(&buf) handoff work(&buf); look for page in cache(&buf, &page); } if (page not in cache(&page)) read page from disk(&buf, &page); retur n page(&page); } (a) (b) Figure 2-9. A rough outline of the code for Fig (a) Dispatcher thread. (b) Worker thread.

20 线程 Model Threads Single-threaded process Finite-state machine Characteristics Parallelism, blocking system calls No parallelism, blocking system calls Parallelism, nonblocking system calls, interr upts 第三种 方法, 当没有线程的 支持时, 需 人为地保存每 个请求的状态

21 线程 经典的线程模型 Process 1 Process 2 Process 3 Process User space Thread Thread Kernel space 特点 : Kernel (a) Kernel (b) 多个线程共享同 一个地址空间 但是, 每个线程各 自执 行行 自 己的任务, 因此也有各 自独 立的状态

22 线程 经典的线程模型 Per-process items Address space Global var iables Open files Child processes Pending alarms Signals and signal handlers Accounting infor mation Per-thread items Program counter Registers Stack State 线程间共享了了哪些资源? 线程间各 自维护着什什么状态?

23 线程 经典的线程模型 Thread 2 Thread 1 Thread 3 Process Thread 1's stack Thread 3's stack Kernel Figure Each thread has its own stack.

24 线程 POSIX 线程 #include <pthread.h> #include <stdio.h> #include <stdlib.h> #define NUMBER OF THREADS 10 void * pr int hello world(void * tid) { / * This function prints the thread s identifier and then exits. * / pr intf("hello World. Greetings from thread %d\n", tid); pthread exit(null); }

25 线程 POSIX 线程 int main(int argc, char * argv[]) { / * The main program creates 10 threads and then exits. * / pthread t threads[number OF THREADS]; int status, i; for(i=0; i < NUMBER OF THREADS; i++) { pr intf("main here. Creating thread %d\n", i); status = pthread create(&threads[i], NULL, print hello world, (void * )i); } if (status!= 0) { pr intf("oops. pthread create returned error code %d\n", status); exit(-1); } } exit(null);

26 线程 用户级线程 Process Thread Process Thread User space Kernel space Kernel Kernel Run-time system Thread table Process table Process table Thread table Figure (a) A user-level threads package. (b) A threads package managed by the kernel.

27 线程 用户级线程 主要特点或区别 : 将整个线程模块放在 用户空间, 内核不不参与管理理线程 优点 : 即使操作系统不不原 生 支持多线程, 也可以通过 自 己编写来实现 ( 比如写个库函数来 支持 ) 切换线程时速度更更快, 不不需要 用户态与内核态的切换 可以 自 己来定义线程的调度算法 可扩展性强 ( 内核所维护的空间受限, 类似于栈空间受限 )

28 线程 用户级线程 难题 : 如何在 用户态中实现阻塞模式 非常困难 一种替代 方法是将 一些操作变成 非阻塞模式 ( 如 read) 另 一种 方法是提前判断下 一个操作是否会阻塞 如何实现线程的切换 运 行行线程需要主动放弃线程 灾难性的问题 : 编程 人员其实只关 心本软件的线程, 但如果其它应 用需要的线程却更更多, 而且频繁阻塞, 怎么办?

29 线程 内核级线程 由内核来保存线程所对应的寄存器器 状态值 及其它信息 缺点 Process Thread 由于系统 ( 内核 ) 调 用, 效率 优点 相对更更低 因为系统调 用, 降低了了编程难 度 Kernel 不不需要使 用 非阻塞 的命令 Process table Thread table

30 线程 内核级线程 问题 1: 当 一个拥有多线程的进程调 用 fork()? 调 用 fork(), 会复制该进程, 生成 子进程 那么, 它拥有的线程也要复制么? 答 : 看情况 问题 2: 一个信号对应多个线程, 怎么办?

31 线程 混 用 用户级与内核级 Multiple user threads on a kernel thread User space Kernel Kernel thread Kernel space Figure Multiplexing user-level threads onto kernel-level threads.

32 进程间通信 InterProcess Communication (IPC) 例例 子 管道 (example: ls -l less ) 滴滴打 车和 支付宝... 三个问题 : 进程之间怎么互传消息? 多个进程不不能 同时 使 用同 一个资源 ( 互斥 ) 资源调度和分配

33 进程间通信 竞态条件 (Race Condition) 两个或多个进程对共享的数据进 行行读或写的操作时, 最终的结果取决于这些进程的执 行行顺序 4 Spooler directory abc out = 4 Murphy s Law: Anything that can go wrong will go wrong Process A 5 6 prog.c prog.n 7 in = 7 Process B 这种情况下, 如何进 行行调试?

34 进程间通信 临界区 (Critical Region) 如何避免 Race condition? 一种 方案 : 禁 止多个进程同时使 用同 一个资源 即 : 互斥 (Mutual exclusion) 那么, 一个程序可以分为两类的 片段 第 一类 片段, 其操作 一定不不会导致互斥, 第 二类 片段, 其操作可能导致互斥 第 二类 片段称之为临界区 (Critical Region, or Critical Section) 进 一步, 我们怎样约束临界区?

35 进程间通信 临界区 (Critical Region) 一个好的 方案应该满 足的条件 任何两个进程不不能同时处于其临界区 ( 阻塞条件 ) 不不应对 CPU 的速度或数量量做任何前提假设 ( 上下 文 ) 临界区外运 行行的进程不不得阻塞任何进程 ( 非阻塞条件 ) 不不得使 用进程 无限期等待进 入临界区 ( 死锁 )

36 进程间通信 临界区 (Critical Region) A enters critical region A leaves critical region Process A B attempts to enter critical region B enters critical region B leaves critical region Process B B blocked T 1 T 2 T 3 T 4 Time

37 进程间通信 实现互斥 忙等 (Busy Waiting) 笨 方法 : 屏蔽中断 (Disabling Interrupts) 当访问临界资源时, 关闭时钟, 没有时钟提示, 则 不不会引起进程切换 缺点 如果始终不不打开中断, 其它进程就 无法运 行行

38 进程间通信实现互斥 忙等 (Busy Waiting) 一个错 方法 : 锁变量量 (Lock Variables) 初始值为 0 如果有进程想进 入临界区, 先看看这个变量量是否为 0 如果为 0, 则设为 1, 离开临界区后, 再设为 0 如果为 1, 则等待 致命问题 : 这个变量量也是互斥的, 访问该变量量的代码也是临界区 ( 看书中例例 子 )

39 进程间通信 实现互斥 忙等 (Busy Waiting) 另 一个 方法 : 严格轮换法 (Strict Alternation) while (TRUE) { while (TRUE) { while (turn!= 0) / * loop * / ; while (turn!= 1) cr itical region( ); cr itical region( ); / * loop * /; tur n = 1; tur n = 0; noncr itical region( ); noncr itical region( ); } } (a) (b) 优点 :turn 已不不是互斥资源, 不不存在竞态条件 此类变量量称为 spin lock ( 自旋锁 ) 缺点 :1, 死循环 (busy-waiting, 忙等 ); 2, 过于严格 ;3, 违背条件 3

40 进程间通信 实现互斥 忙等 (Busy Waiting) Peterson 的解法 (1981) #define FALSE 0 #define TRUE 1 #define N 2 / * number of processes * / int turn; / * whose turn is it? * / int interested[n]; / * all values initially 0 (FALSE) * /

41 进程间通信 实现互斥 忙等 (Busy Waiting) Peterson 的解法 (1981) void enter region(int process); { / * process is 0 or 1 * / int other; / * number of the other process * / } other = 1 process; / * the opposite of process * / interested[process] = TRUE; / * show that you are interested * / tur n = process; / * set flag * / while (turn == process && interested[other] == TRUE) / * null statement * /; void leave region(int process) { / * process: who is leaving * / interested[process] = FALSE; } / * indicate departure from critical region * /

42 进程间通信实现互斥 忙等 (Busy Waiting) TSL 指令 TSL RX, LOCK Test and Set Lock (1) 从 lock 地址读取 一个值,(2) 并将另 一个 非0 值存 入lock 这两个操作不不可以被分割 ( 要么都执 行行, 要么都不不执 行行 )

43 进程间通信 实现互斥 忙等 (Busy Waiting) enter region: TSL REGISTER,LOCK copy lock to register and set lock to 1 CMP REGISTER,#0 was lock zero? JNE enter region if it was not zero, lock was set, so loop RET retur n to caller; critical region entered leave region: MOVE LOCK,#0 RET store a 0 in lock retur n to caller

44 进程间通信 实现互斥 忙等 (Busy Waiting) XCHG 指令 enter region: MOVE REGISTER,#1 XCHG REGISTER,LOCK CMP REGISTER,#0 JNE enter region RET put a 1 in the register swap the contents of the register and lock var iable was lock zero? if it was non zero, lock was set, so loop retur n to caller; critical region entered leave region: MOVE LOCK,#0 RET store a 0 in lock retur n to caller Figure Entering and leaving a critical region using the XCHG instruction.

45 进程间通信 回顾 一下 老老的 方案 屏蔽中断 : 很不不灵活 有问题的 方案 锁变量量 : 出现运 行行错误 严格轮换法 : 违背条件 3 没有问题但低效的 方案 : Peterson 方案,TSL 或 XCHG 的实现 低效的原因 :Busy waiting ( 忙等 死循环 )

46 进程间通信 睡眠与唤醒 (Sleep and Wakeup) sleep, wakeup 系统调 用 sleep 调 用 sleep 之后, 进程变为阻塞状态 wakeup 调 用 wakeup(sb), sb 进程进 入就绪状态

47 进程间通信 生产者 - 消费者问题 两个进程共享同 一个缓存 生产者 : 一个进程 生产数据, 放 入缓存中 消费者 : 一个进程消费数据, 从缓存中取数据 要求 : 缓存满时, 生产者不不能再 生产数据 缓存空时, 消费者不不能再消费数据

48 进程间通信 生产者 - 消费者问题 #define N 100 / * number of slots in the buffer * / int count = 0; / * number of items in the buffer * / void producer(void) { int item; } while (TRUE) { / * repeat forever * / item = produce item( ); / * generate next item * / if (count == N) sleep( ); / * if buffer is full, go to sleep * / inser t item(item); / * put item in buffer * / count = count + 1; / * increment count of items in buffer * / if (count == 1) wakeup(consumer); / * was buffer empty? * / }

49 进程间通信 生产者 - 消费者问题 void consumer(void) { int item; } while (TRUE) { / * repeat forever * / if (count == 0) sleep( ); / * if buffer is empty, got to sleep * / item = remove item( ); / * take item out of buffer * / count = count 1; / * decrement count of items in buffer * / if (count == N 1) wakeup(producer); / * was buffer full? * / consume item(item); / * pr int item * / }

50 进程间通信 生产者 - 消费者问题 问题 :count 也是互斥资源 void producer(void) { int item; void consumer(void) { int item; } while (TRUE) { item = produce item( ); if (count == N) sleep( ); 2 inser t item(item); count = count + 1; if (count == 1) wakeup(consumer); } } 1 3 Sleep forever while (TRUE) { if (count == 0) sleep( ); item = remove item( ); count = count 1; if (count == N 1) wakeup(producer); consume item(item); } 如果是多个 生产者和多个消费者, 则问题更更难

51 进程间通信 信号量量 (semaphore) 解决之前的问题 : 将前 面的 count 值与互斥资源的操作合在 一起, 形成 一种 原 子操作 ( 不不可被拆分的操作 ) 信号量量可表示为某互斥资源的可使 用个数 对消费者 而 言, 信号量量为 count 值 对 生产者 而 言, 信号量量为 (N-count) 信号量量的值可以为 0, 也可以为 一个常数 信号量量的操作 :down(semaphore), up(semaphore)

52 进程间通信信号量量 (semaphore) down(s),or P(s) (Proberen) if s >0, then s=s-1; if s==0, then sleep(); up(s), or V(s) (Verhogen) if s==0 && 有 sleep 进程 then 将其中 一个进程唤醒 if s==0 && 没有 sleep 进程,then s=s+1 if s>0, then s=s+1 < 原 子操作, 不不可分割 >

53 进程间通信 续 : 临界区 semaphore s=1; enter_region() { down(s); } leave_region() { up(s); }

54 进程间通信 续 : 生产者 - 消费者问题 #define N 100 / * number of slots in the buffer * / typedef int semaphore; / * semaphores are a special kind of int * / semaphore mutex = 1; / * controls access to critical region * / semaphore empty = N; / * counts empty buffer slots * / semaphore full = 0; / * counts full buffer slots * / void producer(void) { int item; } while (TRUE) { / * TRUE is the constant 1 * / item = produce item( ); / * generate something to put in buffer * / 1 down(&empty); / * decrement empty count * / down(&mutex); 2 / * enter critical region * / inser t item(item); / * put new item in buffer * / 1 up(&mutex); / * leave critical region * / up(&full); / * increment count of full slots * / } 2

55 进程间通信 续 : 生产者 - 消费者问题 void consumer(void) { int item; } while (TRUE) { / * infinite loop * / down(&full); 1 / * decrement full count * / 2 down(&mutex); / * enter critical region * / item = remove item( ); / * take item from buffer * / up(&mutex); 1 / * leave critical region * / 2 up(&empty); / * increment count of empty slots * / consume item(item); / * do something with the item * / }

56 大作业 : 生产者与消费者问题 作业 : 用Java 程序模拟 生产者与消费者问题 提交 文档 源代码 可执 行行程序 另外, 调整 1 与 2 之间的顺序, 在 文档中说明运 行行结果有什什么不不同 提交形式 : 使 用群功能中的 作业, 在相应地址提交 文件命名 : 学号 + 姓名 + 版本号 ( 提交 文件 无法撤消 ) 提交截 止时间 : 考试之前 ( 第 16 周 )

57 进程间通信 信号量量的两种 用途 互斥 (mutual exclusion) 多个进程争夺同 一个资源使 用权, 如 mutex, 如 文件的读写 同步 (synchronization) 多个进程相互协作, 保证任务按秩序完成, 如 full, empty

58 进程间通信 管程 (Monitor) 想正确使 用信号量量, 并不不容易易 Hansen (1973), Hoare (1974) 提出了了更更 高层的原语 : monitor ( 管程 ) 管程是什什么? 管程是 一个模块, 其中包含 一组过程 变量量和数据结构 管程可以被进程所调 用, 但管程内的数据不不可以被直接操 作

59 进程间通信 管程 (Monitor) monitor example integer i; condition c; procedure producer( );. end; procedure consumer( );... end; end monitor;

60 管程的 一个重要特征 : 进程间通信 管程 (Monitor) 无论何时, 管程内只允许 一个过程是活跃的 ( 就绪或运 行行 ) 如果已经有 一个活跃的过程, 那么, 加 入新的过程时, 新加 入的过程阻塞, 直 至其它过程离开管程 如果没有任何活跃的过程, 那么, 新的过程可以直接加 入 好处 : 很容易易实现互斥 (Mutex) 问题 : 如何实现同步? 使 用 condition variable, wait(), signal()

61 进程间通信 管程 (Monitor) conditional variable 类似信号量量 相关操作 wait(c) 类似 down() signal(c) 类似 up()

62 进程间通信管程 (Monitor) condition variable c, wait(c), signal(c) 的不不同点 condition variable 本身不不绑定资源数 目, 取 而代之, procedure 对资源数 目进 行行判断 wait(c) 不不判断 c 的 大 小, 直接将被调 用进程阻塞 由于该 procedure 阻塞, 可将另 一被阻塞进程激活 signal(c) 不不判断 c 的 大 小, 可以直接将之前被 wait(c) 阻塞的进程激活

63 进程间通信 管程 (Monitor) 但是, 问题来了了, 由于管程中, 同时只有 一个激活的进程, 调 用 signal(c) 时, 调 用 signal(c) 的 procedure 和 wait(c) 可能同时处于激活状态 解决 方案 一 :Hoare 方案 wait(c) 对应进程激活,signal(c) 对应进程阻塞 解决 方案 二 :Hansen 方案 增加约束 :signal(c) 语句句仅能出现在 procedure 的最后 一 行行

64 进程间通信 管程 (Monitor) monitor ProducerConsumer condition full, empty; integer count; procedure insert(item: integer); begin if count = N then wait(full); insert item(item); count := count + 1; if count =1then signal(empty) end; function remove: integer; begin if count =0then wait(empty); remove = remove item; count := count 1; if count = N 1 then signal(full) end; count := 0; end monitor; procedure producer; begin while true do begin item = produce item; ProducerConsumer.insert(item) end end; procedure consumer; begin while true do begin item = ProducerConsumer.remove; consume item(item) end end;

65 进程间通信 管程 (Monitor) 管程在 Java 中的近似实现 synchronized method 没有 conditional variable wait() 和 notify() == sleep() 和 wakeup(), 但仅 限于 synchronized method

66 进程间通信 管程 (Monitor) public class ProducerConsumer { static final int N = 100; // constant giving the buffer size static producer p = new producer( ); // instantiate a new producer thread static consumer c = new consumer( ); // instantiate a new consumer thread static our monitor mon = new our monitor( ); // instantiate a new monitor public static void main(string args[ ]) { p.star t( ); // star t the producer thread c.star t( ); // star t the consumer thread } static class producer extends Thread {

67 static class producer extends Thread { public void run( ) { // run method contains the thread code int item; while (true) { // producer loop item = produce item( ); mon.inser t(item); } } pr ivate int produce item( ) {... } // actually produce } static class consumer extends Thread { public void run( ) { run method contains the thread code int item; while (true) { // consumer loop item = mon.remove( ); consume item (item); } } pr ivate void consume item(int item) {... } // actually consume }

68 static class our monitor { // this is a monitor pr ivate int buffer[ ] = new int[n]; pr ivate int count = 0, lo = 0, hi = 0; // counters and indices } public synchronized void insert(int val) { if (count == N) go to sleep( ); // if the buffer is full, go to sleep buffer [hi] = val; // inser t an item into the buffer hi = (hi + 1) % N; // slot to place next item in count = count + 1; // one more item in the buffer now if (count == 1) notify( ); // if consumer was sleeping, wake it up } public synchronized int remove( ) { int val; if (count == 0) go to sleep( ); // if the buffer is empty, go to sleep val = buffer [lo]; // fetch an item from the buffer lo = (lo + 1) % N; // slot to fetch next item from count = count 1; // one few items in the buffer if (count == N 1) notify( ); // if producer was sleeping, wake it up retur n val; } pr ivate void go to sleep( ) { try{wait( );} catch(interr uptedexception exc) {};}

69 进程间通信 管程 (Monitor) 管程的优点 : 相对信号量量, 更更不不易易出错 管程的缺点 非系统调 用, 而是语 言层次的接 口 不不能完成两台机器器之间的进程通信

70 进程间通信消息传递 (Message Passing) 系统调 用 : send(destination, &message) receive(source, &message) 它考虑了了很多前述机制没考虑或不不需考虑的问题 : 消息丢失 重传 重复消息 身份认证 效率相对更更低, 怎样优化?

71 进程间通信消息传递 (Message Passing) 实现消息传递的 几种 方式 使 用数据结构 mailbox 来进 行行缓存 完全不不使 用缓存 send 执 行行时, 阻塞, 直 至receive 执 行行 receive 执 行行时, 阻塞, 直 至send 执 行行 这种模式称之为 rendezvous ( 会合 )

72 进程间通信 消息传递 (Message Passing) #define N 100 void producer(void) { int item; message m; } while (TRUE) { item = produce item( ); receive(consumer, &m); build message(&m, item); send(consumer, &m); } } void consumer(void) { int item, i; message m; for (i = 0; i < N; i++) send(producer, &m) while (TRUE) { receive(producer, &m); item = extract item(&m); send(producer, &m); consume item(item); }

73 调度 (Scheduling) 当多个进程竞争使 用 CPU, 怎么办? CPU 使 用不不存在竞争条件问题 但有些进程对 CPU 使 用会有特殊的要求 如批处理理 或 GUI 等 进程切换也不不能过于频繁

74 调度 (Scheduling) 进程的 行行为特征 计算密集型 (compute-bound) (a) Long CPU burst Short CPU burst Waiting for I/O (b) IO 密集型 (IO-bound)

75 调度 (Scheduling) 何时需要调度 创建进程 如 : 父进程和 子进程中, 哪个设为运 行行状态? 进程退出 进程阻塞 I/O 中断 基于时钟的调度 非抢占式调度 (nonpreemtive) 抢占式调度 (preemtive)

76 调度 (Scheduling) 调度算法的分类 批处理理 交互式 实时

77 调度 (Scheduling) 算法 目标 All systems Fair ness - giving each process a fair share of the CPU Policy enforcement - seeing that stated policy is carried out Balance - keeping all parts of the system busy Batch systems Throughput - maximize jobs per hour Turnaround time - minimize time between submission and termination CPU utilization - keep the CPU busy all the time Interactive systems Response time - respond to requests quickly Propor tionality - meet users expectations Real-time systems Meeting deadlines - avoid losing data Predictability - avoid quality degradation in multimedia systems

78 调度 (Scheduling) 批处理理系统中的调度 先来先服务 (First-Come, First Served) 易易懂, 但 : 如果第 一个作业是 长作业?

79 调度 (Scheduling) 批处理理系统中的调度 最短作业优先 (Shortest Job First) A B C D B C D A 如果 4 个作业同时到达, 则平均周转时间为 mean turnaround time time a, the second a (4a + 3b + 2c + d)/4.

80 调度 (Scheduling) 批处理理系统中的调度 最短剩余时间调度 (Shortest Remaining Time Next) tip: 最短作业优先的抢占式版本 : 如果新的进程需 更更短时间, 则运 行行新的进程

81 调度 (Scheduling) 交互式系统中的调度 轮转调度 (Round-Robin Scheduling) Current process Next process Current process B F D G A F D G A B 每个进程被分配 一个时间 片段, 简称时间 片 (quantum) 当从 一个进程切换到另 一个进程时, 称这个过程为进程切换 (process switch) 或上下 文切换 (Context Switch)

82 调度 (Scheduling) 交互式系统中的调度 如果设计时间 片的 长短? 进程切换 (Process Switch) 需要额外时间 如果时间 片太短, 则切换时占据时间 比例例较 大 如果时间 片太 长, 则后 面的进程等待时间较 长 一般情况下, 时间 片 长度设置为 20~50msec

83 调度 (Scheduling) 交互式系统中的调度 优先级调度 (Priority scheduling) 每个进程都有优先级 大 小, 挑选最 高优先级的进程 运 行行 例例 : 家 用 PC 中, 邮件进程与视频播放进程

84 调度 (Scheduling) 交互式系统中的调度 优先级调度 (Priority scheduling) 如何设置优先级 : 静态设置 军队中, 根据军衔 商 用计算中 心, 根据收费价格 Unix 中,nice 命令 动态设置 针对 I/O 密集型的进程

85 调度 (Scheduling) 交互式系统中的调度 Queue headers Runnable processes Priority 4 (Highest priority) Priority 3 Priority 2 Priority 1 (Lowest priority)

86 调度 (Scheduling) 交互式系统中的调度 多级队列列 (Multiple Queues) 如果进程切换代价 高, 且 I/O 密集型和 CPU 密集型进程混杂 则多级队列列, 每个队列列中, 进程占有的时间 片 长度 不不 一样

87 调度 (Scheduling) 交互式系统中的调度 最短进程优先 (Shortest Process Next) 作 用类似于最短作业优先 把每个命令当成 一个独 立的进程 怎样预估命令的占据时间? at 0 + (1 a)t 1 T 0, T 0 /2 + T 1 /2, T 0 /4 + T 1 /4 + T 2 /2, T 0 /8 + T 1 /8 + T 2 /4 + T 3 /2

88 调度 (Scheduling) 交互式系统中的调度 保证调度 (Guaranteed Scheduling) 彩票调度 (Lottery Scheduling) 公平分享调度 (Fair-Share Scheduling)

89 调度 (Scheduling) 实时系统中的调度 硬实时 必须满 足的绝对的截 止时间 软实时 偶尔会错过截 止时间, 尽管不不希望如此

90 经典 IPC 问题 哲学家就餐问题 死锁问题 (DeadLocks) 与饿死问题 (Starvation)

91 经典 IPC 问题 哲学家就餐问题 #define N 5 / * number of philosophers * / void philosopher(int i) / * i: philosopher number, from 0 to 4 * / { while (TRUE) { think( ); / * philosopher is thinking * / take fork(i); / * take left for k * / take fork((i+1) % N); / * take right for k; % is modulo operator * / eat( ); / * yum-yum, spaghetti * / put fork(i); / * put left for k back on the table * / put fork((i+1) % N); / * put right for k back on the table * / } } Figure A nonsolution to the dining philosophers problem.

92 经典 IPC 问题 哲学家就餐问题 #define N 5 #define LEFT (i+n 1)%N #define RIGHT (i+1)%n #define THINKING 0 #define HUNGRY 1 #define EATING 2 typedef int semaphore; int state[n]; semaphore mutex = 1; semaphore s[n]; void philosopher(int i) { while (TRUE) { think( ); take forks(i); eat( ); put forks(i); } }

93 经典 IPC 问题 哲学家就餐问题 void take forks(int i) { down(&mutex); state[i] = HUNGRY; test(i); up(&mutex); down(&s[i]); } void put forks(i) { down(&mutex); state[i] = THINKING; test(left); test(right); up(&mutex); } void test(i) / * i: philosopher number, from 0 to N 1 * / { if (state[i] == HUNGRY && state[left]!= EATING && state[right]!= EATING) { state[i] = EATING; up(&s[i]); } }

94 经典 IPC 问题 读者 写者问题 有多个进程同时对 一个 文件或数据库进 行行读写, 有如 下规则 可以同时存在多个读者 也可以同时存在 一个写者 但在有写者的情况下, 不不可有其它的读者或写者

95 经典 IPC 问题 读者 写者问题 typedef int semaphore; / * use your imagination * / semaphore mutex = 1; / * controls access to rc * / semaphore db = 1; / * controls access to the database * / int rc = 0; / * # of processes reading or wanting to * /

96 经典 IPC 问题 读者 写者问题 void reader(void) { while (TRUE) { down(&mutex); rc = rc + 1; if (rc == 1) down(&db); up(&mutex); read data base( ); down(&mutex); rc = rc 1; if (rc == 0) up(&db); up(&mutex); use data read( ); } } void writer(void) { while (TRUE) { think up data( ); down(&db); wr ite data base( ); up(&db); } }

97 死锁问题 (Deadlocks) 资源的类型 可抢占资源 (preemptable resource) 不不可抢占资源 (nonpreemptable resource)

98 死锁问题 (Deadlocks) 如果进程 A lock 资源 R1, 进程 B lock 资源 R2, 与此 同时,A 尝试 lock R2, B 尝试 lock R1, 则 A 和 B 都处 于阻塞状态, 这种情况可称为死锁 下 面是 一种正式的定义 : A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause.

99 typedef int semaphore; semaphore resource 1; semaphore resource 1; semaphore resource 2; semaphore resource 2; void process A(void) { void process A(void) { down(&resource 1); down(&resource 1); down(&resource 2); down(&resource 2); use both resources( ); use both resources( ); up(&resource 2); up(&resource 2); up(&resource 1); up(&resource 1); } } void process B(void) { void process B(void) { down(&resource 1); down(&resource 2); down(&resource 2); down(&resource 1); use both resources( ); use both resources( ); up(&resource 2); up(&resource 1); up(&resource 1); up(&resource 2); } } (a) (b) Figure 6-2. (a) Deadlock-free code. (b) Code with a potential deadlock.

100 死锁问题 引起死锁的四个必要条件 1. 互斥条件 2. 占有和等待条件 3. 不不可抢占条件 4. 环路路等待条件

101 死锁问题 死锁建模 A S D T U R B C (a) (b) (c) Figure 6-3. Resource allocation graphs. (a) Holding a resource. (b) Requesting a resource. (c) Deadlock.

102 死锁问题 死锁建模 A Request R Request S Release R Release S (a) B Request S Request T Release S Release T (b) C Request T Request R Release T Release R (c) 1. A requests R 2. B requests S 3. C requests T 4. A requests S 5. B requests T 6. C requests R deadlock A R B S C T A R B S C T A R B S C T (d) (e) (f) (g) A B C A B C A B C R S T R S T R S T (h) (i)

103 死锁问题 死锁建模 A Request R Request S Release R Release S B Request S Request T Release S Release T C Request T Request R Release T Release R 1. A requests R 2. C requests T 3. A requests S 4. C requests R 5. A releases R 6. A releases S no deadlock A R (a) B S C T A R (b) B S C T A R B S (c) C T (k) (l) (m) (n) A B C A B C A B C R S T R S T R S T (o) (p) (q)

104 死锁问题 鸵 鸟算法 (Ostrich Algorithm) 把头埋在沙 子 里里, 假装没这个问题

105 死锁问题 死锁检测 (Deadlock Detection) 如果每种类型的资源只有 一个 : R A B C S D T E D T E F U V U V W L =[R, A, S ]. G (a) G (b) L =[B, T, E, V, G, U, D].

106 死锁问题 死锁检测 (Deadlock Detection) 如果每种类型的资源不不 止 一个 : 定义 : 现有资源向量量 E (existing resource vector) 可 用资源向量量 A (available resource vector) 当前分配矩阵 C (current allocation matrix) 请求矩阵 R ( request matrix) n Σ C ij + A j = E j i=1 C 11 C 21 C n1 Resources in existence (E 1, E 2, E 3,, E m ) Current allocation matrix C 12 C 22 C n2 C 13 C 23 C n3 C 1m C 2m C nm Row n is current allocation to process n R 11 R 21 R n1 Resources available (A 1, A 2, A 3,, A m ) Request matrix R 12 R 22 R n2 R 13 R 23 R n3 R 1m R 2m R nm Row 2 is what process 2 needs

107 死锁问题死锁检测 (Deadlock Detection) 如果每种类型的资源不不 止 一个 : 检测算法 : 1. 寻找 一个没有标记的进程 Pi, 其对应的第 i 行行的 R 向量量 小于或等于 A, (Ri<=A) 2. 如果找到该进程,A=A+Ci, 标记该进程,goto step 1 3. 如果没有找到该进程, 程序终 止 终 止后, 如果存在未标记的进程, 则死锁

108 死锁问题 死锁检测 (Deadlock Detection) Tape drives Plotters Scanners E = ( ) Blu-rays Tape drives Plotters Scanners A = ( ) Blu-rays Current allocation matrix Request matrix C = R = A = ( ) A = ( ) no deadlock uation of Fig.

109 死锁问题 死锁恢复 (Recovery from Deadlock) 利利 用抢占恢复 (Recovery through Preemption) 利利 用回滚恢复 (Recovery through Rollback) 通过杀死进程恢复 (Recovery through Killing Processes)

110 死锁问题 死锁避免 (Deadlock Avoidance) 资源轨迹图 Printer I 8 B u (Both processes finished) I 7 I 6 t Plotter I 5 r s p q I 1 I 2 I 3 I 4 A Printer Plotter

111 死锁问题死锁避免 (Deadlock Avoidance) 安全状态和不不安全状态 Has Max Has Max Has Max Has Max Has Max A 3 9 A 3 9 A 3 9 A 3 9 A 3 9 B 2 4 B 4 4 B 0 B 0 B 0 C 2 7 C 2 7 C 2 7 C 7 7 C 0 Free: 3 (a) Free: 1 (b) Free: 5 (c) Free: 0 (d) Free: 7 (e) Figure 6-9. Demonstration that the state in (a) is safe. A B C Has Max Has Max Has Max Has Max A B C A B C A B C Free: 3 (a) Free: 2 (b) Free: 0 (c) Free: 4 (d)

112 死锁问题 单个资源的银 行行家算法 (Banker s Algorithm) Has Max Has Max Has Max A 0 6 A 1 6 A 1 6 B 0 5 B 1 5 B 2 5 C 0 4 C 2 4 C 2 4 D 0 7 D 4 7 D 4 7 Free: 10 Free: 2 Free: 1 (a) (b) (c) Figure Three resource allocation states: (a) Safe. (b) Safe. (c) Unsafe.

113 死锁问题 多个资源的银 行行家算法 (Banker s Algorithm) Process Tape drives Plotters Printers Blu-rays A B C Process Tape drives Plotters Printers Blu-rays A B C E = (6342) P = (5322) A = (1020) D E Resources assigned D E Resources still assigned

114 死锁问题 死锁预防 (Deadlock Prevention) 死锁避免是难以实现的!

115 死锁问题 死锁预防 (Deadlock Prevention) 破坏互斥条件 破坏占有和等待条件 破坏不不可抢占条件 破坏环路路等待条件 Condition Mutual exclusion Hold and wait No preemption Circular wait Approach Spool ev erything Request all resources initially Take resources away Order resources numer ically

116 死锁问题 两阶段锁 (Two-Phase Locking) 第 一阶段, 尝试给所需资源上锁 如果成功, 则进 入第 二阶段 如果不不成功, 释放所有锁 第 二阶段, 使 用资源, 结束后, 释放所有锁

117 作业 2.5, 2.9, 2.18, 2.45, 2.55, 2.54, , 6.14, 6.22, 6.26