操作系统概论

第一章操作系统引论主要内容操作系统的目标、作用和模型操作系统的发展过程操作系统的基本特征OS（OperatingSystems)的主要功能OS的结构设计1.1操作系统的目标、作用和模型操作系统概念（p9）一组控制和管理计算机硬件和软件资源、合理地对各类作业进行调度以及方便用户的程序集合。方便性计算机只能识别0、1；用户熟悉的是各种语言。有效性使计算机的各类资源在系统的管理下得到更有效的利用，提高系统吞吐量。可扩充性便于修改和增加功能（如何设计？）。开放性系统能支持世界标准规范。1.1.1操作系统的目标1.1.2操作系统的作用(1)作为用户与计算机硬件系统之间的接口图1－1OS作为接口的从层状示意图计算机硬件操作系统系统调用，命令，图标，窗口应用程序及实用程序系统设计者程序员用户操作系统的作用(2)作为计算机系统资源的管理者处理机管理：分配和控制处理机存储器管理：分配及回收内存I/O(Input/Output)设备管理：I/O分配与操作文件管理：文件存取、共享和保护

作为扩充机器把覆盖了软件的机器称为扩充机或虚拟机。分层扩充的特点。不断提高计算机资源利用率的需要如批处理系统的出现方便用户如分时交互式系统的出现器件的不断更新换代8位－16－32－64－...计算机体系结构的不断发展：单机OS－多机OS－网络OS－…1.1.3操作系统发展的主要动力1.2操作系统的发展过程1.2.1无操作系统时的计算机系统人工操作方式如纸带输入机。特点是用户独占全机及CPU等待人工操作。脱机I/O方式（图1.2）引入I/O机的概念，解决前者的缺点。特点是减少了CPU的空闲时间且提高I/O速度。图1-2脱机I/O示意图输入设备外围机磁盘磁盘磁盘主机磁盘外围机输出设备1.2.2单道批处理系统处理过程（图1.3）监督程序（monitor）概念：系统对作业的处理都是成批进行的、且内存中始终只保持一道作业，称为单道批处理系统（simplebatchsystem）。批处理系统的引入是为了提高系统资源的利用率和吞吐量概念：运行控制权特征自动性、顺序性、单道性图1－3还有下一个作业？把下一个作业的源程序转换为目标程序源程序有错吗？装配目标程序运行目标程序开始是否停止是否1.2.3多道批处理系统基本概念多道：系统中同时驻留多个作业多道引入的优点：提高CPU利用率（图1.4）提高内存和I/O设备利用率提高了系统吞吐量特征多道性、无序性、调度性：作业调度、进程调度缺点平均周转时间长、无交互能力图1－4用户程序监督程序I/O操作I/O中断请求启动I/OI/O完成结束中断I/O中断请求启动I/OI/O完成结束中断t1t2t3t4t5t6t7t8(a)单道程序运行情况图1－4程序A调度程序I/O请求(b)四道程序运行情况程序B程序C程序DI/O请求I/O请求I/O请求I/O完成I/O完成I/O完成A完成表示获得CPUC再运行多道批处理系统(2)需解决的问题处理机管理问题内存管理问题I/O管理问题文件管理问题作业管理问题1.2.4分时系统分时系统的产生概念：指一台主机上连接了多个带有显示器和键盘的终端，同时允许多个用户共享主机中的资源，各个用户都可通过自己的终端以交互方式使用计算机。是用户的需求：人机交互性共享主机便于用户上机分时系统（2）分时系统在实现中的关键问题及时接收：多终端卡、输入缓冲区及时处理：交互作业应在内存、响应时间应短分时系统(3)分时系统的实现方法交互式作业直接进入内存以分配时间片方式实现类型：单道分时系统具有前、后台的分时系统仅当前台无作业或在调进、出时，才运行后台批处理作业。多道分时系统不需要调入、出开销。分时系统(4)分时系统的特征多路性、独立性、及时性、交互性1.2.5实时系统引入：要求及时处理的场合概念：系统能及时响应外部事件的请求，在规定时间内完成对该事件的处理。类型实时控制实时信息处理实时系统(2)实时任务类型按任务执行是否呈现周期性来划分周期性的（联系周期）；非周期性的（联系开始或完成截止时间）根据对截止时间的要求来划分硬实时任务软实时任务实时系统(3)实时、分时的比较多路性：相同独立性：相同及时性：实时系统要求更高交互性：分时系统交互性更强可靠性：实时系统要求更高1.3操作系统的基本特征并发并行是指两或多个事件在同一时刻发生。并发是两或多个事件在同一时间间隔内发生。进程：系统中能独立运行并作为资源分配的基本单位。引入线程后，独立运行的单位变为线程。操作系统的基本特征(2)共享系统中资源可供内存中多个并发执行的进程共同使用互斥共享：一段时间只允许一个进程访问该资源同时访问：微观上仍是互斥的操作系统的基本特征(3)虚拟通过某种技术把一个物理实体变为若干个逻辑上的对应物。若n是某一物理设备所对应的虚拟的逻辑设备数，则虚拟设备的速度必然是物理设备速度的1/n。异步运行进度不可预知。1.4OS的主要功能1.4.1处理机管理功能多道环境下，处理机的运行及分配都是以进程为单位，因此处理机管理可归结为进程管理。一、进程控制创建/撤消进程迁移进程状态一般由进程控制原语完成OS的主要功能(2)二、进程同步为使多个进程有条不紊地运行，应建立同步机制。包括进程互斥/同步，次序协调。三、进程通信源于进程合作，如：输入进程、计算进程、打印进程相互间有信息传递类型：直接通信：进程A发message，进程B收message间接通信：进程A发message到中间实体（如mailbox），进程B从中间实体收messageOS的主要功能(3)四、调度（作业与进程）作业调度：为作业分配必要资源，调入内存建立进程，并使之进入就绪队列。进程调度：从就绪队列中选出进程，分配CPU，使之运行。调度算法：FCFS、优先权等OS的主要功能(4)1.4.2存储管理目的：方便用户使用，且提高存贮器利用率一、内存分配静态分配：动态分配：作业在内存中可移动为此，需内存分配的数据结构及内存分配和回收功能OS的主要功能(5)二、内存保护例：设置上、下界寄存器，每条指令进行越界检查（一般是硬件实现）三、地址映射地址范围 地址逻辑空间 逻辑地址相对地址（）物理空间 物理地址（绝对地址）OS的主要功能(6)四、内存扩充利用虚存技术，从逻辑上扩充内存容量系统应有：请求调入/置换功能以支持虚存技术OS的主要功能(7)1.4.3设备管理功能任务：提高I/O利用率和速度，方便用户一、缓冲管理缓冲区：用来解决CPU－I/O矛盾，如：CPU快则应多创建缓冲区。二、设备分配包括：设备，设备控制器，I/O通信的分配和回收OS的主要功能(8)1.4.3设备管理功能三、设备处理指控制设备进行实际的操作，包括读、写等以及向CPU发中断。设备处理/驱动程序应能根据用户的I/O请求，自动地构成通道程序。四、设备独立性和虚拟设备独立性，即program与设备无关性，使program易于重定向，增加了可移植性。虚拟设备OS的主要功能(9)1.4.4文件管理的功能任务：方便用户，提供安全性一、文件存贮空间的管理例：creatfile：文件系统根据文件长度自动分配连续或离散的扇区，并提供“一句柄”表示该文件。二、目录管理使用户按名存取，提高速度。三、文件的读、写管理和存取控制（保护）OS的主要功能(10)1.4.5用户接口一、命令接口由一组“命令”集组成，分为联机和脱机用户接口1.联机用户接口由一组键盘操作命令及命令解释程序所组成2.脱机（批处理用户接口）用JCL写作业说明书OS的主要功能(11)二、程序接口系统调用高级语言的库函数三、图形接口如win的copy文件，采用“拖”来完成，生动，不需记忆

