计算机操作系统(进程与线程).ppt

《计算机操作系统(进程与线程).ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

主要内容第2章进程与线程2.1进程2.2线程2.3进程间通信2.4调度2.5经典的IPC问题1 2.1进程（补充1）程序指令或语句序列，体现了某种算法所有程序是顺序的①顺序程序计算机系统中只有一个程序在运行，该程序独占系统中的所有资源，其执行不受外界影响特征：顺序性、封闭性、可再现性2 2.1进程（补充2）多道程序执行系统中程序的执行：同时处理多个具有独立功能的程序，应具有以下特点：．独立性：多个程序逻辑独立，并可独立运行．随机性：多用户环境下程序的运行是随机的．资源共享：并发执行的程序：．并发：两个或多个事件在同一个时间间隔之内同时发生．并行：两个或多个事件在同一个时刻同时发生特点：随机性，失去了程序顺序执行所具有的封闭性和可再现性3 例：有栈S,top为栈顶指针，getaddr(top)从栈中取内存数据块地址，reladdr(bld)将内存数据块地址blk放入S中Proceduregetaddr(top)beginlocalrr<-(top)top<-top-1return(r)endProcedurereladdr(blk)begintop<-top+1(top)<-blkend１２abeftopr=?4 2.1.2进程的定义：定义：AProcssisjustanexecutingprogram(Include:PC,R,variablesetc.)或：可以与其他程序并发执行的程序的一次执行，是系统　　　　资源分配的基本单位特征：　．动态．并发．独立．异步．结构5 进程与程序的区别及联系：．进程是动态的，而程序是静态的．进程可以并发，而程序则没有．进程是资源竞争的基本单位联系：一个程序可以生成多个不同的进程进程的层次结构：（进程树）．系统中除根进程外，每个进程都有且只有一个父进程．每个子进程均由它的父进程创建．一个父进程可以有多个子进程6 2.1进程2.1.1进程模型含有4道程序的多道程序4个独立的顺序进程的概念模型在任意时刻仅有一个程序是活跃的7 2.1.2创建进程4种主要事件导致进程的创建系统初始化执行了正在运行的进程所调用的进程创建系统调用用户请求创建一个新进程一个批处理作业的初始化8 2.1.3进程的终止引起进程终止的条件：正常退出(自愿的)错误退出(自愿地)严重错误(非自愿地)被其他进程杀死(非自愿地)9 2.1.4进程的层次结构父进程创建一个子进程，子进程可以创建属于自己的更多进程Unix中所有子女和后裔共同组成一个进程组UNIX叫“进程组"Windows没有进程层次的概念所有的进程都是地位相同的10 2.1.5进程的状态(1)进程课程的状态running（运行态）blocked(阻塞态)ready（就绪态）上图显示出各状态之间的转换进程为等待输入而阻塞调度程序选择另一个进程调度程序选择这个进程出现有效输入11 2.1.5进程的状态(2)以进程构造的操作系统最底层处理中断,调度在该层之上是顺序进程12 2.1.6进程的实现（补充）．进程控制块ＰＣＢ（用来标识进程存在于系统中的唯一的实体，部分或全部常驻内存）．程序．数据集ＰＣＢ：系统用ＰＣＢ反映进程的动态特征，内容包括：．描述信息：进程名（标识号），用户名（标识号），家族链．控制信息：状态，优先级，内存始址，计时，通信信息．资源管理信息：内存大小，设备等．ＣＰＵ现场保护机构：ＰＣＢ中设有13 2.1.6进程的实现(1)典型的进程表表项中的一些字段进程表表项——进程控制块的主要字段14 2.1.6进程的实现(2)当中断发生后操作系统最底层的工作步骤硬件压入堆栈程序计数器等。硬件从中断向量装入新的程序计数器。汇编语言过程保存寄存器值。汇编语言过程设置新的堆栈。C中断服务例程运行（典型的读和缓冲输入）。调度程序决定下一个将运行的进程。C过程返回至汇编代码汇编语言过程开始运行新的当前进程中断发生时，底层处理步骤15 进程与程序的区别（补充）进程更能真实的描述并发（程序不能）进程是由程序和数据两部分组成的程序是静态的。进程是动态的进程有生命周期，有诞生有消亡，短暂的；而程序是相对长久的一个程序可以对应多个进程进程具有创建其他进程的功能16 线程线程是轻量级的进程，它是一个进程内的基本调度单位，有自己的程序计数器、寄存器及堆栈。多线程与多进程-多线程系统允许多个线程共享一个进程的地址空间、打开文件、全局变量等资源。-多进程系统允许多个进程共享物理内存、磁盘、打印机等资源。线程与进程-进程是资源管理的基本单位-线程是调度的基本单位2.2线程2.2.1线程的概念17 2.2.2线程模型(a)三个进程，每个进程有1个线程(b)一个进程有3个线程112318 线程的实现（TCB）一个进程中所有线程共享内容每个线程自己的内容19 每个线程有自己的堆栈(kernel&userstack,TCB)20 2.2.3引入线程的原因伪并行，进一步提高并发度更小的系统开销更高的性能有利于在多CPU系统中实现真正的并行21 2.2.4在用户空间实现线程用户级线程包22 2.2.5在内核中实现线程内核管理的线程包23 2.2.6混合实现用户级线程与内核线程复用24 2.3进程间通信并发进程间的相互制约：．间接制约：诸进程对共享资源的使用通过系统来协调，使得　　　　　　　进程间执行速度相互影响．直接制约：诸进程自行使用共享资源或由进程合作引起，某　　　　　　　一进程直接通过某机构发消息给其他进程，从而　　　　　　　直接其他进程的执行基本概念：．临界资源：一次只允许一个进程使用的资源．临界区：在每个进程中，访问临界资源的那部分代码（那段程　　　　　　序）2.3.1进程通信25 2.3.2互斥定义:．不允许两个以上的共享该资源的并发进程同时进入临界　　　　区，称为互斥并发进程互斥执行准则：．不假设各并发进程的相对执行速度．出于临界区外的进程不能阻止其他进程进入临界区．任何时刻只允许一个进程处于临界区中．不能使进程在临界区外永远等待26 互斥的实现：关中断法：每个进程进入临界区后先关中断，离开前开中断缺点：．系统可能终止．多CPU时，无用加锁法：用锁变量来表示临界区是否可用加锁后的临界区描述如下：lock(key[s])<临界区>//s为临界区类名unlock(key[s])//key[s]为锁变量，为1表示临界区//可用，为0表示临界区不能使用27 lock(key[s]){L:ifkey[s]=0thengotoLelsekey[s]=0}unlock(key[s]){key[s]=1}PA(){L1:lock(key[s])unlock(key[s])gotoL1}PB(){L2:lock(key[s])unlock(key[s])gotoL2}缺点：．不断循环测试，CPU费时．存在不公平现象28 严格的轮转法：用标志严格控制轮流使用临界区PA(){while(true){while(turn!=0);//waitcritical_region();turn=1;noncritical_region();}}PB(){while(true){while(turn!=1);//waitcritical_region();turn=0;noncritical_region();}}缺点：．当一个进程比另一进程慢很多时不好29 TSL指令用TSL指令进入和离开临界区30 信号量法：．信号量：是ＯＳ中表示资源的物理实体，是一个与队列相关的　　　　　　整型变量，其值仅由down，up原语改变．信号量的表示意义：设sem为信号量，则：当sem>=0时，表示可供并发进程使用的资源实体数当sem<0时，表示正在等待使用资源的进程数注：Ｐ、Ｖ原语的操作等同down、up原语操作31 入口s=s-1s>=0调用进程入等待队列转进程调度返回入口s=s+1s<=0唤醒等待队列中的一个进程返回或转进程调度返回down原语up原语YYNN32 用down，up原语实现互斥：ＰA：…down(sem)up(sem)…ＰB：…down(sem)up(sem)…．设一个互斥的信号量sem．描述：S为临界区的类名33 管程．一种更为高级的同步原语，更便于使用，管程的互斥由编译器负责，使用者只需将所有临界区转换为管程即可。．一个管程是由过程、条件变量及数据结构等组成的特殊模块或软件包。进程仅能通过管程访问其中的数据结构。．管程的特性：任一时刻管程中只能有一个活跃进程。34 2.3.3进程同步．例：设有计算进程及打印进程通过共用一个buf缓冲区进行工作，如两进程独立工作，则过程可描述如下：Pc:..A:localBufrepeatbuf<-BufuntilBuf=nullcomputeBuf<-resultgotoA..Pp:..B:localPrirepeatPri<-bufuntilPri=nullprintbuf<-nullgotoB..假定对buf已采取的互斥措施35 定义：异步环境下，一组并发进程因直接制约而相互发送消息，相互合作，相互等待，使各进程按一定速度执行的过程同步的实现：消息名法：为同步进程间发送的事件或消息赋予一个唯一的消息名，用：wait(表示进程等待合作进程发来的消息)signal(表示向合作进程发送消息)则上例表示的同步关系如下：．设消息名Bufempty表示Buf为空，Buffull表示Buf满．初始化：Bufempty=true,Buffull=false36 描述：Pc:A:wait(Bufempty)caculateBuf<-resultBufempty<-falsesignal(Buffull)GotoAPp:B:wait(Buffull)printBuf<-nullBuffull<-falsesignal(Bufempty)GotoB37 信号量法：此处信号量只与制约及被制约进程有关，故为私有的信号量同例：．设SA=0表示Buf中无可供打印的计算结果SB=0表示Buf空，计算结果可放入BufPcPp38 Pc:A:caculatenextnumberBuf<-resultcount=count-1V(SA)P(SB)ifcount=0thendestroy(Pc)elsegotoAPp:B:P(SA)print<-BufV(SB)printthelastnumberifcount=0thendestroy(Pp)elsegotoB39 2.3.4进程通信引入:1)信号量需要编程语言支持.2)信号量在网络环境下不可用实现:1)send(destination,&message)2)receive(source,&message)消息传递40 用N条消息实现的生产者-消费者问题41 管道通信注意：．对管道的使用必须互斥．管道工作时，只有一个读端和一个写端．由读出端和写入端不断反复交替工作，完成通信42 ．作业调度（高级调度）：决定参与CPU与其他系统资源的竞争，即作业由后备到运行　态。．交换调度（中级调度）：决定参与CPU竞争的进程，即进程由运行到阻塞态，或由阻　塞态到就绪态。．进程调度（低级调度）：决定获得CPU的进程，即进程由就绪态到运行态。2.4.1调度的层次：2.4进程调度43 2.4.2作业调度：作业调度功能：．记录系统中各作业的状况．从后备队列中选一部分作业投入运行．为被选中的作业做好执行前的准备工作．在作业执行结束时做善后处理工作作业调度的目标：．公平．高效．大吞吐量．短的响应时间和周转时间44 2.4.3进程调度：进程调度的功能：．记录系统中所有进程的执行情况．选择占有处理机的进程．进程上下文切换调度的时机：．正常执行结束．进程阻塞等待．执行了某些原语（Ｐ，Ｖ）．从系统态返回用户态．在可剥夺调度方式中，高优先级进程进入就绪队列．分时系统中，分配的时间片用　完45 进程上下文切换步骤：．决定是否允许做进程上下文切换．保存当前执行进程的上下文．按一定算法选择就绪队列的一个进程．恢复或装配所选进程的上下文，转交CPU控制权调度方式：．可剥夺式调度：强行剥夺先行进程的CPU周期，分配CPU给　　　　　　　　　另一进程．不可剥夺式调度：进程一直执行下去，直到完成本次CPU执　　　　　　　　　　行周期注：CPU周期－－进程在CPU上一次连续执行过程46 调度的基本准则：所有系统公平、策略的强制执行、均衡批处理系统大的吞吐量、短的周转时间、高的CPU利用率交互式系统短的响应时间、均衡性实时系统满足实时性要求、具有可预测性47 2.4.4进程及作业调度的性能评价指标：．平均周转时间：Ｔi＝tie-tis（tie：作业完成时刻，tis：作业提交时刻）Ｔi＝tie-tir（tie：进程完成本次CPU周期时刻tir：进程进入就绪队列时刻）Ｔ＝1/n（Ｔi）i=1n48 ．平均带权周转时间：设ti表示进程或作业的实际运行时间，则有：Ｔi’＝Ｔi／tiＴ’＝1/n（Ｔi’）i=1n．平均等待时间：（主要针对进程而言）Ｗi＝tip-tir(tip：指进程获得CPU的时刻）Ｗ＝1/n（Ｗi）（tir指进程进入就绪队列的时刻）i=1n49 2.4.5调度算法：先来先服务算法（FCFS)：按作业／进程到来的先后次序进行调度例１：假设有四道作业，它们的提交时刻及执行时间如下表：作业号　　提交时刻　　　执行时间１8.002.00２8.500.50３9.000.10４9.500.20例２：有三个进程p1,p2,p3的本次cpu周期时值分别为21ms,6ms,3ms,进程进入就绪队列的次序为p1,p2,p350 特点：对执行时间短的进程及作业等待时间将长对以上两例分别求调度序列，平均周转时间及平均带权周转时间，对进程还要求其平均等待时间最短作业优先法（ＳＪＦ）：选择估计需要执行时间最短的作业或进程投入运行（对进程而言，指估算的本次cpu周期的长短，如果是可剥夺式调度，则按剩余最短原则）对例１用此算法特点：．吞吐量大．对不断有作业进入的系统，长作业将永得不到执行51 响应比高优先算法（ＨＲＮ）：Ｒ＝响应时间／需运行时间＝１＋Ｔwi/Ｔ选择Ｒ大的作业／进程运行用以上例１求结果特点：．介于ＦＣＦＳ与ＳＪＦ之间．吞吐量减少．增加了系统开销52 轮转法（ＲＲ）：（只使用于进程调度）将ＣＰＵ时间划分成一个个时间片，每个进程轮流使用一个时间片，ＣＰＵ…完成时间片到Ｉ／Ｏ请求阻塞队列对以上例２，用ＲＲ法求解．特点：．时间片的设置：q=T/NT:系统的最大响应时间N:就绪队列中所允许的最大进程数．Q的取值不能过大或过小53 优先级调度算法：选择优先级高的进程／作业执行．优先级的设置方式：－静态：创建时由系统为其确定，一旦设定就不变化－动态：由运行环境及其自身特性的变化而改变优先级a.确定静态优先级的静态特性：．进程类型：（系统，用户）．作业要求资源：b.确定动态优先级的动态特性：．进程已有ＣＰＵ时间长短．进程在就绪队列中等待时间长短54 改变方法：．非线性：进程进入系统后，前一阶段，其优先级不变或随时间线性减少，当等待时间达到某一给定的最大值时，其优先级发生跃变到最高值，使该进程投入运行．线性：进程优先级按线性规律变化ＣＰＵ享受服务队列新创建进程队列…………完成55 设Ｐ为优先级，刚进入时，Ｐ＝０对就绪队列：Ｐ＝a*t(a>0)对享受服务队列：Ｐ＝b*t(a>b>0)新建就绪队列进程转入享受服务队列的时机：．就绪队列的第一个进程的优先级（Ｐ＝a*(t-t1)）＝享受服务队列最后一个进程的优先级（Ｐ＝b*t）时．当享受服务队列为空时，新建就绪队列头一进程可转入享受服务队列注：a>b>0否则：b>a>0，成为ＦＣＦＳa>b=0，成为ＲＲ56 例：有５个进程Ｐ１，Ｐ２，Ｐ３，Ｐ４，Ｐ５，它们的ＣＰＵ周期时值及优先级如下表：ＣＰＵ周期性　　　优先数　　　进入时刻Ｐ１　　　　　　３２　　　　　　５　　　　　０Ｐ２　　　　　　　４　　　　　　３　　　　　０Ｐ３　　　　　　　８　　　　　　５　　　　　０Ｐ４　　　　　　　２　　　　　　６　　　　　０Ｐ５　　　　　　１６　　　　　　４　　　　　１６１）在非剥夺方式下，求它们的调度序列，平均等待时间，平均周转时间，平均带权周转时间２）在可剥夺方式下，设优先级按如下规律变化：连续执行10ms以上后优先数加１，就绪队列中的进程每40ms优先数减１；则求它们的调度序列，平均等待时间，平均周转时间，平均带权周转时间57 多队列轮转法：进程按不同的优先级进入不同的队列，每个队列又采用不同的算法，如图所示：cpu1cpu2cpun完成完成完成ＦＣＦＳ（时间片Ｓ１）ＦＣＦＳ（时间片Ｓ２）RR（时间片Ｓn）时间片到（剥夺）时间片到（剥夺）…………………………注：Ｓ１＜Ｓ２＜．．．＜Ｓn58 2.4.6实时系统调度方法：实时系统处理的外部事件：．硬实时任务：系统必须完全满足任务的时限要求．软实时任务：允许系统对任务的时限要求有一定的延迟实时操作系统的功能:．快速的进程或线程切换．快速的外部中断响应．基于优先级的随时强占式调度策略59 实时操作系统的调度算法：．时限调度算法：选择时限要求最近的任务优先占有处理机，它是抢先式　　　的，即将新任务的时限与当前任务的时限进行比较，选择时　　　限最近的执行（时限可以是处理开始时限或处理结束时限）．频率单调调度算法：周期长的任务优先级越低（适用于多周期性实时任务）注：使用该算法的充分条件：对n个周期的不同任务，设每个周期为Pi，执行时间为Ci,则充分条件为：C1/P1+C2/P2+…+Ci/Pi+…+Cn/Pn<=160 2.4.7线程调度用户级线程的可能调度61 内核级线程的可能调度62 2.5经典的进程间通信问题．2.5.1生产者-消费者问题P1P2Pm…12n…………C1C2C3…有界缓冲区．生产者－消费者之间满足的条件：－消费者想接收数据时，有界缓冲区中至少有一个单元是满的－生产者想发送数据时，有界缓冲区中至少有一个单元是空的－有界缓冲区是临界资源63 64 2.5.2哲学家就餐问题哲学家的活动：吃饭/思考吃饭需要2把叉子一次只拿一把?给出描述哲学家行为的、不会死锁的程序结构*Itisusefulformodelingprocessesthatarecompetingforexclusiveaccesstoalimitednumberofresources,suchasI/Odevices.65 哲学家就餐问题的一种错误解决方案66 哲学家就餐问题的一种解决方案67 哲学家就餐问题的一种解决方案68 2.5.3读者-写者问题Databaser1,r2,r3,……读者队列:rcreaderwriter69 读者-写者问题的一种解决方案70 例题1：某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：(1)用PV操作管理这些并发进程时，应怎样定义信号量，写出信号量的初值以及信号量各种取值的含义。(2)根据所定义的信号量，把应执行的PV操作填入下述方框中，以保证进程能够正确地并发执行。COBEGINPROCESSPI(I=1，2，……)begin；；进入售票厅；购票；退出；;end；COEND(3)若欲购票者最多为n个人，写出信号量可能的变化范围(最大值和最小值)。71 例题2：用P、V操作实现下述问题的解。桌上有一个盘子，可以存放一个水果。父亲总是放苹果到盘子中，而母亲总是放香蕉到盘子中；一个儿子专等吃盘中的香蕉，而一个女儿专等吃盘中的苹果。在本题中，父亲、母亲、儿子和女儿共用一个盘子，盘子一次只能放一个水果。当盘子为空时，父亲及母亲均可以试着将一个水果放入盘子中，但一次只能有一人成功放入水果。若放入盘子中的是香蕉，则允许儿子吃，女儿必须等待；若放入盘子中的是苹果，则允许女儿吃，儿子必须等待。在本题中，应设置三个信号量dish，apple，banana，信号量dish表示盘子是否为空，其初值为1；信号量apple表示盘中是否有苹果，其初值为0；信号量banana表示盘中是否有香蕉，其初值为0。进程之间的同步描述如下：semaphore  dish=1；semaphore  apple=0；semaphore  banana=0；72 main（）{cobeginfather（）；mother（）；son（）；daughter（）；coend}father（）{while（true）{P(dish）；将苹果放入盘中；V(apple）；}}mother（）{while（true）{p（dish）；将香蕉放入盘中；V(banana）；}}73 son（）{while（true）{P(banana）；从盘中取出香蕉；v（dish）；吃香蕉；}}daughter（）{while（true）{p（apple）；从盘中取出苹果；v（dish）；吃苹果；}}74 例题3：设公共汽车上，司机和售票员的活动分别是：司机的活动：启动车辆；正常行车；到站停车。售票员的活动：关车门；售票；开车门。在汽车不断地到站、停站、行驶过程中，这两个活动有什么同步关系？用信号量和P、V操作实现它们的同步。在汽车行驶过程中，司机活动与售票员活动之间的同步关系为：售票员关车门后，向司机发开车信号，司机接到开车信号后启动车辆，在汽车正常行驶过程中售票员售票，到站时司机停车，售票员在车停后开车门让乘客上下车。因此司机启动车辆的动作必须与售票员关车门的动作取得同步；售票员开车门的动作也必须与司机停车取得同步。在本题中，应设置两个信号量：s1、s2。s1表示是否允许司机启动汽车，其初值为0;s2表示是否允许售票员开门，其初值为0。这两个活动的同步用P、V原语描述如下：75 Semaphores1＝0；Semaphores2＝0；main（）｛cobegindriver（）；busman（）；coend｝driver（）｛while（true）｛p(s1)；启动车辆；正常行车；到站停车；v（s2）；｝｝busman（）｛while（true）｛关车门；v（s1）；售票；p（s2）；开车门；上下乘客；｝｝76 例题4：有一个理发师，一把理发椅和n把供等候理发的顾客坐的椅子。如果没有顾客，理发师便在理发椅上睡觉；当一个顾客到来时，必须唤醒理发师进行理发；如果理发师正在理发时又有顾客到来，则如果有空椅子可坐，他就坐下来等，如果没有空椅子，他就离开。为理发师和顾客各编一段程序描述他们的行为，要求不能带有竞争条件。本题中使用三个信号量：customers用来记录等候理发的顾客数（不包括正在理发的顾客），其初值为0；barbers记录正在等候顾客的理发师数，其值为0或1；mutex用于实现共享变量的互斥访问，其初值为1。共享变量count，它也用于记录等候的顾客数，它实际上是customers的一个备份，之所以使用count是因为无法读取信号量的当前值。同步算法描述如下：77 semaphore  customers=0；／*等候的顾客数*／semaphore  barbers=0，／*等候顾客的理发师数*／semaphore  mutex=1；int count=0；／*等候的顾客数（还没理发）*／main（）{cobeginbarbers（）；customers（）；coend}78 barber（）{while（true）{p（customers）；／*是否有等候的顾客*／p（mutex）；count=count-1；／*顾客数减1*／v（barbers）；／*理发师开始理发*／v（mutex）；理发；}}79 customer（）{p（mutex）；if（count