操作系统期末复习（大题）

1. 进程调度

 

周转时间=作业完成时刻-作业到达时刻

带权周转时间=周转时间/服务时间

平均周转时间=各个作业周转时间之和/作业个数

操作系统：周转时间和其他时间_系统为作业提供的时间-CSDN博客

 2. 进程调度

3. 调度算法

4. 临界区互斥访问问题

 

 即证明是否满足互斥（忙则等待），空闲让进，有限等待

分析：

互斥：当flag[i]，flag[j]同时置为true时，且同时进入第一层while()循环，双方都满足循环条件，则双方都能进入第一层while()循环，而if语句里面的turn==j，turn==j不能同时满足，这个时候只有编号为turn的进程因为不能满足if语句条件从而能够进入临界区。

5. 信号量机制（p/v操作）

 个人习惯用p/v操作，实际上完全等价。wait==p; signal==v;

Semaphor max=n+1;		//表示理发店可以容纳的人数
Semaphor chair=n;		//空闲椅子数
Semaphor barber=1;		//表示理发椅空闲
Semaphor ready=0;		//表示客人准备就绪
Semaphor finished=0;	//表示一次理发结束
Customer:while(1){P(max);P(chair);P(barber);V(chair);V(ready);...barberd...P(finished);V(barber);V(max);}
Barber:while(1){P(ready);...barbering...V(finished);}

6. 经典同步互斥问题之抽烟者问题

抽烟者问题：假设一个系统有三个抽烟者进程和一个供应进程。每个抽烟者不停地卷烟并抽掉。但是要卷起并抽掉一个烟，抽烟者需要有三种材料：烟草、纸和胶水。一个抽烟者有纸，另一个有烟草，第三个有胶水。供应进程无限供应所有三种材料，供应者每次将两种材料放到桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉，并给供应者一个信号告诉完成了。供应者就会放另外的两种材料在桌子上，这种过程一直重复。写个程序同步供应者与抽烟者。

Semaphor smoker[3];		//初始0
Semaphor material[3];	//初始0
Semaphor agent;			//初始1
int turn;				//初始0Agent:while(1){P(agent);V(smoker[turn]);V(material[(turn+1)%3]);V(material[(turn+2)%3]);turn=(turn+1)%3;}
Smoker i:while(1){P(smoker[i]);P(material[(i+1)%3]);P(material[(i+2)%3]);...smoking...V(agent);		}

 7. 进程同步问题

一组合作进程，执行顺序如图所示。请用 P 、 V 操作实现进程间的同步操作。

8. 死锁问题（什么时候会发生死锁）

9. 死锁问题

看不懂...

10. 银行家算法

 

b：

安全序列不唯一 ，找到一个即可

比如也可以是：（P0，P3），（P1，P2，P4)       括号内无所谓顺序都可以

c：

安全序列：P0，(P2，P3)，(P1，P4)。括号内无所谓顺序都可。

11. 动态分区分配算法

 

分配内存后，原分区大小会变化。

最佳适应，每次分区后，都要重新按分区从小到大排序，然后依次检索合适的分区

最差适应，每次分区后，都要重新按分区从大到小排序，然后依次检索合适的分区

其中最佳适应算法的内存利用率最高

12. 内存有效访问时间问题

a：存在内存中的页表访问一次，然后再根据页表查询物理块号后再次访问访问一页内存

2*200ns=400ns

b：0.75*200+0.25*（200+200）=250ns

 13. 考虑缺页情况下的内存有效访问时间

 

14. 计算有效访问时间

 分页设备的理解：将磁盘上的文件或是进程传输到内存，或者将内存上的页帧换回磁盘。当要运行一个进程时，需要个这个进程建立一个页面映射表（页表），并开始给这个进程分配内存块。这些功能在此处就是由这个分页设备完成的。就是一个将磁盘上的文件以块的方式拷贝到内存。当发生缺页时，同样需要这个传输设备将进行页面置换。

每秒传输100万字，一页1000个字，可一算出传输一页需要的时间为t=1000/1000000=1ms=1000us

15. 基本分段存储管理

 段表有段号，物理地址需要显示的给出的段号

 

16. 根据有效访问时间求缺页率

 页表放在寄存器中，不考虑查询页表所花费的时间，同时这里的缺页处理包括了包括了访存时间

考试的大题内容

银行家算法
页面置换算法
逻辑地址->物理地址
信号量机制/pv操作
内存有效访问时间
进程调度算法