计算机操作系统入门第二章.ppt

《计算机操作系统入门第二章.ppt》由会员分享，可在线阅读，更多相关《计算机操作系统入门第二章.ppt（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第3课课进程管理进程管理本次课学习如下知识：本次课学习如下知识：进程的概念程序的并发执行进程及其特征进程的状态进程控制块FCB进程调度进程控制进程协作进程间的通信线程第第2章章进程管理进程管理处理机是计算机系统中最重要的资源之一，操作系统对处理机的管理是最重要的功能之一。操作系统负责如下活动和进程管理：创建、删除用户进程和系统进程，进程调度，进程同步，进程通信，以及进程死锁的处理。本章将讨论如下几个方面的知识：1进程的概念：进程的状态、进程的调度、进程操作与协作、进程的通讯、进程的特征。2进程的同步：同步的概念、同步的实现。3处理机调度：调度标准、调度算法、多处理机调度、实时调度、算法评估。

2、4死锁：死锁的定义、死锁的特点、死锁的处理、死锁的预防、死锁避免、死锁检测、死锁的恢复。2.1进程的概念进程的概念2.1.1程序的并发执行程序的并发执行1程序的顺序执行的特点程序的顺序执行的特点顺序性：封闭性：可再现性：2程序的并行执行程序的并行执行并发程序比起顺序程序具有高得多的复杂性。程序与计算不再一一对应。计算之间存在复杂的相互制约关系。2.1.3进程的状态进程的状态进程包含以下几个状态：运行状态：就绪状态：阻塞状态：进程的三种关系是可以转换的，它们之间的转换关系如下图所示进程状态的转换2.1.4进程控制块进程控制块PCB进程控制块是用于对当前系统中的进程进行控制和管理。进程控制块描述和

3、记录了进程在整个生命周期内动态变化的数据结构特征。PCB是进程存在的惟一标志。1进程控制块中的信息进程控制块中的信息进程标识：进程状态：程序计数器：CPU调度信息：CPU寄存器：内存管理信息：输入/输出状态信息：2 2PCBPCB的组织方式的组织方式链接方式：索引方式：2.1.5进程调度进程调度1.调度队列调度队列进程的作业队列：进程的就绪队列：由一个链表组成，链表的头包含着指向第一个进程PCB的指针和指向最后一个进程PCB的指针。进程的等待队列：2.进程调度程序进程调度程序进程调度作业调度程序3.进程切换进程切换系统要储存老进程的状态信息，同时还要装入新进程的状态信息。2.1.6进程控制进程

4、控制操作系统的进程创建和撤消机制。1 1进程创建进程创建子进程，父进程。导致一个进程去创建另一个进程的典型事件：用户登录、作业调度、提供服务。2.2.进程撤消进程撤消进程的删除。进程的终止。引起进程终止的事件：正常结束、异常结束、外界干预。2.1.7 2.1.7 进程协作进程协作独立进程与是协作进程。允许进程协作的原因：信息共享：加快运算速度：模块化：方便：2.1.8 2.1.8 进程间的通信进程间的通信协作进程通过共享内存实现它们之间的通信。操作系统提供的进程通信设施IPC实现进程之间的通信。IPC的最佳方案是消息传递系统。1.1.消息传递系统消息传递系统直接通信：模式1：对称地址形式。在直

5、接通信方式中每一个要通信的进程必须显示接收信息进程名和发送信息进程名。其定义形式为：Send(P,Message)给进程P发送信息。Receive(Q,Message)从进程Q接收信息。模式2：非对称地址形式。由发送进程指定通信进程名，而接收进程则不要求。其格式为：Send(P,Message)给进程P发送信息。Receive(ID，Message)从任何进程接收信息。其中：变量ID将会被进程名所代替。间接通信对于间接通信，发送和接收的消息都是放在信箱中，每个信箱都有惟一的标识。其Send和Receive可定义如下：Send(A,Message)将信息发送至A信箱。Receive(A,Mess

6、age)从A信箱接收信息。这种模式下，其通信链有如下特点：仅仅当一对进程具有共享信箱时，他们之间可建立连接。一个连接也可能与两个以上的进程有关。每一对通信进程之间，可能有许多不同的连接，而每一个连接对应一个信箱。如果信箱属于一个进程（也就是信箱是进程的地址空间的一部分），则当这个进程终止时，它的信箱也就随之消失。如果一个信箱属于操作系统，则它是独立的而不属于任何进程，因此操作系统提供了一种机制而允许进程作如下操作：创建新信箱、通过信箱发送和接收信息、删除信箱。2缓冲区缓冲区无论通信是直接还是间接，进程间的信息交换都驻留在缓冲区中的临时队列中。这种队列有三种实现方法：零容量：有界容量：无界容量：

