PV操作类大题

历年题目类型

  • 生产者消费者问题 —— 进程间关系为“生产资源-消费资源”🍈
  • 理发师问题 —— 进程关系为“服务-被服务”🎉
  • 读者写这问题 —— 同类进程不互斥、异类进程互斥🏆
  • 哲学家进餐问题 —— 只有一类进程，每个进程需要同时拥有多种资源
  • 单纯同步问题 —— 前驱后继图

生产者消费者问题

5步骤

  1. 理清楚有几类进程？一个进程对应一个函数。
  2. 每个函数内部，中文描述动作，(只执行1次，不加while()；重复执行，加while())
  3. 分析每个动作之前需要P(占用)什么? 动作结束需要V(释放)什么？
  4. 所有P、V写完之后再去定义信号量，思考初值是多少？
  5. 检查P连续出现的地方，是否存在死锁？有，则适当调整P的前后顺序。

2.3-7

image.png

答案👇
  • 定义的信号量，最好用//在后面加注释

图片alt

2.3-8

image.png

答案👇

info 提示塊標籤

图片alt

2.3-12

image.png

哲学家进餐问题

  • 哲学家问题的关键点是限制并行，主要是三种思路
  • 1.限制申请资源的顺序 （不建议）
    如：规定单号哲学家先取筷子，双号先取右筷子
  • 2.限制并发进程数 （通用，并发度不高）
    如：规定同一时间只能有一个哲学家就餐
  • 3.让进程一口气取的所有资源后，再运行（通用，并发度较高）
    如：哲学家只有能够取的两个筷子的时候才能就餐

2.3-24

image.png

答案👇

n个哲学家围坐圆桌，由于哲学家左边的筷子，同时是上一位哲学家右边的筷子。

  • 用数组chopsticks[]表示筷子资源
  • 第i号哲学家左筷子为chopsticks[i]；右筷子为chopsticks[(i+1)%n]
  • 本题采用方案3，一次性申请完所有资源。同一时刻只允许一个哲学家申请资源。

semaphore mutex;            //互斥信号量;
semaphore bowl;            //碗资源；
semaphore chopsticks[i];  //筷子资源；


哲学家i(){
    while(1){
        P(mutex);
        P(chopsticks[i]); //拿左筷子；
        P(chopsticks[(i+1)%n]);//拿右筷子；
        P(bowl);//拿碗；
        V(mutex);
        吃饭；
        V(bowl); //还碗；
        V(chopsticks[(i+1)%n]); //还右筷子；
        V(chopsticks[i]); //还左筷子
    }
}

单纯同步互斥问题

2.3-27

image.png

答案👇

图片alt

2017-46

image.png

答案👇

IMG_20231104_203007.jpg

2023-45

image.png

答案👇

A43E16D231DC8773BEA053B7CD230C13.jpg

Swap指令由硬件实现，原理如下
GIF 2023-12-20 16-03-58.gif

2023-46

image.png

答案👇

image.png

理发师问题

理发师问题拆解：

  • 顾客(被服务)
    • 如何使用代码表示“取号”？
    • 是否有等待区“座位上限”？
      1. 有座位上限的->信号量(empty、full) or int变量都可以
      2. 没有座位上限的->只能int 变量
    • 座位满时，是等待还是直接离开？
      1. 座位满等待时->可以是信号量 or int变量
      2. 直接离开时->只能是int变量,不能阻塞直接return
  • 服务人员(提供服务)
    • 如何使用代码表示“叫号”？
    • 没有顾客时，应该”盲等(一直循环检查)“还是“睡觉”？

2.3-14

image.png

答案👇
  • 本题空座椅有数量限制->即可选择int变量，也可选择信号量，但是题目要求是没有座位直接离开return，那么就只能用int变量，如果用信号量就会阻塞而不是直接离开
  • 开始时的semaphore service = 0 ;因为只有叫号后，才提供服务

图片alt

2.3-6

image.png

答案👇
  • 本题有叫号，实际中叫号取号都是有顺序的，所以需要int 型变量。
  • 有顾客数量限制可以用信号量机制，没有数量上限就用int变量。
  • 注意，一开始的semaphore service = 0 ;因为只有叫号后才提供服务服务



int waiting = 0; //表示已取的号码/顾客数量
semaphore mutex=1; //互斥信号量
semaphore service=0; //服务员资源


Customer_i(){
    P(mutex);
    取号；
    wating++;
    V(mutex);
    等待被叫号；
    P(service);
    被服务；
}


Service_j(){
    while(1){
        P(mutex);
        if(waiting>0){
            叫号；
            waiting–;
            V(mutex);
            V(service);
            提供服务
        }
        else(){
            V(mutex);
            做其他事；
        }
    }
}

2.3-19

image.png

答案👇

image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//我写的，不太对
semaphore mutex=1 //实现互斥叫号
semaphore salesman=0 //表示营业员资源；
int count=0; //表示客户叫号数

process 顾客1{
	P(mutex);
	if(count !=10){
		取号；
		count++;
		V(mutex);
		等待叫号;
		P(salesman);
		被服务；
	}else{
		离开；
		V(mutex);
	}
	
}

process 营业员{
	while(true){
		P(mutex);
		if(count>0){
			叫号；
			count--;
			V(mutex);	
			V(salesman);
			为客户服务；
		}else{
			休息
		}
		
	}

}



