大工20秋《操作系统》辅导资料七

易百网

操作系统辅导资料七主    题：第六章的辅导资料
学习时间：2020年11月9日--11月15日 “不忘初心、牢记使命”主题理论学习：
忠诚是共产党人必须具备的优秀品格。“忠诚印寸心，浩然充两间”的坚毅，“砍头不要紧，只要主义真”的无畏，腹中满是草根而宁死不屈的气节，食指钉入竹签而永不叛党的坚贞，无数先烈用鲜血诠释了对党的忠诚。对党忠诚必须是纯粹的、无条件的，是政治标准、更是实践标准，鲜明体现在坚决贯彻党中央决策部署上。
摘选自《在第十九届中央纪律检查委员会第二次全体会议上的讲话》内    容：第六章
这周我们将学习课件第六章。本章的学习要求及需要掌握的重点内容如下：
1．掌握进程的互斥与同步重点掌握内容：
1．重点：进程的互斥与同步。
2．难点：进程的互斥与同步。
进程的互斥与同步（一）
课前问题
进程之间的制约关系有哪些？
什么是临界区？
实现进程互斥的硬件方法有哪些？
实现进程互斥的软件方法有哪些？1.进程之间的制约关系
（1）间接相互制约关系
指同处于一个系统中的诸进程，由于共享资源而产生的相互制约关系。例如，有两个并发执行的进程P1和P2，如果在进程P1提出打印请求时，系统已将唯一的打印机分配给了进程P2，则进程P1只能阻塞等待，直到P2进程释放了打印机，P1进程才被唤醒。像打印机这种在一段时间内只能由一个进程使用的资源称为临界资源。并发诸进程对临界资源的共享导致进程之间出现了间接相互制约关系。间接相互制约关系的存在使得并发诸进程不能同时访问临界资源，只有其他进程没有占用临界资源时，当前进程才能访问，即进程访问临界资源必须以互斥方式进行。
（2）直接相互制约关系
指并发诸进程因相互合作完成同一任务而产生的相互制约关系。例如，为了提高运行效率，系统为一个应用程序分别建立了输入进程PI、计算进程PC和输出进程PO。PI通过缓冲区A向PC提供数据，PO从缓冲区B中接收PC的计算结果并输出。若缓冲区A空，则PC因不能获得输入数据只能将自己阻塞起来等待，当PI将数据输进缓冲区A后，再将PC唤醒进行计算；与之类似，若缓冲区B空，则PO因不能获得输出数据只能将自己阻塞起来等待，当PC将数据输进缓冲区B后，再将PO唤醒进行输出。相互合作进程之间存在的直接相互制约关系导致了必须采用进程同步方法，对诸进程的执行顺序进行协调，使进程的运行结果具有可再现性。
进程同步与进程互斥关系
进程同步：就是对并发诸进程的执行顺序进行协调，使进程的执行结果具有可再现性；
进程互斥：则指并发诸进程必须以互斥方式访问临界资源。
进程互斥关系实际上是一种特殊的进程同步关系，即对诸进程访问临界资源的次序进行协调。并发诸进程之间若不进行同步，将出现严重后果。
例题：
/
（1）P1→P2或P2→P1，即进程顺序执行。两种方式的执行结果相同，count变成1050。
（2）P1:S1→P2→P1:S2→P1:S3，即先执行P1中的S1语句，再执行P2，最后执行P1中剩余的语句。执行结果是count变成1100。
（3）P2:S1→P1→P2:S2→P2:S3，即先执行P2中的S1语句，再执行P1，最后执行P2中剩余的语句。执行结果是count变成950。
2.临界区
对临界资源，无论是硬件临界资源，还是软件临界资源，并发诸进程必须以互斥方式进行访问。若将访问临界资源的那段代码称为临界区，显然，只要能保证诸进程以互斥方式进入自己的临界区，就能实现并发诸进程对临界资源的互斥访问。
/
在进入临界区之前进行检查的那段代码可以称为“进入区”，而将临界资源正在被访问的标志恢复为临界资源未被访问的标志那段代码可以称为“退出区”。
进程访问临界区应遵循以下原则：
（1）空闲让进
（2）忙则等待
（3）有限等待
（4）让权等待3.实现进程互斥的硬件方法
所谓采用硬件方法实现进程互斥就是通过使用计算机提供的一些机器指令来实现进程互斥。实现进程互斥本质上是实现临界区互斥，而实现临界区互斥的关键是正确设置进入区和退出区。机器指令本身在一个指令周期内执行，且不能被中断，因此，只要采用它正确地设置了进入区和退出区，就能够实现临界区互斥。
实现进程互斥的机器指令有以下三个：
1.开关中断指令
2.测试与设置指令
3.交换指令4. 实现进程互斥的软件方法
两标志算法
算法思想：为希望访问临界资源的两个并发进程设置两个标志T1和T2，以表示进程是否在临界区；若Ti（i=1,2）等于0，则表示进程Pi（i=1,2）没有在临界区；若Ti（i=1,2）等于1，则表示进程Pi（i=1,2）在临界区；在每个进程进入临界区之前，先判断临界区是否已被另一进程访问，若是，则本进程等待，否则，本进程进入临界区。
三标志法
算法基本思想是：设置三个标志T1、T2、T，其中T1和T2的作用与两标志法相同，而T是一个公共标志，用来表示允许进入临界区的进程标号；若进程希望进入临界区，则先设置自己的标志Ti（i=1,2），然后再检测公共标志T，若T等于Ti（i=1,2），则表示允许进程Pi（i=1,2）进入临界区。Peterson算法较好解决了当两个进程同时到达时，进程互斥使用临界区问题。进程的互斥与同步（二）
课前问题
什么是信号量？
如何使用信号量实现进程互斥？
如何使用信号量实现进程同步？信号量机制在1965年提出，该方法使用信号量及有关的P、V操作原语来解决进程的互斥与同步问题。
在操作系统中，信号量代表了一类物理资源，它是相应物理资源的抽象。具体实现时，信号量被定义成具有某种类型的变量，通常的类型有整型类型和结构体类型。具有整型类型的信号量称为整型信号量；具有结构体类型的信号量称为结构型信号量或记录型信号量。信号量除了初始化以外，在其他情况下其值只能由P和V两个原语操作才能改变。P操作和V操作又称为wait操作和signal操作。
1. 整型信号量
将信号量定义为一个整型变量。若信号量是S，则P操作原语和V操作原语可以分别描述如下：
              int S;
              P(S):  while( S<=0 );
                        S = S - 1;
              V(S):  S = S + 1;