7、2.1.9线程线程为了减少系统的开销，提高程序的并发执行效率，而产生了线程的概念。1.线程简介线程简介轻量级进程：是被系统独立调度和CPU的基本运行单位。多线程：2多线程的优点多线程的优点多线程编程的优点可有以下四点：响应：资源共享：经济：多处理器结构的应用：3用户线程和内核线程用户线程和内核线程线程的实现方式：用户线程、内核线程。用户线程内核线程小结小结进程的概念是操作系统最重要的概念。处理机的管理主要是进程的管理。学习本章时，首先要理解进程的概念、处理机调度的概念、死锁的概念。重点知识是：一是与进程管理有关的的知识，包括进程状态、进程调度、进程协作、进程通讯、进程同步；二是与处理机有关的知

8、识，包括处理机调度的标准、算法，多处理机调度，算法评估。本讲应掌握的知识：进程及其特征进程的状态、进程控制块PCB进程调度、进程控制难点知识：进程的概念进程协作进程间的通信进程同步的实现和处理机调度算法的评估。第第4课课进程的同步进程的同步本次课学习如下知识：本次课学习如下知识：同步的概念临界资源临界区问题同步的实现2.2进程的同步进程的同步进程的引入虽然改善了系统的资源利用率和提高了系统的吞吐量，但是进程的异步性，特别是它们在争用临界资源时，会给系统造成一定的混乱。为了解决这个问题，提出了进程同步的概念。2.2.1同步的概念同步的概念系统中存在着许多进程，它们之间可以有两种关系：1资源共享资

9、源共享进程是独立运行的基本单位，各个进程彼此之间没有联系，但它们同处于一个系统中，共享系统资源。进程在访问这些资源时，可能会被系统中运行的其它进程所影响。2相互协作相互协作协作进程可能直接共享逻辑地址空间（比如代码和数据）或通过文件共享数据。并发访问共享数据，可能会导致数据的不一致性。3进程同步的任务进程同步的任务保证各进程能互斥地访问这些资源（有效地共享资源）。保证协作进程或线程的顺序执行，使它们不会出现与时间有关的差错，对数据的一致性进行维护（有效地相互合作）。2.2.2临界资源临界资源临界资源的概念：在一段时间内只允许一个进程访问的资源对临界资源的访问必须采用互斥的方式进行，以实现对资源

10、的共享。生产者消费者问题：一个经典同步问题来说明进程同步的必要性。这个问题的主要描述如下：有一个生产者进程在生产消息，并提供给消费者进程进行消费，所生产的消息存放在一个有几个缓冲区的缓冲池中。生产者进程可将它所生产的消息放入一个缓冲区中，消费者进程则从一个缓冲区中取走一个消息。它们之间必须保持同步，即不允许消费者进程到一个空缓冲区中去取消息，也不允许生产者进程向一个已装满消息而尚未取走的缓冲区中投放消息，其代码如下：生产者代码：While(Count=Buffer_SIZE)+Count;/增加一项至缓冲区Bufferin=item;in=(in+)%Buffer_SIZE);消费者代码：Wh

11、ile(count=0)-Count;/从缓冲区减去一项item=Bufferout;out=(out+1)%Buffer_SIZE;其中指针in来指示下一个可存放消息的缓冲区，每存放一个消息，in+1。指针out来指示下一个可获得消息的缓冲区，每当取走一个消息后，输出指针out+1。由于缓冲池是循环缓冲，因此输入指针in=(in+)%BufferSRE,输出指针out=(out+)%BufferSRE。尽管两段代码是正确的，但当他们并行运行时，其结果也许不正确。原因是两段进程共享变量Count,Count是缓冲区中项目的计数，+Count和-Count用机器语言实现为如下操作：r1=Coun

