【第四章 | 进程同步】《操作系统慕课版》课后答案 + 复习

「爱情、让人受尽委屈。」 2023-09-28 11:29 127阅读 0赞

#### 文章目录 ####

*  【第四章】进程同步
 *   *  | 本章概念
     *   *  1.进程同步相关概念
         *  2.软件同步机制
         *  3.硬件同步机制
         *  4.信号量机制
         *  5.管程机制（了解）
     *  | 本章算法
     *   *  1.生产者-消费者 进程同步问题
         *  2.读者-写者 进程同步问题
         *  3.信号量与进程数的关系
     *  | 课后简答题

--------------------

## 【第四章】进程同步 ##

### | 本章概念 ###

#### 1.进程同步相关概念 ####

*  进程同步的目的：使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性
 *  进程间的制约关系：互斥关系（进程互斥使用临界资源）、同步关系（进程间相互合作）
 *  临界资源：一次只允许一个 进程使用，称这样的资源为临界 资源或互斥资源或共享变量。进程间应采取互斥方式，实现对临界资源的共享。
 *  进入区：用于检查是否可以进入临界区的代码段
    
    临界区：进程中涉及临界资源的代码段；
    
    退出区：将临界区正被访问的标志恢复为未被访问标志。
    
    剩余区：其它代码

item nextConsumed;
    while (1) {
    	//进入区
    	while (counter == 0)
    	 	/* do nothing */
    	nextConsumed = buffer[out];
    	out = (out + 1) % BUFFER_SIZE;
    	counter--; //临界区
    	//退出区
    	break;
    	//其它区
    }

*  解决临界区问题的同步机制，需要遵循下列4条准则：空闲让进、忙则等待、有限等待、让权等待（当进程不能进入自己的临界区时，应该立即释放处理机，避免进程陷入忙等）
 *  进程同步的机制有：软件同步机制、硬件同步机制、信号量机制、管程机制

--------------------

#### 2.软件同步机制 ####

*  使用编程方法解决临界区问题，有难度、具有局限性，现在很少采用
 *  介绍一种重要的软件同步机制算法 —— Peterson算法
    
    算法思想：如果双方都想进入临界区，可以尝试让进程“孔融让梨”，主动让对方先使用临界区

//共享变量
    bool flag[2];  //数组，下标对应进程号，元素表示对应下标的进程有无进入临界区的意愿
    int turn = 0;  //若在P1中 turn=0，则表示若P0想进入临界区，P1愿意让P0插队进入临界区；若在P0中 turn=1，则表示若P1想进入，P0愿意让P1插队进入临界区
    
    
    //P0进程
    //【进入区】
    flag[0] = true; //P0想进入临界区，则flag[0]表示为true
    turn = 1;  //P0进入临界区的时候若P1也想进，则turn=1表示P0愿意给P1插队
    while(flag[1] && turn==1); //若P1正在占用临界区（flag[1]==true）或者 P1不愿意让P0插队，则P0进入就绪状态，等待P1用完临界资源
    critical section;  //【临界区】
    flag[0] = false; //【退出区】使用完临界资源，则想进入临界区改为false
    ramainder section;  //【剩余区】
    
    
    //P1进程
    flag[1] = true;
    turn = 0;
    while(flag[0] && turn==0);
    critical section;
    flag[1] = false;
    remainder section;

--------------------

#### 3.硬件同步机制 ####

*  缺点：不符合“让权等待”原则，浪费CPU时间。很难解决复杂的同步问题
 *  关中断：
    
     *  进入锁测试之前关闭中断，完成锁测试并上锁之后才打开中断（与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也不能发生进程切换，进而不可能发生两个进程同时访问临界区的情况）
     *  优点：简单、高效
     *  缺点：不适用于多处理机，只适用于操作系统内核进程，不适用于用户进程（因为开 / 关中断指令只运行在内核态，这组指令如果能让用户用会很危险）
 *  互斥锁：
    
     *  设临界区的类名为S。为了保证每一次临界区中只能有一个程序段被执行， 又设锁定位 key\[S\]。key\[S\] 表示该锁定位属于类名为S的临界区。
     *  key\[S\]=1时表示类名为Ｓ的临界区可用， 位 key\[S\]=0时表示类名为Ｓ的临界区不可用。
 *  TestAndSet 指令：是一种借助一条硬件指令——“测试并建立”指令TS(Test-andSet)以实现互斥的方法。在许多计算机中都提供了这种指令

