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. 进程同步问题
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操作
内存有效访问时间
进程调度算法