12、t;r1=r1+1;Count=r1;r2=Count;r2=r2-1Count=r2假设Count为5，如果两段进程是按顺序执行，则不会产生错误，即可得到结果：Count=5。然而如果我们按如下顺序执行，则我们会得到错误的结果。即：Count=4。T0:生产者进程执行：r1=Count;T1:生产者进程执行：r1=r1+1;T2:消费者进程执行：r2=Count;T3:消费者进程执行：r2=r2-1;T4:生产者进程执行：Count=r1;T5:消费者进程执行：Count=r2;而如果我们交换T4和T5的顺序，我们又会得到count=6的错误结果。2.2.3临界区问题临界区问题临界区的概念：

13、将多个进程访问临界资源的那一段程序代码称为临界区。在临界区中，进程能改变变量的值，更新数据表或写文件等。系统只允许一个进程在临界区执行，而不允许其它进程进入临界区。解决临界区问题必须遵循的原则：1.当某一时刻没有进程处于临界区内时，相应的临界资源处于空闲状态。因而可允许一个请求进入临界区进程立即进入临界区，以有效地利用临界资源。2.如果此时已有进程进入临界区，则其它试图进入临界区的进程必须等待，以保证各进程互斥地访问临界资源。3.当某个进程申请进入临界区时，它应在有限时间内获得系统的响应，而能够进入临界区，以免进程陷入无限等待状态。4.当进程不能进入临界区时，应立即释放处理机，以免进程陷入忙等

14、待状态。2.2.4同步的实现同步的实现解决临界区问题可以用软件或硬件实现。使用硬件实现进程的同步，可以使用户的编程任务更容易且系统的效率更高。1关中断关中断使用关中断解决单处理器环境下临界区的问题。使用关中断不能解决多处理器环境下临界区的问题。关闭中断将延误处理器的处理时间，使系统性能下降。2锁变量的测试与设置锁变量的测试与设置锁变量Lock：测试锁变量Lock：设置锁变量：“测试与设置”指令：3信号量信号量信号量：PV操作：P操作P（S）S-;if(S=0)继续执行；else阻塞并进入等待队列；V操作V（S）S=S+1;if(S0)继续运行；else唤醒等待队列中的一个进程，并继续运行；PV

15、操作实现进程的互斥小结小结本次课应掌握的知识：进程之间和资源共享和进程相互协作的概念。进程同步的必要性。临界资源的概念以及对临界资源访问的解决方案。临界区的概念和解决临界区问题必须遵循的原则。锁变量的设置与测试。难点知识：如何实现进程的同步：关闭中断的概念及其优缺点。P操作和V操作的实现和如何使用PV操作实现进程的互斥第第5课课处理机调度处理机调度本次课学习如下知识：本次课学习如下知识：基本概念调度标准调度算法多处理器调度实时调度算法评估2.3处理机调度处理机调度2.3.1基本概念基本概念调度是操作系统的基本功能，几乎所有的系统资源都是通过调度而被使用。1.调度程序调度程序操作系统做出选择进程

16、的决定是由调度程序来实现的。调度程序面临的问题：2调度类型调度类型从作业进入系统到作业运行完毕，它要经历以下调度过程：高级调度作业调度（长程调度）、接纳调度。每次执行作业调度时，都需要做出以下两个决定：接纳多少个作业：接纳哪些作业：低级调度进程调度是最基本的一种调度。依据下面四种情况决定是否进行CPU重新调度。当进程从运行态转到等待态。当进程从运行态转到就绪态。当进程从等待状态转到就绪状态。当进程终止时。进程调度的非抢占方式：进程调度的抢占方式：进程调度抢占的原则：时间片原则：优先权原则：短作业优先原则：中级调度2.3.2调度标准调度标准1CPU利用：2吞吐量：3周转时间：4等待时间：5响应时

