软件技术基础 (11)处理器管理2

1、NO：1 第四章第四章 操作系统操作系统4.2 4.2 处理器管理处理器管理 阅读者写入者问题阅读者写入者问题 一些读者和一些写者对同一黑板进行读写。多个读者一些读者和一些写者对同一黑板进行读写。多个读者可同时读黑板，但一个时刻只能有一个写者，读者、写者可同时读黑板，但一个时刻只能有一个写者，读者、写者不能同时使用黑板。不能同时使用黑板。 分析：分析： 对于读者来说：对于读者来说： 1) 无读者、写者，新读者可以读无读者、写者，新读者可以读 2) 有写者等，但有其他读者正在读，则新读者也可以读有写者等，但有其他读者正在读，则新读者也可以读 3) 有写者，新读者等有写者，新读者等 对于写者来说：

2、对于写者来说： 1) 无读者，新写者可以写无读者，新写者可以写 2) 有读者，新写者等待有读者，新写者等待 3) 有其他写者，新写者等待有其他写者，新写者等待NO：2 第四章第四章 操作系统操作系统设置设置2个信号量，个信号量，w控制谁使用黑板，控制谁使用黑板，mutex保护临界区，保护临界区，初值都为初值都为1读者：读者：P(mutex)Readcount+if(Readcount=1)P(w)V(mutex)读数据读数据P(mutex)Readcount - -if(readcount=0)V(w)写者：写者：P(w)写数据写数据V(w)V(mutex)上述方法其实是上述方法其实是”读者优

3、先读者优先”，只要有一个读者，就允许其后只要有一个读者，就允许其后的读者访问数据。如果一直有的读者访问数据。如果一直有新的读者陆续到来，写者将被新的读者陆续到来，写者将被严重推迟。严重推迟。NO：3为了防止为了防止”读者优先读者优先”导致的导致的写者饥饿写者饥饿，可以考虑，可以考虑写者优先写者优先。当共享区被读者占用时，后续紧邻到达的读者可以继续进入。当共享区被读者占用时，后续紧邻到达的读者可以继续进入。若此时有一个写者到来且阻塞等待，则写者后面到来的若干若此时有一个写者到来且阻塞等待，则写者后面到来的若干读者全部阻塞等待。读者全部阻塞等待。换句话说，只要有一个写者申请写数据，则不允许新的读者

4、换句话说，只要有一个写者申请写数据，则不允许新的读者进入读数据。这样，写者只需等先于它到来的读者完成其读进入读数据。这样，写者只需等先于它到来的读者完成其读数据，就可以写入。数据，就可以写入。 第四章第四章 操作系统操作系统4.2 4.2 处理器管理处理器管理NO：4读者进程读者进程 写者进程写者进程 P(z) P(y) P(rsem) writecount+ P(x) if writecount = 1 readcount+ P(rsem) if readcount = 1 V(y) P(wsem) P(wsem) V(x) : V(rsem) : V(z) 写数据写数据 : : 读读 :

5、: V(wsem) P(x) P(y) readcount- writecount- if readcount = 0 if writecount=0 V(wsem) V(rsem) V(x) V(y)x 互斥对互斥对readcount访问访问y 互斥对互斥对writecount访问访问rsem 当至少有当至少有1个写进程申请个写进程申请写数据时，互写数据时，互斥新的读进程斥新的读进程读数据读数据z rsem阻塞队阻塞队列仅允许一个列仅允许一个读者排队等待，读者排队等待，其后来的读者其后来的读者将在信号量将在信号量z的的阻塞队列中等阻塞队列中等待待NO：5一个简单例子：一个简单例子：/Defi

6、ne a global variable. long g_x = 0;DWORD WINAPI ThreadFunc1(PVOID pvParam) g_x+; return(0); DWORD WINAPI ThreadFunc2(PVOID pvParam) g_x+; return(0); 第四章第四章 操作系统操作系统线程同步问题线程同步问题MOV EAX, g_xINC EAX MOV g_x, EAXNO：6 第四章第四章 操作系统操作系统线程同步问题线程同步问题 两个线程不可能在完全相同的时间内执行这个代码。因两个线程不可能在完全相同的时间内执行这个代码。因此，如果一个线程在另一

