计算机操作系统原理 第二章 进程描述与控制

计算机操作系统东华大学计算机科学与技术学院主讲：李继云[e-mail]2本章重点并发程序的特点进程的概念进程和程序的区别进程状态进程控制原语线程的概念进程的同步与互斥32.1进程描述2.2进程控制2.3线程2.4实例：Solaris第2章进程描述与控制主要内容2.5进程同步2.6经典进程的同步问题2.7管程机制2.8进程通信42.1进程描述2.1.1程序的顺序执行2.1.2程序的并发执行2.1.3进程的定义2.1.4进程的特征2.1.5进程的状态及转换2.1.6进程控制块52.1.1程序的顺序执行程序的顺序执行如图在计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行不受外界影响。一道程序执行完后另一道才能开始。6程序顺序执行的特点顺序性：一个程序开始执行必须要等到前一个程序已执行完成。封闭性：程序一旦开始执行，其计算结果不受外界因素影响。可再现性：程序的结果与它的执行速度无关（即与时间无关），只要给定相同的输入，一定会得到相同的结果。前趋图前趋图(PrecedenceGraph)是一个有向无循环图，记为DAG(DirectedAcyclicGraph)，用于描述进程之间执行的前后关系。结点：一个程序段或进程，乃至一条语句有向边：偏序或前趋关系把没有前趋的结点称为初始结点(InitialNode)没有后继的结点称为终止结点(FinalNode)每个结点还具有一个重量(Weight)，用于表示该结点所含有的程序量或结点的执行时间。P1P3P8P9P4P2P5P6P7S1S2S3(a)具有九个结点的前趋图(b)具有循环的前趋图前趋图中必须不存在循环前趋图92.1进程描述2.1.1程序的顺序执行2.1.2程序的并发执行2.1.3进程的定义2.1.4进程的特征2.1.5进程的状态及转换2.1.6进程控制块102.1.2程序的并发执行所谓程序的并发执行是指：若干个程序同时在系统中执行，这些程序的执行在时间上是重叠的，一个程序的执行尚未结束，另一个程序的执行已经开始。并发与并行概念的区别？Concurrency，parallel11并发执行实例－－并发程序的时间相关性誊抄用卡片输入机尽快地把一个文本复写（誊抄）到行式打印机上去。由BrinchHansen提出12循环顺序程序的誊抄方案输入：f输出：g{while(f不为空）{input;output;}}13循环顺序程序的誊抄方案设读卡机的标定速度是1000卡/分，打印机的标定速度是600行/分，那么此系统的最高传输速度为（）行/分？14两个并发程序方案设有一台标准输入设备（键盘），和一台标准输出设备（显示器或打印机），输入程序负责从标准设备中读取一个字符，送缓冲区中。输出程序从缓冲区中取数据，送标准设备输出。15两个并发程序方案缓冲区标准输入（键盘）f标准输出（打印机）输出程序输入程序g16两个并发程序方案{cobeginwhile(不为结束符）{input;send;}while(buffer不为空）{receive;output;}coend}17两个并发程序方案誊抄的速度可以提高到600行/分。存在的问题：读卡机和打印机速度不匹配，导致虽然提高了设备利用率，但是不能正确誊抄。a、若打印的速度高于输入的速度；b、若输入的速度高于打印的速度18三个并发程序方案假设有两个缓冲区，每个缓冲区只存放一个字符，get程序负责从输入序列f中读一个字符，然后，送到缓冲区s中，copy程序负责将s中的字符复制到t中，put负责从t中提取字符打印。19三个并发程序方案缓冲区T标准输入（键盘）f标准输出（打印机）getgcopy缓冲区Sput20三个并发程序方案如何实现？{while(誊抄未完成){cobeginget(s,f);copy(s,t);put(t,g);coend}}21三个并发程序方案{if(f不为空){get(s,f);while(誊抄未完成){t=s;cobeginput(t,g);get(s,f);coend}}}22方案比较方案1系统利用率最低方案2、3提高了设备利用率，但需要增设缓冲区，且方案2会因速度匹配出错。思考：试举出现实生活中的此类例子。23程序并发执行的特点失去了程序的封闭性如果一个程序的执行可以改变另一个程序的变量，那么后者的输出就可能有赖于各程序执行的相对速度，即失去了程序封闭性的特点。程序与计算不再一一对应程序－静态；计算－动态程序并发执行的相互制约直接制约－－相互之间有逻辑关系（I,C,P）间接制约－－由于资源共享引起的联系（I1,I2）242.1进程描述2.1.1程序的顺序执行2.1.2程序的并发执行2.1.3进程的定义2.1.4进程的特征2.1.5进程的状态及转换2.1.6进程控制块252.1.3进程的定义进程的概念是60年代初首先由麻省理工学院的MULTICS系统和IBM公司的CTSS/360系统引入的。进程有很多各式各样的定义，如：行为的一个规则叫做程序，程序在处理机上执行时所发生的活动称为进程（Dijkstra）一个具有一定独立功能的程序关于某个数据集合的一次运行活动。进程是一个程序与其数据一道通过处理机的执行所发生的活动26进程同程序的比较程序是指令的有序集合，其本身没有任何运行的含义，是一个静态的概念。而进程是程序在处理机上的一次执行过程，它是一个动态的概念。程序可以作为一种软件资料长期存在，而进程是有一定生命期的。程序是永久的，进程是暂时的。27进程同程序的比较进程更能真实地描述并发，而程序不能进程是由程序和数据两部分组成的进程具有创建其他进程的功能，而程序没有同一程序同时运行于若干个数据集合上，它将属于若干个不同的进程。也就是说同一程序可以对应多个进程28思考为什么要引入进程的概念？292.1进程描述2.1.1程序的顺序执行2.1.2程序的并发执行2.1.3进程的定义2.1.4进程的特征2.1.5进程的状态及转换2.1.6进程控制块302.1.4进程的特征动态性：进程是程序的执行并发性：多个进程可同存于内存中，能在一段时间内同时运行独立性：独立运行的基本单位，独立获得资源和调度的基本单位。异步性：各进程按各自独立的不可预知的速度向前推进结构特征：由用户程序、用户数据、系统栈和进程控制块四部分组成31进程的类型按其任务性质分系统进程用户进程按其活动特点分受CPU时间限制－－科学计算受I/O限制－－商业联机事务处理32进程产生通常有4种事件会导致新进程产生：①在一个交互式环境中，当一个新用户在终端键入登录命令后，若是合法用户，系统将为该用户建立一个进程。②在一个批处理环境中，为了响应一个任务的要求而产生进程。③当运行中获取用户程序提出的某种请求后，OS可以代用户程序产生进程以实现某种功能，使用户不必等待。④基于应用进程的需要，由已存在的进程产生另一个进程，以便使新程序以并发运行方式完成特定任务。33进程终止导致进程终止的事件大致有14种：正常结束、超时限制、内存不足、超界、保护错误、算术错误、超越时限、I/O失败、非法指令、特权指令、错误使用数据、操作员或OS干预、父进程终止、父进程需要。342.1进程描述2.1.1程序的顺序执行2.1.2程序的并发执行2.1.3进程的定义2.1.4进程的特征2.1.5进程的状态及转换2.1.6进程控制块352.1.5进程的状态及转换进程有三种基本状态，进程在生命消亡前处于且仅处于三种基本状态之一。不同系统设置的进程状态数目不同。36进程的三种基本状态就绪状态（Ready）：存在于处理机调度队列中的那些进程，它们已经准备就绪，一旦得到CPU，就立即可以运行。这些进程所处的状态为就绪状态。运行状态（Running）：正在运行的进程所处的状态为运行状态。拥有CPU。等待状态（Wait/Blocked）：若一进程正在等待某一事件发生（如等待输入输出工作完成），这时，即使给它CPU，它也无法运行，称该进程处于等待状态、阻塞、睡眠、封锁状态。37进程的状态变迁图38进程状态模型运行：进程当前处于运行状态。就绪；进程已准备好运行。阻塞；进程等待某些事件发生（如I/O操作）后才能运行。创建：进程刚产生，但还未被操作系统提交到可运行进程池中。消失（撤销）：进程被操作系统从可运行进程池中释放。事件发生准许创建就绪分派运行超时释放消失阻塞等待事件39进程状态模型进程状态转换（转下表）原状态转换后状态创建运行就绪阻塞终止OS根据作业控制请求；分时系统用户登录；进程产生子进程而创建进程××××创建××OS准备运行新的进程××40进程状态模型原状态转换后状态创建运行就绪阻塞终止运行××超时；OS服务请求；OS响应具有更高优先级的进程；进程释放控制OS服务请求；资源请求；事件请求进程完成，进程夭折就绪×被分派程序选择为下一个即将执行的进程××被父进程终止阻塞××事件发生×被父进程终止41进程挂起处于非运行状态的进程：内存----外存由于I/O操作比CPU计算慢得多，故常会出现内存中所有进程都等待I/O的现象。即使运行多个程序，处理器在大多数时间仍处于空闲状态。为此可采用交换方法，将内存中的一部分进程转移到磁盘中。在进程行为模式中需增加一个新的挂起状态，当内存所有进程阻塞时，操作系统可将一进程置为挂起状态并交换到磁盘，再调入另一进程执行。挂起状态与原有的阻塞和就绪状态结合为阻塞挂起状态和就绪挂起状态。42事件发生准许创建就绪分派运行超时准许消失阻塞等待事件挂起激活挂起事件发生就绪，挂起就绪运行分派超时释放消失阻塞等待事件阻塞挂起激活挂起激活事件发生创建挂起准许准许有挂起状态的进程转换图(a)带有一个挂起状态(b)带有两个挂起状态原因说明交换OS需要释放足够的内存空间以调入就绪进程执行其他OS原因OS可能会挂起一个后台进程或怀疑引起问题的进程交互用户要求用户可能为了调试或与资源连接而要求挂起进程间断一个进程可能是周期性地执行的，那么它在等待下一次执行时如被挂起父进程请求父进程有时希望挂起某个后代进程以检查或修正挂起进程，或协调多个后代进程的运行进程挂起的原因进程挂起44【思考题】1．在单处理机系统中，如果系统中有N个进程，运行的进程最多几个，最少几个；就绪进程最多几个最少几个；等待进程最多几个，最少几个？2.有没有这样的状态转换，为什么？等待—运行；就绪—等待452.1进程描述2.1.1程序的顺序执行2.1.2程序的并发执行2.1.3进程的定义2.1.4进程的特征2.1.5进程的状态及转换2.1.6进程控制块462.1.6进程控制块（PCB）为了描述一个进程和其它进程以及系统资源的关系，为了刻画一个进程在各个不同时期所处的状态，人们采用了一个与进程相联系的数据块，称为进程控制块（PCB）。系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志进程与PCB是一一对应的47PCB的内容进程标识处理器状态信息进程调度信息进程控制信息48PCB的内容进程标识：–本进程的标识符(processID)，唯一，通常是一个整数–创建本进程的进程（父进程）的标识符–用户标识符(userID)；进程组关系49PCB的内容处理器状态信息：–通用寄存器–指令计数器–程序状态字PSW状态码、状态信息–用户栈指针PCB的内容进程调度信息：–进程状态–进程优先级–调度所需其他信息等待时间/执行时间等与调度算法有关–等待的事件5051PCB的内容进程控制信息：–程序和数据地址–进程同步和通信机制信号量、消息队列指针–资源清单–链接指针下一个PCB的首址52PCB表：系统把所有PCB组织在一起，并把它们放在内存的固定区域，就构成了PCB表。PCB表的大小决定了系统中最多可同时存在的进程个数，称为系统的并发度。PCB表组织方式53链接结构相同状态的进程PCB组成一个链表，不同状态对应多个不同的链表就绪链表、阻塞链