1.5OS的结构设计无结构模块式层次式微内核1.5.1软件工程的基本概念软件：软件工程：运用系统、规范和可定量的方法开发、运行和维护软件。1.5.2传统的操作系统结构1.无结构操作系统一组过程集，各过程可相互调用，也叫整体系统结构。缺点：逻辑复杂，维护困难.传统的操作系统结构（2）2、模块化操作系统通过分解来控制大型软件复杂度。如：进程模块、内存模块…，各模块内进一步划分子模块。优点：提高了OS设计的可维护性增强的OS的可适应性加速了OS的开发过程：并行开发模块缺点：接口不易确定模块依赖关系可能复杂（对于大型软件而言）传统的操作系统结构（3）3、分层式操作系统有序分层的基本概念可简化设计的复杂度下层为上层提供服务层次的设置应考虑的因素程序嵌套：各模块间嵌套关系复杂运行频率：随层次的增高，相应软件的运行速度就随之下降公用模块：低层用户接口：高层1.5.3微内核操作系统结构客户进程进程服务器终端服务器文件服务器存储服务器核心请求回答C/S服务器模式提高了系统的灵活性和可扩充性提高了软件的可靠性适合于分布式系统面向对象的程序设计技术概念：优点：a.可扩展性b.继承性微内核技术引入：提高系统的灵活性；采用C/S模式基本功能进程、内存、IPC等基本管理功能微内核操作系统结构（2）第二章

进程管理2.1.1程序的顺序执行及特征一、程序执行有固定的时序。（图2-1p27）二、特征：顺序性、封闭性、可再现性2.1进程的基本概念I1C1P1I2C2P22.1.2前趋图定义有向无循环图表示方式： （1）p1--->p2（2）--->={(p1,p2)|p1必须在p2开始前完成}（图2-2P27）节点表示：一条语句，一个程序段，一进程。P1P1P1P12.1.3程序的并发执行一、多个程序的并发执行（可能性分析）I1I2I3I4C1C2C3C4P1P2P3P4t程序的并发执行(2)二、特征间断性失去封闭性：主要由共享资源引起不可再现性：P29例，设N的初值为n。有2个循环程序A和B，它们共享一个变量N，程序A每执行一次时，都要做N:=N+1;B则每次要执行Print(N),然后再做N:=0.若程序A,B以不同的速度运行有以下三种不同的结果程序的并发执行(3)N:=N+1在print(N)和N:=0之前，则N值分别为n+1,n+1,0.N:=N+1在print(N)和N:=0之后，则N值分别为n,0，1.N:=N+1在print(N)和N:=0之间，则N值分别为n,n+1,0.

2.1.4进程的特征和状态1.进程的特征和定义一、定义：程序的一次执行过程1.结构特征进程：由程序段、数据段及进程控制块三部分构成，总称“进程映像”。2.动态性由“创建”而产生，由“调度”而执行；由得不到资源而阻塞；由撤消而消亡。（而程序是静态的）。2.1.4进程的特征和状态(2)3.并发性只有建立了进程，才能并发执行。4.独立性。独立运行，独立获得资源。5.异步性：（间断性）2.1.4进程的特征和状态(3)2.进程的三种基本状态（图2-5p31）就绪状态执行状态阻塞状态就绪阻塞执行时间片完进程调度I/O请求I/O完成图2－5进程的三种基本状态及其转换2.1.4进程的特征和状态(4)3.挂起状态（被换出内存的状态）引入原因终端用户请求父进程请求负荷调节需要操作系统需要进程状态的转换(图2-6)活动就绪

静止就绪活动阻塞

静止阻塞静止就绪

活动就绪静止阻塞