//lock表示当前临界区是否被加锁，true加了，false没加
    bool TestAndSet (bool *lock){
        
    	bool old = *lock;
    	*lock = true;
    	return old;
    }
    
    //进程Pi
    while(TestAndSet(&lock));
    //临界区代码
    .....
    lock = false; //解锁
    //剩余区代码
    .....

*  Swap指令：用硬件实现的，执行过程中不允许被中断，只能一气呵成

//Swap 指令的作用是交换两个变量的值
    Swap (bool *a , bool *b){
        
    	bool temp;
    	temp = *a;
    	*a = *b;
    	*b = temp;
    }
    
    //进程Pi
    do{
        
    	key = true;
    	do{
        
    		Swap(lock,key);
    	}while(key != false)
    	//临界区代码
    	......
    	lock = false;
    	//剩余区代码
    	......
    }while(true)

--------------------

#### 4.信号量机制 ####

*  软件同步机制和硬件同步机制，都无法实现“让权等待”
 *  原语：只能一气呵成，不能被中断。原语是由关中断 / 开中断指令实现的。因此若能把进入区、退出区的操作用原语来实现，则可避免同时访问临界区的问题
 *  wait(S) 原语和 Signal(S) 原语，可以理解为一个名为wait / signal的方法（函数），S即为我们传入的参数——信号量。
 *  PV操作：
    
     *  常常把 wait(S) 写成 P操作，Signal(S) 写成V操作。即：Wait(s)又称为P(S)，为进入操作；Signal(s)又称为V(S)，V为退出操作
     *  P.V操作必须成对出现，有一个P操作就一 定有一个V操作
     *  当为互斥操作时，它们同处于同一进程；当为同步操作时，则不在同一进程中出现
 *  信号量机制缺点：同步操作分散、易读性差、不利于修改和维护、正确性难以保证

下面介绍一些常见信号量：

*  整型信号量：S为整型变量。缺点：进程忙等

wait(S)：
    	while s<=0 ; /*do no-op*/
    	s:=s-1;
    	
    signal(S)：
    	s:=s+1;

*  记录型信号量：去除忙等的信号量
    
     *  每个信号量S除一个整数值S.value外，还有一个进程等待队列S.list，存放阻塞在该信号量的各个进程PCB
     *  信号量只能通过初始化和两个标准的原语PV来访问，作为OS核心代码执行，不受进程调度的打断
     *  初始化指定一个非负整数值，表示空闲资源总数（又称为"资源信号量"），若为非负值表示当前的空闲资源数，若为负值其绝对值表示当前等待临界区的进程数

wait(semaphores *S) {
         //请求一个单位的资源
    	S->value --; //资源减少一个
    	if (S->value<0) block(S->list) //进程自我阻塞
    }
    signal(semaphores *S) //释放一个单位资源
    {
        
    	S->value++; //资源增加一个
    	if (S->value<=0) wakeup(S->list); //唤醒等待队列中的一个进程
    }

*  AND型信号量：
    
     *  基本思想：将进程在整个运行过程中需要的所有 资源，一次性全部分配给进程，待进程使用完后再一起释放。
     *  对若干个临界资源的分配，采用原子操作。
     *  在wait(S)操作中增加了一个“AND”条件，故称之为AND同步

Swait(S1，S2，…，Sn) {
        
    		while (TRUE) {
        
    			if (Si>=1 && … && Sn>=1) {
        
    				for (i =1;i<=n;i++) Si--){
        
    					break;
    				}
    			}
    		}
    	}
    	else {
        
           //......
    	}
    }}

信号量集——扩充AND信号量：对进程所申请的所有资源以及每类资源不同的资源需求量，在 一次P、V原语操作中完成申请或释放

