操作系统精-孟庆昌ppt课件

.,第1章操作系统引论,.,参考书：操作系统精髓与设计原理第五版WilliamStalling著操作系统原理与设计曹先彬陈兰香编操作系统第二版孟庆昌牛欣源编,.,本章内容提要,计算机硬件结构什么是操作系统操作系统概念操作系统的主要功能操作系统的地位操作系统的发展历程操作系统的类型操作系统的特征操作系统结构设计,.,1.1计算机硬件结构,计算机系统是由硬件和软件组成的硬件是软件建立与活动的基础软件是对硬件进行管理和功能扩充计算机硬件结构由五大功能部件组成，即：运算器、控制器、存储器、输入设备和输出设备。它们经由系统总线连接在一起，实现彼此通信。,.,现代计算机硬件结构,.,1.1.1处理器,CPU工作的基本周期是：提取指令，译码分析，执行指令每个CPU可以执行的指令集是专用的所有CPU都包含某些寄存器通用寄存器专用寄存器程序计数器栈指针PSW（程序状态字）两种处理机执行状态核心态用户态,.,1.1.2存储器,寄存器高速缓存内存磁盘磁带,.,1.1.3I/O设备,通常由控制器和设备本身两部分组成控制器设备设备驱动程序,.,1.1.4总线,总线分类数据总线地址总线控制总线,.,1.2什么是操作系统,1.2.1操作系统概念1操作系统作为扩展机器把硬件细节与程序员隔离开，隐藏了底层硬件的特性功能更强、使用更方便2操作系统作为资源管理器监视各种资源，随时记录它们的状态；实施某种策略以决定谁获得资源，何时获得，获得多少；分配资源供需求者使用；回收资源，以便再分配。3.操作系统的用户观点和系统观点,.,定义：操作系统是控制和管理计算机系统内各种硬件和软件资源，有效地组织多道程序运行的系统软件（或程序集合），是用户与计算机之间的接口。,.,操作系统是系统软件基本职能是控制和管理系统内各种资源，有效地组织多道程序的运行提供众多服务，方便用户使用，扩充硬件功能,.,1.2.2操作系统的主要功能,1存储管理内存分配地址映射内存保护内存扩充,.,1.2.2操作系统的主要功能,2作业和进程管理作业和进程调度进程控制进程通信,.,1.2.2操作系统的主要功能,3设备管理缓冲区管理设备分配设备驱动设备无关性,.,1.2.2操作系统的主要功能,4文件管理功能文件存储空间的管理文件操作的一般管理目录管理文件的读/写管理和存取控制,.,1.2.2操作系统的主要功能,5用户接口程序接口命令行接口图形用户接口（GUI）,.,1.2.3操作系统的地位,计算机系统的层次关系,.,简言之，软件是计算机执行的程序软件通常可分为三大类应用软件支撑软件系统软件操作系统是裸机之上的第1层软件，它只在核心态模式下运行。通常把经过软件扩充功能后的机器称为“虚拟机”,.,1.3操作系统的发展历程,1.3.1操作系统的形成1手工操作阶段2早期批处理阶段早期联机批处理早期脱机批处理3多道批处理系统,.,多道批处理系统,.,多道程序设计：在内存中同时存放多道程序，在管理程序的控制下交替地执行。这些作业共享CPU和系统中的其他资源。并发：多道程序在CPU上交替运行系统吞吐量：在一段给定的时间内，计算机所能完成的总工作量。,.,1.3.2操作系统的发展,.,1.3.3推动操作系统发展的动力,硬件技术更新应用需求扩大,.,1.4操作系统的类型,5大基本类型批处理系统分时系统实时系统网络系统分布式系统,.,1.4.1批处理系统,1作业是用户定义的、由计算机完成的工作单位。它通常包括一组计算机程序、文件和对操作系统的控制语句。作业步由作业控制语句明确标识的计算机程序的执行过程,.,2工作流程,多道批处理系统中的作业流程,.,批处理系统,3.特点多道：系统在内存中存放多个作业，并且在外存上还保存大量的后备作业。成批：系统按批次调度作业，而在系统运行过程中不允许用户和机器之间发生交互作用。批处理系统的主要优点：系统资源利用率高系统吞吐量大明显缺点：用户作业的等待时间长没有交互能力,.,1.4.2分时系统,1分时概念和分时系统的实现方法分时：广义上，是指对时间的共享。在分时系统中，分时主要是指若干并发程序对CPU时间的共享并行：是指在同一时刻有两个或两个以上的活动发生。时间片,.,分时系统,2分时系统的特征和优点基本特征同时性交互性独立性及时性主要优点人机交互友好应用方便资源共享,.,1.4.3实时系统,1实时系统的引入实时系统具有实时特性，能够支持实时控制系统工作的操作系统。重要特征：对时间有严格限制和要求三种典型应用形式过程控制系统信息查询系统事务处理系统,.,2实时系统与分时系统的差别交互性实时性可靠性,.,实时系统,3实现方式硬式实时系统对时间严格约束软式实时系统对时间限制稍弱一些,.,1.4.4网络操作系统,1计算机网络的特征分布性自治性互连性可见性,.,2网络操作系统服务器客户机网络操作系统实现网络通信、资源共享和保护，以及提供网络服务和网络接口等本地操作系统完成本地资源的管理和服务功能客户-服务器模式Sun公司的NFSNovell公司的Netware5.0Microsoft公司的WindowsNTServer4.0IBM公司的LANServer4.0SCO公司的UNIXWare7.1自由软件Linux,.,3网络操作系统的特性接口一致性资源透明性操作可靠性处理自主性执行并行性,.,1.4.5分布式操作系统,分布式系统特点透明性灵活性可靠性高性能可扩充性,.,1.4.6其他操作系统,1.个人机系统WindowsXP、WindowsVista、UNIX、Linux2.多处理器系统对称多处理（SMP）系统增加吞吐量提高性能/价格比提高可靠性3嵌入式系统,.,1.5操作系统的特征,（1）并发两个或多个活动在同一给定的时间间隔中进行。（2）共享计算机系统中的资源被多个进程所共用。（3）不确定性系统中各种事件发生顺序的不可预测性。,.,1.6操作系统结构设计,1.6.1整体系统任意调用，耦合紧密，实现的效率高结构关系不清晰，系统的可靠性降低,模块调用示意图,.,1.6.2层次式系统,THE操作系统的层次结构具有整体系统的长处新优点结构关系清晰，提高系统的可靠性、可移植性和可维护性。,.,1.6.3虚拟机结构,带CMS的VM/370结构,通过共享物理机器资源来实现主要优点同时运行多个操作系统系统安全,有效地保护系统资源提供良好的工作环境组建虚拟网络,.,1.6.4客户-服务器系统,客户-服务器系统模型微内核,.,客户-服务器系统,适于在分布式系统中应用,分布式系统中的客户-服务器模型,.,第2章进程和线程,.,本章内容提要,进程概念进程的状态和组成进程管理线程进程的同步和通信经典进程同步问题管程进程通信,.,2.1进程概念,2.1.1多道程序设计1顺序程序活动的特点顺序性封闭性可再现性2多道程序设计程序并发执行提高系统资源利用率增加作业吞吐量,.,多道程序设计,3程序并发执行的特征失去封闭性程序与计算不再一一对应并发程序在执行期间相互制约,.,2.1.2进程概念,1进程概念的引入多道程序并发执行所引发的一系列新情况,.,2进程概念,进程最根本的属性是动态性和并发性进程定义：程序在并发环境中的执行过程进程和程序的区别（1）动态性（2）并发性（3）非对应性（4）异步性,.,进程概念,3进程的基本特征（1）动态性（2）并发性（3）调度性,.,2.2进程的状态和组成,2.2.1进程的状态及其转换1进程的基本状态运行状态（Running）就绪状态（Ready）阻塞状态（Blocked）,.,进程的5种基本状态及其转换,.,2进程状态的转换,（1）新建就绪（2）就绪运行（3）运行阻塞（4）阻塞就绪（5）运行就绪（6）运行终止,.,2.2.2进程描述,1进程映像进程映像通常就由程序、数据集合、栈和PCB等4部分组成,进程映像模型,.,进程描述,2进程控制块的组成进程控制块（PCB）也称进程描述块（ProcessDescriptor），它是进程组成中最关键的部分，其中含有进程的描述信息和控制信息，是进程动态特性的集中反映，是系统对进程施行识别和控制的依据。,.,进程描述,进程控制块应包含的主要内容：进程名特征信息进程状态信息调度优先权通信信息现场保护区资源需求进程实体信息族系关系其他信息,.,进程描述,3进程控制块的作用每个进程有惟一的进程控制块操作系统根据PCB对进程实施控制和管理进程的动态、并发等特征是利用PCB表现出来的PCB是进程存在的唯一标识,.,2.2.3进程队列,1线性方式,PCB线性队列示意图,.,进程队列,2链接方式,PCB链接队列示意图,.,PCB索引结构示意图,3索引方式,进程队列,.,2.3进程管理,2.3.1进程图进程图（ProcessGraph）是描述进程族系关系的有向树,进程创建的层次关系,.,2.3.2进程创建,引发创建进程的事件：调度新作业用户登录操作系统提供特定服务派生新进程,.,进程创建,创建新进程时要执行创建进程的系统调用（如UNIX/Linux系统中的fork）其主要操作过程有如下四步：（1）申请一个空闲的PCB（2）为新进程分配资源（3）将新进程的PCB初始化（4）将新进程加到就绪队列中,.,#include#include#includeintmain(intargc,char*argv)intpid;pid=fork();/*创建一个子进程*/if(pid0)/*出现错误。进程ID号不可能小于0*/fprintf(stderr,ForkFailed);/*输出出错消息ForkFailed*/exit(-1);/*程序终止，返回码-1*/elseif(pid=0)/*下面是子进程执行*/execlp(/bin/ls,ls,NULL);/*执行目录/bin下面的ls命令*/else/*下面是父进程执行*/wait(NULL);/*父进程等待子进程完成*/printf(ChildComplete);/*输出子进程完成的信息*/exit(0);/*终止*/,.,2.3.3进程终止,导致进程终止的三种情况：正常终止异常终止外部干扰,.,进程终止,终止进程的主要操作过程如下：找到指定进程的PCB终止该进程的运行回收该进程所占用的全部资源终止其所有子孙进程，回收它们所占用的全部资源。将被终止进程的PCB从原来队列中摘走,.,2.3.4进程阻塞,进程阻塞的过程如下：立即停止当前进程的执行现行进程的CPU现场保存现行状态由“运行”改为“阻塞”转到进程调度程序,.,2.3.5进程唤醒,唤醒原语执行过程如下：把阻塞进程从相应的阻塞队列中摘下将现行状态改为就绪状态，然后把该进程插入就绪队列中如果被唤醒的进程比当前运行进程的优先级更高，则设置重新调度标志,.,2.4线程,2.4.1线程概念现代操作系统中，进程只作为资源拥有者，而调度和运行的属性赋予新的实体线程。线程（Thread）是进程中实施调度和分派的基本单位,.,线程概念,1线程的组成每个线程有一个thread结构，即线程控制块，用于保存自己私有的信息，主要由以下4个基本部分组成：一个唯一的线程标识符一组寄存器两个栈指针一个私有存储区,thread结构示意图,.,线程的组成,线程必须在某个进程内执行一个进程可以包含一个线程或多个线程,单线程和多线程的进程模型,.,2线程的状态运行状态就绪状态阻塞状态终止状态,.,3线程的管理线程创建线程终止线程等待线程让权,.,4线程和进程的关系一个进程可以有多个线程，但至少要有一个线程；而一个线程只能在一个进程的地址空间内活动。资源分配给进程，同一进程的所有线程共享该进程的所有资源。处理机分配给线程，即真正在处理机上运行的是线程。线程在执行过程中需要协作同步。不同进程的线程间要利用消息通信的办法实现同步。,.,5引入线程的好处易于调度提高并发性开销少利于充分发挥多处理器的功能,.,2.4.2线程的实现,在用户空间实现优点：切换速度快；调度算法可专用；可运行在任何操作系统上缺点：阻塞问题；多处理器利用问题在核心空间实现优点：克服了用户级线程方式的两个主要缺陷；本身也可以是多线程的缺点：控制转移开销大组合方式,.,2.5进程的同步和通信,进程间的相互关系主要分为如下三种形式：互斥竞争同一资源而发生相互制约同步协同完成一项任务通信交换信息,.,2.5.1进程的同步与互斥,1同步同步进程通过共享资源来协调活动，在执行时间的次序上有一定约束。虽然彼此不直接知道对方的名字，但知道对方的存在和作用。在协调动作的情况下，多个进程可以共同完成一项任务。,.,2互斥在逻辑上这两个进程本来完全独立，毫无关系，只是由于竞争同一个物理资源而相互制约。它们的运行不具有时间次序的特征,.,互斥示例假定进程Pa负责为用户作业分配打印机，进程Pb负责释放打印机。系统中设立一个打印机分配表，由各个进程共用。打印机分配表（初始情况）打印机分配表（出错情况）,.,竞争条件（RaceCondition）两个或多个进程同时访问和操纵相同的数据时，最后的执行结果取决于进程运行的精确时序。,.,2.5.2临界资源和临界区,1临界资源和临界区临界资源（CriticalResource）一次仅允许一个进程使用的共享资源临界区（CriticalSection），简称CS区在每个进程中访问临界资源的那段程序,.,2进程的一般结构,典型进程的一般结构,.,3临界区进入准则单独进入独占该区限时退出主动让权,进程A和进程B互斥使用临界区的过程,.,2.5.3互斥实现方式,1利用硬件方法解决进程互斥问题禁止中断进入临界区之后立即关闭所有的中断专用机器指令TSL（TestandSetLock，即测试并上锁）的指令：TSLRX，LOCK汇编代码示例enter_region:TSLREGISTER,LOCKCMPREGISTER,#0JNEenter_regionRETleave_region:MOVELOCK,#0RET,.,2原语是机器指令的延伸，往往是为完成某些特定的功能而编制的一段系统程序。原语操作也称做“原子操作”（atomicaction），即一个操作中的所有动作要么全做，要么全不做。执行原语操作时，要屏蔽中断，以保证其操作的不可分割性。,.,3利用软件方法解决进程互斥问题可为每类临界区设置一把锁，该锁有打开和关闭两种状态。关锁原语lock(W):while(W=1);W=1;开锁原语unlock(W):w=0;,.,进程Alock(W);打印信息S;CS区unlock(W);,进程Block(W);打印信息S;CS区unlock(W);,用锁实现进程互斥设系统中有一台打印机，有两个进程A和B都要使用它，以变量W表示锁，预先把它的值置为0。,.,2.5.4信号量,1整型信号量P操作最初源于荷兰语proberen，表示测试；V操作源于荷兰语verhogen，表示增加。在有些书上将P操作称做wait或者DOWN操作，将V操作称做signal或者UP操作。对信号量的操作有以下限制：信号量可以初始化为一个非负值。只能由P和V两个操作来访问信号量。,.,整型信号量,P和V操作都是原语伪代码形式P(S)V(S)while(S0);S+;S-;实现互斥的伪代码形式doP(mutex);临界区V(mutex);其他代码区while(1);,.,信号量,2结构型信号量结构型信号量又称计数信号量，简称信号量一般是由两个成员组成的数据结构。其中一个成员是整型变量，表示该信号量的值；另一个是指向PCB的指针。typedefstructintvalue;structPCB*list;semaphore;,.,结构型信号量,信号量的值与相应资源的使用情况有关信号量的一般结构及PCB队列,.,对信号量的操作有如下严格限制：信号量可以赋初值，且初值为非负数。在使用过程中，信号量的值可以修改，但只能由P和V操作来访问，不允许通过其他方式来查看或操纵信号量。,结构型信号量,.,P、V操作的定义voidP(semaphoreS)voidV(semaphoreS)S.value-;S.value+；if(S.value0)if(S.value=0)把这个进程加到S.list队列；从S.list队列中移走进程Q；block()；wakeup(Q)；在具体实现时应注意，P,V操作都应作为一个整体实施，不允许分割或相互穿插执行,结构型信号量,.,结构型信号量3二值信号量一种特例，它的值只能在0和1之间选择,typedefstructenumfalse,truevalue;/*枚举量*/structPCB*list;B_semaphore;voidP_B(B_semaphoreS)if(S.value=true)S.value=false;else把该进程放入S.list队列;block();,voidV_B(B_semaphoreS)if(S.list=NULL)S.value=true;else从S.list队列中移走进程Q;wakeup(Q);,.,2.5.5信号量的一般应用,1用信号量实现进程互斥打印机分配表的互斥使用Pa:Pb:P(mutex)P(mutex)分配打印机释放打印机（读写分配表）（读写分配表）V(mutex)V(mutex),.,用信号量实现进程互斥,利用信号量实现互斥的一般模型是：进程P1进程P2进程PnP(mutex);P(mutex);P(mutex);临界区临界区临界区V(mutex);V(mutex);V(mutex);,.,用信号量实现进程互斥,注意点：在每个程序中用于实现互斥的P(mutex)和V(mutex)必须成对出现，即先做P，进入临界区；后做V，退出临界区。互斥信号量mutex的初值一般为1。,.,2用信号量实现进程简单同步对缓冲区的同步使用问题,简单供者和用者对缓冲区的使用关系,.,用信号量实现进程简单同步,供者和用者间要交换两个消息：缓冲区空缓冲区满设置两个信号量：S1表示缓冲区是否空（0表示不空，1表示空）。S2表示缓冲区是否满（0表示不满，1表示满）。规定S1和S2的初值分别为1和0,.,用信号量实现进程简单同步,供者进程用者进程L1:P(S1)L2:启动读卡机P(S2);从缓冲区取出信息收到输入结束中断V(S1);V(S2);加工并且存盘gotoL1;gotoL2;,.,用信号量实现进程简单同步,用P和V操作实现同步时应注意如下三点：分析进程间的制约关系，确定信号量种类。信号量的初值与相应资源的数量有关，也与P,V操作在程序代码中出现的位置有关。同一信号量的P,V操作要“成对”出现，但是，它们分别出现在不同的进程代码中。,.,2.6经典进程同步问题,1生产者-消费者问题生产者:能产生并释放资源的进程消费者:单纯使用（消耗）资源的进程问题表述一组生产者进程和一组消费者进程（设每组有多个进程）通过缓冲区发生联系。生产者进程将生产的产品（数据、消息等统称为产品）送入缓冲区，消费者进程从中取出产品。假定缓冲区共有N个，不妨把它们设想成一个环形缓冲池。,.,生产者-消费者问题,生产者-消费者问题环形缓冲池,它们应满足如下同步条件：任一时刻所有生产者存放产品的单元数不能超过缓冲区的总容量（N）。所有消费者取出产品的总量不能超过所有生产者当前生产产品的总量。,.,生产者-消费者问题,设缓冲区的编号为0N-1，in和out分别是生产者进程和消费者进程使用的指针，指向下面可用的缓冲区，初值都是0。设置三个信号量：full：表示放有产品的缓冲区数，其初值为0。empty：表示可供使用的缓冲区数，其初值为N。mutex：互斥信号量，初值为1，表示各进程互斥进入临界区，保证任何时候只有一个进程使用缓冲区。,.,生产者-消费者问题,生产者进程Producer：消费者进程Consumer：while(TRUE)while(TRUE)P(empty);P(full);P(mutex);P(mutex);产品送往buffer(in);从buffer(out)中取出产品；in=(in+1)modN;out=(out+1)modN;/*以N为模*/*以N为模*/V(mutex);V(mutex);V(full);V(empty);,.,2读者-写者问题读者-写者问题也是一个著名的进程互斥访问有限资源的同步问题。例如，一个航班预订系统有一个大型数据库，很多竞争进程要对它进行读、写。允许多个进程同时读该数据库，但是在任何时候如果有一个进程写（即修改）数据库，那么就不允许其他进程访问它既不允许写，也不允许读。,.,读者-写者问题,信号量设置：读互斥信号量rmutex初值为1写互斥信号量wmutex初值为1rmutex：读者互斥地访问readcountwmutex：保证一个写者与其他读者/写者互斥地访问共享资源,读计数器readcount，整型变量，初值为0。,.,读者-写者问题,读者Readerswhile(TRUE)P(rmutex);readcount=readcount+1;if(readcount=1)P(wmutex);V(rmutex);执行读操作P(rmutex);readcount=readcount-1;if(readcount=0)V(wmutex);V(rmutex);使用读取的数据,写者Writerswhile(TRUE)P(wmutex);执行写操作V(wmutex);,这个算法隐含读者的优先级高于写者,.,3哲学家进餐问题五位哲学家围坐在一张圆桌旁进餐，每人面前有一只碗，各碗之间分别有一根筷子。每位哲学家在用两根筷子夹面条吃饭前独自进行思考，感到饥饿时便试图占用其左、右最靠近他的筷子，但他可能一根也拿不到。他不能强行从邻座手中拿过筷子，而且必须用两根筷子进餐；餐毕，要把筷子放回原处并继续思考问题。,哲学家进餐问题,.,哲学家进餐问题,=#defineN5#defineLEFT(i-1)%N#defineRIGHT(i+1)%N#defineTHINKING0#defineHUNGRY1#defineEATING2typedefstruct/*定义结构型信号量*/intvalue;structPCB*list;semaphore;intstateN;semaphoremutex=1;/*互斥进入临界区*/semaphoresN;/*每位哲学家一个信号量*/,.,哲学家进餐问题,voidphilosopher(inti)while(TRUE)think();/*哲学家在思考问题*/take_chopstick(i);/*拿到两根筷子或者等待*/eat();/*进餐*/put_chopstick(i);/*把筷子放回原处*/voidtake_chopstick(inti)P(mutex);statei=HUNGRY;test(i);/*试图拿两根筷子*/V(mutex);P(si);,.,哲学家进餐问题,voidput_chopstick(inti)P(mutex);statei=THINKING;test(LEFT);/*查看左邻，现在能否进餐*/test(RIGHT);/*查看右邻，现在能否进餐*/V(mutex);voidtest(inti)if(statei=HUNGRY=,.,打瞌睡的理发师,4打瞌睡的理发师问题理发店有一名理发师，一把理发椅和几把座椅，等待理发者可坐在上面。如果没有顾客到来，理发师就坐在理发椅上打盹。当顾客到来时，就唤醒理发师。如果顾客到来时理发师正在理发，该顾客就坐在椅子上排队；如果满座了，他就离开这个理发店，到别处去理发。,.,打瞌睡的理发师问题,理发师和每位顾客都分别是一个进程=#defineCHAIRS5typedefstructintvalue;structPCB*list;semaphore;semaphorecustomers=0;semaphorebarbers=0;semaphoremutex=1;intwaiting=0;,.,voidbarber(void)while(TRUE)P(customers);/*如果没有顾客，则理发师打瞌睡*/P(mutex);/*互斥进入临界区*/waiting-;V(barbers);/*一个理发师准备理发*/V(mutex);/*退出临界区*/cut_hair();/*理发（在临界区之外）*/,打瞌睡的理发师问题,.,打瞌睡的理发师问题,voidcustomer(void)P(mutex);/*互斥进入临界区*/if(waitingCHAIRS)waiting+;V(customers);/*若有必要，唤醒理发师*/V(mutex);/*退出临界区*/P(barbers);/*如果理发师正忙着，则顾客打瞌睡*/get_haircut();elseV(mutex);/*店里人满了，不等了*/,.,2.7管程,管程：一个管程定义一个数据结构和能为并发进程在其上执行的一组操作，这组操作能使进程同步和改变管程中的数据。由管程名称、局部于管程的共享数据的说明、对数据进行操作的一组过程和对该共享数据赋初值的语句四部分组成。,管程的结构,.,管程,管程具有以下三个特性：管程内部的局部数据变量只能被管程内定义的过程所访问，不能被管程外面声明的过程直接访问。进程要想进入管程，必须调用管程内的某个过程。一次只能有一个进程在管程内执行，而其余调用该管程的进程都被挂起，等待该管程成为可用的。即管程能有效地实现互斥。,.,管程,实现互斥是由编译程序完成为解决同步问题，引入两个条件变量x和y：conditionx,y;操作原语wait(x)：挂起等待条件x的调用进程，释放相应的管程，以便供其他进程使用。操作原语signal(x)：恢复执行先前因在条件x上执行wait而挂起的那个进程。管程的职责与信号量的职责不同。,带条件变量的管程结构,.,2.8进程通信,进程通信进程间的信息交换低级进程通信高级进程通信共享存储器方式：在内存中分配一片空间作为共享存储区消息传递方式：以消息（Message）为单位在进程间进行数据交换直接通信方式间接通信方式管道文件方式：写者向管道文件中写入数据；读者从该文件中读出数据,.,2.8.1消息传递系统允许进程彼此进行通信，而不必借助于共享数据提供两个原语（系统调用）send和receive：send(destination,message)receive(source,message),.,消息传递系统,消息传送系统设计涉及同步、寻址、格式和排队规则等多项问题同步寻址直接通信方式对称寻址；非对称寻址间接通信方式信箱公用信箱共享信箱私有信箱,.,消息传送系统设计,消息格式取决于消息机制的目标和在什么系统上运行排队规则先进先出优先权法接收方挑选,一般消息格式,.,消息传递系统,用消息传递方式解决生产者-消费者问题#defineN100/*缓冲区个数*/voidproducer(void)intitem;messagem;/*消息缓冲区*/while(TRUE)item=produce_item()；/*生成一些数据放入缓冲区*/receive(consumer,/*使用数据项进行操作*/,.,2.8.2客户-服务器系统中的通信,1socket好像一条通信线两端的接插口一对进程通过网络进行通信要用一对socket，每个进程一个。三个要素：网络地址表明一个socket用于哪种网络连接类型表明网络通信所遵循的模式，主要分为“有连接”和“无连接”模式。网络规程表明具体网络的规程。一般来说，网络地址和连接类型结合在一起就基本上确定了适用的规程。,socket通信流程,.,2远程过程调用远程过程调用（RemoteProcedureCall,RPC）是远程服务的一种最常见的形式。远程过程调用的思想：允许程序调用另外机器上的过程远程过程调用的具体步骤,.,第3章死锁,.,本章内容提要资源死锁概念死锁的预防死锁的避免死锁的检测和恢复处理死锁的综合方式,.,3.1资源,3.1.1资源使用模式申请使用释放,.,3.1.2可剥夺资源与不可剥夺资源,按占有方式划分：可剥夺资源当该资源被某进程拥有后，其它进程仍可以把它剥夺过去为己所用，并且不会产生任何不良影响。例如，内存就是可剥夺资源。不可剥夺资源该资源一旦被某进程占有，则其它进程不能强行抢占，必须由拥有者自动释放，否则会引起相关计算的失效。如光盘刻录机。死锁和不可剥夺资源有关按其它方式划分,.,3.2死锁概念,3.2.1什么是死锁1死锁示例,汽车过窄桥时的冲突,在计算机系统中，涉及软件、硬件资源的进程都可能发生死锁,.,2死锁定义死锁是指在一个进程集合中的每个进程都在等待仅由该集合中的另一个进程才能引发的事件而无限期地僵持下去的局面。计算机系统产生死锁的根本原因就是资源有限且操作不当死锁的危害系统瘫痪资源浪费,.,什么是死锁,有两个进程A和B，竞争两个资源R和S，这两个资源都是不可剥夺资源。进程A进程B申请并占用R申请并占用S申请并占用S申请并占用R释放R释放S释放S释放R,.,什么是死锁,进程推进顺序对引发死锁的影响,.,3.2.2死锁的条件,产生死锁的4个必要条件1互斥条件2占有且等待条件3不可抢占条件4循环等待条件只要有一个必要条件不满足，则死锁就可以排除。,.,3.2.3资源分配图,1资源分配图的构成由结对组成：G=(V,E)V是顶点的集合，E是边的集合。顶点集合可分为两部分：P=p1,p2,pn由系统中所有活动进程组成R=r1,r2,rm由系统中全部资源类型组成有向边pirj称为申请边有向边rjpi称为赋给边在资源分配图中，通常用圆圈表示每个进程，用方框表示每种资源类型。,.,2资源分配图示例（1）集合P,R和E如下：P=p1,p2,p3R=r1,r2,r3,r4E=p1r1,p2r3,r1p2,r2p2,r2p1,r3p3（2）资源数量分别为1，2，1，3（3）进程状态该图不含环路，没有死锁,资源分配图示例,.,3环路与死锁如果每类资源的实体都只有一个，那么图中出现环路就说明死锁了。,.,环路与死锁,有死锁的资源分配图,有环路但无死锁的资源分配图,如果每类资源的实体不止一个，那么资源分配图中出现环路并不表明一定出现死锁。,资源分配图中存在环路是死锁产生的必要条件，但不是充分条件。,.,3.2.4处理死锁的方法,利用某些协议预防或避免死锁，保证系统不会进入死锁状态。允许系统进入死锁状态，然后设法发现并克服它。完全忽略这个问题，好像系统中从来也不会出现死锁。,.,3.3死锁的预防,3.3.1破坏互斥条件3.3.2破坏占有且等待条件预分资源策略静态分配“空手”申请资源策略不占有资源时才可以申请资源存在以下4个主要缺点不可预测利用率低降低并发性“饥饿”现象,.,3.3.3破坏非抢占条件,隐式抢占方式抢占等待者资源,.,3.3.4破坏循环等待条件,资源有序分配策略资源编号设R=r1,r2,rm，表示一组资源定义一对一的函数F：RN，N是一组自然数。如：F（磁带机）=1，F（磁盘机）=5，F（打印机）=12依序分配约定：所有进程对资源的申请严格按照序号递增的次序进行。,.,破坏循环等待条件,先弃大，再取小一个进程申请资源rj，它应释放所有满足F(ri)F(rj)关系的资源ri,这两种办法都是可行的，都可排除环路等待条件,优点：资源利用率和系统吞吐量都有很大提高缺点：资源请求受限，合理编号困难，增加系统开销。暂不使用的资源也需提前申请，增加资源占用时间。,.,3.4死锁的避免,排除死锁的动态策略。关键是确定资源分配的安全性3.4.1安全状态在当前分配状态下，进程的安全序列P1,P2,Pn是：若对于每一个进程Pi（1in），它需要的附加资源可被系统中当前可用资源与所有进程Pj（ji）当前占有资源之和所满足，则P1,P2,Pn为一个安全序列。这时系统处于安全状态。存在安全序列时一定不会有死锁发生死锁是不安全状态中的特例,.,安全状态,安全状态示意设系统中共有10台磁带机，有三个进程p1,p2和p3，分别拥有3台、2台和2台磁带机，而它们各自的最大需求分别是9台、4台和7台磁带机。此时，系统已分配了7台磁带机，还有3台空闲。下表给出三个进程在不同时刻占有资源及向前推进的情况。,.,不安全状态示意,若不按照安全序列分配资源，则系统可能会由安全状态转换为不安全状态,.,死锁的避免,死锁状态是不安全状态。如果系统处于不安全状态，并不意味着它就在死锁状态，而是表示存在导致死锁的危机。如果一个进程申请的资源当前是可用的，但为了避免死锁，该进程也可能必须等待。此时资源利用率会下降。,.,3.4.2资源分配图算法,资源类单体资源类多体资源类单体资源类的资源分配图除申请边和赋给边之外，还要有一种称为“要求边”的新边。要求边pirj表示进程pi能够申请资源rj，有时用虚线表示。,资源分配图示例,处于不安全状态的资源分配图,.,3.4.3银行家算法,“银行家算法”（BankersAlgorithm）针对多体资源类设计思想：当用户申请一组资源时，系统必须做出判断：如果把这些资源分出去，系统是否还处于安全状态。若是，就可以分出这些资源；否则，该申请暂不予满足。,.,银行家算法数据结构令n表示系统中进程的数目，m表示资源分类数。Available是一个长度为m的向量，它表示每类资源可用的数量。Availablej=k，表示rj类资源可用的数量是k。Max是一个nm矩阵，它表示每个进程对资源的最大需求。Maxi,j=k，表示进程pi至多可申请k个rj类资源单位。Allocation是一个nm矩阵，它表示当前分给每个进程的资源数目。Allocationi,j=k，表示进程pi当前分到k个rj类资源。Need是一个nm矩阵，它表示每个进程还缺少多少资源。Needi,j=k，表示进程pi尚需k个rj类资源才能完成其任务。记号：令X和Y表示长度为n的向量可以把矩阵Allocation和Need中的每一行当做一个向量，并分别写成Allocationi和Needi。Allocationi表示当前分给进程pi的资源。,.,1资源分配算法令Requesti表示进程pi的申请向量。Requestij=k，表示进程pi需要申请k个rj类资源。当进程pi申请资源时，就执行下列动作：若RequestiNeedi，表示出错，如果RequestiAvailable，则pi等待。假设系统把申请的资源分给进程pi，则应对有关数据结构进行修改：Available：=AvailableRequestiAllocationi：=Allocationi+RequestiNeedi：=NeediRequesti系统执行安全性算法，查看此时系统状态是否安全。如果是安全的，就实际分配资源，满足进程pi的此次申请；否则，若新状态是不安全的，则pi等待，对所申请资源暂不予分配，并且把资源分配状态恢复成之前的情况。,.,2安全性算法令Work和Finish分别表示长度为m和n的向量，最初，置Work：=Available，Finishi：=false，i=1,2,n。搜寻满足下列条件的i值：Finishi=false，且NeediWork。若没有找到，则转向。修改数据值：Work：=Work+Allocationi（pi释放所占的全部资源）Finishi=true转向。若Finishi=true对所有i都成立（任一进程都可能是pi），则系统处于安全状态；否则，系统处于不安全状态。,.,3算法应用示例假定系统中有4个进程A,B,C,D和三类资源R1,R2和R3，各自的数量分别为9,3和6个单位。,T0时刻资源分配表（安全）,资源情况,.,（1）T0时刻是安全的存在一个安全序列B,A,C,D,进程,T0时刻的安全序列,.,（2）进程A请求资源进程A发出请求Request（1,0,1）,系统进入不安全的状态不能为进程A分配所申请的资源,为进程A分配资源后的有关数据,.,银行家算法,优点：限制条件少资源利用程度提高缺点：难以保证进程数固定不变未考虑实时进程快速响应增加了系统开销,.,3.5死锁的检测和恢复,死锁检测与恢复是指系统设有专门的机构，当死锁发生时，该机构能够检测到死锁发生的位置和原因，且能通过外力破坏死锁发生的必要条件，从而使并发进程从死锁状态中解脱出来。,.,3.5.1对单体资源类的死锁检测,等待图资源分配图的变形从资源分配图中去掉表示资源类的节点，且把相应边折叠在一起得到的,资源分配图和对应的等待图,.,3.5.2对多体资源类的死锁检测,采用若干随时间变化的数据结构，与银行家算法相似Available是一个长度为m的向量Allocation是一个nm的矩阵Request是一个nm的矩阵，Requesti,j=k，表示进程pi正申请k个rj类资源仍把矩阵Allocation和Request的行作为向量对待，并分别表示为Allocationi和Requesti,.,对多体资源类的死锁检测,检测算法简单地调查尚待完成的各个进程所有可能的分配序列令Work和Finish分别表示长度为m和n的向量，初始化Work：=Available；对于i=1,2,n如果Allocationi0，则Finishi：=false；否则Finishi：=true。寻找一个下标i，它应满足条件：Finishi=false且RequestiWork若找不到这样的i，则转到。修改数据值：Work：=Work+AllocationiFinishi=true转向。若存在某些i（1in），Finishi=false，则系统处于死锁状态。此外，若Finishi=false，则进程pi处于死锁环中。,.,对多体资源类的死锁检测,设系统中有5个进程p1,p2,p3,p4和p5，有3类资源R1,R2和R3，每类资源的个数分别为7,2,6。,死锁检测示例资源分配情况,可以找到序列p1,p3,p4,p2,p5，对于所有的i都有Finishi=true，系统在T0时刻没有死锁。,资源情况,进程,.,假定，进程p3现在申请一个单位的R3资源,由于对所有i=1,2,5，Allocationi0，所以Finishi=false。,p3申请一个单位的R3资源后的资源分配数据,资源情况,进程,.,3.5.3从死锁中恢复,1通过抢占资源实现恢复临时性地把资源从当前占有它的进程那里拿过来，分给另外某些进程，直至死锁环路被打破。2通过回退执行实现恢复由系统管理员做出安排，定期对系统中各个进程进行检查，并将检查点的有关信息（如进程状态、资源状态等）写入文件。当检测到死锁时，就让某个占有必要资源的进程回退到它取得另外某个资源之前的一个检查点。回退过程所释放的资源分配给一个死锁进程，然后重新启动运行。系统中应保存一系列检查点的文件。要确定这个进程后退多远。还有一种“全体”回退方式,.,3通过杀掉进程实现恢复终止所有的死锁进程。一次终止一个进程，直至消除死锁环路。,.,3.5.4“饥饿”状态,在某些策略下，系统会出现这样一种情况：在可以预计的时间内，某个或某些进程永远得不到完成工作的机会，因为它们所需的资源总是被别的进程占有或抢占。这种状况称做“饥饿”或者“饿死”（Starvation）。饥饿不同于死锁,.,3.6处理死锁的综合方式,把以前介绍的基本方法组合起来，使得系统中各级资源都以最优的方式加以利用。对待死锁问题除以上三种最基本的方法外，还有第四种方法，即采取“鸵鸟政策”完全忽略死锁问题。,.,操作系统处理死锁的三种方法比较,.,第4章调度,.,本章内容提要,调度类型作业调度进程调度调度准则调度算法线程调度多处理器调度实时调度UNIX/Linux进程调度中断处理信号机制,.,4.1调度类型,按调度层次进行分类：高级调度、中级调度和低级调度高级调度又称作业调度或长期调度中级调度又称中期调度低级调度又称进程调度或短期调度,作业三级调度示意图,.,4.2作业调度,4.2.1作业状态提交状态后备状态执行状态完成状态,.,4.2.2作业控制块和作业调度的功能,1作业控制块JCB系统为每个作业设置了一个作业控制块（JCB）它记录该作业的有关信息JCB是作业在系统中存在的标志,.,2.作业调度的功能,记录系统中各个作业的情况按照某种调度算法从后备作业队列中挑选作业为选中的作业分配内存和外设等资源为选中的作业建立相应的进程，并把该进程放入就绪队列中作业结束后进行善后处理工作设计目标是最大限度地发挥各种资源的利用率和保持系统内各种活动的充分并行,.,3常用作业调度算法,先来先服务法（First-ComeFirst-Served）短作业优先法（ShortestJobFirst）最短剩余时间优先法（ShortestRemainingTimeNext）,.,4.3进程调度,4.3.1进程调度的功能（1）保存现场（2）挑选进程（3）恢复现场,.,4.3.2进程调度的时机,创建进程进程终止等待事件中断发生运行到时,.,4.