活动阻塞图2－6具有挂起状态的进程状态图执行活动就绪静止就绪活动阻塞静止阻塞激活挂起激活挂起释放释放挂起请求I/O实验写一个程序描述进程状态迁移过程。要求：提供导致进程状态变化的调用接口，包括创建、删除、调度、阻塞、时间到、挂起、激活等。实现进程列表显示的接口。注：这里设计的进程是一个假设的对象实体，是由程序自己创建和删除，不是系统维护的进程。2.1.5进程控制块1.进程控制块的作用是进程存在的唯一标志；PCB(processcontrolblock)常驻内存2.进程控制块中的信息标识、处理机状态，进程调度信息，进程控制信息pid进程状态现场优先级阻塞原因程序地址同步机制资源清单链接指针2.1.5进程控制块(2)3.PCB的组织链接（p33图2-7）索引(p34图2-8)执行指针就绪队列指针阻塞队列指针空闲队列指针PCB14PCB23PCB30PCB48PCB5PCB67PCB79PCB80PCB91等待队列示例structwait_queue{ structtask_struct*task; structwait_queue*next;};PCBPCBPCB2.1.5进程控制块(3)3.PCB的组织索引(p34图2-8)PCB1PCB2PCB3PCB4PCB5PCB6PCB7执行指针就绪表指针阻塞表指针补充PCB和进程的代码数据放在一起吗？系统态和用户态系统空间和用户空间系统调用和普通调用的区别？系统调用会引起从用户态进入核心态2.2进程控制2.2.1进程的创建一、进程图：描述了进程的家族关系：（P34图2-9）子进程可继承父的资源，撤消时应归还给父进程，父的撤消会撤消全部子进程。二、引起创建进程的事件：1.用户登录：为终端用户建立一进程2.作业调度：（不是进程调度）为被调度的作业建立进程3.提供服务：如要打印时建立打印进程2.2.1进程的创建(2)4.应用请求：由应用程序建立多个进程三、进程的创建：（creat原语）1.申请空白PCB（一个系统的PCB是有限的）2.为新进程分配资源（不同于一般的分配，PCB-LIST在一个特殊区域）3.初始化PCB4.将新进程插入就绪队列。2.2.2进程的终止一、引起进程终止的事件1.正常结束：如Halt、logoff2.异常结束：如Protecterror、overtime等3.外界干预：a.系统员kill进程；b.父进程终止；c.父进程请求。2.2.2进程的终止(2)二、进程的终止过程（1）检查进程状态；（2）执行态――>中止，且置调度标志为真。（3）有无子孙需终止。（4）归还资源给其父进程或系统。（5）从PCB队列中移出PCB.2.2.3进程的阻塞与唤醒一、引起进程阻塞和唤醒的事件1.请求系统服务而得不到满足时，如问系统请求打印。2.启动某种操作而需同步时：如该操作和请求该操作的进程需同步运行（即非异步操作）。3.新数据尚未到达：如进程A写，进程B读，则A未写，完B不能读。4.无新工作可做。2.2.3进程的阻塞与唤醒(2)二、进程阻塞过程：是进程自身的一种主动行为a.调block原语b.停止执行，修改PCB入阻塞队列（一个或多个），并转调度。三、唤醒过程其它相关进程完成。a.wakeup原语b.修改PCB，入就绪队列可见，有block原语，在其它进程中就应有wakeup原语。2.2.4进程的挂起与激活一、进程的挂起过程由进程自己或其父进程调suspend原语完成，将该进程PCB移到指定区域，注意状态的改变，有可能要重新调度。二、进程的激活过程。active原语（如在外存，调入内存，改变状态，根据情况看是否调度，如抢先或非抢先）。阻塞、唤醒一般由OS实现，而挂起与激活可由用户干预。2.3进程同步同步：并发进程在执行次序上的协调，以达到有效的资源共享和相互合作，使程序执行有可再现性。2.3.1进程同步的基本概念1.两种形式的制约关系资源共享关系：（进程间接制约）需互斥地访问临界资源。相互合作关系：（进程直接制约）2.临界资源：（一次仅允许一个进程访问的资源）引起不可再现性是因为临界资源没有互斥访问。生产者－消费者问题Varn,integer;Typeitem=…;varbuffer:array[0,1,…,n-1]ofitem;in,out:0,1,…,n-1;counter:0,1,…,n;生产者－消费者问题producer:repeat… produceaniteminnextp;…whilecounter=ndono-op;buffer[in]:=nextp;in:=(in+1)modn;counter:=counter+1;untilfalse;consumer:repeatwhilecounter=0dono-op;nextc:=buffer[out];out:=(out+1)modn;counter:=counter-1;consumertheiteminnextc;untilfalse;生产者－消费者问题（2）设counter的初值为5register1:=counter;register2:=counter;register1:=register1+1;register2:=register2-1;counter:=register1;counter:=register2;register1:=counter; (register1:=5)register1:=register1+1; (register1:=6)register2:=counter; (register2:=5)register2:=register2-1; (register2:=4)counter:=register1; (counter:=6)counter:=register2; (counter:=4)定义：进程访问临界资源的那段代码。访问临界资源的描述：进入区：检查有无进程进入临界区：退出区：将访问标志复位Repeat Entrysection Criticalsection Exitsection Untilfalse3.临界区4.同步机制应遵循的准则1.空闲让进2.忙则等待3.有限等待：应保证为有限等待，不会产生死等。4.让权等待：不能进入临界区的执行进程应放弃CPU执行权。2.3.2信号量机制1整型信号量是一个整型量，通过2个原子操作wait(s)和signal(s)来访问。Wait(s):whiles<=0dono-op s:=s-1;Signal(s): s:=s+1;2记录型信号量由于整型机制中会不断测试不满足“让权等待”而引入typesemaphore=recordvalue:integer;L:listofprocess;endL:为进程链表，用于链接所有等待该类资源进程。procedurewait(s)vars:semaphorebegins.value:=s.value–1;ifs.value<0themblock(S,L)end2记录型信号量(2)proceduresignal(S)vars:semaphonebegins.value:=s.vaule+1ifs.value<=0thenwakeup(s.L)end用wait(s)和signal(s)实现同步与互斥。在记录型信号量机制中：s.value初值：表示系统中某类资源的数目。s.value<0:表该信号量链表中已阻塞进程的数目。3AND型信号量当不用它时，有可能发生系统死锁。死锁：在无外力作用下的一种僵持状态。AND信号量例：P42.特点：要么全分配，要么一个也不分配。3AND型信号量processA:wait(Dmutex);wait(Emutex);processB:wait(Emutex);wait(Dmutex);若2进程交替执行，则死锁3AND型信号量Swait(s1,s2,…,sn) ifs1≥1and…andsn≥1then fori:=1tondosi:=si-1;endfor else placetheprocessinthewaitingqueuewiththefirstsifoundwithsi<1,andsettheprogramcountofthisprocesstothebeginningofswaitoperation endifSsignal(s1,s2,…,sn) fori:=1tondosi:=si+1;removealltheprocesswaitinginthequeueassociatedwithsiintothereadyqueueendfor4信号量集(略)为提高效率而对AND信号的扩充。（P43）三种特例：（1）Swait(S,d,d)：允许每次申请d个资源。 当资源数少于d时，不予分配。（2）Swait(s,1,1)：S>1，记录型信号量。 S=1时，互斥型信号量。（3）Swait(s,1,0)，可控开关，当时，允许进入，S<1时，不能进入。2.3.3信号量的应用1.利用信号量实现互斥varmutex:semaphore:=1 begin parbegin process1:begin repeat

