|
知识路径: > 计算机系统知识 > 计算机软件知识 > 操作系统知识 > 处理机管理(状态转换、同步与互斥、分时、抢占、死锁) >
|
相关知识点:67个
|
|
|
|
|
进程的概念是操作系统中最基本、最重要的概念。它是多道程序系统出现后,为了刻画系统内部出现的动态情况,描述系统内部各道程序的活动规律而引进的一个新概念,所有的多道程序设计操作系统都建立在进程的基础上。操作系统专门引入进程的概念,从理论角度看,是对正在运行的程序过程的抽象;从实现角度看,则是一种数据结构,目的在于清晰地刻画动态系统的内在规律,有效管理和调度进入计算机系统主存储器运行的程序。
|
|
|
进程的定义也是多种多样的,国内学术界较为一致的看法是:进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动(1978年全国操作系统学术会议)。从操作系统管理的角度出发,进程由数据结构以及在其上执行的程序(语句序列)组成,是程序在这个数据集合上的运行过程,也是操作系统进行资源分配和保护的基本单位。它具有如下属性:
|
|
|
(1)结构性。进程包含了数据集合和运行于其上的程序。
|
|
|
(2)共享性。同一程序同时运行于不同数据集合上时,构成不同的进程。或者说,多个不同的进程可以共享相同的程序。
|
|
|
(3)动态性。进程是程序在数据集合上的一次执行过程,是动态概念,同时,它还有生命周期,由创建而产生,由撤销而消亡;而程序是一组有序指令序列,是静态概念,所以,程序作为一种系统资源是永久存在的。
|
|
|
(4)独立性。进程既是系统中资源分配和保护的基本单位,也是系统调度的独立单位(单线程进程)。凡是未建立进程的程序,都不能作为独立单位参与运行。通常,每个进程都可以各自独立的速度在CPU上进行。
|
|
|
(5)制约性。并发进程之间存在着制约关系,进程在进行的关键点上需要相互等待或互通消息,以保证程序执行的可再现性和计算结果的唯一性。
|
|
|
|
|
|
一个进程从创建而产生至撤销而消亡的整个生命周期,可以用一组状态加以刻画,为了便于管理进程,一般来说,按进程在执行过程中的不同状况至少定义3种不同的进程状态:
|
|
|
(1)运行(running)态。占有处理器正在运行。
|
|
|
(2)就绪(ready)态。指具备运行条件,等待系统分配处理器以便运行。
|
|
|
(3)等待(wait)态。又称为阻塞(blocked)态或睡眠(sleep)态,指不具备运行条件,正在等待某个事件的完成。
|
|
|
一个进程在创建后将处于就绪状态。每个进程在执行过程中,任一时刻当且仅当处于上述三种状态之一,同时,在一个进程执行过程中,它的状态将会发生改变。下图表示进程的状态转换。
|
|
|
|
|
运行状态的进程将由于出现等待事件而进入等待状态,当等待事件结束之后等待状态的进程将进入就绪状态,而处理器的调度策略又会引起运行状态和就绪状态之间的切换。引起进程状态转换的具体原因如下:
|
|
|
运行态——等待态:等待使用资源,如等待外设传输,等待人工干预。
|
|
|
等待态——就绪态:资源得到满足,如外设传输结束,人工干预完成。
|
|
|
运行态——就绪态:运行时间片到,出现有更高优先权进程。
|
|
|
|
|
在一个实际的系统里进程的状态及其转换比上节叙述的会复杂一些,例如引入专门的新建态(new)和终止态(exit)。下图给出了进程五态模型及其转换的示意图。
|
|
|
|
|
引入新建态和终止态对于进程管理来说是非常有用的。新建态对应于进程刚刚被创建的状态。创建一个进程要通过两个步骤,首先,是为一个新进程创建必要的管理信息;然后,让该进程进入就绪态。此时进程将处于新建态,它并没有被提交执行,而是在等待操作系统完成创建进程的必要操作。必须指出的是,操作系统有时将根据系统性能或主存容量的限制推迟新建态进程的提交。
|
|
|
类似地,进程的终止也要通过两个步骤,首先,是等待操作系统进行善后;然后,退出主存。当一个进程到达了自然结束点,或是出现了无法克服的错误,或是被操作系统所终结,或是被其他有终止权的进程所终结,它将进入终止态。进入终止态的进程以后不再执行,但依然保留在操作系统中等待善后。一旦其他进程完成了对终止态进程的信息抽取之后,操作系统将删除该进程。
|
|
|
|
|
当一个程序进入计算机的主存储器进行计算就构成了进程,主存储器中的进程到底是如何组成的?操作系统中把进程物理实体和支持进程运行的环境合称为进程上下文(context)。当系统调度新进程占有处理器时,新老进程随之发生上下文切换。因此,进程的运行被认为是在上下文中执行。简单地说,一个进程映像(Process Image)包括:
|
|
|
(1)进程程序块,即被执行的程序,规定了进程一次运行应完成的功能。通常它是纯代码,作为一种系统资源可被多个进程共享。
|
|
|
(2)进程数据块,即程序运行时加工处理对象,包括全局变量、局部变量和常量等的存放区以及开辟的工作区,常常为一个进程专用。
|
|
|
(3)系统/用户堆栈,每一个进程都将捆绑一个系统/用户堆栈。用来解决过程调用或系统调用时的地址存储和参数传递。
|
|
|
(4)进程控制块,每一个进程都将捆绑一个进程控制块,用来存储进程的标志信息、现场信息和控制信息。进程创建时,建立一个PCB;进程撤销时,回收PCB,它与进程一一对应。
|
|
|
|
|
|
|
进程控制块是操作系统中最为重要的数据结构,每个进程控制块包含了操作系统管理所需的所有进程信息,进程控制块的集合事实上定义了一个操作系统的当前状态。当系统创建一个进程时,就为它建立一个PCB,当进程执行结束便回收它占用的PCB。操作系统是根据PCB来对并发执行的进程进行控制和管理的,借助于进程控制块进程才能被调度执行。
|
|
|
|
(1)标识信息。用于唯一地标识一个进程,常常分为由用户使用的外部标识符和被系统使用的内部标识号两种。
|
|
|
(2)现场信息。用于保留一个进程在运行时存放在处理器现场中的各种信息,任何一个进程在让出处理器时必须把此时的处理器现场信息保存到进程控制块中,而当该进程重新恢复运行时也应恢复处理器现场。常用的现场信息包括通用寄存器的内容、控制寄存器(如PSW寄存器)的内容、用户堆栈指针、系统堆栈指针等。
|
|
|
(3)控制信息。用于管理和调度一个进程。常用的控制信息包括:进程的调度相关信息,进程组成信息、进程间通信相关信息、进程在二级存储器内的地址、CPU资源的占用和使用信息、进程特权信息、资源清单。
|
|
|
|
在多道程序设计系统中,同一时刻可能有许多进程,这些进程之间存在两种基本关系:竞争关系和协作关系。
|
|
|
第一种是竞争关系,系统中的多个进程之间彼此无关,它们并不知道其他进程的存在。例如,批处理系统中建立的多个用户进程,分时系统中建立的多个终端进程。由于这些进程共用了一套计算机系统资源,因而,必然要出现多个进程竞争资源的问题。当多个进程竞争共享硬设备、变量、表格、链表、文件等资源时,可能导致处理出错。
|
|
|
(1)进程的互斥(Mutual Exclusion)。
|
|
|
是解决进程间竞争关系的手段。指若干个进程要使用同一共享资源时,任何时刻最多允许一个进程去使用,其他要使用该资源的进程必须等待,直到占有资源的进程释放该资源。临界区管理可以解决进程互斥问题。
|
|
|
第二种是协作关系,某些进程为完成同一任务需要分工协作。
|
|
|
(2)进程的同步(synchronization)。
|
|
|
是解决进程间协作关系的手段。指一个进程的执行依赖于另一个进程的消息,当一个进程没有得到来自于另一个进程的消息时则等待,直到消息到达才被唤醒。
|
|
|
不难看出,进程互斥关系是一种特殊的进程同步关系,即逐次使用互斥共享资源。
|
|
|
|
下面通过例子来进一步阐明进程同步的概念。著名的生产者-消费者(Producer-Consumer)问题是计算机操作系统中并发进程内在关系的一种抽象,是典型的进程同步问题。在操作系统中,生产者进程可以是计算进程、发送进程;而消费者进程可以是打印进程、接收进程等。解决好了生产者-消费者问题就解决好了一类并发进程的同步问题。
|
|
|
生产者-消费者问题表述如下:有n个生产者和m个消费者,连接在一个有k个单位缓冲区的有界缓冲上,故又叫有界缓冲问题。其中,pi和cj都是并发进程,只要缓冲区未满,生产者pi生产的产品就可投入缓冲区;类似地,只要缓冲区不空,消费者进程cj就可从缓冲区取走并消耗产品。
|
|
|
|
|
其中,假如一般的高级语言都有sleep()和wakeup()这样的系统调用。从上面的程序可以看出,算法是正确的,两进程顺序执行结果也正确。但若并发执行,就会出现错误结果,出错的根源在于进程之间共享了变量counter,对counter的访问未加限制。
|
|
|
生产者和消费者进程对counter的交替执行会使其结果不唯一。例如,counter当前值为8,如果生产者生产了一件产品,投入缓冲区,拟做conuter加1操作。同时消费者获取一个产品消费,拟做counter减1操作。假如两者交替执行加或减1操作,取决于它们的进行速度,counter的值可能是9,也可能是7,正确值应为8。
|
|
|
操作系统实现进程同步的机制称为同步机制,它通常由同步原语组成。不同的同步机制采用不同的同步方法,迄今己设计出许多同步机制,最常用的同步机制:信号量及PV,管程。
|
|
|
|
1965年荷兰的计算机科学家E.W.Dijkstra提出了新的同步工具——信号量和P、V操作。他将交通管制中多种颜色的信号灯管理交通的方法引入操作系统,让两个或多个进程通过信号量(semaphore)展开交互。信号量仅能由同步原语对其进行操作,原语是操作系统中执行时不可中断的过程,即原子操作(Atomic Action)。Dijkstra发明了两个同步原语:P操作和V操作(荷兰语中“测试(Proberen)”和“增量(verhogen)”的头字母。利用信号量和P、V操作既可以解决并发进程的竞争问题,又可以解决并发进程的协作问题。
|
|
|
使用PV操作实现同步时,对共享资源的管理分散在各个进程之中,进程能直接对共享变量进行处理,因此,难以防止有意或无意的违法同步操作,而且容易造成程序设计错误。如果能把有关共享变量的操作集中在一起,就可使并发进程之间的相互作用更为清晰,更容易编写出正确的并发程序。
|
|
|
|
在1974年和1975年,霍尔(Hoare)和汉森(Brinch Hansen)提出了一个新的同步机制——管程。把系统中的资源用数据结构抽象地表示出来,因此,对资源的管理就可用数据及在其上实施操作的若干过程来表示;对资源的申请和释放通过过程在数据结构上的操作来实现。而代表共享资源的数据及在其上操作的一组过程就构成了管程,管程被请求和释放资源的进程所调用。
|
|
|
管程是一种程序设计语言结构成分,便于用高级语言来书写,它和信号量有同等的表达能力。管程是由若干公共变量及其说明和所有访问这些变量的过程所组成的;进程可以互斥地调用这些过程;管程把分散在各个进程中互斥地访问公共变量的那些临界区集中了起来。管程可以作为语言的一个成分,采用管程作为同步机制便于用高级语言来书写程序,也便于程序正确性验证。
|
|
|
|
|
计算机系统中有许多独占资源,它们在任一时刻都只能被一个进程使用,如磁带机、键盘、绘图仪等独占型外围设备,或进程表、临界区等软件资源。两个进程同时向一台打印机输出将导致一片混乱,两个进程同时进入临界区将导致数据错误乃至程序崩溃。正因为这些原因,所有操作系统都具有授权一个进程独立访问某一资源的能力。一个进程需要使用独占资源必须通过以下的次序。
|
|
|
|
|
|
若申请时资源不可用,则申请进程等待。对于不同的独占资源,进程等待的方式是有差异的,如申请打印机资源、临界区资源时,申请失败将意味着阻塞申请进程;而申请打开文件资源时,申请失败将返回一个错误码,由申请进程等待一段时间之后重试。值得指出的是,不同的操作系统对于同一种资源采取的等待方式也是有差异的。
|
|
|
在许多应用中,一个进程需要独占访问不止一种资源。而操作系统允许多个进程并发执行共享系统资源时,此时可能会出现进程永远被阻塞的现象。例如,两个进程分别等待对方占有的一个资源,于是两者都不能执行而处于永远等待,这种现象称为“死锁”。
|
|
|
下面举一死锁的例子来加深对其理解:竞争资源产生死锁。
|
|
|
设系统有打印机、读卡机各一台,它们被进程P和Q共享。两个进程并发执行,它们按下列次序请求和释放资源。
|
|
|
|
它们执行时,相对速度无法预知,当出现进程P占用了读卡机,进程Q占用了打印机后,进程P又请求打印机,但因打印机被进程Q占用,故进程P处于等待资源状态;这时,进程Q执行,它又请求读卡机,但因读卡机被进程P占用而也只好处于等待资源状态。它们分别等待对方占用的资源,致使无法结束这种等待,产生了死锁。
|
|
|
|
|
(1)互斥条件(Mutual Exclusion)进程应互斥使用资源,任一时刻一个资源仅为一个进程独占,若另一个进程请求一个已被占用的资源时,它被置成等待状态,直到占用者释放资源。
|
|
|
(2)占有和等待条件(Hold and Wait)一个进程请求资源得不到满足而等待时,不释放已占有的资源。
|
|
|
(3)不剥夺条件(No Preemption)任一进程不能从另一进程那里抢夺资源,即已被占用的资源,只能由占用进程自己来释放。
|
|
|
(4)循环等待条件(Circular Wait)存在一个循环等待链,其中,每一个进程分别等待它前一个进程所持有的资源,造成永远等待。
|
|
|
|