7、个线程的后面执行这个代码，那么此，如果一个线程在另一个线程的后面执行这个代码，那么下面就是实际的执行情况：下面就是实际的执行情况： MOV EAX, g_x ; Thread 1INC EAX MOV g_x, EAX MOV EAX, g_x ; Thread 2INC EAX MOV g_x, EAX当两个线程都将当两个线程都将 g _ x 的值递增之的值递增之后，后， g _ x 中的值就变成了中的值就变成了2。 但但 Wi n d o w s是个是个抢占式抢占式多线程环境。多线程环境。一个线程可以随时中断运行，而另一一个线程可以随时中断运行，而另一个线程则可以随时继续执行个线程则可以随

8、时继续执行。 NO：7 第四章第四章 操作系统操作系统线程同步问题线程同步问题MOV EAX, g_x ; Thread 1INC EAX ; Thread 1MOV EAX, g_x ;Thread 2INC EAX ;Thread 2MOV g_x, EAX ;Thread 2MOV g_x, EAX ;Thread 1如果代码按这种形式来运行，如果代码按这种形式来运行， g _ x中的最后值就不是中的最后值就不是2，而是，而是1。 编译器生成代码的方法，哪个编译器生成代码的方法，哪个C P U在执行这个代码，以在执行这个代码，以及主计算机中安装了多少个及主计算机中安装了多少个C P U等

9、因素，决定了产生的结果等因素，决定了产生的结果可能是不同的。这就是该环境的运行情况，我们对此无能为力。可能是不同的。这就是该环境的运行情况，我们对此无能为力。但是，但是， 操作系统确实提供了一些函数，如果正确地使用这些操作系统确实提供了一些函数，如果正确地使用这些函数，就能确保产生应用程序的代码得到的结果。函数，就能确保产生应用程序的代码得到的结果。 NO：8多个线程同时访问同一个全局变量，如果都是读取操作，则多个线程同时访问同一个全局变量，如果都是读取操作，则不会出现问题。如果不会出现问题。如果一个线程负责一个线程负责改变改变此变量的值此变量的值，而，而其他其他线程负责线程负责同时读取同时读

10、取变量内容变量内容，则不能保证读取到的数据是经，则不能保证读取到的数据是经过写线程修改后的。过写线程修改后的。为了确保读线程读取到的是经过修改的变量，就必须在为了确保读线程读取到的是经过修改的变量，就必须在向变量向变量写入数据时禁止其他线程对其的任何访问写入数据时禁止其他线程对其的任何访问，直至赋值，直至赋值过程结束后再解除对其他线程的访问限制。象这种保证线程过程结束后再解除对其他线程的访问限制。象这种保证线程能了解其他线程任务处理结束后的处理结果而采取的保护措能了解其他线程任务处理结束后的处理结果而采取的保护措施即为线程同步。施即为线程同步。 第四章第四章 操作系统操作系统VC+ 对线程同步

11、的处理对线程同步的处理NO：9临界区（临界区（Critical Section）是一段独占对某些共享资源访问的是一段独占对某些共享资源访问的代码，在任意时刻代码，在任意时刻只允许一个线程只允许一个线程对共享资源进行访问。如对共享资源进行访问。如果有多个线程试图同时访问临界区，那么在有一个线程进入果有多个线程试图同时访问临界区，那么在有一个线程进入后其他所有试图访问此临界区的线程将被挂起，并一直持续后其他所有试图访问此临界区的线程将被挂起，并一直持续到进入临界区的线程离开。临界区在被释放后，其他线程可到进入临界区的线程离开。临界区在被释放后，其他线程可以继续抢占，并以此达到用以继续抢占，并以此达

12、到用原子方式原子方式操作共享资源的目的。操作共享资源的目的。 第四章第四章 操作系统操作系统4.2 4.2 处理器管理处理器管理NO：10临界区在使用时以临界区在使用时以CRITICAL_SECTION结构对象保护结构对象保护共享资源，并分别用共享资源，并分别用EnterCriticalSection（）（）和和LeaveCriticalSection（）（）函数去标识和释放一个临界区。所用函数去标识和释放一个临界区。所用到的到的CRITICAL_SECTION结构对象必须经过结构对象必须经过InitializeCriticalSection（）（）的初始化后才能使用，而且必须的初始化后才能使