17、间：2.3.3调度算法调度算法1.先来先服务调度先来先服务调度按进程进入等待队列的先后顺序进行分配CPU。CPU总是选择就绪队列中的第一个进程，将处理机分配给它。FCFS算法比较有利于长作业，而不利于短作业。假设有进程P1、P2和P3，他们到达的时间顺序和CPU脉冲时间长短如下所示。进程与脉冲时间表进程脉冲时间（毫秒）P23P33各进程按FCFS算法的执行顺序如下图所示。P124P1P2P30242730FCFS算法中进程的运行顺序进程P1的等待时间是零，进程P2需等待24，P3是27，则它们的平均等待时间是（0+27+27）/33。FCFS调度是非抢占式。2.最短作业优先最短作业优先从就绪队

18、列中选出一个估计在下一个CPU脉冲时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞后放弃处理机时，系统再重新调度。如果两个进程运行时间相同，则采用FCFS算法选一个较早到达的进程。该算法也存在着不容忽视的缺点：长作业得不到及时调度。不能保证紧急性的作业会得到及时处理。算法较难实现。3.优先权调度优先权调度系统按某种原则将进程指定一个优先权来表示进程所享有的调度优先权。优先权调度算法的类型优先权调度算法有抢占式和非抢占式两种。抢占式优先权调度算法：非抢占式优先权调度算法：优先权的类型静态优先权：动态优先权：优先权调度算法的主要问题：4.时间片轮转法调度时间片轮

19、转法调度时间片轮转调度算法的含义。决定时间片轮转算法的性能的因素：系统对响应时间的要求：就绪队列中进程的数目：系统的处理能力：5.多级队列调度多级队列调度多级队列调度算法的含义：多级队列调度算法的实现：6、多级反馈队列调度、多级反馈队列调度多级反馈队列调度的含义：多级反馈调度的实现：2.3.4多处理器调度多处理器调度多处理器情况下要解决的问题：对称式多处理调度：2.3.5实时调度实时调度硬实时系统的概念：软实时系统的概念：2.3.6算法评估算法评估选择算法的标准：在最大响应时间为1秒的限制下，CPU最大利用率。在平均周转时间为线性总执行时间的条件下，CPU的最大吞吐量是多少。分解评估法对以下五

20、个进程到达的时间为0，其顺序及CPU脉冲时间如下表所示：五个进程的脉冲时间表进程脉冲时间（毫秒）P110P229P33P47P512FCFS算法进程的执行顺序如下图所示。P1P2P3P4P501039424961FCFS算法中进程的运行顺序各进程的等待时间为：P1=0（毫秒）P2=10（毫秒）P3=39（毫秒）P4=42（毫秒）P5=49（毫秒）平均等待时间是(0+10+39+42+49)/5=28（毫秒）。SJF算法各进程的执行顺序如下图所示。P3P4P1P5P20310203261SJF算法中进程的运行顺序各进程的等待时间为：P1=10（毫秒）P2=32（毫秒）P3=0（毫秒）P4=3（毫

21、秒）P5=20（毫秒）平均等待时间是(10+32+0+3+20)/5=13（毫秒）。RR算法各进程执行顺序如下图所示(假设RR时间片=10毫秒)。P1P2P3P4P5P2P5P201020233040505261RR算法中进程的运行顺序各进程的等待时间为：P1=0（毫秒）P2=32（毫秒）P3=20（毫秒）P4=23（毫秒）P5=40（毫秒）平均等待时间是(0+32+20+23+40)/5=23毫秒队列模型模拟模拟的概念：实现小结小结本次课应掌握如下知识：操作系统调度程序的功能。高级调度和低级调度的作用及其实现过程。恒量调度优劣的五个标准。调度算法：时间片轮转法调度、优先权调度、最短作业优先、

