操作系统Chapter-02(进程与线程).ppt

《操作系统Chapter-02(进程与线程).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 2）FCFS的特点比较有利于长作业，而不利于短作业。有利于CPU繁忙的作业，而不利于I/O繁忙的作业。6.51.310.810.61.10.29.5D4→16.01.610.610.51.50.19.0C3→4.02.010.510.01.50.58.5B2→1.02.010.08.00.02.08.0A1→wititctbtwtsta进程调度次序ta到达时间、tb开始时间、tc完成时间、ts服务时间、tw等待时间；ti周转时间时间单位：分钟T=6.9/4=1.725W=27.5/4=6.87551 特点：对执行时间短的进程及作业等待时间将长对以上两例分别求调度序列，平均周转时间及平均带权周转时间，对进程还要求其平均等待时间最短作业优先法（ＳＪＦ）：选择估计需要执行时间最短的作业或进程投入运行（对进程而言，指估算的本次cpu周期的长短，如果是可剥夺式调度，则按剩余最短原则）对例１用此算法特点：．吞吐量大．对不断有作业进入的系统，长作业将永得不到执行52 534.00.810.310.10.60.29.5D3→11.01.110.110.01.00.19.0C2→4.62.310.810.31.80.58.5B4→1.02.010.08.00.02.08.0A1→wiTitctbtwtsta进程调度次序ta到达时间、tb开始时间、tc完成时间；时间单位：小时T=6.2/4=1.55W=20.6/4=5.15T=6.9/4=1.725W=27.5/4=6.875比较FCFS53 响应比高优先算法（ＨＲＮ）：Ｒ＝响应时间／需运行时间＝１＋Ｔwi/Ｔ选择Ｒ大的作业／进程运行用以上例１求结果特点：．介于ＦＣＦＳ与ＳＪＦ之间．吞吐量减少．增加了系统开销Rp=(等待时间+要求执行时间)/要求执行时间Rp=(tw+tsi)/tsi=1+tw/tsi54 22.76.5T=1.625W=5.6756.51.310.810.66.51.10.29.5D4→4.00.60.29.5D4.22.110.610.14.21.60.58.5B3→3.50.50.29.5D11.01.110.110.011.01.00.19.0C2→4.01.50.58.5B1.02.010.08.01.00.02.08.0A1→wiTitctbRptwtsta作业调度次序ta到达时间、tb开始时间、tc完成时间Rp=1+tw/tsi55 56T=1.625W=5.675T=6.2/4=1.55W=20.6/4=5.15T=6.9/4=1.725W=27.5/4=6.875比较FCFS比较SJFHRRN56 57FCFS短作业优先SJ(P)F：对预计执行时间短的作业（进程）优先调度；最高响应比优先HRRNRp=(等待时间+要求执行时间)/要求执行时间时间片轮转算法几个重要的指标：周转时间Ti：作业（进程）从提交到完成所经历的时间(1）平均周转时间TTsi指的是系统为其服务的时间，带权周转时间为：TsinW=－∑Tii=1n1(2）平均带权周转时间WTsiTiWi=/57 轮转法（ＲＲ）：（只使用于进程调度）将ＣＰＵ时间划分成一个个时间片，每个进程轮流使用一个时间片，ＣＰＵ…完成时间片到Ｉ／Ｏ请求阻塞队列对以上例２，用ＲＲ法求解．特点：．时间片的设置：q=T/NT:系统的最大响应时间N:就绪队列中所允许的最大进程数．Q的取值不能过大或过小例２：有三个进程p1,p2,p3的本次cpu周期时值分别为21ms,6ms,3ms,进程进入就绪队列的次序为p1,p2,p358 优先级调度算法：选择优先级高的进程／作业执行．优先级的设置方式：－静态：创建时由系统为其确定，一旦设定就不变化－动态：由运行环境及其自身特性的变化而改变优先级a.确定静态优先级的静态特性：．进程类型：（系统，用户）．作业要求资源：b.确定动态优先级的动态特性：．进程已有ＣＰＵ时间长短．进程在就绪队列中等待时间长短59 改变方法：．非线性：进程进入系统后，前一阶段，其优先级不变或随时间线性减少，当等待时间达到某一给定的最大值时，其优先级发生跃变到最高值，使该进程投入运行．线性：进程优先级按线性规律变化ＣＰＵ享受服务队列新创建进程队列…………完成60 设Ｐ为优先级，刚进入时，Ｐ＝０对就绪队列：Ｐ＝a*t(a>0)对享受服务队列：Ｐ＝b*t(a>b>0)新建就绪队列进程转入享受服务队列的时机：．就绪队列的第一个进程的优先级（Ｐ＝a*(t-t1)）＝享受服务队列最后一个进程的优先级（Ｐ＝b*t）时．当享受服务队列为空时，新建就绪队列头一进程可转入享受服务队列注：a>b>0否则：b>a>0，成为ＦＣＦＳa>b=0，成为ＲＲ61 例：有５个进程Ｐ１，Ｐ２，Ｐ３，Ｐ４，Ｐ５，它们的ＣＰＵ周期时值及优先级如下表：ＣＰＵ周期性　　　优先数　　　进入时刻Ｐ１　　　　　　３２　　　　　　５　　　　　０Ｐ２　　　　　　　４　　　　　　３　　　　　０Ｐ３　　　　　　　８　　　　　　５　　　　　０Ｐ４　　　　　　　２　　　　　　６　　　　　０Ｐ５　　　　　　１６　　　　　　４　　　　　１６１）在非剥夺方式下，求它们的调度序列，平均等待时间，平均周转时间，平均带权周转时间２）在可剥夺方式下，设优先级按如下规律变化：连续执行10ms以上后优先数加１，就绪队列中的进程每40ms优先数减１；则求它们的调度序列，平均等待时间，平均周转时间，平均带权周转时间62 多队列轮转法：进程按不同的优先级进入不同的队列，每个队列又采用不同的算法，如图所示：cpu1cpu2cpun完成完成完成ＦＣＦＳ（时间片Ｓ１）ＦＣＦＳ（时间片Ｓ２）RR（时间片Ｓn）时间片到（剥夺）时间片到（剥夺）…………………………注：Ｓ１＜Ｓ２＜．．．＜Ｓn63 2.4.6实时系统调度方法：实时系统处理的外部事件：．硬实时任务：系统必须完全满足任务的时限要求．软实时任务：允许系统对任务的时限要求有一定的延迟实时操作系统的功能:．快速的进程或线程切换．快速的外部中断响应．基于优先级的随时强占式调度策略64 实时操作系统的调度算法：．时限调度算法：选择时限要求最近的任务优先占有处理机，它是抢先式　　　的，即将新任务的时限与当前任务的时限进行比较，选择时　　　限最近的执行（时限可以是处理开始时限或处理结束时限）．频率单调调度算法：周期长的任务优先级越低（适用于多周期性实时任务）1/n65 2.4.7线程调度用户级线程的可能调度66 内核级线程的可能调度67 2.5经典的进程间通信问题．2.5.1生产者-消费者问题P1P2Pm…12n…………C1C2C3…有界缓冲区．生产者－消费者之间满足的条件：－消费者想接收数据时，有界缓冲区中至少有一个单元是满的－生产者想发送数据时，有界缓冲区中至少有一个单元是空的－有界缓冲区是临界资源68 69 2.5.2哲学家就餐问题哲学家的活动：吃饭/思考吃饭需要2把叉子一次只拿一把?给出描述哲学家行为的、不会死锁的程序结构*Itisusefulformodelingprocessesthatarecompetingforexclusiveaccesstoalimitednumberofresources,suchasI/Odevices.70 哲学家就餐问题的一种错误解决方案71 哲学家就餐问题的一种解决方案72 哲学家就餐问题的一种解决方案73 2.5.3读者-写者问题Databaser1,r2,r3,……读者队列:rcreaderwriter74 读者-写者问题的一种解决方案75 进程控制(补充)系统使用具有特定功能的程序段来创建，撤消进程及完成进程之间状态转换原语的概念：asingle,indivisibleatomicaction（系统态下执行的某些具有特定功能的程序段）．机器指令级：不允许中断．功能级：不允许并发执行用于进程控制的原语：创建原语，撤消原语，阻塞原语，唤醒原语76 ．创建原语：入口查ＰＣＢ链表有空PCB吗取空PCB(i)表将参数填入PCB(i)PCB(i)入就绪队列PCB(i)入家族链返回创建失败．由系统创建或由父进程创建77 入口返回．撤消原语：查进程家族链有此PCB吗该PCB有子进程吗释放资源及PCB表有无出错处理有无．由系统或祖先进程撤消78 ．阻塞原语：入口保存当前ＣＰＵ现场置该进程的状态被阻塞进程入等待队列转进程调度自己调用阻塞原语阻塞自己79 ．唤醒原语：入口从等待队列摘下被唤醒进程将被唤醒进程置为就绪态将被唤醒进程送入就绪队列转进程调度或返回由系统唤醒或事件发生进程唤醒80