13、用，而且必须确保所有线程中的任何试图访问此共享资源的代码都处在此确保所有线程中的任何试图访问此共享资源的代码都处在此临界区的保护之下。否则临界区将不会起到应有的作用，共临界区的保护之下。否则临界区将不会起到应有的作用，共享资源依然有被破坏的可能。享资源依然有被破坏的可能。 第四章第四章 操作系统操作系统4.2 4.2 处理器管理处理器管理NO：11例：通过例：通过两个线程两个线程来分别对来分别对全局变量全局变量g_cArray10进行写入进行写入操作，用临界区结构对象操作，用临界区结构对象g_cs来保持线程的同步，并在开启来保持线程的同步，并在开启线程前对其进行初始化。线程前对其进行初始化。为

14、了使实验效果更加明显，体现出临界区的作用，在线程函为了使实验效果更加明显，体现出临界区的作用，在线程函数对共享资源数对共享资源g_cArray10的写入时，以的写入时，以Sleep（）函数延迟（）函数延迟1毫秒，使其他线程同其抢占毫秒，使其他线程同其抢占CPU的可能性增大。如果不使的可能性增大。如果不使用临界区对其进行保护，则共享资源数据将被破坏，而使用用临界区对其进行保护，则共享资源数据将被破坏，而使用临界区对线程保持同步后则可以得到正确的结果。临界区对线程保持同步后则可以得到正确的结果。 第四章第四章 操作系统操作系统4.2 4.2 处理器管理处理器管理NO：12 第四章第四章 操作系统操

15、作系统4.2 4.2 处理器管理处理器管理2 进程通信进程通信进程间的通信机制（进程间的通信机制（IPC），就是多进程间相互通讯、交还），就是多进程间相互通讯、交还信息的方法。信息的方法。Linux中提供了下面几种通信机制。中提供了下面几种通信机制。 管道（管道（pipe） 命名管道（命名管道（FIFO） System V机制，包括消息队列、信号量和共享内存机制，包括消息队列、信号量和共享内存 网络网络socket方式方式NO：13 第四章第四章 操作系统操作系统4.2 4.2 处理器管理处理器管理 管道通信管道通信 PIPE管道就是将一个进程的管道就是将一个进程的标准输出标准输出和另一个进程

16、的和另一个进程的标准输入标准输入联联系到一起，以供二个进程互相通信的方法。系到一起，以供二个进程互相通信的方法。当一个进程创建了管道时，系统内核为使用管道准备了当一个进程创建了管道时，系统内核为使用管道准备了二个二个文件描述符文件描述符，一个用于管道输入，也就是，一个用于管道输入，也就是往管道写入往管道写入数据；数据；另一个用户管道输出，也就是另一个用户管道输出，也就是从管道读出从管道读出数据。数据。用户进程用户进程fd0fd1管道管道内内 核核NO：14 第四章第四章 操作系统操作系统4.2 4.2 处理器管理处理器管理管道只能用于有管道只能用于有相同祖先相同祖先的进程之间的通信，通常是一个

17、进的进程之间的通信，通常是一个进程创建管道后，调用程创建管道后，调用fork函数创建子进程，而这个管道就是函数创建子进程，而这个管道就是用于用于父进程和子进程间的通信父进程和子进程间的通信。int fd2;int fd2;pid_t pid;pid_t pid;.if ( if ( pipe(fd)pipe(fd) 0) printf(stderr, pipe error); exit(1); 0) printf(stderr, pipe error); exit(1); if (if (pid=fork()pid=fork()0) printf(stderr, fork error); ex

18、it(1); ) 0pid 0) /) /* *父进程父进程* */ / close( close(fd0fd0); write(); write(fd1fd1, how are you ?n, 12);, how are you ?n, 12);else /else /* * 子进程子进程 * */ / close( close(fd1fd1); n= read(); n= read(fd0fd0, line, MAXLINE); , line, MAXLINE); . 管道是半双工方式，如果要父子双方互相传递数据，需要建立二道管道管道是半双工方式，如果要父子双方互相传递数据，需要建立二道管

19、道NO：15 第四章第四章 操作系统操作系统4.2 4.2 处理器管理处理器管理 命名管道命名管道 FIFO命名管道又叫命名管道又叫先进先出队列先进先出队列，类似于前面介绍的管道。但可，类似于前面介绍的管道。但可用于没有任何联系的进程间通信（不局限于父子进程之间）用于没有任何联系的进程间通信（不局限于父子进程之间）管道管道PIPE是在内核中存储的，程序运行结束后不复存在，而是在内核中存储的，程序运行结束后不复存在，而命名管道命名管道FIFO是作为是作为特殊设备文件特殊设备文件存储在文件系统中。除非存储在文件系统中。除非删除该文件，否则不会消失。删除该文件，否则不会消失。命名管道创建：命名管道创