整型信号量机制中的P操作，只要信号量S小于等于0；就会不断循环测试，因此，该机制没有遵循“让权等待”原则，而使进程处于“忙等”状态。针对这种情况，人们对整型信号量机制进行了扩充，增加了一个阻塞进程队列，从而出现了结构型信号量。
2．结构型信号量
结构型信号量又称为记录型信号量。该信号量被定义成具有两个分量的结构体型数据结构。结构型信号量中的一个分量是一个整型变量，代表相应资源当前空闲的数量；另一个分量是一个队列指针，指向因等待对应资源而阻塞的进程队列。
        结构型信号量描述为：
         typedef struct {
               int value;   
               struct pcb * L;
// L指向因等待相应资源而阻塞的进程队列，pcb为 PCB对应的结构体类型
               }semaphore;
              semaphore S;  
S.L是一个指针，指向因等待相应资源而阻塞的进程队列的队首。S.value的初值是一个非负整数，代表系统中某种资源的数量。
随着该资源被不断分配，S.value的值将发生变化，对应出现以下几种情况：
（1）当S.value大于0时S.value表示该资源当前空闲的数量；
（2）当S.value等于0时S.value表示该资源正好用完。
（3）当S.value小于0时S.value表示因等待该资源而阻塞的进程数量。若S.value的初值为１，则表示只有一个临界资源，一段时间内只允许一个进程对该资源进行访问。这种情况下的结构型信号量又称为互斥信号量。
     P(S)原语操作可以用以下函数描述：
          void P( semaphore &S )
           {  S.value = S.value - 1;
             if( S.value < 0 )block( S.L );  // block是阻塞原语
            }
P(S)操作的物理含义是：执行一次P(S)操作相当于申请一个资源；若S.value大于0，则S.value减1表示该资源当前空闲的数量减少了１个；若S.value减１后小于０，则立即调用阻塞原语block将本进程阻塞起来，并插入到S.L指针指向的阻塞进程队列中，这时因等待该资源而阻塞的进程又多了一个。结构型信号量机制采用了“让权等待”策略。
V(S) 原语操作的功能通过函数如下：
             void V( semaphore &S )
              {  S.value = S.value + 1;
                if( S.value <＝ 0 ) wakeup( S.L );  　/ wakeup是唤醒原语
              }
V(S)操作的物理含义是：执行一次V(S)操作相当于释放一个资源，于是执行S.value加１操作；若S.value加１后的值仍然小于或等于０，表明仍有处于阻塞状态的进程在等待这类资源，于是调用唤醒原语wakeup将阻塞队列（S.L）的第一个等待进程唤醒，并移入就绪队列。
3．使用信号量实现进程互斥
为临界资源设置一个互斥信号量（即value初值为1的结构型信号量）mutex，然后将各进程的临界区置在P(mutex)和V(mutex)之间。程序模型如下：
          semaphore  mutex;
          mutex.value = 1;
           cobegin                  
// 伪代码cobegin和coend表示夹在它们之间的进程可以并发执行
            process Pi( )         // i=1,2,…,n
             {  ……
                P(mutex);
                临界区;
                V(mutex);
                  ……  
                }
             coend