*  信号量的应用：信号量必须置一次且只能置一次初值，初值不能为负数；除了初始化，只能通过执行P、V操作来访问信号量
    
     *  利用信号量实现进程互斥：设置互斥信号量
     *  利用信号量实现前趋关系
     *  利用信号量实现进程同步：设置同步信号量

//信号量实现互斥
    semaphore mutex; 
    mutex=1; // 初始化为1
    while(1)
    {
        
    	wait(mutex);
    	临界区；
    	signal(mutex);
    	剩余区；
    }

//信号量实现进程同步
    P1(){
        
    	C1;
    	signal(s);
    	…
    }
    
    P2(){
        
    	…
    	wait(s); 
    	C2;
    }

#### 5.管程机制（了解） ####

*  由编程语言解决同步互斥问题
 *  一个管程定义了一个数据结构和能为并发进程所执行（在该 数据结构上）的一组操作
 *  管程的功能：互斥（管程中的变量只能被管 程中的操作访问、任何时候只有一个进程在管程中操作、类似临界区、由编译器完成）、同步

--------------------

### | 本章算法 ###

#### 1.生产者-消费者 进程同步问题 ####

*  需要注意的地方
    
     *  用于实现互斥的wait(mutex)和signal(mutex)必须成对出现
     *  每个程序中的多个wait操作的顺序不能颠倒，应先执行对资源信号量的wait操作，再执行对互斥信号量的wait操作，否则可能会引起进程死锁。
 *  具体代码与实现，请参考：https://blog.csdn.net/liushall/article/details/81569609

//生产者-消费者 伪代码
    
    var items = 0, space = 10, mutex = 1;
    var in = 0, out = 0;
    item buf[10] = {
         NULL };
    
    producer {
        
        while( true ) {
        
            wait( space );  // 等待缓冲区有空闲位置， 在使用PV操作时，条件变量需要在互斥锁之前
            wait( mutex );  // 保证在product时不会有其他线程访问缓冲区
    
            // product
            buf.push( item, in );  // 将新资源放到buf[in]位置 
            in = ( in + 1 ) % 10;
            
            signal( mutex );  // 唤醒的顺序可以不同
            signal( items );  // 通知consumer缓冲区有资源可以取走
        }
    }
    
    consumer {
        
        while( true ) {
        
            wait( items );  // 等待缓冲区有资源可以使用
            wait( mutex );  // 保证在consume时不会有其他线程访问缓冲区
    
            // consume
            buf.pop( out );  // 将buf[out]位置的的资源取走
            out = ( out + 1 ) % 10;
    
            signal( mutex );  // 唤醒的顺序可以不同
            signal( space );  // 通知缓冲区有空闲位置
        }
    }

--------------------

#### 2.读者-写者 进程同步问题 ####

*  有两组并发进程：读者和写者， 共享一组数据区
 *  要求：允许多个读者同时执行读操作；不允许读者、写者同时操作；不允许多个写者同时操作。
 *  分类：读者优先(第一类 读者写者问题) ；写者优先(第二类 读者写者问题)
 *  具体代码与实现，请参考：https://blog.csdn.net/qq\_35235032/article/details/106652964?spm=1001.2101.3001.6661.1&utm\_medium=distribute.pc\_relevant\_t0.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-1-106652964-blog-104970354.pc\_relevant\_multi\_platform\_whitelistv1&depth\_1-utm\_source=distribute.pc\_relevant\_t0.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-1-106652964-blog-104970354.pc\_relevant\_multi\_platform\_whitelistv1&utm\_relevant\_index=1

//读者优先（伪代码）
    
    // 互斥读者与读者
    semaphore rmutex = 1;
    // 互斥读者与写者，写者与写者
    semaphore mutex = 1;
    // 表示读者数量，需看成临界资源，即进来一个读者就+1操作
    int readcount = 0;
     
    // 读者进程
    void reader()
    {
        
    	while(TRUE)
    	{
        
    		// 互斥其他读者，只允许一个读者进入
    		P(rmutex);
    		if(readcount == 0)
    			// 如果读者数目为0，所以就必须互斥写者
    			P(mutex);
    		// 读者数+1
    		readcount++;
    		// 释放，让其他读者进来修改readcount
    		V(rmutex);
     
    		/* 读操作 */
     
    		// 读者离开，需要访问readcount
    		P(rmutex);
    		readcount--;
    		// 如果此时没有读者了，表示写者可以进行写了
    		if(readcount == 0)
    			V(mutex);
    		// 释放readcount资源
    		V(rmutex);
    	}
    }
     
    void writer()
    {
        
    	while(TRUE)
    	{
        
    		// 写者和一般消费者进程一样，获取信号量值
    		P(mutex);
     
    		/* 写操作 */
     
    		// 让文件可读和可写
    		V(mutex);
    	}
    }
     
    void main()
    {
        
    	reader();
    	writer();
    	reader();
    	/*.......*/
    }