20、建： int mkfifo ( const char * pathname, mode_t mode); int mknod ( char * pathname, mode_t mode, dev_t dev); NO：16 第四章第四章 操作系统操作系统4.2 4.2 处理器管理处理器管理命名管道的应用命名管道的应用 : 简单的客户服务器模式简单的客户服务器模式 服务器打开一个所有客户进程都可以访问的命名管道，服务器打开一个所有客户进程都可以访问的命名管道，通过这个管道接收客户进程的信息。通过这个管道接收客户进程的信息。服务器服务器客户都可访客户都可访问的问的FIFOreadread客客 户

21、户客客 户户writewritewritewriteNO：17 第四章第四章 操作系统操作系统4.2 4.2 处理器管理处理器管理 System V IPC机制机制三种机制：三种机制：消息队列消息队列、信号量信号量、共享内存共享内存 消息队列消息队列：消息队列是一条由消息连接而成的链表，它消息队列是一条由消息连接而成的链表，它保存在内核中，通过消息队列的引用标识符来访问。保存在内核中，通过消息队列的引用标识符来访问。 创建或打开消息队列创建或打开消息队列 int msgget( key_t key, int flag ); 向消息队列发送消息向消息队列发送消息 int msgsnd(int m

22、sqid, const void *ptr, size_t nbytes, int flag); 从消息队列中接收消息从消息队列中接收消息 int msgrcv(int msqid, void *ptr, size_t nbytes, long type, int flag);NO：18 第四章第四章 操作系统操作系统4.2 4.2 处理器管理处理器管理 信号量信号量：与先前与先前PV操作中的相同，实际上是个整数计数操作中的相同，实际上是个整数计数器，用来控制多个进程对共享资源的访问。器，用来控制多个进程对共享资源的访问。 创建信号量创建信号量 int semget( key_t key, i

23、nt flag ); 对信号量操作对信号量操作 int semop(int semid, struct sembuf semoparray, size_t nops); int semctl(int sem_id, int semnum, int cmd,/*union semun arg*/); NO：19 第四章第四章 操作系统操作系统4.2 4.2 处理器管理处理器管理 共享内存：共享内存：多个进程共享一块内存，达到交换信息的目的。多个进程共享一块内存，达到交换信息的目的。由于没有中间介质，如消息队列、管道等延迟，数据直接由由于没有中间介质，如消息队列、管道等延迟，数据直接由内存映射到进

24、程空间。是目前内存映射到进程空间。是目前速度最快速度最快的一种进程通信机制。的一种进程通信机制。 使用是需要一定的同步机制来控制多个进程对同一块内存使用是需要一定的同步机制来控制多个进程对同一块内存的读写。常常和信号量控制结合在一起使用。的读写。常常和信号量控制结合在一起使用。NO：20 第四章第四章 操作系统操作系统4.2 4.2 处理器管理处理器管理3 死锁死锁 两个或两个以上的进程中的每一个都在等待其中另一个进两个或两个以上的进程中的每一个都在等待其中另一个进程释放资源而被封锁，它们都无法向前推进，这种现象称为程释放资源而被封锁，它们都无法向前推进，这种现象称为死锁死锁。 死锁问题是一种

25、具有普遍性的现象，日常生活中屡见不鲜。死锁问题是一种具有普遍性的现象，日常生活中屡见不鲜。例如例如北北北北南南西西车队死锁问题车队死锁问题NO：21 第四章第四章 操作系统操作系统4.2 4.2 处理器管理处理器管理在计算机系统中，这种现象比较多。进程产生死锁是因在计算机系统中，这种现象比较多。进程产生死锁是因竞争资竞争资源源而引起的，与而引起的，与执行顺序执行顺序有关。如将车队视为进程，马路视为有关。如将车队视为进程，马路视为资源，在计算机系统中有各种资源，如外设、数据、文件等资源，在计算机系统中有各种资源，如外设、数据、文件等例如系统有两个进程例如系统有两个进程P1 和和P2，以及一个打印

