操作系统原理与设计.ppt

1、操作系统原理与设计 Operating Systems: Design and Implementation,Department of Computer Science and Technology University of Science and Technology of China,本课程的内容,概论 处理机管理 内存管理 设备管理 文件管理 典型示例分析,参考书,A.S.Tanenbaun 三本书 (1) Operating systems: Design and Implementation (2) Distributed Operating Systems (3) Modern

2、 Operating Systems Prentice-Hall Press 电子工业出版社 汤子瀛，计算机操作系统，西安电子科技大学出版社 滕至阳，现代操作系统教程，高等教育出版社，2000.2 D.A.Solomon, M.E.Russinorich, Inside windows 2000，Microsoft Press，2000,课程特点,涉及面广（与许多课程相关）,实践性强（从实践总结出原理）,如何学好？把握总体思路+各专题涉及的知识Learn DOS concepts by coding them!,在计算机学科中的重要地位,注意学习方式的变化,教师只指出要点 要通过自学、研读参考

3、书掌握内容,整理笔记相当重要 不能只通过PowerPoint来复习课程,善于发现问题、提出问题 要努力寻求问题的答案,课程基本目的,介绍： 操作系统原理 操作系统设计方法 培养： 分析问题、解决问题的能力 独立承担专门技术工作的能力,要求,出席 作业 实习,辅导老师,许言午 尹洪章 华 北 电3楼704,Thanks for your attention!,操作系统概论,单处理机OS 外部特性： 概念，特征，研究观点，发展历程， 分类，功能 内部特性： 内核、结构设计 操作系统标准化,1、操作系统的概念,（1）目标 方便性 -人 有效性 -系统管理 扩展性 -体系结构：软件结构和硬件结构 开放

4、性 -体系结构：软件结构和硬件结构 （2）层次模型 是叠加在硬件上的第一层软件， 是其他软件和硬件之间的接口 （3）定义 有效地管理计算机的软硬件资源， 合理地组织计算机的工作流程， 方便用户 （三点的权重也在发展变化）,操作系统设计者,应用软件设计者,有效：系统效率，资源利用率 （如：CPU利用的充足与否，内存、外部设备是否忙碌）,合理： 公平与否，如果不公平则会产生“死锁”或“饥饿”,方便：两种角度： 用户界面 编程接口,2、操作系统的特征,（1）进程/线程执行的并发性（concurrency）： 并发：内存中的多个进程宏观上同时执行，但 微观上是串行的（因为单CPU） 并行（parall

5、el）：,操作系统特征（续）,（2）资源的使用共享性（sharing）： 互斥共享（临界资源如音频设备） 同步共享（如可重入代码，磁盘文件）,（3）设备的虚拟性（Virtual）： 一个物理实体映射为若干个对应的逻辑实体分时或分空间。虚拟是操作系统管理系统资源的重要手段，可提高资源利用率,操作系统特征（续）,（4）进程的异步（随机）性： 进程的运行速度不可预知：分时系统中，多个进程并发执行，“走走停停”，无法预知每个进程的运行推进快慢 难以重现系统在某个时刻的状态（包括重现运行中的错误）,操作系统特征（续）,（5）不确定性(可能不再现性)： 由共享和并发引起 在操作系统中可运行多道用户程序，而

6、每个用户程序的运行时间、要使用哪些系统资源、使用多长时间、使用的资源是共享还是独占的，操作系统在程序运行前是不知道的 要求操作系统的设计要很好地解决并发和共享的问题，否则，将会产生可不再现的错误。,操作系统特征（续）,3、操作系统的几种研究观点,资源管理的观点,进程的观点,虚机器观点,服务提供者观点,（1）资源管理的观点,操作系统-资源管理者（自底向上） 硬件资源： CPU，内存，外部设备(I/O设备，外存，时钟，网络接口等) 软件资源： 硬盘上的文件，信息 两种方式实现复用（共享）：时间 及 空间,管理资源涉及的工作,记录资源使用状况 如 哪些资源空闲，好坏与否，被谁使用,使用多长时间等 申

7、请资源 分配资源 静态分配策略 (在程序运行前分配，但效率不高) 动态分配策略 (在程序运行过程中何时用资源，何时分配。其缺点是会出现死锁) 回收资源,资源管理的目的,实现资源共享 提高资源利用率,（2）进程的观点,从操作系统运行的角度动态地观察操作系统 从这个观点来看： 操作系统是由一些可同时独立运行的进程（运行的程序）和一个对这些进程进行协调的核心组成,（3）虚机器观点,从操作系统内部结构来看： 把操作系统分成若干层 每一层完成其特定功能，从而构成一个虚机器，并对上一层提供支持 通过逐层功能扩充,最终完成整个操作系统虚机器 而操作系统虚机器向用户提供各种功能,完成用户请求,（4） 服务提供