wait(mutex); criticalsetion

signal(mutex); remaindersection untilfalse; end1.利用信号量实现互斥(2)process2:begin repeat

wait(mutex); criticalsetion

signal(mutex); remaindersection untilfalse; endparend

2.利用信号量来描述前趋关系(1)S1S2S3S4S5S6abcdegf图2－10前趋图举例利用信号量来描述前趋关系(2)Vara,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0;Begin parbegin beginS1;signal(a);signal(b);end; beginwait(a);S2;signal(c);signal(d);end; beginwait(b);S3;signal(e);end; beginwait(c);S4;signal(f);end; beginwait(d);S1;signal(g);end; beginwait(e);wait(f);wait(g);S6;end; parendend2.4经典进程同步问题2.4.1生产者－－消费者问题2.4.2哲学家进餐问题2.4.3读者－－写者问题一、利用记录型信号量解决生产者一消费者问题mutex：使诸进程互斥地访问缓冲区（n个缓冲区）empty、full：空、满缓冲区数量。Varmutex,empty,full:semaphore:=1,n,0;buffer:array[0,1,…,n-1]ofitem; in,out:integer:=0,0; begin parbeginproducer:begin repeat … Produceaniteminnextp; …一、利用记录型信号量解决生产者一消费者问题wait(empty);wait(mutex);buffer(in):=nextp;in:=(in+1)modn;signal(mutex);signal(full);Untilfalse;endconsumer:begin repeat

wait(full);wait(mutex);nextc:=buffer(out);out:=(out+1)modn;signal(mutex);signal(empty);Consumertheiteminnextc;Untilfalse;endparendend二、利用AND信号量解决生产者——消费者问题varmutex,empty,full:semaphore:=1,n,0; buffer:array[0,…,n-1]ofitem; inout:integer:=0,0;begin parbegin producer:begin repeat … produceaniteminnextp; …

swait(empty,mutex); buffer(in):=nextp;in:=(in+1)modn;ssingal(mutex,full);Untilfalse;EndConsumer:beginrepeat

swait(full,mutex); nextc:=buffer(out); out:=(out+1)modn;

ssignal(mutex,empty); consumertheiteminnextc;untilfalse;endparendend2.4.2哲学家进餐问题1.利用记录型信号量解决哲学家进餐问题Varchopstick:array[0,…,4]ofsemaphore;Repeatwait(chopstick[i]);wait(chopstick[(i+1)mod5]);…eat…signal(chopstick[i]);signal(chopstick[(i+1)mod5]);…think;Untilfalse2.4.2哲学家进餐问题1.利用AND信号量解决哲学家进餐问题Varchopstick:array[0,…,4]ofsemaphore:=(1,1,1,1,1);processiRepeatthink;Sswait(chopstick[(i+1)mod5],chopstick[i]);eatSsignal(chopstick[(i+1)mod5],chopstick[i]);Untilfalse2.4.3读者——写者问题特点： 读进程可共享同一对象。写进程不可共享同一对象。一、利用记录型信号量解决读者——写者问题varrmutex,wmutex:semaphore:=1,1;readcount:integer:=0; begin parbegin reader:begin repeat wait(rmutex); ifreadcount=0thenwait(wmutex); readcount:=readcount+1; signal(rmutex); … performreadoperation一、利用记录型信号量解决读者——写者问题 performreadoperation … wait(rmutex); readcount:=readcount-1; ifreadcount=0thensignal(wmutex); signal(rmutex); untilfalse; end

一、利用记录型信号量解决读者——写者问题 writer:begin repeat wait(wmutex) performwriteoperation; signal(wmutex) untilfalse; endparendend二、信号量集解决读者——写者问题(略)varRNinteger; L,mx:semaphore:=RN,q;beginparbeginreader:begin repeatswait(L,1,1);swait(mx,1,0);… performreadoperation; … ssignal(L,1);untilfalse;endwriter:begin

二、信号量集解决读者——写者问题（略）writer:beginrepeatswait(mx,1,1;L,RN,0);performwriteoperation;ssignal(mx,1);untilflase;endparendend