26、机（，以及一个打印机（R1）和输入）和输入机（机（R2）。在运行程中，）。在运行程中， P1 占用了占用了 R1和和P2占用占用了了 R2，此时，此时P1又又申请申请输入机而输入机而P2又又申请申请打印机，那么这时打印机，那么这时P1 和和P2均无法均无法运行，系统进入死锁状态。用下图所示。运行，系统进入死锁状态。用下图所示。进程循环链进程循环链P1P2R1R2由由进程进程指向指向资源资源的箭头的箭头表示对资源的表示对资源的申请申请，而，而由由资源资源指向指向进程进程的箭头的箭头表示资源的表示资源的分配分配NO：22 第四章第四章 操作系统操作系统4.2 4.2 处理器管理处理器管理 死锁的原

27、因和必要条件死锁的原因和必要条件 产生死锁的原因为产生死锁的原因为 系统资源不足系统资源不足 进程推进的顺序不当进程推进的顺序不当 产生死锁的产生死锁的必要必要条件为条件为 互斥条件互斥条件：存在互斥使用的资源存在互斥使用的资源 占有等待条件占有等待条件：进程在等待新资源时，继续占用已分进程在等待新资源时，继续占用已分配到的资源配到的资源一次只能给一一次只能给一个进程使用的个进程使用的资源资源NO：23 第四章第四章 操作系统操作系统4.2 4.2 处理器管理处理器管理 非剥夺条件非剥夺条件：一个进程占有的资源不能被别的进程强一个进程占有的资源不能被别的进程强行抢占。行抢占。 循环等待条件循环

28、等待条件：一个进程获得的资源同时被另一个进一个进程获得的资源同时被另一个进程所请求，从而形成一个进程的循环链。程所请求，从而形成一个进程的循环链。 随着系统的不断增大和复杂化，产生死锁的可能性也随随着系统的不断增大和复杂化，产生死锁的可能性也随着增加，着增加，解决死锁的方法解决死锁的方法大致有以下三类：大致有以下三类： 死锁的预防死锁的预防 死锁的避免死锁的避免 死锁的检测和恢复死锁的检测和恢复NO：24 第四章第四章 操作系统操作系统4.2 4.2 处理器管理处理器管理 死锁的预防死锁的预防:在系统设计时就确定资源分配的算法，在系统设计时就确定资源分配的算法，使得系统在运行时不会发生死锁，这

29、是一种使得系统在运行时不会发生死锁，这是一种静态措施静态措施。 死锁的避免死锁的避免:一种判定和发现死锁的方法，即每当申一种判定和发现死锁的方法，即每当申请一个资源时，都要依据一定的算法判断是否许可这次申请一个资源时，都要依据一定的算法判断是否许可这次申请，如有死锁发生的可能就不许可。这是一种请，如有死锁发生的可能就不许可。这是一种动态措施动态措施。 死锁的检测和恢复死锁的检测和恢复:既不预防死锁的发生，也不在系既不预防死锁的发生，也不在系统运行时避免，而是允许死锁的发生，只是在死锁发生后统运行时避免，而是允许死锁的发生，只是在死锁发生后消除死锁。是消除死锁。是善后措施善后措施。NO：25 第

30、四章第四章 操作系统操作系统4.2 4.2 处理器管理处理器管理 死锁的预防死锁的预防 由产生死锁的必要条件可知：由产生死锁的必要条件可知： D C1C2C3C4 则有则有: C1 C2 C3 C4 D 因此只要保证系统中有一个必要条件不成立，就能保证系因此只要保证系统中有一个必要条件不成立，就能保证系统中不会出现死锁。统中不会出现死锁。 破坏互斥条件破坏互斥条件 较难实现，因为有些系统资源的性质是较难实现，因为有些系统资源的性质是非共享的，但可以采用非共享的，但可以采用假脱机假脱机技术将非共享设备变成共享设技术将非共享设备变成共享设备来实现。备来实现。NO：26 第四章第四章 操作系统操作系

31、统4.2 4.2 处理器管理处理器管理 破坏占有等待条件破坏占有等待条件 常用的方法是预先静态分配法，规定常用的方法是预先静态分配法，规定各进程所需的全部资源只能事先各进程所需的全部资源只能事先一次一次申请，并在没有获得全申请，并在没有获得全部资源之前，不能运行。实现较容易，但分配到的资源可能部资源之前，不能运行。实现较容易，但分配到的资源可能使用时间很短，而被某个进程长时间占用，资源利用率低。使用时间很短，而被某个进程长时间占用，资源利用率低。 破坏非剥夺条件破坏非剥夺条件 根据申请资源的优先级别高低来剥夺根据申请资源的优先级别高低来剥夺占用的资源。该方法目前主要用在处理机和存储资源调度上，

