计算机操作系统

1、计算机操作系统1第二章 进程1、进程的状态运行态：进程占用处理机就绪态：进程能够但是没有占用处理机阻塞态：等待某些事件的发生而不能占用处理机。2第二章 进程1、进程的状态 3第二章 进程2、线程 在传统操作系统中，每个进程中只存在一条控制线索和一个程序计数器，但是在现代操作系统中，提供了对单个进程多条控制线索的支持，这些控制线索通常被称为线程（thread）,有时也称为轻量进程（lightweight process）。 属于统一进程的各个线程共享进程的资源，包括打开的文件和进程虚拟地址空间。4第二章 进程2、线程 线程的实现：在用户空间实现：操作系统内核感觉不到多个线程的存在。效率较高，但是

2、若一个线程阻塞，属于该进程的所有线程也就阻塞了。在核心空间实现：效率较低，但是操作系统内核能够感觉到多个线程的存在。在用户空间和核心空间联合实现。5第二章 进程2、线程 在unix操作系统中，无论在用户空间实现，还是在核心空间实现，都存在一些问题，例如 fork()是复制进程，还是复制线程？ 两个线程同时读写一个设备时如何处理冲突？ 全局变量errno 信号问题 堆栈管理6第二章 进程3、竞争条件 两个或多个进程读写某些共享数据，而最后的结果取决于进程运行的精确时序，这种情况称为竞争条件。7第二章 进程3、竞争条件 一个例子：在银行存钱、取钱假设一个帐号存储在记录M中 存钱 取钱 R1=M R

3、2=M R1=R1+10000 R2=R2-1000 M=R1 M=R28第二章 进程4、临界区 以某种手段确保当一个进程在使用一个共享变量和文件时，其它进程不能做同样的操作，这种情况称为互斥。 对共享内存进行访问的程序片段称作临界区或临界段。如果能够适当地安排使得两个进程不可能同时处于临界区，则就能够避免竞争条件。9第二章 进程4、临界区 进程进入临界区的条件：任何两个进程不能同时处于临界区不应对CPU的速度和数目做出任何假设临界区外的进程不得阻塞其它进程不得使进程在临界区外无休止的等待如果一个进程已进入临界区，其它欲进入临界区的进程必须等待。10第二章 进程4、临界区 进程进入临界区的条件

4、：当进程退出临界区时，如果存在欲进入临界区的进程，应使其进入临界区如果临界区是空闲的，多个进程欲进入临界区，仅仅一个进程被允许进入临界区。不能使欲进入临界区的进程永久的等待。11第二章 进程5、忙等待互斥 一、关中断 进入临界区时关闭中断， 退出临界区时打开中断。 缺点：不应该把开关中断的权利交给用户 关闭中断后，所有进程不能进入任何临界区 仅仅适应单处理机12第二章 进程5、忙等待互斥 二、锁变量和严格轮转法 这两种方法不能实现互斥13 三、peterson解决方案#defiine N 2 /*进程数*/int turn; /*轮到谁了?*/int interestedN; /*所有值初始为

5、0（FALSE）*/void enter_region（int process） /*进程号为0或1*/ int other; /*另一个进程的进程号*/ other=1-process; /*另一个进程*/ interestedprocess=TRUE; /*标识出希望进入临界区*/ turn=process; /*设置标志位*/ while（turn=process&interestedother=TRUE）; /*空语句*/void leave_region（int process） /*process即将离开临界区的进程*/ interestedprocess=FALSE; /*标识将

6、离开临界区*/14第二章 进程5、忙等待互斥 四、TSL指令 将一个存储器中的字读到一个寄存器，然后在该内存地址上存储一个非零值。 该指令执行时，读操作和写操作是不可分割的，即该指令执行完毕以前其它应用程序不能访问处理机。 利用TSL指令很容易实现临界区。15第二章 进程5、忙等待互斥 四、TSL指令在进入临界区前执行enter_region ，退出临界区后执行leave_regionenter_region： tsl register，lock 复制lock到寄存器，并将lock置为1 cmp register，#0 lock等于0吗? jne enter_region 如果不等于0，已上锁