2.5管程机制引入原因：为了避免凡要使用临界资源的进程都自备同步操作wait(s)和signal(s).将同步操作的机制和临界资源结合到一起，形成管程。2.5.1管程的基本概念一、定义：一个数据结构和能为并发进程所执行的一组操作。局部于管程的共享变量。对该数据结构进程操作的一组过程。对局部管程数据设置初值。二、条件变量： x.y:x.wait;x.signal;x.queue2.5.2利用管程解决生产者——消费者问题一、建立管程：PC包括：二过程： （1）put(item)过程；（2）get(item)过程一变量：count≥n时满；≤0时空初始：in=out=count=0Typeproducer-consumer=monitorvarin,out,count：integer;buffer:array[0,…,n-1]ofitem;notfull,notempty:condition;procedureentryput(item)procedureentryget(item)2.5.2利用管程解决生产者——消费者问题Procedureentryput(item) begin ifcount≥nthennotfull.wait; buffer(in):=nextp; in:=(in+1)modn count:=count+1; ifnotempty.queuethennotempty.signal; endProcedureentryget(item) begin ifcount≤0thennotempty.wait; nextc:=buffer(out); out:=(out+1)modn count:=count-1; ifnotfull.queuethennotfull.signal; endBeginin:=out:=0;count:=0end2.5.2利用管程解决生产者——消费者问题例：producer:begin repeat produceaitemnextp PC.put(item); untilfalse. EndConsumer:begin repeat PC.get(item); Consumetheiteminnextc; Untilfalse end 可见，由管程来实现后，进程的同步更简单明了。练习a,b两点间是一段东西向的单行车道，现要设计一个自动管理系统，管理规则如下：当ab间有车辆在行驶时同方向的车可以同时驶入ab段，但另一方向的车必须在ab段外等待；当ab之间无车时，到达a（或b）的车辆可以进入ab段，但不能从a，b点同时驶入；当某方向在ab段行驶的车辆使出了ab段且无车辆进入ab段时，应让另一方向等待的车辆进入ab段行驶。请用wait,signal工具对ab段实现正确管理。答：Semaphores,mutexab,mutexbaPab：Wait(mutexab)Countab++Ifcountab=1thenwait(s);Signal(mutexab)

…..wait(mutexab)countab--;ifcountab=0thensignal(s)signal(mutexab);答：Pba:wait(mutexba)countba=countba+1;Ifcountba=1thenwait(s)wait(mutexba)enter; ……wait(mutexba)countba--;ifcountba=0thensignal(s) signal(mutexba);2.6进程通信概念：进程间的信息交换。实例：信号量机制（一种低级通信） 缺点：（1）效率低 （2）通信对用户不透明高级通信特点：效率高，通信实现细节对用户透明2.6.1进程通信的类型一、共享存贮器系统1.基于共享数据结构的通信方式：produce-consume中的缓冲区，低效，不透明。系统只提供了一共享存贮器，适于少量通信。2.基于共享存储区的通信方式：系统提供：共享存储区。通信过程：（1）向系统申请一个或多个分区（2）获得分区获后即可读/写.特点：高效，速度快。2.6.1进程通信的类型二、消息传递系统（可用于异种机）信息单位：消息（报文）是目前的主要通信方式，分为直接通信方式、间接通信方式实现：一组通信命令（原语），具有透明性--->同步的实现。三、管道通信管道：连接一个读进程和一个写进程之间通信的共享文件。功能：大量的数据发收。注意：（1）互斥（2）同步（3）对方是否存在2.6.2直接/间接通信方式（消息通信的2种方式）一、直接send(Receiver,message)receive(Sender,message)例：解决生产—消费问题。 repeat …produceaniteminnextp;…send(consumer,nextp);untilfalse;repeatreceive(producer,nextc);…consumertheiteminnextc;untilfalse;2.6.2直接/间接通信方式（消息通信的2种方式）二、间接（可以实现非实时通信）优点：在读/写时间上的随机性写进程――>信箱（中间实体）――>读进程原语（1）信息的创建与撤消：信箱名属性（公用、私用、共享）（共享者名字）（2）消息的发送和接收Send(mailbox,message)Receive(mailbox,message)2.6.2直接/间接通信方式（消息通信的2种方式）二、间接（可以实现非实时通信）信箱类型（1）私用：拥有者有读/写数，其它只有写权，（单向）存在期＝进程存在期。（2）公用：系统创建，双向，存在期=系统存在期。（3）共享信箱：一般进程创建，并指明其共享者，是双向。发送—接收进程之间的关系：（1）一对一关系；（2）多对一关系；（3）一对多关系；（4）多对多关系：公用信箱。2.6.3消息传递系统中的几个问题一、通信链路：（1）显式建立：（进程完成）（2）隐式建立：（系统完成）链路类型：（1）由连接方法分：点—点链路，多点链路。（2）由通信方式分：单向、双向。（3）由容量分：无容量（无缓冲区）、有（有缓冲区）。2.6.3消息传递系统中的几个问题二、消息格式：消息头：含控制信息如：收/发进程名，消息长度、类型、编号消息内容：定长消息：系统开销小，用户不便（特别是传长消息用户）变长消息：开销大，用户方便。2.6.3消息传递系统中的几个问题三、进程同步方式1.发送和接收进程阻塞（汇合）用于紧密同步，无缓冲区时。2.发送进程不阻塞，接收进程阻塞（多个）相当于接收进程（可能是多个）一直等待发送进程，如：打印进程等待打印任务。3.发送/接收进程均不阻塞一般在发、收进程间有多个缓冲区时。2.6.4消息缓冲队列通信机制一、数据结构1.消息缓冲区typemessagebuffer=recordsender:size:text:next:指向下一指针2.PCB中应增数据项：typepcb=recordmq 消息队列指针mutex消息队列互斥信息量sm 消息队列资源信息量（表资源消息数）2.6.4消息缓冲队列通信机制二、发送原语proceduresend(receiver,a)begin getbuf(a.size,i); i.sender:=a.sender; i.size:=a.size; i.text:=a.text; i.next:=0; getid(PCBset,receiver.j);

wait(j.mutex); insert(j.mq,i);

signal(j.mutex);

signal(j.sm);end2.6.4消息缓冲队列通信机制三、接收原语procedurereceive(b) begin j:=internalname;

wait(j.sm);

wait(j.mutex); remove(j.mq,i);