32、占用的资源。该方法目前主要用在处理机和存储资源调度上，而对某些设备就不合适，如对打印机的剥夺就会使各个用户而对某些设备就不合适，如对打印机的剥夺就会使各个用户输出的信息混杂在一起。输出的信息混杂在一起。 NO：27 第四章第四章 操作系统操作系统4.2 4.2 处理器管理处理器管理这样，进程与资源请求不会产生循环等待问题，即不会出现环这样，进程与资源请求不会产生循环等待问题，即不会出现环路。该方法提高了资源利用率，但进程实际需要资源的顺序不路。该方法提高了资源利用率，但进程实际需要资源的顺序不一定与资源的编号一致，因此仍会造成资源浪费。一定与资源的编号一致，因此仍会造成资源浪费。破坏循环等待条

33、件破坏循环等待条件 常采用有序资源使用方法，即资源按类常采用有序资源使用方法，即资源按类型赋予一个型赋予一个唯一唯一的代号。如令输入机的代号。如令输入机=1,打印机打印机=2,穿孔机穿孔机=3, 磁盘磁盘=4等，所有进程对资源的请求必须严格按照等，所有进程对资源的请求必须严格按照序号递增次序号递增次序序进行，并且要求在前一要求得到满足的前提下，才能进一进行，并且要求在前一要求得到满足的前提下，才能进一步请求。步请求。例如：进程例如：进程PA，使用资源的顺序是，使用资源的顺序是R1，R2； 进程进程PB，使用资源的顺序是，使用资源的顺序是R2，R1；若采用动态分配有可能形成若采用动态分配有可能形

34、成环路条件环路条件，造成死锁。，造成死锁。采用有序资源分配法：采用有序资源分配法：R1的编号为的编号为1，R2的编号为的编号为2； PA：申请次序应是：申请次序应是：R1，R2 PB：申请次序应是：申请次序应是：R1，R2 这样就破坏了环路条件，避免了死锁的发生。这样就破坏了环路条件，避免了死锁的发生。NO：28 第四章第四章 操作系统操作系统4.2 4.2 处理器管理处理器管理 死锁的避免死锁的避免 在避免死锁的方法中，允许进程动态地申请在避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此

35、次分配不会导致系统进入不安全状态，则将的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；资源分配给进程； 否则，令进程等待。下面介绍一种死锁避否则，令进程等待。下面介绍一种死锁避免的算法免的算法 - 银行家算法银行家算法 安全状态和不安全状态安全状态和不安全状态 安全状态：安全状态：所谓安全状态是指系统能够按照某种所谓安全状态是指系统能够按照某种进程进程顺序顺序，如，如(称其为称其为安全序列安全序列),分别为这分别为这n个进程个进程分配所需资源，直至最大需求，使每个进程都能顺利完成。分配所需资源，直至最大需求，使每个进程都能顺利完成。若系统不存在这样一个安全序列，则称系统处于

36、若系统不存在这样一个安全序列，则称系统处于不安全状态不安全状态 系统处于安全状态，且按照安全序列分配资源，可以保系统处于安全状态，且按照安全序列分配资源，可以保证系统不会出现死锁。因此，避免死锁的实质在于证系统不会出现死锁。因此，避免死锁的实质在于避免系统避免系统进入不安全状态。进入不安全状态。NO：29 第四章第四章 操作系统操作系统4.2 4.2 处理器管理处理器管理下面通过一个例子说明安全性。假定系统有下面通过一个例子说明安全性。假定系统有3 3个进程个进程P1P1, ,P2P2, ,P3P3共有共有1414台打印机台打印机。进程。进程P1P1共要求共要求1212台打印机台打印机，P2P