7、，再次循环 ret 返回调用程序，进入临界区leave_region： move lock ， #0 置lock为0 ret 返回调用程序 16第二章 进程5、忙等待互斥 当线程不能运行时，通过忙等待实现互斥，浪费了处理机资源。17第二章 进程6、信号量 信号量是E. W. Dijkstra在1965年提出的一种实现临界区互斥和同步的方法，它使用一个整型变量来累记唤醒次数。一个信号量的值可以为0，表示没有积累下来的唤醒操作；或者为正值，表示有一个或多个被积累下来的唤醒操作。 信号量的两个操作：down操作和up操作18第二章 进程6、信号量 信号量down操作：首先检查信号量的值是否大于零，若

8、是则将其值减一并进程继续运行，若值为零，则进程将睡眠，而且此时DOWN操作并未结束。 检查数值、改变数值、以及可能发生的睡眠操作均作为一个单一的、不可分割的原子操作(atomic action)完成。即保证一旦一个信号量操作开始，则在操作完成或阻塞之前别的进程均不允许访问该信号量。19第二章 进程6、信号量 信号量up操作：UP操作递增信号量的值。如果一个或多个进程在该信号量上睡眠，无法完成一个先前的DOWN操作，则由系统选择其中的一个（例如，随机挑选）并允许其完成它的DOWN操作。 对一个有进程在其上睡眠的信号量执行一次UP操作之后，该信号量的值仍旧是0，但在其上睡眠的进程却少了一个。 递增

9、信号量的值和唤醒一个进程同样也是不可分割的。不会有进程因执行UP而阻塞。20第二章 进程6、信号量：用信号量实现临界区互斥 设置一信号量，信号量初值唯一，进入临界区以前对信号量执行down操作，退出临界区后对信号量执行up操作.21第二章 进程6、信号量：用信号量解决生产者 消费者问题 生产者 消费者问题简介22第二章 进程6、信号量：用信号量解决生产者 消费者问题数据结构#define N 100 /* 缓冲区内槽数 */typedef int semaphone; semaphone mutex =1; /* 控制对临界区的访问 */semaphone empty=N; /* 记录缓冲区内

10、空的槽数 */semaphone full=0; /* 记录缓冲区内满的槽数 */23第二章 进程6、信号量：用信号量解决生产者 消费者问题生产者void producer（void） int item; while（TRUE） /* TRUE为常数1 */ produce_item（&item）; /* 产生一个需放入缓冲区的数据项 */ down（&empty）; /* 递减空槽数 */ down（&mutex）; /* 进入临界区 */ enter_item（item）; /* 将一个新数据项放入缓冲区 */ up（&mutex）; /* 离开临界区 */ up（&full）; /* 递

11、增满槽数 */ 24第二章 进程6、信号量：用信号量解决生产者 消费者问题消费者void consumer（void） int item; while（TRUE） /* 无限循环 */ down（&full）; /* 递减满槽数 */ down（&mutex）; /* 进入临界区 */ remove_item（&item）; /* 从缓冲区中取走一个数据项 */ up（&mutex）; /* 离开临界区 */ up（&empty）; /* 递增空槽数 */ consume_item（item）; /* 对数据项进行操作 */ 25第二章 进程7、管程和条件变量 Hoare（1974）和Brin

12、ch Hansen（1975）提出了一种高级的同步原语，称为管程( monitor )。一个管程是一个由过程、变量及数据结构等组成的一个集合，它们组成一个特殊的模块或软件包。进程可在任何需要的时候调用管程中的过程，但它们不能在管程外的过程中直接访问管程内的数据结构。26第二章 进程7、管程和条件变量 管程有一个很重要的特性，任一时刻管程中只能有一个活跃进程。 使管程能有效地完成互斥，只要把临界区代码放在管程中即可。27第二章 进程7、管程和条件变量 管程提供了一种实现互斥的简便途径，但这还不够，还需要一种办法以使得进程在无法继续运行时被阻塞。 例如，在生产者消费者问题中，很容易将针对缓冲区满和

