操作系统复习要点 - 图文

进程的三个基本状态：运行状态（当一个进程在处理机上运行时，则称该进程处于运行状态）、就绪状态（一个进程获得了除处理机外的一切所需资源，一旦得到处理机即可运行，则称此进程处于就绪状态）、阻塞状态（一个进程正在等待某一事件发生而暂时停止运行，这时即使把处理机分配给进程也无法运行，故称该进程处于阻塞状态）（五种：+创建态、终止态）（七种：+挂起就绪、挂起阻塞）

三个基本状态之间可能转换和转换原因如下：

就绪态――＞运行态：进程调度程序按某种算法将处于就绪队列的某个进程选出，把CPU分配给它，该进程便由就绪状态转变为运行状态。

运行态――＞就绪态：处于运行状态的进程因时间片用完而被中断，将该进程的PCB表插入就绪队列，该进程便由运行状态转变为就绪状态。如果在采用抢占式调度策略的系统中，进入就绪队列的进程的优先级高于正处在运行状态的进程，可抢占CPU，将执行状态进程的PCB表插入就绪队列，由运行状态转变为就绪状态。

运行态――＞阻塞态：进程在某等待事件发生（例如I/O请求、原语P操作等）而无法执行时，会由运行状态转变为阻塞状态，在等待该事件的完成过程中将放弃CPU的使用权。

进程源语：终止（Holt、Logs off）、阻塞（block）、唤醒（wakeup）、挂起（suspend）、激活（active）

——共享资源与临界资源

共享资源：进程同步机制的主要任务，是对多个相关进程在执行次序上进行协调，使并发执行的诸进程之间能按照一定的规则（或时序）共享系统资源，并能很好的相互合作，从而使程序的执行具有可再现性。

临界资源：像打印机这类一次只允许一个进程使用的资源称为临界资源。属于临界资源的硬件有打印机，软件有变量、数组、缓冲区等。临界资源又称独享资源。

——信号量及其含义

信号量是一种特殊的变量，代表可用资源实体的数量。

信号量机制的发展：从整型信号量机制发展到记录型信号量机制，进而发展为“信号集”机制。现在信号量机制已广泛应用于OS中。

*公用信号量（互斥信号量）：它为一组需互斥共享临界资源的并发进程而设置，代表共享的临界资源，每个进程均可对它施加P、V操作，即都可申请和释放该临界资源，其初始值置为1。

*专用信号量（同步信号量）：为一组需同步协作完成任务的并发进程而设置，只有拥有该资源的进程才能对它施加P操作（即可申请资源），而由其合作进程对它施加V操作（即释放资源）

*整型信号量：用一个整型变量作为信号量(如 S)，信号量的初值表示同类临界资源的个数。设置两种基本操作PV，利用对信号量的改变达到互斥与同步的目的。

*记录型信号量机制：让p1和p2共享一个共同信号量synch，且初始化为0。

在进程p1中插入语句：

s1;

signal (synch);

在进程p2中插入语句： wait(synch); s2;

*AND型信号量：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。

引入AND信号量后，上面的例子就可以简单改写为： process A: process B: Swait(Dmutex,Emutex); Swait(Emutex,Dmetux);

??? ??? Ssignal(Dmutex,Emutex); Ssignal(Emutex,Dmutex); 这样也就不会出现死锁问题。

*信号量集：对AND信号量机制加以扩充，形成一般化的“信号量集”机制。

——P、V操作

用一个整型变量作为信号量(如 S)，信号量的初值表示同类临界资源的个数。设置两种基本操作wait(S)/P(S)和signal(S)/V(S) (P和V分别是荷兰文的“等待”和“发信号”两词的首字母) ，利用对信号量的改变达到互斥与同步的目的。当信号量被初始化后，只能为P、V操作所改变。P、V是一对同步原语，是不可中断的原子操作。

P.V操作必须成对出现，有一个P操作就一定有一个V操作； 当为互斥操作时，它们同处于同一进程； 当为同步操作时，则不在同一进程中出现； 如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要,一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前；

两个V操作顺序无关紧要。 ——进程的互斥与同步

互斥：这是指诸进程(线程)在对临界资源进行访问时，应采用互斥方式

同步：这是指在相互合作去完成共同任务的诸进程(线程)间，由同步机构对它们的执行次序加以协调。

进程同步和互斥的区别：

互斥的各个进程在各自单独执行时都可以得到正确的运行结果，但是当它们在临界区内交叉执行时就可能出现问题。 而同步的各个进程，如果各自单独执行将不会完成作业的特定任务，只要当它们互相配合、共同协调推进时才能得到正确的运行结果。

互斥的进程只要求它们不能同时进入临界区，而至于哪个进程先进入则不会产生运行的错误。但同步的进程的协调关系是建立在它们之间执行时序的基础上，所以，各个进程必须按照严格的先后次序执行。

一般情况下，互斥的进程并不知道对方的存在，而同步的进程不仅知道其它进程的存在，还要通过与其它进程的通信来达到相互的协调。

——写程序完成互斥、同步操作

互斥1：夫妻两人的共同存款，保存在count(共享资源)变量中。

semaphore S=1; int count; 进程p1： { int R1; P(S); R1∶=count; R1∶=R1+1; count∶=R1; V(S) }

进程 P2： { int R1; P(S);

R1∶=count; R1∶=R1+1; count∶=R1; V(S) }

互斥2：设一民航航班售票系统有n个售票处。每个售票处通过终端访问系统中的公用数据区，假定公共数据区中一些单元xk(k=1, 2, ?)分别存放×月×日×次航班的现存票数。设P1，P2， ?，Pn表示各售票处的处理进程，R1, R2, ?, Rn表示各进程执行时所用的工作单元。用信号量实现进程间互斥的程序如下：

Semaphore S=1; 进程 Pi (i=1, 2, ?, n) { 按旅客订票要求找到xk; P(S) Ri =xk;

if (Ri>=1) { Ri=Ri-1; xk=Ri; V(S); 输出一张票; }

else { V(S); 输出“票已售完”;} }

同步1：用信号量实现司机和售票员的同步。 (1) 确定同步的规则

根据一般常识，司机和售票员在车上的操作规则如下： 1) 售票员操作的规则是只有司机停车后，售票员才能开门 让乘客上下车；

2) 司机操作的规则是只有售票员关门后，司机才能启动开 始行驶汽车。 （2）进程的操作流程 售票员进程 do while

关车门；

设立车门已关标志; 售票；

是否停车？没停则等待; 开车门； 上下乘客； enddo

司机进程 do while

是否关门？没关则等待; 启动车辆； 正常行车； 到站停车； 设立车停标志; enddo

(3) 确定信号量的个数和含义

根据同步规则以及操作流程确定信号量的个数是2个,S1和S2。 S1的含义是否关门； S2的含义是否停车。

(4)确定信号量的初值(假设正处于停车状态) S1=0； S2=1。

(5)确定P、V操作的位置

1）司机操作中，是否关门？没关则等待，这是一个P操作， P(S1)；

2）司机操作中，设立停车标志，这是一个V操作，V(S2)； 3）售票员操作中，是否停车？没停则等待，这是一个P操作 ，P(S2)；

4）售票员操作中，设立关门标志，这是一个V 操作，V(S1)

(6) P、V操作实现 int S1=0， S2=1; main() {

cobegin

driver(); busserver(); coend }

driver()

{ do while T { P(S1)；

启动车辆；