37、2和和P3P3分别要分别要求求4 4台台和和9 9台台打印机。假定打印机。假定T0T0时刻时刻, ,进程进程P1,P2P1,P2和和P3P3分别获得分别获得5 5台台,2,2台和台和4 4台台, ,尚有尚有3 3台空闲台空闲未分配，如下表未分配，如下表进程进程最大需求最大需求已分配已分配还需要还需要可用可用P112573P2422P3945经分析发现，在经分析发现，在T0T0时刻是安全的。因为，存在一个安全序时刻是安全的。因为，存在一个安全序列列,系统按此序列分配资源，每个进程可以顺利系统按此序列分配资源，每个进程可以顺利完成。完成。NO：30 第四章第四章 操作系统操作系统4.2 4.2 处

38、理器管理处理器管理进程进程最大需求最大需求已分配已分配还需要还需要可用可用P1P112126 66 62P2P24 42 22 2P3P39 94 45 5 由安全状态向不安全状态转换由安全状态向不安全状态转换假设在假设在T0T0时刻时刻P1P1要求要求6 6台台打印机，则系统进入不安全状态。因打印机，则系统进入不安全状态。因为如果把剩余的为如果把剩余的2 2台台分配给分配给P2P2，当，当P2P2完成后，仅能释放出完成后，仅能释放出4 4台台，既不能满足既不能满足P1P1的要求，也不能满足迹的要求，也不能满足迹P3P3的要求。这样的要求。这样P1P1和和P3P3都无法执行都无法执行完成，彼此

39、都阻塞等待对方释放资源，结果将完成，彼此都阻塞等待对方释放资源，结果将导导致死锁致死锁。NO：31 第四章第四章 操作系统操作系统4.2 4.2 处理器管理处理器管理银行家算法银行家算法 银行家算法把银行家算法把操作系统操作系统比作是一个比作是一个银行家银行家，它占有有限的，它占有有限的资源，而要求资源的资源，而要求资源的进程进程好比要贷款的好比要贷款的顾客顾客。算法规定：。算法规定： 1. 每个用户必须预先申请它所需的每个用户必须预先申请它所需的贷款总数贷款总数，且数值不，且数值不能超过银行资金总数。能超过银行资金总数。 2. 每个用户每次只能向银行申请每个用户每次只能向银行申请一个单位一个

40、单位贷款数。贷款数。 3. 银行根据当时的资金情况，银行根据当时的资金情况，可能立即满足可能立即满足用户申请，用户申请，或需要用户或需要用户等待一段等待一段有限时间。有限时间。 4. 当用户贷款总数达到申请数后，必须在有限时间内当用户贷款总数达到申请数后，必须在有限时间内一次性归还一次性归还所有贷款。所有贷款。NO：32 第四章第四章 操作系统操作系统4.2 4.2 处理器管理处理器管理态态状状行行银银甲甲乙乙丙丙例如某银行资金总数为例如某银行资金总数为10万元万元，用户甲、乙、丙申请贷款，用户甲、乙、丙申请贷款总数分别为总数分别为8万元万元、3万元万元、9万元万元。用户每次向银行申请。用户每

41、次向银行申请贷款数为贷款数为1万元。万元。 A为初始状态，银行库存为初始状态，银行库存10万元，甲乙丙申请贷款万元，甲乙丙申请贷款分别为分别为万元。万元。 当借贷进行到状态当借贷进行到状态B时，甲、乙、丙分别得到贷款时，甲、乙、丙分别得到贷款4，2，2万元。括号中的数字为尚可申请的贷款数。万元。括号中的数字为尚可申请的贷款数。NO：33 第四章第四章 操作系统操作系统4.2 4.2 处理器管理处理器管理 若甲乙丙继续提出贷款申请，银行要考虑库存与各用户若甲乙丙继续提出贷款申请，银行要考虑库存与各用户尚可申请的贷款数，为使借贷安全，只同意继续提供用尚可申请的贷款数，为使借贷安全，只同意继续提供用

42、户户乙乙的贷款，而的贷款，而甲和丙甲和丙暂时暂时等待等待，待用户，待用户乙乙获得全部贷获得全部贷款并在有限时间内款并在有限时间内全部归还后全部归还后再考虑贷款。如此进行下再考虑贷款。如此进行下去，各用户均能获得贷款，而银行也可以如数收回资金，去，各用户均能获得贷款，而银行也可以如数收回资金，其过程如下页表所示：其过程如下页表所示：态态状状行行银银甲甲乙乙丙丙NO：34 第四章第四章 操作系统操作系统4.2 4.2 处理器管理处理器管理状态状态银行银行甲甲乙乙丙丙NO：35 第四章第四章 操作系统操作系统4.2 4.2 处理器管理处理器管理 非银行算法可能引起的死锁状态非银行算法可能引起的死锁状

