写在前面
这遍博客主要是记录博主期末操作系统速成的笔记!
博主平时不听课,全靠期末速成
学霸可以自行离开
笔记内容来自于B站UP主:夜连三 视频:【操作系统】操作系统期末考试不挂科 大题详解 从0开始的不挂科生活 内容,学渣拯救者!!!40分钟速成,大家可以去看!
常考的五大题型
缺页问题
计算物理地址
银行家算法
磁盘调度
进程调度
缺页问题
三类算法:
先进先出FIFO(First Input First Output)
最佳置换算法OPT(Optimal replacement)
最近最少使用LRU(Least Recently used)
例题:
在一个请求分页系统中,假如一个作业的页面走向为:1.2.3.4.5.1.4.1.2.3.4.5 ,当分配给该作业的物理块数为4时,分别采用FIFO,LRU,OPT算法,计算访问过程中发生的缺页次数和缺页率!
解题步骤:
读题划重点信息 :页面走向,物理块数!
画表 页面走向第一行!
开局4缺页!因为这4个页面都要放入到cpu中!
FIFO算法
要点:先进先出!看那个页面最先进就替换!
每次替换左边出现次数最多的页面!看谁长,谁长替换谁!
缺页次数为10 缺页率:5/6
OPT算法
要点:
最佳替换算法,看已经在物理页中的页面在右边最后使用到的先替换!
淘汰的页面将是未来长时间内不再被访问的页面!
就比如:开始1234 然后5要替换,后面有 14123显然 3最后使用!所以先替换3!
缺页次数为6 缺页率:1/2
LRU算法
要点:
最近最少使用算法!最近未使用!
看需要添加页面的左边,页面走向哪个页面理该页面最远就替换该页面!!!
直接看页面走向就可以!
这里要和FIFO区分开!!!
先进先出,看哪个物理页最长!
LRU最近最少使用,看页面走向哪个理该页面最远!
缺页:9 缺页率:3/4
总结:
缺页问题,先画图,页面走向数+1为列,物理块+2为行!
开局都缺页!
FIFO:看(整个表)左边,谁长替换谁!
OPT:看(表头)右边,谁最远替换谁!
LRU:看(表头)左边,谁最远替换谁!
计算物理地址
物理地址计算3步曲!
求出页号
对照页表
计算地址
地址转换:
绝对地址 = 块号*块长 + 块内地址
例题:
在采用页式存储管理的系统中,某进程的逻辑地址空间为4页(每页2048字节),且已知该进程的页面映像表(页表)如下:
计算有效逻辑地址4865所对应的物理地址.
解题:
读题划重点: 每页多少字节, 页表,有效逻辑地址!
3步曲解题!
页号:
页号 = 逻辑地址/每页字节数
d = 4065/2048 = 2
对照页表:
根据页号找到块号!
看页表 ,页号2对应块号6!
数地址:
绝对地址 = 块号*块长 + 块内地址
块内地址= 逻辑地址%每页字节数
块内地址: 4065%2048 = 769
地址:6*2048 + 769 = 13057
银行家算法
2种题型
判断系统是否"死锁"
提供安全系列
例题:
假定系统中有5个进程{ P0,P1,P2,P3,P4}和三类资源{A,B,C},各种资源的数量分别是10,5,7,在T0时刻的资源分配情况如下图所示:
1.判断在T0时刻的安全性?
2.P1请求资源:P1发出请求向量Request(1,0,2),系统按照银行家算法进行检查!
3.P4请求资源:P4发出请求向量Request(3,3,0),系统按照银行家算法进行检验!
MAX:进程所需资源
Allocation:系统已经分配给进程的资源数
Need:进程还需要的资源数; Need=MAX - Allocation
Available:系统剩余的资源数;Available=Total-AllAllocation
解题:
第一问:
题目可能会给我们资源分配表,也可能不给我们,我们需要创建该表进行解题!
Need是我们需要计算的! MAX - Allocation
Available: Total(题目给的总资源数) - AllAllocation(全部已经分配的资源数)
画一张新表
Work:当前所剩资源
work+allocation:计算机处理完当前进程后所剩资源!
我们根据上面的表得到的Available剩余进程数,看那个进程Need<=Available先执行填入到work中
然后一步步将该表完善!1
如果最后一行得到的work+allocation与题目所给的总资源数一样说明结果正确!
如果都可以完成说明进程安全!
p1,p3,p4,p0,p2就是一组线程安全序列(不唯一)
第二问:
解题步骤:
1.先判断请求是否<=所需:Request(1,0,2)<=Need(1,2,2)
2.判断请求是否<=系统所剩的:Request(1,0,2)<=Available(3,3,2)
3.根据请求资源量进行分配(更改表)
4.列表计算
根据上表可以看到如果满足Request<=Need&&Request<=Available
然后就更改表: Need -=Request Allocation+=Request Available-=Request
Request(1,0,2)满足!
然后通过更改后的表进行第一问的操作!
线程安全序列:P1,P3,P0,P2,P4
第三问:
解题步骤:
和第二问相同,
注意这里要在第二问的基础上,如果第二问请求成功的话!
1.判断请求是否<=所需 :Request(3,3,0)<=Need(4,3,1) true
2.判断请求是否<=系统剩余:Request(3,3,0)<=Available(2,3,0) false
线程不安全!不需要进行下面的计算了!
磁盘调度
4种算法!
先来先服务FCFS
最短寻道时间优先SSTF
扫描算法SCAN
循环扫描算法C-SCAN
例题:
一个磁盘驱动器有150个柱面,考虑一个磁盘队列,它按照到达时间顺序分别是35,52,37,17,80,120,135,104如果读写磁头最初位于柱面90,请使用FCFS,SSTF,SCAN,CSCAN算法求总寻道长度和平均寻道长度.
FCFS 先来先服务!
到达顺序就是服务顺序!
记得磁头一开始位置90!
//磁头移动顺序: 90 -> 35 -> 52 -> 37 -> 17 -> 80 -> 120 -> 135 -> 104 //总寻道长度 = (90-35) + (52-35) + (52-37) + ... + (135-120) + (135-104) = 256
总寻道长度就是将磁头移动的总距离!
平均寻道长度 = 总长/移动次数
256/8 = 32
SSTF 最短寻道时间优先
向画一条数轴!
然后根据初始磁头位置90,判断两边距离,往距离更短的一遍走!
//磁头移动顺序: 90 -> 80 -> 104 -> 120 -> 135 -> 52 -> 37 -> 35 -> 17 //总寻道长度: //平均寻道长度:
SCAN 扫描算法
看刚刚的数轴,分成左右两部分!
//磁头移动顺序: //移动顺序分两种 //1.向左移动完再往右边最近优先寻道! 90-> 80 -> 52 -> 37 -> 35 -> 17 -> 104 -> 120 -> 135 //2.向右移动完再往左边最近优先寻道! 90 -> 104 -> 120 -> 135 -> 80 -> 52 -> 37 -> 35 -> 17
CSCAN 循环扫描算法
这里和扫描算法的不同是先左(右)扫描完,直接到最右(左)边开始扫描!
//磁头移动顺序: //移动顺序分两种 //1.向左移动完再往右边最远优先寻道! 90-> 80 -> 52 -> 37 -> 35 -> 17 -> 135 -> 120 ->104 //2.向右移动完再往左边最远优先寻道! 90 -> 104 -> 120 -> 135 -> 17 -> 35 -> 37 -> 52 -> 80
进程调度
3类算法
先来先服务FCFS(First Come First Service)
短作业优先SJF(Shortest Job First)
高响应比优先HRRN(Highest Response Ratio Next)(了解即可)
导学
到达时间(提交时间):就是进程告诉操作系统要开始处理的时间点,进程进入就绪队列等待等待处理!
开始时间:就是操作系统真正开始处理该进程的时间点
执行时间(CPU突发时间):就是操作系统处理这个进程的时间
例题:
从P1到P4有4个进程,每个进程的到达时间和运行时间如下表所示:
先来先服务调度算法:
按照进程到达先后顺序执行进程:P1,P2,P3,P4
方法一:
等待时间 = 开始时间 - 到达时间
周转时间 = 结束时间 - 到达时间(就是进程从就绪队列等待开始到进程结束所需要的时间)
带权周转时间 = 周转时间/执行时间
方法二:
Gantt图
这种方法比较直观!操作快推荐使用!
等待时间: 进程开始时间 - 到达时间
周转时间 : 用进程的结束时间 - 到达时间
短作业优先调度算法SJF
非抢占:就是进程从开始执行就一直是该进程执行到结束再执行其他进程
按照进程长度,进程越短越先执行: P1,P2,P4,P3
抢占 :就是有其他进程抢占执行,当一个进程到达后,发现自己的执行时间比正在执行进程的所需的剩余时间短,就抢占执行该进程!
抢占执行使用Gantt图更加直观!
这里就不画表格,表格比较麻烦!
高响应比优先调度算法:按优先权 = (等待时间+执行时间)/执行时间优先执行等待时间长执行时间短的进程!
非抢占:先执行P1
计算后面3个进程优先权:
P2 = (7+4)/4
P3 = (5+5)/5
p4 = (6+9)/9
这里P2的优先权更大!先执行P2