读者写者问题

  • 多个读者可以并行的读，由第一个读进程lock,由最后一个读进程unlock
  • 写进程永远只能一个一个写，所以每个写都要对文件lock与unlock

2.3-15

image.png

答案👇
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

semaphore L_mutex=1;
semaphore lock=1;
semaphore c_mutex1=0;
semaphore c_mutex2=0;
semaphore c_mutex3=0;
int count1=0;
int count2=0;
int count3=0;

Customer1{
	while(1){
		P(c_mutex1);
		if(count1==0){
			P(lock);
		}
		count1++;
		V(c_mutex1);
		看电影；
		P(c_mutex1);
		count1--;
		if(count1==0){
			V(lock);
			离开；
		}
		V(c_mutex1);
	}
}

Customer2{
	while(1){
		P(c_mutex2);
		if(count2==0){
			P(lock);
		}
		count2++;
		V(c_mutex2);
		看电影；
		P(c_mutex2);
		count2--;
		if(count2==0){
			V(lock);
			离开；
		}
		V(c_mutex2);
	}
}

Customer3{
	while(1){
		P(c_mutex3);
		if(count3==0){
			P(lock);
		}
		count3++;
		V(c_mutex3);
		看电影；
		P(c_mutex3);
		count1--;
		if(count3==0){
			V(lock);
			离开；
		}
		V(c_mutex3);
	}
}

测试8

image.png

答案👇
  • 读优先: 常规写法，写会被阻塞，读能一直进入，会导致写饥饿.
  • 写优先: 比较复杂，不容易考
  • 读写公平 : 利用排队队列，实现先来先服务。
读优先🥝
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
semaphore lock=1; //⽤于实现对共享⽂件的互斥访问
int count = 0; //记录当前有⼏个读进程在访问⽂件
semaphore mutex = 1; //⽤于保证对count变量的互斥访问
writer (){
 while(1){
  P(lock);  //写之前“加锁”
  写⽂件…
  V(lock);  //写完了“解锁”
	}
}
reader (){
 while(1){
  P(mutex); //各读进程互斥访问count
   if(count==0) P(lock); //第⼀个读者，读之前“上锁”
   count++; //访问⽂件的读进程数+1
  V(mutex);
  读⽂件…
  P(mutex); //各读进程互斥访问count
   count--; //访问⽂件的读进程数-1
   if(count==0) V(lock); //由最后⼀个读进程负责“解锁”
  V(mutex);
	}
}
读写公平🎄
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
semaphore lock=1; //⽤于实现对共享⽂件的互斥访问
int count = 0; //记录当前有⼏个读进程在访问⽂件
semaphore mutex = 1; //⽤于保证对count变量的互斥访问
semaphore queue = 1; //⽤于实现“读写公平”。咸⻥注：可以将queue理解为⼀个“队列”，当资源暂
不可访问时，⽆论读者、写者都需要公平排队
writer (){
	while(1){
	  P(queue); //先排队
	  P(lock); //尝试“上锁”
	  V(queue); //唤醒下⼀个队头进程
	  写⽂件…
	  V(lock); //使⽤完资源，解锁
	}
}
reader (){
	while(1){
		P(queue); //先排队
		P(mutex); //互斥访问count
		if(count==0)
			P(lock); //第⼀个到达的读者尝试“上锁”
		count++; //读者计数+1
		V(mutex);
		V(queue); //唤醒队头进程
		读⽂件…
		P(mutex); //互斥访问count
		count--; //读者计数-1
		if(count==0) //最后⼀个离开的读者，负责“解锁”
			V(lock);
		V(mutex);
	}
}

文件系统

文件系统整理👇
  1. 将文件的各种属性的信息包括地址的信息存放在索引结点中，使得FCB变得更加简洁。
  2. 其中inode中的地址信息,分为直接地址、一级间接地址、二级间接地址
  • 直接地址：指向的物理块存放的就是文件信息。
  • 一级间接地址：指向的整个物理块存放的全是直接地址。
  • 二级间接地址：指向的整个块存放的全是一级间接地址。
  1. 注意，inode结点，并不是一整个块的大小

扫描全能王 2023-11-06 19.10.jpg

图片alt

2011-46 顺序分配

image.png

答案👇

扫描全能王 2023-11-23 20.28.jpg

2016-47 链式分配(显式)

image.png

答案👇

FAT-File Allocation Table 文件分配表 - 显示链接分配标志
扫描全能王 2023-11-23 21.07.jpg

2012-46 索引分配

image.png

答案👇

扫描全能王 2023-11-24 15.41.jpg
image.png

2014-46

image.png

答案👇

image.png

2018-46

image.png

答案👇

扫描全能王 2023-11-25 22.24.jpg

考点

  1. 操作系统的概念、特征和功能
  2. 内核态和用户态
  3. 中断、异常
  4. 系统调用
  5. 操作系统的引导
  6. 进程与线程
  7. 进程状态与进程控制
  8. 处理及机制
  9. 进程同步与互斥
  10. 经典同步问题
  11. 死锁
  12. 内存管理概念
  13. 连续分配管理方式
  14. 非连续分配管理方式
  15. 虚拟页式存储管理
  16. 文件元数据和索引结点
  17. 文件的操作
  18. 文件共享和保护
  19. 磁盘组织与管理
  20. IO控制方式
  21. IO软件的层次结构
  22. IO调度和缓冲区
  23. 设备分配与回收