自考操作系统原理第七章进程同步与进程通信

进程同步与进程通信进程的顺序性进程的顺序性是指进程在顺序处理器上的执行是严格按序的，即按照程序规定的操作顺序，只有在前一个操作结束后才能开始后继操作。当一个进程独占处理器时，它具有两个特性：封闭性可再现性进程的并发性每一个进程具有顺序性，但是在多道程序设计系统中，多个进程要竞争，轮流占用处理器。有两个进程A和B，它们各自顺序执行时的操作序列如下：进程A：a1，a2，a3，…，am进程B：b1，b2，b3，…，bm在多道程序设计系统中，处理器可能执行的操作序列a1，b1，a2，b2，a3，b3…a1，a2，b1，a3，b2，b3…进程的并发性在一个进程的工作没有完成之前，另一个进程就可以开始工作，这些进程就称为可同时执行的。或者称它们具有并发性，并且把可同时执行的进程称为并发进程。进程的并发性如果一个进程的执行不影响另一个进程的执行结果，也不依赖一个进程的进展情况，即它们是各自独立的，则称这些进程相互之间是无关的。如果一个进程的执行要依赖其他进程的进展状况，或者可能会影响其他进程的执行结果，则说这些进程是有交互的。与时间有关的错误对于有交互的并发进程来说，并发会破坏“封闭性”和“可再现性”例1：车辆自动计数系统processObserverbeginL1:observealorry;count:=count+1;gotoL1;end;processReporterbeginprintcount;count:=0;end;系统功能：统计每小时的卡车流量观察者进程(Observer)：观察到一辆卡车，计数器+1报告者进程(Reporter)：每隔1小时，将计数值输出，计数器清零例2：航班售票系统processPi(i=1,2,…)beginRi:=Ak;ifRi=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;Ak代表某天某次航班的剩余票数；Pi代表售票处理进程；Ri是每个售票进程的私有变量；各个售票处进程的工作如左边代码所示：processP2beginRi:=Ak;ifRi=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;processP3beginRi:=Ak;ifRi=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;Ri=5假设某时刻Ak为5，A、B两个人同时在2号3号窗口买票processP2beginRi:=Ak;ifRi=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;processP3beginRi:=Ak;ifRi=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;Ri=5假设某时刻Ak为5，A、B两个人同时在2号3号窗口买票processP3beginRi:=Ak;ifRi=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;processP2beginRi:=Ak;ifRi=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;Ri=5假设某时刻Ak为5，A、B两个人同时在2号3号窗口买票processP2beginRi:=Ak;ifRi=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;processP3beginRi:=Ak;ifRi=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;Ri=5假设某时刻Ak为5，A、B两个人同时在2号3号窗口买票processP3beginRi:=Ak;ifRi=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;processP2beginRi:=Ak;ifRi=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;Ri=4假设某时刻Ak为5，A、B两个人同时在2号3号窗口买票processP2beginRi:=Ak;ifRi=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;processP3beginRi:=Ak;ifRi=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;Ak=4假设某时刻Ak为5，A、B两个人同时在2号3号窗口买票processP2beginRi:=Ak;ifRi=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;processP3beginRi:=Ak;ifRi=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;Ri=4假设某时刻Ak为5，A、B两个人同时在2号3号窗口买票processP3beginRi:=Ak;ifRi=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;processP2beginRi:=Ak;ifRi=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;Ak=4假设某时刻Ak为5，A、B两个人同时在2号3号窗口买票processP3beginRi:=Ak;ifRi=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;processP2beginRi:=Ak;ifRi=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;假设某时刻Ak为1，两个窗口同时卖票，可能出现什么情况？与时间有关的错误由于进程交替修改了共享变量造成结果可能不正确。造成不正确的因素与进程占据处理器的时间、执行速度以及外界的影响（卡车），这些因素都与时间有关，所以称为与时间有关的错误。临界区有交互的并发进程执行时出现与时间有关的错误，其根本原因是对共享资源（变量）的使用不受限，为了使并发进程能正确地执行，必须对共享变量的使用加以限制。processObserverbeginL1:observealorry;count:=count+1;gotoL1;end;临界区processReporterbeginprintcount;count:=0;end;把并发进程中与共享变量有关的程序段称为临界区。涉及相同共享变量的临界区称为相关临界区。临界区processPi(i=1,2…)beginRi:=Ak;ifRi=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;如果能保证一个进程在临界区执行时，不让另一个进程进入相关的临界区执行，即各进程对共享变量的访问是互斥的，就不会造成与时间有关的错误。临界区(1)当无进程在临界区时，若有进程要进入，则允许一个进程进入临界区(2)当有进程在临界区执行时，其他试图进入临界区的进程必须等待(3)当有一个进程离开临界区，若有等待进入临界区的进程，则允许一个进程进入它的临界区信号量机制（Semaphores）1965年，荷兰的E.W.Dijkstra(狄克斯特拉)提出了信号量同步机制。用于进程同步广泛应用于存在临界资源和临界区控制的场合信号量的概念信号量S是一个整数S≥0可供并发进程使用的资源实体数0绝对值表示等待使用资源的进程数PV操作对信号量的操作只能由P、V操作来进行，即：信号量数值的改变只能由P、V操作完成PV操作由P操作和V操作组成，也称P操作原语和V操作原语。P操作P(S):将信号量S减1，若结果小于0，则把调用P(S)的进程设置成等待信号量S的状态ProcedureP(VarS:Semaphore);beginS:=S-1;ifS0thenW(s)end;{P}W(s)表示把调用P(S)的进程设置成等待信号量S的状态V(S):将信号量S加1，若不大于0(小于等于0)，则释放一个等待信号量S的进程。ProcedureV(VarS:Semaphore);beginS:=S+1;ifS=0thenR(s)end;{V}V操作R(s)表示释放一个等待信号量S的进程进程的互斥进程的互斥是指有若干进程都要使用某一共享资源时，任何时刻最多只允许一个进程去使用该资源，其他要使用的进程必须等待，直到该资源的占用者释放了该资源。beginS:semaphore;S:=1;cobegin:processPi（i=1,2,3…）beginP(S);{临界区Ci（访问共享资源的代码）}V(S);end;coend:end;假设有n个进程P1，P2，P3..Pn共享某一资源,任意时刻只允许一个进程访问该资源，它们各自的临界区分别为C1，C2…Cn。begincount:integer;count:=0;S:semaphore;S:=1;cobegin:processObserverbeginL1:observealorry;P(S);count:=count+1;V(S);gotoL1;end;processReporterbeginP(S);printcount;count:=0;V(S);end;coend:end;beginS:semaphore;S:=1;cobegin:processPi(i=1,2,3…)beginP(S);Ri:=Ak;ifRi=1thenbeginRi:=Ri-1;Ak=RiV(S);输出一张票；end;elsebeginV(S);输出”票已售完“end;coend:end;读者/写者问题计算机中，把可供多个进程使用的文件称为共享文件。想读文件的进程称为读进程，写文件的进程称为写进程。不允许多个进程同时使用共享文件beginS:semaphore;S:=1;cobeginprocessReaderi(i=1,2,3…)beginP(S);readfileF;V(S);end;processWriterj(j=1,2,3…)beginP(S);writefileF;V(S);end;coend:end;P22612有4个并发执行的进程A，B，C，D,它们在执行时都要读共享文件F。限定：不允许进程A和进程B同时读文件F，不允许进程C和进程D同时读文件F。写出用PV操作管理时四个进程的程序。beginS1,S2:semaphore;S1:=1;S2:=1;cobeginprocessAbeginP(S1);readfileF;V(S1);end;processBbeginP(S1);readfileF;V(S1);end;coend:end;processDbeginP(S2);readfileF;V(S2);end;processCbeginP(S2);readfileF;V(S2);end;某系统允许最多10个进程同时读文件F，当同时读文件F的进程不满10个时，欲读该文件的其他进程可立即读，当已有10个进程在读文件F时其他欲读文件F的进程必须等待，直至有进程读完后退出方可去读,写出进程并发执行时的程序。beginS：semaphore;S:=10;cobeginprocessReaderi(i=1,2,3…)beginP(S);readfileF;V(s);end;coend:end;允许多个进程同时使用共享文件要求：(1)多个进程可以同时读文件F(2)任何一个进程在对文件F进行写时，不允许其他进程读或写(3)有进程在读文件F时，不允许任何进程去写PV操作的实现思路：processWriteri(i=1,2,3)beginP