signal(j.mutex); b.sender:=i.sender; b.size:=i.size; b.text:=i.text; end2.6.4消息缓冲队列通信机制mqmutexsmsender:Asize:5text:Hellosend(B,a)sender:Asize:5text:hellonext:0发送区Asender:Asize:5text:Helloreceive(b)接收区Bab进程APCB(B)进程B练习试说明如果使用send_mailbox和receive_mailbox原语实现打印文件的系统。欲打印的进程将要打印的文件名发送到邮箱printer,打印机假脱机将打印邮箱中出现名字的任何文件//processwishtoprintChar filename[];Status=send_mailbox(“printer”,filename);If(status<0){//failure}//printspoolercharfilename[]while(true){ status=receive_mailbox(“printer”,filename); if(status<0) {//failure} print(filename);}2.7线程2.7.1线程的基本概念1.线程的引入减少并发执行时的时空开销，进程的创建、撤消、切换较费时空，因它既是调度单位，又是资源拥有者。线程是系统独立调度和分派的基本单位，其基本上不拥有系统资源，只有少量资源（IP，寄存器，栈），但共享其所属进程所拥有的全部资源。2.7线程2.7.1线程的基本概念2.线程的属性轻型实体独立调度和分派的基本单位可并发实体共享进程资源3.线程的状态状态参数寄存器状态、堆栈、运行状态、优先级、线程专有存储器、信号屏蔽线程的运行状态2.7线程2.7.1线程的基本概念4.线程的创建和终止5.多线程中的进程拥有系统资源的基本单位，不再是一个开执行的实体。2.7.2线程的同步和通信1.互斥锁阻塞方式lock(mutex)访问unlock(mutex)非阻塞方式if（trylock）thenelse2.7.2线程的同步和通信2.条件变量略3.信号量机制私用信号量（privatesemaphore)作用域在一个进程中公用信号量（publicsemaphore)作用于多个进程间2.7.3内核级和用户级线程用户级线程不依赖于内核，内核级依赖内核，其创建、撤消和切换都由内核实现，在内核中为其保留一张线程控制块。比较：1.线程的调度和切换速度：内核级线程切换类似于进程切换，但速度快于进程切换。用户级线程切换通常发生在同一用户进程的诸线程间，无需进入内核，更快。2.7.3内核级和用户级线程2.系统调用（用户级线程对内核是以进程为单位；这时进入系统态，并阻塞调用者）当一个进程含多个用户线程，其中某一个线程进行系统调用，由于内核不知道这些线程的存在，因此将进程阻塞。当一个进程含多个系统线程，其中某一线程进行系统调用，则阻塞该线程，进程仍可运行。3.线程执行时间（用户级以用户进程为单位；由内核分配）用户级线程以进程为单位平均分配时间，对线程间并发执行并不有利。系统级线程以线程为单位平均分配时间。2.7.3内核级和用户级线程思考进程间通信和同一进程内线程间通信的效率？第三章

处理机的调度和死锁

3.1处理机调度的基本概念3.1高、中、低三级调度1、高级调度（作业调度、长程调度、接纳调度）将外存作业调入内存，创建PCB等，插入就绪队列。一般用于批处理系统，分/实时系统一般直接入内存，无此环节。调度特性1.接纳作业数（内存驻留数）太多―――> 周转时间T长太少―――> 系统效率低2.接纳策略：即采用何种调度算法：FCFS、短作业优先等处理机调度的基本概念（2）2、低级调度（进程调度，短程调度）主要是由分派程序（Dispatcher）分派处理机。1.非抢占方式： 简单，实时性差(如win31)2.抢占方式（1）时间片原则（2）优先权原则（3）短作业优先原则。3、中级调度（中程）为提高系统吞吐量和内存利用率而引入的一内------外存对换功能（换出时，进程为挂起或就绪驻外状态）

运行频率：低>中>高。问？三种调度被引发的事件？事件的表现方式？3.1.2调度的队列模型一、仅有进程调度的队列模型就绪队列CPU阻塞队列交互用户时间片完进程调度进程完成等待事件事件出现3.1.2调度的队列模型二、具有高/低级模型就绪队列CPU阻塞队列时间片完进程调度进程完成等待事件1事件1出现后备队列阻塞队列等待事件2事件2出现作业调度三、具有三级调度就绪队列CPU就绪、挂起队列时间片完进程调度进程完成后备队列阻塞、挂起队列事件出现作业调度阻塞队列等待事件挂起事件出现中级调度交互型作业3.1.3选择调度方式和算法的若干准则一、面向用户的准则1．周转时间短（常用于批处理系统）概念：作业从提交――>完成的时间.分为：（1）驻外等待调度时间（2）驻内等待调度时间（3）执行时间（4）阻塞时间一、面向用户的准则平均周转时间

平均带权