13、缓冲区空的测试放到管程的过程中，但是生产者在发现缓冲区满的时候如何阻塞? 28第二章 进程7、管程和条件变量 解决方法在于引入条件变量(condition variables)，及相关的两个操作：WAIT和SIGNAL。当一个管程过程发现它无法继续时（例如，生产者发现缓冲区满），它在某些条件变量上执行WAIT，如full。这个动作引起调用进程阻塞。它也允许另一个先前被挡在管程之外的进程现在进入管程。 另一个进程，如消费者，可以通过对其伙伴正在其上等待的一个条件变量执行SIGNAL来唤醒正在睡眠的伙伴进程。为避免管程中同时有两个活跃进程，我们需要一条规则来通知在SIGNAL之后该怎么办。Hoar

14、e建议让新唤醒的进程运行，而挂起另一个进程。Brinch Hansen则建议要求执行SIGNAL的进程必须立即退出管程。换言之，SIGNAL语句只可能作为一个管程过程的最后一条语句。我们将采纳Brinch Hansen的建议，因为它在概念上更简单，并且更容易实现。如果在一个条件变量上正有若干进程等待，则对该条件变量执行SIGNAL操作，调度程序将在其中选择一个使其恢复运行。 29第二章 进程7、管程和条件变量 另一个进程，如消费者，可以通过对其伙伴正在其上等待的一个条件变量执行SIGNAL来唤醒正在睡眠的伙伴进程。 为避免管程中同时有两个活跃进程，我们需要一条规则来通知在SIGNAL之后该怎么

15、办。 Hoare建议让新唤醒的进程运行，而挂起另一个进程。 Brinch Hansen则建议要求执行SIGNAL的进程必须立即退出管程。换言之，SIGNAL语句只可能作为一个管程过程的最后一条语句。如果在一个条件变量上正有若干进程等待，则对该条件变量执行SIGNAL操作，调度程序将在其中选择一个使其恢复运行。 30第二章 进程7、管程和条件变量：使用管程解决生产者消费者问题数据结构monitor ProducerConsumercondition full，empty;integer count;procedure enter;begin if count=N then wait（full）;

16、 enter_item; count：=count+1; if count=1 then signal（empty）end;31第二章 进程7、管程和条件变量：使用管程解决生产者消费者问题数据结构procedure remove;begin if count=0 then wait（empty）; remove_item; count：=count-1; if count=N-1 then signal（full）; end;count：=0;end monitor; 32第二章 进程8、经典IPC问题：哲学家就餐问题 33第二章 进程8、经典IPC问题：哲学家就餐问题# define N 5

17、 /* 哲学家数目 */# define LEFT （i-1+N）%N /* i的左邻号码 */# define RIGHT （i+1）%N /* i的右邻号码 */# define THINKING 0 /* 哲学家正在思考 */# define HUNGRY 1 /* 哲学家想取得叉子 */# define EATING 2 /* 哲学家正在吃面 */typedef int semaphore; /* 信号量是一个特殊的整型变量 */int stateN; /* 记录每个人状态的数组 */semaphore mutex=1; /* 临界区互斥 */semaphore sN; /* 每个哲学

18、家一个信号量 */34第二章 进程8、经典IPC问题：哲学家就餐问题void philosopher（int i）/* i：哲学家号码，从0到N-1 */ while（TRUE） /* 无限循环 */ think（）; /* 哲学家正在思考 */ take_forks（i）; /* 需要两只叉子，或者阻塞 */ eat（）; /* 进餐 */ put_forks（i）; /* 把两把叉子同时放回桌子 */ 35第二章 进程8、经典IPC问题：哲学家就餐问题void take_forks（int i） /* i：哲学家号码从0到N-1 */ down（&mutex）; /* 进入临界区 */ s

19、tatei=HUNGRY; /* 记录下哲学家i饥饿的事实 */ test（i）; /* 试图得到两只叉子 */ up（&mutex）; /* 离开临界区 */ down（&si）; /* 如果得不到叉子就阻塞 */void put_forks（int I） /* i：哲学家号码从0到N-1 */ down（&mutex）; /* 进入临界区 */ statei=THINKING; /* 哲学家进餐结束 */ test（LEFT）; /* 看一下左邻居现在是否能进餐 */ test（RIGHT）; /* 看一下右邻居现在是否能进餐 */ up（&mutex）; /* 离开临界区 */36第二章