//写者优先（伪代码）
     
    // 互斥读者与写者
    semaphore mutex = 1;
    // 互斥读者
    semaphore rmutex = 1;
    // 互斥写者
    semaphore wmutex = 1;
    // 表示是否还有写者
    semaphore readable = 1;
     
    // 读者数量，写者数量
    int readcount = 0, writecount = 0;
     
    void reader()
    {
        
    	// 先看是否可读
    	P(readable);
    	// 互斥其他读者修改readcount
    	P(rmutex);
    	if(readcount == 0)
    		// 如果没有读者，需要互斥写者
    		P(mutex);
    	readcount++;
    	V(rmutex);
    	V(readable);
    	/* 读取中 */
    	P(rmutex);
        readcount--;
    	if(readcount == 0)
    		V(mutex);
    	V(rmutex);
    }
     
    void writer()
    {
        
    	// 互斥其他写者，写入writecount
    	P(wmutex);
    	if(writecount == 0)
    		// 此时不能让写者以后的读者进去
    		P(readable)
    	writecount++;
    	V(wmutex);
    	// 互斥在写者之前的读者
    	P(mutex);
    	/* 写入中 */
    	// 写入完成离开
    	V(mutex);
    	P(wmutex);
    	writecount--;
    	if(writecount == 0)
    		// 让写者以后的读者可读
    		V(readable);
    	V(wmutex);
     
    }
     
    void main()
    {
        
    	reader();
    	writer();
    	reader();
    	/* ... */
    }

--------------------

#### 3.信号量与进程数的关系 ####

书本课后13题．若信号量的初值为2，当前值为-1，则表示有多少个等待进程?请分析。

信号量初值：表示系统中的资源数量

当信号量 <0 的时候，表示资源已经分配完毕，进程自我阻塞。

因而，” 等待进程 “ 的数量等于 |负值的信号量的绝对值|

因此题目中，有 |-1| = 1个等待进程

书本课后14题.有m个进程共享同一临界资源,若使用信号量机制实现对某个临界资源的互斥访问,请求出信号量的变化范围。

信号量初值为信号量的最大值，表示最多可以分配的请求

若信号量初值为1，则信号量最大为1，最小量为1-m（总有一个进程会进行，因此最多有1-m个阻塞的）

因而变化范围为 \[1-m , 1\]

书本课后15题．若有4个进程共享同一程序段，而且每次最多允许3个进程进入该程序段，则信号量值的变化范围是什么?

程序段作为共享资源，最多允许3个进程进人其中，因此设置信号量初值为3。当4个进程共享该程序段时，在每个进程申请进入时，信号量都会执行减1操作。

当第1个进程申请进入时，信号量值变为2;

第2个进程申请进入时，信号量值变为1;

第3个进程申请进入时，信号量值变为0,

第4个进程申请进入时，信号量值变为-1。

因此，信号量的变化范围是3，2，1，0，-1

--------------------

### | 课后简答题 ###

![在这里插入图片描述][03dc62316baf4e5daacb46ea7c6bfde2.png]![在这里插入图片描述][3d6af73b88b4407cb98b4ee4f9a25a0d.png]

[03dc62316baf4e5daacb46ea7c6bfde2.png]: https://img-blog.csdnimg.cn/03dc62316baf4e5daacb46ea7c6bfde2.png
[3d6af73b88b4407cb98b4ee4f9a25a0d.png]: https://img-blog.csdnimg.cn/3d6af73b88b4407cb98b4ee4f9a25a0d.png