可见带权w越小越好,Ts为实际服务时间。3.1.3选择调度方式和算法的若干准则一、面向用户的准则2．响应时间快：（对交互性作业）概念：键盘提交请求到首次响应时间（1）输入传送时间（2）处理时间（3）响应传送时间3．截止时间的保证（特别于实时系统）4．优先权准则：（即需要抢占调度）3.1.3选择调度方式和算法的若干准则二、面向系统的准则1．吞吐量高（特别于批处理）：单位时间完成作业数2．处理机利用率好：（因CPU贵，特别于大中型多用户系统）3．各类资源的平衡利用。（？折算标准）3.1.3选择调度方式和算法的若干准则3.2调度算法——是一个资源分配问题3.2.1先来先服务和短作业（进程）优先调度算法1.FCFS特点：简单，有利于长作业即CPU繁忙性作业2.短作业进程优先调度算法：SJ(P)F提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量）特点：对长作业不利，有可能得不到服务（饥饿）估计时间不易确定例进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B110011011001C21101102100100D31001022021991.99图3.4FCFS和SJF比较进程名ABCDE平均到达时间01234服务时间43524FCFS完成时间47121418周转时间461011149带权周转时间1225.53.52.8SJF完成时间4918613周转时间4816398带权周转时间12.673.11.52.252.13.2.2高优先权优先调度算法1.优先权调度算法类型非抢占式优先权算法抢占式优先权算法，实时性更好。2.优先权类型：1．静态优先权：进程优先权在整个运行期不变。确定优先权依据（1）进程类型（2）进程对资源的需求；（3）根据用户需求。特点：简单，但低优先权作业可能长期不被调度。3.2.2高优先权优先调度算法(2)2．动态优先权：如：优先权随执行时间而下降，随等待时间而升高。响应比Rp=（等待时间＋服务时间）/服务时间作为优先权优点：长短兼顾缺点：需计算Rp3.高响应比优先算法：特点：响应比Rp=（tw+ts）/ts（1）短作业RP大。（2）ts（要求服务时间）相同的进程间相当于FCFS。（3）长作业等待一段时间仍能得到服务。3.2.3基于时间片的轮转调度算法1.时间片轮转时间片大小的确定太大：退化为FCFS；太小：系统开销过大系统对响应时间的要求；T=nq就绪队列中进程的数目；系统的处理能力：（应保证一个时间片处理完常用命令）3.2.3基于时间片的轮转调度算法2.多级反馈队列调度特点：长、短作业兼顾，有较好的响应时间（1）短作业一次完成；（2）中型作业周转时间不长；（3）大型作业不会长期不处理。就绪队列1至CPUS1就绪队列2S2至CPU就绪队列3S3至CPU就绪队列nSn至CPU时间片：S1<S2<S3图3－5多级队列反馈调度算法3.3.1实现实时调度的基本条件1．提供必要的调度信息（1）就绪时间；（2）开始/完成截止时间；（3）处理时间；（4）资源要求；（5）优先级；2．系统处理能力强3.3实时调度Ci为处理时间，Pi为周期时间（基于周期性实时任务）3.3.1实现实时调度的基本条件3.采用抢占调度方式剥夺方式：一般都采用此非剥夺方式（实现简单）：一般应使实时任务较小，以及时放弃CPU。4.具有快速切换机制具有快速响应外部中断能力。快速任务分派3.3实时调度3.3.2实时调度算法的分类1非抢占式调度算法时间片轮转 秒级非抢占优先权（协同） 秒~毫秒级2抢占式调度算法时钟中断抢占优先权 毫秒级基于抢占点抢占立即抢占immediatepreemption毫秒~微秒级只要不在临界区即抢占（中断引发）进程1进程2进程n实时进程调度时间实时进程要求调度调度实时进程运行a非抢占轮转调度当前进程实时进程实时进程要求调度当前进程运行完成b非抢占优先权调度调度时间c基于时钟中断抢占的优先权抢占调度当前进程实时进程实时进程要求调度抢占时刻（其它中断）b立即抢占优先权调度当前进程实时进程实时进程要求调度时钟中断到达时调度时间调度时间3.3.3常用的几种实时调度算法1.最早截止时间优先EDF（earliestdeadlinefirst)算法根据任务的截止时间来确定任务的优先级截止时间越早，优先级越高可以是抢占式或非抢占式最早截止时间优先EDF例134213421234t开始截止时间任务到达任务执行图3－7EDF算法用于非抢占调度方式2.最低松弛度优先LLF算法松弛度：若A进程需在200ms时完成，其本身运行需要100ms，当前时刻是10ms，则A的松弛度为：200－100－10＝90主要用于可抢占的调度方式中例：A1A2A3A4A5A6A7A8B1B2B3020406080100120140160t图3－8A/B任务每次必须完成的时间最低松弛度优先LLF算法(2)A1(10)A2(10)A3(10)A4(10)t01020304050607080t1=0B1(20)B1(5)B2(15)B2(10)t1t2t3t4t5t6t7t83.4多处理机系统中的调度1.紧密耦合MPS和松弛耦合MPS紧密耦合共享RAM和I/O高速总线和交叉开关连接松弛耦合独立RAM和I/O通道和通信线路连接2.对称多处理器系统和非对称多处理器系统处理器是否结构相同3.4.2进程分配方式1.SMP中进程分配方式静态分配动态分配可防止系统中多个处理器忙闲不均2.非SMP中进程分配方式进程调度在主处理器上执行有潜在的不可靠性3.4.3进程（线程）调度方式

1.自调度各个处理机自行在就绪队列中取任务。特点；简单，分布式调度，调度算法可采用前述方法，多个CPU利用率都不错（不会闲）但：瓶颈问题，（单队列）低效性；（需拷贝现场）线程切换频繁（当线程合作时,各线程并行的条件不容易满足）2.成组调度优点：（1）对相互合作的进（线）程组调度，可以减小切换，减小系统开销。（2）每次分配一组CPU，减少了调度频率。分配时间（1）面向程序（2）面向线程：使处理机利用率更高。2.成组调度应用程序A应用程序BCpu1线程1线程1Cpu2线程2空闲Cpu3线程3空闲Cpu4线程4空闲时间1/21/2浪费37.5%应用程序A应用程序BCpu1线程1线程1Cpu2线程2空闲Cpu3线程3空闲Cpu4线程4空闲时间4/51/5浪费15%3.专用处理机分配