注意：P(mutex)和V(mutex)操作必须成对出现；缺少P操作将会导致系统混乱，对临界资源进行互斥访问将得不到保证；缺少V操作将会使临界资源永远不会被释放，且导致因等待该资源而阻塞的进程不再被唤醒。
4．使用信号量实现进程同步
在需要同步的地方插入对信号量的P操作或V操作，可以实现进程间同步。
有两个并发执行的进程P1和P2，P1：x=5;y=x+5；P2中语句：z=y+10；显然只有执行了y=x+5这条语句后，才能执行语句z=y+10。设置一个由两个进程共享的信号量S，初值赋为0，再将P(S)操作放在z=y+10前面，将V(S)操作放在y=x+5语句后面。描述如下：
                                                          由于S被初始化为0，所以P2进程执行到P(S)原语处必定受阻塞。只有进程P1执行完y =x+5语句，并进行V(S)操作使S增1后，P2进程方能执行语句z=y+10。
由于S被初始化为0，所以P2进程执行到P(S)原语处必定受阻塞。只有进程P1执行完y =x+5语句，并进行V(S)操作使S增1后，P2进程方能执行语句z=y+10。进程的互斥与同步（三）
课前问题：
生产者——消费者问题
哲学家进餐问题
读者——写者问题
理发店问题生产者——消费者问题
/
生产者进程和消费者进程以异步方式运行，但它们之间必须保持同步
不允许消费者进程到一个空缓冲区中取产品
不允许生产者进程将产品投放到一个已装满产品的缓冲区。
item B[n];           // item表示缓冲区的类型，数组B模拟具有n个缓冲区的缓冲池
semaphore mutex, empty, full;
mutex.value = 1; empty.value = n; full.value = 0;
int in = 0;    // 缓冲区指针，指向当前可投放产品的缓冲区
int out = 0;   // 缓冲区指针，指向当前可取走产品的缓冲区
item product;  // product代表一个产品
/程序中的函数produce( )和consume( )分别表示生产和消费产品。哲学家进餐问题
/
筷子为临界资源，在一段时间内只允许一位哲学家使用
每支筷子设置一个互斥信号量，其初值均为1
/
此解法有可能引起死锁。例如，若每个哲学家各拿了1支左边（或右边）筷子，则再去拿右边（或左边）筷子时就会出现死锁。可以采用以下方法之一来预防出现死锁：
（1）最多允许4位哲学家同时拿左边（或右边）的筷子。
（2）仅当哲学家的左、右两支筷子均可用时，才允许他拿起筷子吃饭。
（3）奇数号哲学家先取左边筷子，然后再取右边的筷子；而偶数号哲学家先取右边筷子，然后再取左边的筷子。读者——写者问题
/
（1）允许多个读者进程同时读文件。
（2）不允许写者进程与其他进程同时访问文件。
Readcount记录正在读文件的进程数目
设置一个互斥信号量rmutex来保证对Readcount进行互斥访问
设置一个信号量wmutex来保证这种访问的互斥性，用来判断是否允许读或是否允许写。
semaphore rmutex, wmutex;
rmutex.value = 1; wmutex.value = 1;
int Readcount = 0;
/理发店问题
/
解决这个问题需要设置三个信号量和一个共享变量。共享变量count用来记录当前坐在沙发上等候的顾客数，初值为0。注意：坐在沙发上等候的顾客不一定全都要理发。信号量barbers用来记录当前空闲的理发师数，初值为k；信号量customers用来记录当前等待理发的顾客数，初值为0；信号量mutex用来实现对共享变量count的互斥访问，初值为1。
在理发师进程中，首先通过P(customers)原语判断是否有顾客需要理发，若无，则进程将自己阻塞起来等待，若有，则将count减1（由于一个顾客去理发，所以在沙发上等待的顾客减少了一个）；当理发师给顾客理完发后，空闲的理发师又增加了一个，于是执行V(barbers)操作，该操作还将因等待理发师而阻塞的第一个顾客进程唤醒（若它存在的话）；P(mutex)和 V(mutex)原语用来保证以互斥方式访问共享变量count。
在顾客进程中，首先判断是否有空闲的沙发，若无，新到顾客离开理发店，若有，新顾客坐到沙发上等待，于是执行count++操作；新顾客到来后，需要理发的顾客又增加了一个，于是执行V(customers)操作，该操作还将因等待顾客而阻塞的第一个理发师进程唤醒（若它存在的话）；由于有顾客需要理发，于是通过P(barbers)判断是否有空闲的理发师，若无，则进程将自己阻塞起来等待，若有，则请他给顾客理发。P(mutex)和 V(mutex)原语同样用来保证以互斥方式访问共享变量count。
/重要考点
一、名词解释汇总
1.临界区：将访问临界资源的代码段称为临界区。
2.临界区的进入区：在进入临界区之前进行检查的那段代码可以称为“进入区”。
3.临界区的退出区：将临界资源正在被访问的标志恢复为临界资源未被访问的标志那段代码可以称为“退出区”。
二、单项选择题1.若PV操作的信号量S初值为2，当前值为-1，则表示有（     ）等待进程。
A．0个
B．1个
C．2个
D．3个
答： B
分析：当S.value大于0时， S.value表示该资源当前空闲的数量；
当S.value小于0时， S.value表示因等待该资源而阻塞的进程数量。
本内容由易百教育整理发布
网址www.openhelp100.com
QQ 515224986