43、态状态状态银行银行甲甲乙乙丙丙 如果银行随意给各申请用户贷款，则可能出现银行库存满如果银行随意给各申请用户贷款，则可能出现银行库存满足不了甲、乙、丙的申请余额，使它们永不归还贷款，从而足不了甲、乙、丙的申请余额，使它们永不归还贷款，从而使银行无法收回资金，系统处于使银行无法收回资金，系统处于死锁状态死锁状态，如下表所示。，如下表所示。NO：36 第四章第四章 操作系统操作系统4.2 4.2 处理器管理处理器管理Habermann算法算法：用户对多类资源提出的请求用户对多类资源提出的请求根据系统中进程数和所需资源写出进程请求矩阵根据系统中进程数和所需资源写出进程请求矩阵B 例如：某系统由例如：某

44、系统由4个个进程进程P1,P2,P3和和P4组成，其相应的请求组成，其相应的请求矩阵为：矩阵为：bij表示第表示第i个进程对第个进程对第j类资源的需求情况，如果类资源的需求情况，如果 bij=0 则说则说明进程明进程 Pi 对资源对资源 Rj 没有要求没有要求NO：37 第四章第四章 操作系统操作系统4.2 4.2 处理器管理处理器管理死锁的检测是采用进程有向图死锁的检测是采用进程有向图 , E，其中其中 = P1,P2,Pn, eE，有向边，有向边eik=Pi,Pk 表示进程表示进程Pi申请的资申请的资源源Rj也可能为进程也可能为进程Pk所申请。每当有向图出现环路时，认为所申请。每当有向图出

45、现环路时，认为该进程的资源请求将导致死锁，系统拒绝分配。该进程的资源请求将导致死锁，系统拒绝分配。 开始开始P1P2P3P4 P1请求请求R1P1P2P3P4NO：38 第四章第四章 操作系统操作系统4.2 4.2 处理器管理处理器管理 P2请求请求R3P1P2P3P4 P2请求请求R2P1P2P3P4P1,P2形成环路，拒形成环路，拒绝分配，绝分配，P2阻塞阻塞 P3请求请求R2P1P2P3P4P1,P2,P3形成环路，形成环路，拒绝分配，拒绝分配，P3阻塞阻塞 P4请求请求R4P1P2P3P4 P1请求请求R2P1P2P3P4 P1运行完毕运行完毕P2P3P4释放释放R1,R2，唤醒，唤醒

46、P2，把把R2分配给分配给P2NO：39 第四章第四章 操作系统操作系统4.2 4.2 处理器管理处理器管理(3) 死锁的检测与恢复死锁的检测与恢复如果系统不愿意附加太多的约束来预防死锁，也不希望系统额如果系统不愿意附加太多的约束来预防死锁，也不希望系统额外开销预测并避免死锁，那么只能外开销预测并避免死锁，那么只能允许允许死锁的发生，但能在适死锁的发生，但能在适当时间当时间检测出来检测出来，并设法进行，并设法进行恢复恢复。死锁检测算法通常针是检。死锁检测算法通常针是检测否存在进程的循环链。测否存在进程的循环链。资源分配图资源分配图P1P2r1r2凡属于凡属于E中的一个边中的一个边eE，都连接，

47、都连接着着P中的一个结点中的一个结点和和R中的一个结中的一个结点点，e=pi, rj是是资源请求边资源请求边，由进，由进程程pi指向资源指向资源rj，它表示进程，它表示进程pi请请求一个单位的求一个单位的rj资源。资源。e=rj, pi是是资源分配边资源分配边，由，由资源资源rj指向进程指向进程pi, 它表示把一个单位的资源它表示把一个单位的资源rj分配给分配给进程进程pi。NO：40 第四章第四章 操作系统操作系统4.2 4.2 处理器管理处理器管理查找图中非孤立进程结点查找图中非孤立进程结点Pi，其全部请求能够满足，说明它能，其全部请求能够满足，说明它能得到需要的所有资源，顺利向前推进，直至最后完成，并释放得到需要的所有资源，顺利向前推进，直至最后完成，并释放所有占用的资源。这样可以所有占用的资源。这样可以去掉去掉Pi的的请求边请求边和和分配边分配边，使