引入：多处理机系统，每个处理已不再属宝贵资源。特点：每个进（线）程专用处理机，使其切换小，提高效率。主要用于大型计算，实时系统3.5产生死锁的原因和必要条件3.5.1产生死锁的原因。一、竞争资源引起死锁。1．可剥夺（CPU、内存，）和非剥夺性（打印机，磁带机）资源2．竞争非剥夺性资源——可造成死锁p1p2R1R23.5产生死锁的原因和必要条件3．竞争临时性资源临时性资源是指由一个进程产生，被另一个进程使用一段时间后便无用的资源。二、进程推进顺序不当引起死锁。213DP2Req(R2)P2Req(R1)P1Req(R1)P1Req(R2)P2Rel(R2)P2Rel(R1)P1Rel(R1)P1Rel(R2)43.5.2产生死锁的必要条件1．互斥条件（资源的临界性）2．请求和保持条件3．不剥夺条件4．环路等待3.5.3处理死锁的基本方法1．预防；破坏4个条件之一：有效，使资源利用率低。2．避免：防止进入不安全态。3．检测：检测到死锁再清除。4．解除：与“检”配套。3.6死锁预防和避免3.6.1死锁预防一、互斥条件是资源固有属性，不能避免。二、摒弃请求和保持条件全分配，全释放（AND）缺点：（1）延迟进程运行 （2）资源严重浪费三、摒弃“不剥夺”条件 增加系统开销，且进程前段工作可能失效。3.6死锁预防和避免3.6.1死锁预防 四、摒弃“环路”条件有序资源分配法：为资源编号，申请时需按编号进行。缺点：（1）新增资源不便，（原序号已排定）（2）用户不自由（3）资源与进程使用顺序不同造成浪费3.6.2系统的安全状态在“避免死锁”方法中的判断条件1.安全状态按某种顺序并发进程都能达到获得最大资源而顺序完成的序列为安全序列。能找到安全序列的状态为安全状态。3.6.2系统的安全状态（2）2.安全状态例进程最大需求已分配可用P11053P242P392安全序列：p2

p1

p33.6.2系统的安全状态（3）3安全——不安全的转换上例中，若P3再申请一台，则不安全进程最大需求已分配可用P11052P242P3933.6.3利用银行家算法避免死锁1．数据结构available[j]=k:系统现有Rj类资源k个；max[i,j]=k:进程i需要Rj的最大数k个；alloc[i,j]=k:进程i已得到Rj类资源k个；need[i,j]=k: 进程i需要Rj类资源k个有：need[i,j]=max[i,j]－alloc[i,j]requesti 进程i请求资源数worki：进程i执行完后系统应有资源数（也即可用数）finish[i]：布尔量，表进程i能否顺序完成。3.6.3利用银行家算法避免死锁2．银行家算法reqi<=needierrorreqi<=availiblock3.6.3利用银行家算法避免死锁avail=avail-reqialloci=alloci+reqineedi=needi-reqifinish[i]=.F.needi<=workwork=work+allocifinish[i]=.T.4实例MaxABCAllocationABCNeedABCAvailableABCp0753010743332(230)p1322200(302)122(020)p2902302600p3222211011p4433002431T0时刻的资源分配表4实例WorkABCNeedABCAllocABCWork+allocABCFinishp1332122200532truep3532011211743truep4743431002745truep27456003021047truep010477430101057trueT0时刻的安全序列4实例WorkABCNeedABCAllocABCWork+allocABCFinishp1230020302532truep3532011211743truep4743431002745truep0745743010755truep27556003021057trueP1申请资源(1,0,2)时安全性检查(安全)4实例AllocationABCNeedABCAvailableABCp0030723210p1302020p2302600p3211011p4002431为P0分配（0，2，0）后的情况（不安全）3.7死锁的检测和解除3.7.1检测1.资源分配图p1p23.7死锁的检测和解除2.死锁定理简化资源分配图若能完全简化则消去所有的边。定理：死锁状态的充分条件，资源分配图不可完全简化3.检测死锁的算法：Work=availableL:={Li|alloci=0reqi=0}(孤立进程点)ForallLiLdoBegin Forallreqi<=workdo Begin Work=work+alloci L=Li∪L end EndDeadlock=~(L={p1…pn})3.7死锁的检测和解除解除检测到死锁后，回退到上一状态（要进行资源剥夺，且需保存以前状态的分配信息），重新分配，若不行，继续回退……，第四章存储器管理4.1程序的装入和链接编辑―――编译―――链接―――装入―――运行图4.14.1.1程序的装入1、绝对装入：编译后，装入前已产生了绝对地址（内存地址），装入时不再作地址重定位。绝对地址的产生：（1）由编译器完成，（2）由程序员编程完成。对（1）而言，编程用符号地址。2、可重定位装入；静态重定位：装入时完成，主要工作是对相对地址中的指令和数据地址的调整过程，例：图4－2问题：如何知道哪些位置需调整？链接时产生可装入模块的具体功能?0100025005000LOAD1,2500LOAD1,250036536510000110001250015000作业地址空间内存空间图4-24.1.1程序的装入3.动态运行时装入在装入后不能移动，该情况一般在执行时才完成相对——绝对地址的转换且有硬件的支持,能保证进程的可移动性。4.1.2程序的链接1、静态链接a．对相对地址的修改b．变换外部调用符号2、装入时动态链接a.便于修改和更新b.便于实现对目标模块的共享3、运行时动态链接模块ACALLB;RETURN模块BCALLC;RETURN模块CRETURN0L-10M-10N-1(a)目标模块模块AJSRL;RETURN模块BJSRL+M;RETURN模块CRETURN0L-1LL+M-1L+ML+M+N-1(b)装入模块4.2连续分配方式单一连续分配用于单用户，单任务中分区式分配固定式可变式可重定位分区分配4.2.1单一连续分区系统区用户区存贮保护一般不设置保护也可，因单任务。

4.2.2固定分区特点：有n个分区，则可同时装入n个作业/任务。一、分区大小：相等:不相等：不相等利用率更高。二、内存分配：数据结构将分区按大小排序，并将其地址、分配标识作记录例：dos的MCB三、特点：简单，有碎片（内零头）图4－4a分区号大小（K)起址（K）状态11220已分配23232已分配36464已分配4128128已分配图4－4b操作系统作业A作业B作业C24K32K64K128K256K~~~~分配情况4.2.3可变式分区（比固定式分区有改善）一、数据结构1．空闲分区表2．空闲分区链前向指针N个字节可用后向指针N+2N+20（分配标识）0