22、先来先服务调度、多级反馈队列调度、多级队列调度多处理器调度：实时调度了解以下知识：多处理器调度：实时调度难点知识：算法评估：分解评估法的几种算法的含义及其进程的执行顺序。第第6课课死锁死锁本次课学习如下知识：死锁的定义产生死锁的原因死锁的特点死锁的处理方法死锁的预防死锁的避免死锁的检测死锁的恢复2.4死锁死锁2.4.1死锁的定义死锁的定义死锁的概念：几个并发进程为竞争系统资源而进入了等待状态，且它们永远不会改变这种状态。系统资源的分配过程：为什么会出现死锁：2.4.2产生死锁的原因产生死锁的原因产生死锁的原因：可剥夺资源：不可剥夺资源：2.4.3死锁的特点死锁的特点死锁产生的后果：发生死锁的必

23、要条件：互斥条件：占有和等待：非抢占：循环等待：资源分配图用有向图来表示资源分配与死锁的关系，称之为系统资源分配图。如下图所示。资源分配图图中：P=P1，P2，P3Pn，表示进程的圆形结点集。R=R1，R2Rn，表示资源的方形结点集。有向边P1R1表示进程P1正在申请资源R1。有向边R1P1表示资源R1已分配给进程P1。从资源分配图中我们可以看出：如果图中没有环路，则表明系统中没有死锁发生。如果图中包括一个环路，则说明系统中有可能存在死锁现象。将上图加以修改，就产生了两个环路（如下图所示）：P1R1P2R2P3R3P1P2R2P3R3P2有死锁的资源分配图从图中的两个环路可以看出：进程P1，P

24、2和P3处于死锁状态；P2等待资源R2，而R2已分配给进程P3；P3正等待P1和P2释放资源R3；进程P1正等待进程P2释放R1。现在我们看下图，虽然图中有环路P1R1P3R2P1，但却不会发生死锁。因为：P2释放R1后，系统可重新分配给P1；同样P4释放R2后，再分配给P3就打破了环路。无死锁环路的资源分配图2.4.4死锁的处理方法死锁的处理方法解决死锁问题的方法有：1预防：使用一种协议来保证系统永远不会进入死锁状态。2避免：采用动态分配资源，以避免死锁的发生。3恢复：允许系统进入死锁状态，然后再恢复。4忽略：假设系统不会发生死锁。2.4.5死锁的预防死锁的预防使产生死锁的四个必要条件中至少

25、有一个条件不满足，以达到预防死锁的发生的目的。1互斥：破坏互斥使用条件。2占有和等待：破坏占有和等待条件，达到预防死锁的目的。3非抢占：破坏非抢占条件。4循环等待：破坏循环等待条件。2.4.6死锁的避免死锁的避免限制进程提出的资源申请：动态检测资源分配状态，以保证没有循环等待条件发生。用资源分配图来说明。如下图所示：实线表示进程的请求或资源的分配已经得到系统的认可。虚线则表示将来进程可能会提出的申请。系统采用循环检测算法来确认系统是否安全。假设进程P2申请资源R2，虽然目前R2处于空闲状态，但是系统也不能将资源R2分配给P2，因为如果系统将R2分配给P2，从图中我们可以看出，如果此时P1也申请

26、R2，这一分配势必将形成环路，使系统处于不安全状态，则死锁必定发生。死锁避免的资源分配图（1）死锁避免的资源分配图（2）2.4.7死锁的检测死锁的检测系统提供了死锁检测机制，当检测到死锁发生时，便采取措施进行恢复。假设，系统中的各种资源仅有一个。我们从资源分配图可以得到相应的资源等待图。如下面两个图所示。资源分配图资源等待图如何确定系统中是否发生了死锁。系统应该在什么时候调用算法进行检测呢。2.4.8死锁的恢复死锁的恢复当检测到系统中存在死锁时，防止出现死锁的方法：终止一个或多个进程，将循环等待破坏；剥夺一个或多个死锁进程所拥有的资源。1.进程终止：终止一个或几个死锁进程。终止所有死锁进程：终止一个死锁进程：2.资源抢占：选择一个牺牲者：回退：饥饿：小结小结本次课应掌握如下知识：系统资源的分配过程死锁的定义和产生死锁的原因：可剥夺资源、不可剥夺资源死锁的特点发生死锁的必要条件：互斥条件、占有和等待、非抢占、循环等待死锁的预防了解以下知识：死锁的避免死锁的处理方法资源分配图难点知识：死锁的检测死锁的恢复