20、 进程8、经典IPC问题：哲学家就餐问题void test（i） /* i：哲学家号码从0到N-1 */ if（statei=HUNGRY&stateLEFT!=EATING&stateRIGHT!=EATING） statei=EATING; up（&si）; 37第二章 进程8、经典IPC问题：读者写者问题当没有进程读写记录时，允许任意进程读写记录。当存在进程读记录时，允许任意其它进程读记录，但是不允许进程写记录。当存在一个进程写记录时，即不允许其它进程读记录，也不允许其它进程写记录。38第二章 进程8、经典IPC问题：读者写者问题typedef int semaphore;semapho

21、re mutex=1; /* 控制对RC的访问 */semaphore db=1; /* 控制对数据库的访问 */int rc=0; /* 正在读或想要读的进程数 */39第二章 进程8、经典IPC问题：读者写者问题void reader（void） while（TRUE） /* 无限循环 */ down（&mutex）; /* 排斥对RC的访问*/ rc = rc+1; /*又多了一个读者*/ if（rc = 1）down（&db）; /*如果这是第一个读者，那么.*/ up（&mutex）; /*恢复对RC的访问*/ read_data_base（）; /*访问数据*/ down（&mut

22、ex）; /*排斥对RC的访问*/ rc = rc -1; /*读者又少了一个*/ if（rc=0）up（&db）; /*如果这是最后一个读者，那么.*/ use_data_read（）; /*非临界区操作*/ 40第二章 进程8、经典IPC问题：读者写者问题void writer（void） while（TRUE） think_up_data（）; /*非临界区操作*/ down（&db）; /*排斥访问*/ write_data_base（）; /*修改数据*/ up（&db）; /*恢复访问*/ 41第二章 进程8、经典IPC问题：理发师睡觉问题42第二章 进程8、经典IPC问题：理发师

23、睡觉问题#define CHAIRS 5 /*为等待的顾客准备的椅子数*/typedef int semaphone ; /*运用你的想象力*/semaphone customers=0; /*等待服务的顾客数*/semaphone barbers=0; /*等待顾客的理发师数*/semaphone mutex=1; /*用于互斥*/int waiting=0; /*等待的顾客（还没理发的）*/43第二章 进程8、经典IPC问题：理发师睡觉问题void barber（void） while（TRUE） down（customers）; /*如果顾客数是0，则睡眠*/ down（mutex）;

24、/*要求进程等待*/ waiting=waiting-1; /*等待顾客数减1*/ up（barbers）; /*一个理发师现在开始理发了*/ up（mutex）; /*释放等待*/ cut_hair（）; /*理发（非临界区操作）*/ 44第二章 进程8、经典IPC问题：理发师睡觉问题void customers（void） down（mutex）; /*进入临界区*/ if（waitingCHAIRS） /*如果没有空的椅子，就离开*/ waiting=waiting+1; /*等待顾客数加1*/ up（customers）; /*如果必要的话，唤醒理发师*/ up（mutex）; /*释

25、放访问等待*/ down（barbers）; /*如果barbers为0，就入睡*/ get_haircut（）; /*坐下等待服务*/ else up（mutex）; /*店里人满了，走吧*/ 45第二章 进程8、经典IPC问题：猴子过桥问题 见第二章习题35（P114）46第二章 进程8、经典IPC问题：猴子过桥问题typedef int semaphore;extern void P(semaphore *s);extern void V(semaphore *s);int rc=0;semaphore read_mutex=1,write_mutex=1,db=1;478、经典IPC问

26、题：猴子过桥问题void left_to_right()p(mutex)for(;)if(on_bridge_number=0)direction=LEFT_TO_RIGHT;if(direction=LEFT_TO_RIGHT)break;waitting_number+;v(mutex);p(left);p(mutex);on_bridge_number+;v(mutex);48 过桥 p(mutex);on_bridge_number-;if(on_bridge_number=0)for(i=0;iwaitting_number;i+)v(right);waitting_number=0;v(mutex)