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

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;				//初始0

Agent:
	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