8、者的观点,从用户角度来看： 操作系统为用户提供一组功能强大的、方便易用的命令或系统调用,操作系统作为 标准服务提供者 提供每个用户需要的标准工具,4、操作系统的发展历程,动力: 人的需求+计算机本身发展的推动 软件:程序设计方法语言 硬件 体系结构 历程： 无OS时代-批处理系统-分时系统-实时系统 -PC-分布式系统-移动系统-。 * 每一阶段内，都有对应的软件、硬件和体系结构等领域的发展,历史上的操作系统,FMS（FORTRAN Monitor System，FORTRAN监控系统） OS/360（IBM为系列机360配备的操作系统） CTSS（Compatible Time Sharin

9、g System） MULTICS（MULTiplexed Information and Computer Service） UNIX类、Linux CP/M,历史上的操作系统,Windows Macintosh Mach VxWorks 嵌入式领域 国产操作系统 研究阶段的操作系统,典型的操作系统,FMS（FORTRAN Monitor System，FORTRAN监控系统） IBMSYS（IBM为7094机配备的操作系统） 这些操作系统由监控程序，特权指令，存储保护和简单的批处理构成,1964 年IBM 宣布推出System/360计算机系统。是第一个采用小规模集成电路的主流机型 试图一

10、次性地解决厂家和用户需要软件在不同型号的计算机之间兼容 由于所有的计算机都有相同的体系结构和指令集，在理论上，为一型号编写的程序可以在其他型号机器上运行,OS/360操作系统,分时系统的思想1959年在MIT提出 每个用户有一个联机终端 调试程序的用户常常只发出简短的命令 很少有长的费时命令 计算机能够为许多用户提供交互式、快速服务 同时在CPU空闲时还能在后台运行大作业,第一个分时操作系统CTSS,第一个分时系统（CTSS）由 MIT的Fernando Corbato 等1961年在一改装的IBM 7090/94机上开发成功（有32个交互式用户） 第一个有虚拟存储器(virtual memo

11、ry)和页面调度(paging) 的机器 指令执行是 pipelined 的,MULTICS的灾难,1965年，MULTICS (MULTiplexed Information and Computing Service ) MULTICS设计目标是： 便利的终端使用大量远程终端通过电话线接入计算机主机 高可靠的大型文件系统大容量的用户信息共享；存储和构造层次化信息结构的能力,MULTICS研制难度超出所有人的预料（PL/1语言） MULTICS的意义 引入了许多现代操作系统领域概念雏形，对随后的操作系统特别是UNIX的成功有着巨大的影响,MULTICS,UNIX,1969年，在贝尔退出MUL

12、TICS研制项目后，Ken Thompson和Dennis M. Ritchie 想申请经费买计算机从事操作系统研究，但多次申请得不到批准 项目无着落，他们在一台无人用的PDP-7上，重新摆弄原先在MULTICS项目上设计的“空间旅行”游戏 为了使游戏能够在PDP-7上顺利运行，他们陆续开发了浮点运算软件包、显示驱动软件，设计了文件系统、实用程序、shell 和汇编程序 到了1970年，在一切完成后，给新系统起了个同MULTICS发音相近的名字UNIX 随后，UNIX用C语言全部重写，自此，UNIX诞生了,UNIX,UNIX是现代操作系统的代表。Unix运行时的安全性、可靠性以及强大的计算能力

13、赢得广大用户的信赖 促使UNIX系统成功的因素： 首先，由于UNIX是用C语言编写，因此它是可移植的，UNIX 是世界上唯一能在笔记本计算机、PC机、工作站直至巨型机上运行的操作系统 第二，系统源代码非常有效，系统容易适应特殊的需求 最后，也是最重要的一点，它是一个良好的、通用的、多用户、多任务、分时操作系统,UNIX,两个版本系列 AT free = false; 临界区 free = true;,软件解法 (2),turn: true P进入临界区 false Q进入临界区 . P: while (not turn); 临界区 turn = false; Q: while (turn);

14、临界区 turn = true;,软件解法(3),pturn,qturn: 初值为false P进入临界区的条件: pturn not qturn Q进入临界区的条件: not pturn qturn P . Q . pturn = true; pturn = true; while (qturn); while (pturn); 临界区 临界区 pturn = false; qturn = false; . .,软件解法(4) : Dekker算法,在解法(3)基础上引入turn枚举类型 初值任意 P : while (true) pturn = true; while (qturn) if

