- 银行家算法
- 地址变换、页面置换
- 作业调度、进程调度
- 磁盘调度
- PV操作
1.银行家算法
某系统有A、B、C三类资源可供五个进程P1、P2、P3、P4、P5共享。进程对资源的需求和分配情况如下：
进程
最大需求
A B C
已分配
A B C
可用
A B C
P1
7 6 4
2 2 1
0 1 2
P2
4 3 3
3 1 1
P3
10 1 3
4 1 3
P4
3 3 3
3 2 2
P5
4 4 6
1 1 3
按银行家算法回答下列问题：
(1)请写出尚需资源矩阵need; (2)现在系统是否处于安全状态？为什么？（如果有安全序列，请写出）
(3)P5资源请求request (0, 1, 1)可否满足，为什么？
2.地址变换、页面置换
1.某分页存储管理中，页面大小为4KB,某进程的页号0~8对应的物理块号分别为8，9， 10、15. 18. 20、 21、22、 23，计算该进程的逻辑地址05AF8H对应的物理地址（描述计算过程）
2.在一个请求页式存储管理系统中，进程P共有5页，访问串为3，2，1，0，3，2，4，3，2，1，0，4时，试用LRU置换算法和FIFO置换算法，计算当分配给该进程的页面数为3时，访问过程中发生的缺页次数和缺页率。
4.在某请求分页系统中，有一作业，它依次要访问的地址序列是：18、351、198、99、436、50、556，若该作业的第0号页已经装入主存，现分配给该作业的主存共3块，页的大小为100字节。请回答下列问题（需要详细过程）：(1) 按FIFO调度算法产生的缺页中断次数是多少？依次写出淘汰的页号？缺页中断率是多少？（2）按LRU调度算法产生的缺页中断次数是多少？依次写出淘汰的页号？缺页中断率是多少
5.假定某页式管理系统中，主存为128KB，分成32块,块号为0,1,2,3,4……31,某作业有五块,其页号为0,1,2,3,4, 被分别装主存的3,8,4,6,9块中，有一逻辑地址为[3,70],试求出相应的物理地址(其中方括号中的第一个元素为页号,第二个元素为页内地址，按十进制计算)，并画图说明地址变换过理。
3.作业调度、进程调度
1.有一个**单CPU**的**多道批处理系统**(内存中可**同时装入两道作业**)，**作业调度**采用“**短作业优先**”调度算法，**进程调度**采用“**优先数抢占式**”调度算法，且优先数越小优先级越高，列出所有作业进入内存的时间及结束时间并计算平均周转时间填入下表。
作业
到达时间
运行时间
优先数
1
8:00
40分钟
5
2
8:20
30
3
3
8:30
50
4
4
8:50
20
6
作业
到达时间
运行时间
优先数
进入内存时间
结束时间
周转时间
1
8:00
40分钟
5
8：009：1070分钟
2
8:20
30
3
8：208：5030
3
8:30
50
4
9：1010：0090
4
8:50
20
6
8：5010：2090
2.一个多道程序系统，有一个作业序列，作业的提交时间及运行时间在下表中所列。当第一个作业进入系统后开始调度，假定作业都是仅作计算。请列出在分别采用先来先服务算法和计算时间短的优先算法管理作业时各个作业的开始时间、完成时间和周转时间。注意：忽略系统开销。
作业号 到达输入井时刻 需计算时间
1 10∶00 2小时
2 10∶10 1小时
3 10∶20 0.5小时
4 10∶30 0.2小时
4.磁盘调度
1.磁盘共有200个柱面(0-199)，它刚刚从92号磁道移到98号随道完成读写，假设此时系统中等待访问磁盘盘的磁道序列为190，97，90，45，150，32，162，108，112，80，试给出采用下列磁头移动算法的顺序并计算寻道距离。
(1)FCFS算法:(2)SSTF算法:(3)SCAN算法(4)C-SCAN算法
2. 有一磁盘组共有8个盘面 ，每个盘面上有100个磁道，每个磁道有 8个扇区，假定以扇区为一个盘块，若使用位示图管理磁盘空间，问：
（1）位示图需占用多少（字节）存储空间；
（2）若位示图的字长为32位（一行的位数），那么， 3号字5号位（字号、位号从0开始）对应的块号是多少？
（3）某文件记录存放到3866号逻辑磁盘块，请问该记录存放到哪个柱面的第几个磁道的第几个扇区？（柱面号、磁头号、扇区号、逻辑磁盘块号从0开始编号）
3.设文件索引节点中有8个地址项，其中6个地址项为直接地址索引，1个地址项是一级间接地址索引，1个地址项是二级间接地址索引，每个地址项大小为4字节，若磁盘索引块和磁盘数据块大小均为512字节，则可表示的单个文件的最大长度是多少KB？（写出计算过程）
5.PV操作
1、桌上有一空盘，最多允许存放一只水果。爸爸可向盘中放一个苹果或放一个桔子，儿子专等吃盘中的桔子，女儿专等吃苹果。
试用P、V操作实现爸爸、儿子、女儿三个并发进程的同步。
提示：设置一个信号量表示可否向盘中放水果，一个信号量表示可否取桔子，一个信号量表示可否取苹果。
semaphore mutex = 1;//互斥访问盘子
semaphore SA = 0;//是否放入苹果
semaphore SO = 0;//是否放入橘子
semaphore empty = 1;//盘子是否为空
Father(){
while(1){
P(empty);//占用盘子
P(mutex);
放入水果
V(mutex);
if(放入橘子）
V(SO);
else
V(SA);
}
}
Son(){
while(1){
P(SO);
P(mutex);
拿橘子
P(mutex);
V(empty);//通知盘子为空
}
}
Daughter(){
while(1){
P(SA);
P(mutex);
拿苹果
P(mutex);
V(empty);
}
}
2.问题描述：假定阅览室最多容纳100人阅读，读者进入时，必须在门口的登记表上登记，内容包括：姓名、座号等；离开时要撤销登记内容。用P、V操作描述读者进程的同步算法。
semaphore mutex=1;
int count = 100;
Reader(){
while(1){
P(count);
P(mutex);
进入登记
V（mutex）;
阅读
P(mutex);
离开 注销
V(mutex);
V(count);
}
}
3.设有一缓冲池P，P中有20个可用缓冲区，一个输入进程讲外部数据读入P，另有一个输出进程讲P中数据取出并输出。若进程每次操作均以一个缓冲区为单位，试用记录性信号量写出两个进程的同步算法，要求写出信号量的初值；
semaphore empty = 20;//可用的缓冲区
semaphore full = 0;//已用的缓冲区
semaphore mutex = 1;//互斥访问
int in = 0, out = 0;
Input(){
while(1){
生产一个nextP;
P(empty);
P(mutex);
P[in] = nextP;
in = (in+1)%20;
V(mutex)
V(full);
}
}
Output(){
while(1){
P(full);
P(mutex);
next = P[out]
out = (out + 1) % 20;
输出next
V(mutex);
V(empty);
}
}
4.某寺庙，有小、老和尚若干，有一水缸，有小和尚提水入缸供老和尚饮用。水缸可容10桶水，水取自同一井中。水井径窄，每次只能容一个桶取水。水桶总数为3个。每次入、取缸水仅为1桶，且不可同时进行。给出取水、入水的算法描述。
semaphore mutex1 = 1,mutex2 = 1;//井和水缸的互斥访问
semaphore empty = 10,full = 0;//水缸使用情况
int count = 3;//3个水桶
get(){//入水
while(1){
P(empty);//当前水缸内有空位
p(count);//小和尚拿水桶
P(mutex1);
小和尚从井里取水
V(mutex1);
P(mutex2);
小和尚将水倒入水缸内
P(mutex2);
V(full);//通知老和尚进程可以取水了
V(count);//归还水桶
}
}
use(){
while(1){
P(full);
P(count);
P(mutex2);
老和尚从井里取水
V(mutex2);
V(empty);//通知小和尚进程水缸内有空位，可以去提水了
V(count);
}
}
5.有一个盒子中放有数量相等的黑白棋子各100枚，现在用自动分拣系统将黑白棋子分开，系统中有两个B。A负责捡黑子，B则负责捡白子，两者必须交替进行分拣，每个进程每次只拣一个子，当一个进程拣子时不允许另一个进程去拣子，且分拣结束前不得停止。用PV操作解决该问题。
semaphore mutex = 1;//拣子互斥
semaphore SA = 1,SB = 0;
int block = 100,white = 100;
A(){
while(1){
P(SA);
P(black);
拣黑子
V(SB);//通知B进程可以拣子了
}
}
B(){
while(1){
P(SB);
P(white);
拣白子
V(SA);
}
}
6.有三个进程P1、P2和P3协作打印文件， P1将文件记录从磁盘读入内存的缓冲区Buffer_1中，每执行一次读取一个记录；P2将Buffer_1中的内容加工后复制到缓冲区Buffer_2中，每执行一次加工复制一个记录；P3负责从Buffer_2中取出信息并送到打印机输出，每执行一次打印一个记录；缓冲区的大小和一个记录的大小一样。 请用wait和signal操作协调实现这三个进程的并发执行。
问题描述：设公共汽车上，司机和售票员的活动分别为：
司机：启动汽车； 售票员：上下乘客；
正常行车； 关车门；
到站停车； 售票；
开车门；
上下乘客；
用P、V原语描述：在汽车不断到站，停车，行驶的过程中两个人的同步活动
8.读者写者问题，读者优先，写者优先
读者优先：
有一个许多进程共享的数据区，这个数据区可以是一个文件或者主存 的一块空间；有一些只读取这个数据区的进程（Reader）和一些只往数据区写数据的进 程(Writer)，此外还需要满足以下条件：
（1）任意多个读进程可以同时读这个文件；
（2）一次只有一个写进程可以往文件中写；
（3）如果一个写进程正在进行操作，禁止任何读进程度文件。
int count=0; //用于记录当前的读者数量
semaphore mutex=1; //用于保护更新count变量时的互斥
semaphore rw=1; //用于保证读者和写者互斥地访问文件
writer () { //写者进程
while (1){
P(rw); // 互斥访问共享文件
Writing; //写入
V(rw) ; //释放共享文件
}
}
reader () { // 读者进程
while(1){
P (mutex) ; //互斥访问count变量
if (count==0) //当第一个读进程读共享文件时
P(rw); //阻止写进程写
count++; //读者计数器加1
V (mutex) ; //释放互斥变量count
reading; //读取
P (mutex) ; //互斥访问count变量
count--; //读者计数器减1
if (count==0) //当最后一个读进程读完共享文件
V(rw) ; //允许写进程写
V (mutex) ; //释放互斥变量 count
}
}
写者优先：
int count = 0; //用于记录当前的读者数量
semaphore mutex = 1; //用于保护更新count变量时的互斥
semaphore rw=1; //用于保证读者和写者互斥地访问文件
semaphore w=1; //用于实现“写优先”
writer(){
while(1){
P(w); //在无写进程请求时进入
P(rw); //互斥访问共享文件
writing; //写入
V(rw); // 释放共享文件
V(w) ; //恢复对共享支件的访问
}
}
reader () { //读者进程
while (1){
P (w) ; // 在无写进程请求时进入
P (mutex); // 互斥访问count变量
if (count==0) //当第一个读进程读共享文件时
P(rw); //阻止写进程写
count++; //读者计数器加1
V (mutex) ; //释放互斥变量count
V(w); //恢复对共享文件的访问
reading; //读取
P (mutex) ; //互斥访问count变量
count--; //读者计数器减1
if (count==0) //当最后一个读进程读完共享文件
V(rw); //允许写进程写
V (mutex); //释放互斥变量count
}
}
主要的大题：
计算题
1****、作业（进程）调度算法：
先来先服务（FCFS）、短作业优先（SJF）、高响应比有限调度
2****、虚拟存储器中的页面置换算法：
先进先出页面置换算法（FIFO）、最近最未使用置换算法（LRU）、最佳置换算法（Optimal）
3****、地址转换（逻辑地址到物理地址的转换）：
分页式、分段式，重点是分页
4****、银行家算法：
安全状态一定不死锁，不安全状态不一定死锁
5**、磁盘调度算法: **
先来先服务（FCFS）、扫描算法（SCAN）、循环扫描算法（CSCAN）
6****、位示图法
7**、PV操作，如生产者-**消费者问题（记录型信号量的应用）
版权归原作者 是小天不是小兲 所有， 如有侵权，请联系我们删除。