15、 (turn=2) pturn = false; while (turn=2)； pturn = true; 临界区 turn = 2; pturn = false; . ,软件解法(4)（续1）,Q : while (true) qturn = true; while (pturn) if (turn=1) qturn = false; while (turn=1)； qturn = true; 临界区 turn = 1; qturn = false; . ,软件解法(5) : Peterson算法,enter_region ( i ); 临界区 leave_region ( i ); 非临

16、界区,process i,当一个进程想进入临界区时，先调用enter_region函数，判断是否能安全进入，不能的话等待；当它从临界区退出后，需调用leave_region函数，允许其它进程进入临界区。两个函数的参数均为进程号,#define FALSE 0#define TRUE 1#define N 2/ 进程的个数 int turn;/ 轮到谁？int interestedN;/ 兴趣数组，初始值均为FALSE void enter_region ( int process)/ process = 0 或 1 int other;/ 另外一个进程的进程号 other = 1 - proc

17、ess; interestedprocess = TRUE;/ 表明本进程感兴趣 turn = process;/ 设置标志位 while( turn = process ,软件解法(5) : Peterson算法（续1）,void leave_region ( int process) interestedprocess = FALSE;/ 本进程已离开临界区,Peterson算法解决了互斥访问的问题，而且 克服了强制轮流法的缺点，可以完全正常地 工作,软件解法(5) : Peterson算法（续2）,软件解法的缺点： 1. 忙等待 2. 实现过于复杂，需要高的编程技巧 硬件解法：提供专门的

18、硬件指令，允许对一个字的内容进行检测和修正，或交换两个字的内容 目的：解决共享变量的完整性和正确性 简单、有效，特别适用于多处理机 缺点：忙等待,硬件解法 (1) “测试并设置”指令,boolean TS (boolean *lock) boolean old; old = *lock; *lock = true; TS指令功能描述,while TS( 每个临界资源设置一个lock，初值为false,硬件解法 (2) “交换”指令,void SWAP(int *a, int *b) int temp; temp = *a; *a = *b; *b = temp; Swap指令的功能描述,key

19、 = true; do SWAP( 每个临界资源设置一个lock，初值为false,中断屏蔽方法 “开关中断”指令,进入临界区前执行： 执行“关中断”指令 离开临界区后执行： 执行“开中断”指令 简单，有效 较高的代价，限制CPU并发能力（临界区大小） 不适用于多处理器,2.进程的同步机制信号量及P.V操作,以上介绍的各种算法都存在问题，它们是平等进程间的一种协商机制，需要一个地位高于进程的管理者来解决公有资源的使用问题 操作系统可从进程管理者的角度来处理互斥的问题，信号量就是操作系统提供的管理公有资源的有效手段,进程的同步机制（续）,同步机制： 信号量及P、V操作；管程；条件临界域；路径表达

20、式等（用于集中式系统中） 会合；通信顺序进程；分布进程；远程过程调用等（适用于分布式系统中）,同步机制应满足的基本要求： * 描述能力 * 可以实现 * 效率高 * 使用方便,进程的同步机制（续）,1965年，由荷兰学者Dijkstra提出（所以P、V分别是荷兰语的test(proberen)和increment(verhogen)） 一种卓有成效的进程同步机制 信号量机制：信号量、P/V原语、实现方法 互斥信号量机制整型信号量机制记录型信号量机制 -多信号量机制 -一般信号量机制,信号量及P、V操作,信号量：semaphore,是一个数据结构 定义如下： struc semaphore in

21、t value; pointer_PCB queue; 信号量说明： semaphore s;,P、V操作,P(s) s.value = s.value -; if (s.value 0) 该进程状态置为等待状态 将该进程的PCB插入相应的等待队列末尾s.queue；重新调度 ,P、V操作,V(s) s.value = s.value +; if (s.value = 0) 唤醒相应等待队列s.queue中等待的一个进程 改变其状态为就绪态，并将其插入就绪队列 ,P、V操作为原语操作 原语：primitive or atomic action 是完成某种特定功能的一段程序，具有不可分割性或不可

22、中断性 即原语的执行必须是连续的，在执行过程中不允许被中断 实现：屏蔽中断,信号量及P、V操作（续1）,信号量的使用： 必须置一次且只能置一次初值 初值不能为负数 只能执行P、V操作,信号量及P、V操作（续2）,用P、V操作实现进程间互斥,C：P-Q （1）对应条件C设一信号量c（条件成立时c=0）, （2）在P最后加V(c) （3）在Q最前加P(c),用P、V操作实现同步,经典的生产者消费者问题,消费者,生产者,经典的生产者消费者问题（续1）,同步问题： P进程不能往“满”的缓冲区中放产品，设置信号量为S1 Q进程不能从“空”的缓冲区中取产品，设置信号量S2,S1初值为1，S2初值为0,P：

23、 Q： while (true) while (true) 生产一个产品; P(s2); P(s1) ; 从缓冲区取产品; 送产品到缓冲区; V(s1); V(s2); 消费产品; ; ;,经典的生产者消费者问题（续2）,多个缓冲区的生产者和消费者,P：i = 0;while (true) 生产产品; P(S1); 往Buffer i放产品; V(S2); i = (i+1) % n; ;,Q： j = 0; while (true) P(S2); 从Bufferj取产品; V(S1); 消费产品; j = (j+1) % n; ;,Q： while (true) P(S2); P(mutex

24、); 从Bufferj取产品; V(mutex); V(S1); 消费产品; j = (j+1) % n; ; j的初值为0,n个缓冲区、m个生产者和k个消费者,P：while (true) 生产产品; P(S1); P(mutex); 往Buffer i放产品; V(mutex); V(S2); i = (i+1) % n; ; i的初值为0,有错误？若颠倒两个P操作的顺序？,Q： j = 0; while (true) P(S2); P(mutex2); 从Bufferj取产品; j = (j+1) % n; V(mutex2); V(S1); 消费产品; ;,n个缓冲区、m个生产者和k个

25、消费者,P：i = 0;while (true) 生产产品; P(S1); P(mutex1); 往Buffer i放产品; i = (i+1) % n; V(mutex1); V(S2); ;,正确,1) 信号量的物理含义： S0表示有S个资源可用 S=0表示无资源可用 S0则| S |表示S等待队列中的进程个数 P(S)：表示申请一个资源 V(S)：表示释放一个资源。信号量的初值应该大于等于0,信号量及P、V操作,2) P.V操作必须成对出现，有一个P操作就一定有一个V操作 当为互斥操作时，它们同处于同一进程 当为同步操作时，则不在同一进程中出现 如果P(S1)和P(S2)两个操作在一起，

26、那么P操作的顺序至关重要,一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前 而两个V操作无关紧要（细微区别）,信号量及P、V操作（续1）,3）P.V操作的优缺点 优点： 简单，而且表达能力强（用P.V操作可解决任何同步互斥问题） 缺点： 不够安全；P.V操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂,信号量及P、V操作,3.信号量集AND型信号量集,AND型信号量集是指同时需要多种资源且每种占用一个时的信号量操作 AND型信号量集的基本思想：在一个原语中申请整段代码需要的多个临界资源，要么全部分配给它，要么一个都不分配 AND型信号量集P原语为Swait AND型信号量集

27、V原语为Ssignal,Swait(S1, S2, , Sn)/P原语； while (TRUE) if (S1 =1 ,信号量集AND型信号量集（续）,Ssignal(S1, S2, , Sn) for (i = 1; i = n; +i) +Si;/释放占用的资源； for (在Si.queue中等待的每一个进程P) /检查每种资源的等待队列的所有进程； 从等待队列Si.queue中取出进程P;,信号量集AND型信号量集（续1）,if (判断进程P是否通过Swait中的测试) /注：与signal（V）不同，要重新判断； /通过检查（资源够用）时的处理； 进程P进入就绪队列; else /

28、未通过检查（资源不够用）时的处理； 进程P进入某等待队列； ,信号量集AND型信号量集（续2）,采用AND信号量集解决生产者-消费者问题： Swait(empty, mutex), Ssignal(full, mutex),信号量集AND型信号量集（续3）,一般“信号量集”,一般信号量集是指同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的信号量处理 （一次需要N个某类临界资源时，就要进行N次P操作低效又可能死锁） 一般信号量集的基本思路就是在AND型信号量集的基础上进行扩充，在一次原语操作中完成所有的资源申请,进程对信号量Si的 测试值为ti（表示信号量的判断条件，要求

29、Si = ti；即当资源数量低于ti时，便不予分配） 占用值为di（表示资源的申请量，即Si = Si - di） 对应的P、V原语格式为： Swait(S1, t1, d1; .; Sn, tn, dn); Ssignal(S1, d1; .; Sn, dn);,一般“信号量集”（续）,一般“信号量集”可以用于各种情况的资源分配和释放，几种特殊情况：,Swait(S, d, d)表示每次申请d个资源，当少于d个时，便不分配 Swait(S, 1, 1)表示互斥信号量 Swait(S, 1, 0)可作为一个可控开关（当S1时，允许多个进程进入临界区；当S=0时，禁止任何进程进入临界区） 一般信

30、号量集未必成对使用Swait和Ssignal：如：一起申请，但不一起释放,Thanks for your attention!,IPC经典问题,（1）读者写者问题 问题描述： 有两组并发进程: 读者和写者,共享一组数据区 要求： 允许多个读者同时执行读操作 不允许读者、写者同时操作 不允许多个写者同时操作,第一类：读者优先,如果读者到： 1）无读者、写者，新读者可以读 2）有写者等，但有其它读者正在读，则新读者也可以读 3）有写者写，新读者等 如果写者到： 1）无读者，新写者可以写 2）有读者，新写者等待 3）有其它写者，新写者等待,第一类读者写者问题的解法,读者： while (true)

31、P(mutex); readcount +; if (readcount=1) P (w); V(mutex); 读 P(mutex); readcount -; if (readcount=0) V(w); V(mutex); ;,写者： while (true) P(w); 写 V(w); ;,第一类读者写者问题的解法（一般信号量集）,读者： Swait(wmutex,1,1; rcount,R,0); 写； Ssignal(wmutex,1);,写者： Swait(rcount,1,1; wmutex,1,0); 写； Ssignal(rcount,1);,增加一个限制条件：同时读的“读

32、者”最多R个 Wmutex表示“允许写”，初值是1 Rcount表示“允许读者数目”，初值为R,（2）哲学家就餐问题,问题描述： 有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子 每个哲学家的行为是思考，感到饥饿，然后吃通心粉 为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子,哲学家就餐问题解法（1）,#define N 5 void philosopher (int i) while (true) 思考； 取forki; 取fork(i+1) % 5； 进食； 放forki; 放fork(i+1) % 5； ,为

33、防止死锁发生可采取的措施： 最多允许4个哲学家同时坐在桌子周围 仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子（） 给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之 为了避免死锁，把哲学家分为三种状态，思考，饥饿，进食，并且一次拿到两只筷子，否则不拿,哲学家就餐问题解法（2）,#define N 5 #define THINKING 0 #define HUNGRY 1 #define EATING 2 #typedef int semaphore; int stateN; semaphore mutex=1; semaphore sN;,void test(i

34、nt i) if (state i = HUNGRY) ,void philosopher (int i) while (true) 思考; P( 拿左筷子； 拿右筷子； 进食；,放左筷子； 放右筷子； P( state i = THINKING s i = 0,5.进程的同步机制管程,管程的提出 采用PV同步机制来编写并发程序，对于共享变量及信号量变量的操作将被分散于各个进程中 缺点： （）易读性差，因为要了解对于一组共享变量及信号量的操作是否正确，则必须通读整个系统或者并发程序,（）不利于修改和维护，因为程序的局部性很差，所以任一组变量或一段代码的修改都可能影响全局 （）正确性难以保证，因

35、为操作系统或并发程序通常很大，要保证这样一个复杂的系统没有逻辑错误是很难的 Dijkstra(1971)：“秘书”进程 Hansen和Hoare(1973)：管程,进程的同步机制管程（续1）,管程：一种同步机制 (管程-类程-进程) 管程定义: 指关于共享资源的数据及在其上操作的一组过程或共享数据结构及其规定的所有操作 系统按资源管理的观点分解成若干模块，用数据表示抽象系统资源，同时分析了共享资源和专用资源在管理上的差别，按不同的管理方式定义模块的类型和结构，使同步操作相对集中，从而增加了模块的相对独立性,进程的同步机制管程（续2）,管程的形式,TYPE monitor_name = MONI

36、TOR; 共享变量说明 define 本管程内所定义、本管程外可调用的过程（函数）名字表 use 本管程外所定义、本管程内将调用的过程（函数）名字表 PROCEDURE 过程名（形参表）； 过程局部变量说明； BEGIN 语句序列； END; .,FUNCTION 函数名（形参表）：值类型； 函数局部变量说明； BEGIN 语句序列； END; . BEGIN 共享变量初始化语句序列； END; 管程的四个组成部分： 名称 数据结构说明 对该数据结构进行操作的一组过程/函数 初始化语句,管程的形式（续）,（一）模块化，一个管程是一个基本程序单位，可以单独编译 （二）抽象数据类型，管程是一种特殊

37、的数据类型，其中不仅有数据，而且有对数据进行操作的代码 （三）信息掩蔽，管程是半透明的，管程中的外部过程（函数）实现了某些功能，至于这些功能是怎样实现的，在其外部则是不可见的,管程的三个主要的特性,管程有如下几个要素： （一）管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的外部过程（函数）来间接地访问管程中的共享变量 （二）为了保证管程共享变量的数据完整性，规定管程互斥进入 （三）管程通常是用来管理资源的，因而在管程中应当设有进程等待队以及相应的等待及唤醒操作,管程的要素,问题：多个进程出现在管程中 当一个进入管程的进程执行等待操作时，它应当释放管程的互斥权；当一个进入管程

38、的进程执行唤醒操作时（如唤醒），管程中便存在两个同时处于活动状态的进程 处理方法有三种： 等待继续，直到退出或等待（Hoare） 等待继续，直到等待或退出 规定唤醒为管程中最后一个可执行的操作,管程的实现问题,因为管程是互斥进入的，所以当一个进程试图进入一个巳被占用的管程时它应当在管程的入口处等待，因而在管程的入口处应当有一个进程等待队列，称作入口等待队列 如果进程唤醒进程，则等待继续，如果进程在执行又唤醒进程，则等待继续，如此，在管程内部，由于执行唤醒操作，可能会出现多个等待进程，因而还需要有一个进程等待队列，这个等待队列被称为紧急等待队列。它的优先级应当高于入口等待队列的优先级,管程的实现

39、问题（续1）,由于管程通常是用于管理资源的，因而在管程内部，应当存在某种等待机制。当进入管程的进程因资源被占用等原因不能继续运行时使其等待。为此在管程内部可以说明和使用一种特殊类型的变量，称作条件变量： VAR C:condition; 对于条件型变量，可以执行wait和signal操作：,管程的实现问题（续2）,wait（c）：如果紧急等待队列非空，则唤醒第一个等待者；否则释放管程的互斥权，执行此操作的进程的PCB进入c链尾部 signal（c）：如果c链为空，则相当于空操作，执行此操作的进程继续；否则唤醒第一个等待者，执行此操作的进程的PCB进入紧急等待队列的尾部,管程的实现问题（续3）,

40、管程的实现 两个主要途径： * 直接构造 效率高 * 间接构造 用某种已经实现的同步机制去构造 例子：用PV操作构造管程,管程的实现,TYPE one_instance=RECORD mutex:semaphore;（初值1） urgent:semaphore;（初值0） urgent_count:integer;（初值0） END; TYPE monitor_elements=MODULE; define enter,leave,wait,signal; mutex（入口互斥队列） urgent（紧急等待队列） urgent_count（紧急等待队列计数）,PROCEDURE enter(V

41、AR instance:one_instance);,BEGIN P(instance.mutex) END;,PROCEDURE leave(VAR instance:one_instance);,BEGIN IF instance.urgent_count 0 THEN BEGIN instance.urgent_count-; V(instance.urgent) END ELSE V(instance.mutex) END;,PROCEDURE wait(VAR instance:one_instance;VAR s:semephore;VAR count:integer); BEGI

42、N count+; IF instance.urgent_count0 THEN BEGIN instance.urgent_count-; V(instance.urgent) END ELSE V(instance. mutex); P(s); END;,PROCEDURE signal(VAR instance:one_instance; VAR s:semaphore;VAR count:integer); BEGIN IF count0 THEN BEGIN count-; instance.urgent_count+; V(s); P(instance.urgent) END EN

43、D;,例子：一个信息缓冲区是一个共享资源 抽象成一个数据结构：数组 构造一些操作（过程或函数） 发送：向缓冲区发消息 接收：从缓冲区取消息 隐藏了内部的数据结构和实现细节,例子：读者-写者问题,TYPE r_and_w=MODULE; VAR instance:one_instance; rq,wq:semaphore; r_count,w_count:integer; reading_count,write_count:integer; define start_r,finish_r,start_w,finish_w; use monitor_elements.enter, monitor_

44、elements.leave, monitor_elements.wait, monitor_elements.signal;,PROCEDURE start_r; BEGIN monitor_elements.enter(instance); IF write_count0 THEN monitor_elements.wait (instance,rq,r_count); reading_count+; monitor_elements.signal (instance,rq,r_count); monitor_elements.leave(instance); END;,PROCEDURE

45、 finish_r; BEGIN monitor_elements.enter(instance); reading_count-; IF reading_count=0 THEN monitor_elements.signal (instance,wq,w_count); monitor_elements.leave(instance); END;,PROCEDURE start_w; BEGIN monitor_elements.enter(instance); write_count+; IF (write_count1) OR(reading_count0) THEN monitor_

46、elements.wait (instance,wq,w_count); monitor_elements.leave(instance); END;,BEGIN reading_count:=0; write_count:=0; r_count:=0; w_count:=0; END;,读者的活动： r_and_w.start_r; 读操作； r_and_w.finish_r; 写者的活动： r_and_w.start_w; 写操作； r_and_w.finish_w;,管程和进程的异同点： （1）设置进程和管程的目的不同 （2）系统管理数据结构 进程：PCB 管程：等待队列 （3）管程被进

47、程调用 （4）管程是操作系统的固有成分，无创建和撤消,管程与进程比较,进程通信,1.概述,P.V操作实现的是进程之间的低级通讯，所以P.V为低级通讯原语。它只能传递简单的信号，不能传递交换大量信息 如果要在进程间传递大量信息则要用Send / Receive原语（高级通讯原语）,（1）进程通信的方式,共享内存： 相互通信的进程间设有公共内存，一组进程向该公共内存中写，另一组进程从公共内存中读，通过这种方式实现两组进程间的信息交换 UNIX的特殊方式,消息传递： 系统为进程提供了两个高级通讯原语send和receive send： 当要进行消息传递时执行send receive： 当接收者要接收

48、消息时执行receive,进程通信的方式（续1）,消息传递模式： 消息缓冲 在内存中开设缓冲区，发送进程将消息送入缓冲区，接收进程接收传递来的缓冲区 信箱通信,进程通信的方式（续2）,共享文件模式： 管道通信,进程通信的方式（续3）,直接通信和间接通信,直接通信：信息直接传递给接收方，如管道 在发送时，指定接收方的地址或标识，也可以指定多个接收方或广播式地址 在接收时，允许接收来自任意发送方的消息，并在读出消息的同时获取发送方的地址 间接通信：借助于收发双方进程之外的共享数据结构作为通信中转，如消息队列。通常收方和发方的数目可以是任意的,2.消息缓冲,（有界缓冲区原理）： 在操作系统空间设置一

49、组缓冲区，当发送进程需要发送消息时，执行send系统调用，产生自愿性中断，进入操作系统，操作系统为发送进程分配一个空缓冲区，并将所发送的消息从发送进程copy到缓冲区中，然后将该载有消息的缓冲区连接到接收进程的消息链链尾，如此就完成了发送过程。发送进程返回到用户态继续执行,消息缓冲（续1）,（有界缓冲区原理）： 在以后某个时刻，当接收进程执行到receive接收原语时，也产生自愿性中断进入操作系统，由操作系统将载有消息的缓冲区从消息链中取出，并把消息内容copy到接收进程空间，之后收回缓冲区，如此就完成了消息的接收，接收进程返回到用户态继续进行,PCB,. Send(R, M) . SIZE:

50、消息长度 TEXT:消息正文,. 消息链指针 .,. Receive(pid, N) . SIZE:消息长度 TEXT:消息正文 .,M:,N:,接收进程 R,发送进程 S,消息缓冲区结构： 消息长度 消息正文 发送者 消息队列指针,消息缓冲（续2）,用P.V操作来实现Send原语: Send（R，M） P(m-mutex); Begin 把缓冲区挂到接收进程 根据R找接收进程， 的消息链链尾; 如果没找到出错返回; V(m-mutex); 申请空缓冲区P（s-b）； V(s-m); P(b-mutex); END 摘空缓冲区; V(b-mutex); 把消息从M处copy到空缓冲区; 其中s

51、-b初值:n ;s-m初值:0,消息缓冲（续3）,3.信箱通信,信箱组成 信箱说明 与 信箱体 可存放信件数，已存放信件数，指针 信箱使用规则 若发送信件时信箱已满，则发送进程被置为“等信箱”状态，直到信箱有空时才被释放 若取信件时信箱中无信，则接收进程被置为“等信件”状态，直到有信件时才被释放,信箱通信（续1）,Send实现 send（N，M）：把信件M送到指定的信箱N中 步骤： 查找指定信箱N； 若信箱未满，则把信件M送入信箱且释放“等信件”者； 若信箱已满置发送信件进程为“等信箱”状态；,信箱通信（续2）,Receive实现 receive（N，X）：从指定信箱N中取出一封信，存放到指定

52、的地址X中 步骤： 查找指定信箱N； 若信箱中有信，则取出一封信存于X中且释放“等信箱”者； 若信箱中无信件则置接收信件进程“等信件”状态；,3.信箱通信（续3）,应用实例 磁盘管理进程：从信箱中收取信件，处理，启动磁盘工作 其他进程：要求访问磁盘，向磁盘管理进程发一封信,4. 管道通信方式 Pipe,也称共享文件方式，基于文件系统，利用一个打开的共享文件连接两个相互通信的进程，文件作为缓冲传输介质,5. 高级通信的特征,通信链路： 点对点/多点/广播 单向/双向 有容量（链路带缓冲区）/无容量（发送方和接收方需自备缓冲区） 数据格式： 字节流：各次发送之间的分界，在接收时不被保留，没有格式

53、报文：各次发送之间的分界，在接收时被保留，通常有格式（如表示类型），定长/不定长报文，可靠报文/不可靠报文 收发操作的同步方式 发送阻塞（直到被链路容量或接收方所接受）和不阻塞（失败时立即返回） 接收阻塞（直到有数据可读）和不阻塞（无数据时立即返回） 由事件驱动收发：在允许发送或有数据可读时，才做发送和接收操作,线程的基本概念,线程的引入 线程与进程的比较 线程的实现,1.线程的引入,进程的两个基本属性： 资源的拥有者： 给每个进程分配一虚拟地址空间，保存进程映像，控制一些资源（文件，I/O设备），有状态、优先级、调度 调度单位： 进程是一个执行轨迹 以上两个属性构成进程并发执行的基础,线程的

54、引入（续1）,系统必须完成的操作： 创建进程 撤消进程 进程切换 缺点： 时间空间开销大，限制并发度的提高,线程的引入（续2）,在操作系统中，进程的引入提高了计算机资源的利用效率。但在进一步提高进程的并发性时，人们发现进程切换开销占的比重越来越大，同时进程间通信的效率也受到限制 线程的引入正是为了简化线程间的通信，以小的开销来提高进程内的并发程度,线程的引入（续3）,线程：有时称轻量级进程 进程中的一个运行实体 是一个CPU调度单位 资源的拥有者还是进程或称任务 将原来进程的两个属性分开处理,线程的引入（续4）,线程： 有执行状态（状态转换） 不运行时保存上下文 有一个执行栈 有一些局部变量的

55、静态存储 可存取所在进程的内存和其他资源 可以创建、撤消另一个线程,线程和进程： 单进程、单线程 单进程、多线程 多进程、一个进程一个线程 多进程、一个进程多个线程,引入线程的好处,创建一个新线程花费时间少（结束亦如此） 两个线程的切换花费时间少 （如果机器设有“存储恢复所有寄存器”指令，则整个切换过程用几条指令即可完成） 因为同一进程内的线程共享内存和文件，因此它们之间相互通信无须调用内核 适合多处理机系统,2.线程与进程的比较,调度 并发性 拥有资源 系统开销,调度：线程是调度与分派的基本单位，进程是占有资源的基本单位 并发：两级：进程之间和同一进程内的多个线程之间 拥有资源：线程只拥有程

56、序计数器PC、寄存器等资源，但可调用其隶主进程的资源（注意：资源仍然是分给进程的） 系统开销：线程不涉及对存储器的管理,注： 在同一进程内，线程的切换不会引起进程的切换； 在同一进程内，各线程共享同一地址空间； 一进程中的线程在另一进程中是不可见的； 同一进程内的线程间的通信主要是基于全局变量进行的；而以同步手段为辅。,3.线程的实现机制,用户级线程 核心级线程 两者结合方法,（1）用户级线程（User Level Thread）,由应用程序完成所有线程的管理 通过线程库(用户空间) 一组管理线程的过程 核心不知道线程的存在 线程切换不需要核心态特权 调度是应用特定的,线程库,创建、撤消线程

57、在线程之间传递消息和数据 调度线程执行 保护和恢复线程上下文,对用户级线程的核心活动,核心不知道线程的活动，但仍然管理线程的进程的活动 当线程调用系统调用时，整个进程阻塞 但对线程库来说，线程仍然是运行状态 即线程状态是与进程状态独立的,用户级线程的优点和缺点,优点： 线程切换不调用核心 调度是应用程序特定的：可以选择最好的算法 ULT可运行在任何操作系统上（只需要线程库） 缺点： 大多数系统调用是阻塞的，因此核心阻塞进程，故进程中所有线程将被阻塞 核心只将处理器分配给进程，同一进程中的两个线程不能同时运行于两个处理器上,（2）核心级线程（KLT）,所有线程管理由核心完成 没有线程库，但对核心

58、线程工具提供API 核心维护进程和线程的上下文 线程之间的切换需要核心支持 以线程为基础进行调度 例子：Windows 2000/XP,核心级线程的优点和缺点,优点： 对多处理器，核心可以同时调度同一进程的多个线程 阻塞是在线程一级完成 核心例程是多线程的 缺点： 在同一进程内的线程切换调用内核，导致速度下降,（3）两者分析,针对不同的操作系统 开销和性能（线程的调度和切换速度） 系统调用（阻塞） 线程执行时间 灵活性 可扩充性 抢占CPU 共享进程的资源,（4）ULT和KLT结合方法,线程创建在用户空间完成 大量线程调度和同步在用户空间完成 程序员可以调整KLT的数量 可以取两者中最好的,Thanks for your attention!,处理机调度（CPU调度）,(1)起因 (2)调度范围