操作系统CATS典型题目大全

操作系统CATS典型题目大全

很久没有在博客上面写学习方面的笔记了,主要是觉得之前写的很多都是记录性质的,把源代码copy一下就完事,意义不大,也很少能帮助到其他人。之前博客访客非常少,自己写一写权当是自娱自乐;现在访客量渐渐大起来,让从四面八方来的访客看到那样的文章就真的有一点不像话了QAQ...

这一学期开了操作系统课,用的是老师自己开发的CATS系统。操作系统中考试的大题、套路都是相对固定的,期末考试题目考的浅一些,考研题目考的深一些,难一些,但基本的做法是一样的。这篇文章中,我就将用简单、通(bu)俗(zhuan)易(ye)懂的的记录操作系统中各种大题的套路和算法,长期更新~

啥是CATS

如果你是SDUT的大二/大三学生,那么恭喜你,你成功的找到组织咯~有的老师可能不用这套CATS系统,但是这里面的题目与期末考试的是一样的,请放心食用!知识都是一样的,其他学校的同学也欢迎看一看,对于期末考试会有帮助的。

CATS考试系统是你学习操作系统课程的小杀手小帮手,是老师自己开发的,年久失修,bug很多 想要从操作系统这一科目中拿到高分(不管是平时成绩 还是期末成绩,因为期末考试应该也是用这套系统),经常刷CATS是必不可少的。

CATS中平均成绩95分以上,你的平时成绩才能达到满分。所以,争取每一次都全部做对吧!但是,这对普通人来说基本上不可能做到的事情。因此,每次做题之前记得备份,万一成绩不理想,还可以回滚,消除成绩不好的记录。废话就说这么多,那么,正文开始咯。

专题一 信号量机制

难度:简单。先来简单的、用通俗易懂的语言介绍一下本专题内的概念和算法:

信号量:你可以把它可以理解为当前系统中的资源余量。当信号量小于0时,说明资源已经分配完毕,再来请求资源的进程就只能进入就绪队列等待。大于等于0时,说明资源有余量,进程就可以得到CPU时间来执行。

P操作:请求某个资源。

V操作:释放某个资源。

优先级:两个进程中,优先级高的进程首先执行。

抢占式调度算法:只要满足了优先级高的进程的运行条件时(有了足够的资源),优先级高的进程将会强行取得CPU的使用权,优先级低的进程就只能等待优先级高的进程运行完毕或者阻塞。

非抢占式算法:不论优先级,得到资源的进程将一直执行,直到这个进程运行完毕或者阻塞。

知道了上面对机制的简单描述,做题就非常简单了。下面来看这道例题:

先看是不是抢占式,本题是非抢占式的,先记牢在心里。再看优先级,C的优先级高于F,因此C1先执行。等执行到C5,执行对信号量E进行P操作,E-1<0,不够用了,所以现在C进程进入了阻塞状态。

于是开始执行进程F。等执行到F5时,对E进行了V操作,信号量E够用了。由于是非抢占式,因此F能够继续执行。之后的就顺理成章下来了。

下面的填空是最基本的算法,用用二年级数学就能做对咯。信号量机制专题就介绍到这里。

专题二 时间片轮转算法

难度:中等。难度比上面的信号量机制的难一些,是因为时间片轮转算法要先写出进行的甘特图(Gantt chart),这一过程中出现了任何差错都会前功尽弃,后面零碎的计算也容易出错。因此难度大一些。

这个算法最重要的就是画甘特图,甘特图画对了,这个题就做对一大半了。其实还有很多CPU时间的分配算法,比如高响应比优先调度算法(HRRN),短作业优先算法(SPF),只要掌握了它们的基本规律,就很好画出它们的甘特图。这里就以最难画甘特图的时间片轮转算法来举个栗子,栗子中的RR = 1,也就是每个时间片的长度只有1:

时间片

0时刻,只有P1到达,运行队列中只有P1,P1先运行一个时间片。此时队列中的是P1. 0~1时刻运行P1.

1时刻,P2到达,P2进入队列;然而P1还没有运行完毕,于是P1再进入队列。注意,是P2先进入队列,然后P1进入。队列中的是P2P1. 1~2时刻运行P2.

2时刻,没有新进程到达,P2没有运行完毕,P2进入队列。此时的队列中的是P1P2. 2~3时刻运行P1.

3时刻,没有新进程到达,P1没有运行完毕,P1进入队列。此时的队列中的是P2P1. 3~4时刻运行的是P2.

4时刻,P3到达,P3进入队列;然而P2还没有运行完毕,于是P2再进入队列。此时的队列中的是P1P3P2. 4~5时刻运行的是P1.P1已经运行了3次,达到服务时间,P1运行完毕。

5时刻,P4到达,P4进入队列;P1运行完毕,不再进入队列。此时的队列中的是P3P2P4. 5~6时刻运行的是P3.

............直到所有的进程运行完毕。过程有一(亿)点点复杂,一步都不能错。

下面的表格中,最后一栏保留三位小数,四舍五入。最后结果保留两位小数。

公式:

  1. 周转时间(T) = 完成时间(F) - 到达时间(A)

  2. 周期(W) = 周转时间(T) / 服务时间(S)

专题三 银行家算法

难度:较简单。防止、判断死锁产生的算法。咋一看上去可能觉得它比较复杂,但实际上它就是两位数的加减法。不过要注意的是必须得全部做对,错一个就try again咯~

先来扫清一些概念:

  • Max:最大需求矩阵,一个进程一次性向系统申请的最大资源量。

  • Allocation:已经分配给该进程的资源量

  • Need:还需要分配给该进程的资源量,进程在得到这些资源后,将能正常运行,运行后释放所有占用的资源。对于某种资源,Need = Max - Allocation.

  • Available:当前系统中剩余的可用资源。对于某种资源,Available = Max之和 - Allocation之和

  • Work:当前系统中剩余的可用资源,只在运行中有这个概念。初始的Work = Available. Work + Allocation = 该进程运行完毕后,系统中拥有的可用的资源,也就等于下一行的Work.

银行家算法

P0->P4循环扫描方法,先从P0开始:

  • 如果P0需要的资源(Need)比系统中现在拥有的可用资源(Availabe)多,那么把所有的资源交给P0,P0还是不能运行完毕,所以不能给P0,往下看P1是否满足;反之,则将资源给与P0,P0运行完毕后就会释放更多资源。

  • 如果第一次循环中,没有进程能够满足系统的可用资源,那么T0状态就是不安全的(但是这种可能性非常小),反之,如果一遍遍循环,到最后所有的进程都运行完毕了,就可以得到安全序列,则系统是安全的。

专题四 页面置换算法

进程运行时,若其访问的页面不在内存而需将其调入,但内存已无空闲空间时,就需要从内存中调出一页程序或数据,送入磁盘的对换区,其中选择调出页面的算法就称为页面置换算法。

常用页面置换算法:

  • 最佳(Optimal)置换算法:被淘汰的页面是以后永久不使用的,或未来最长时间内不使用的页。由于未来无法被预知,所以此算法永远无法被实现,只是理想的算法。

  • 先进先出(FIFO)置换算法:淘汰最先进入内存的页面。

  • 最近最久未使用(LRU)置换算法:给每个页面添加访问字段t,记录页面最后一次被访问的时间,然后优先淘汰最近最久没有使用(t最大)的页面。

  • Clock置换算法:待更新

先以最常见的最近最久未使用(LRU)题目示例。LRU是要看之前访问的情况,再决定如何进行置换的。这个算法常见的题目如下:

LRU
Tips:内存在从上到下放置的情况下,物理地址是从低到高的。

访问串从头开始,进程访问第0页,现在内存中没有第0页,但内存中还有空余,因此只发生缺页中断,将第0页从硬盘调入内存即可。

继续,访问第1页,内存中有,PASS.

继续,访问第2页,现在内存中没有第2页,内存中没有空余,不但要发生缺页中断,还要发生页面置换。前面最近访问过0,1页,7、5号页没有访问过,可以对他们进行置换。但由于是低地址优先,因此第7页被置换,换成2号页。

继续,访问第5页,内存中有,PASS.

继续,访问第6页,现在内存中没有第6页,内存中没有空余,不但要发生缺页中断,还要发生页面置换。5、2、1、0页,第0页没有被访问的时间最长,因此对第0页进行置换,换成6号页。

......如此类推,直到推到最后一个为止。很容易的,能够得出中断次数、置换次数和置换的次序。


与LRU类似的,还有最佳(Optimal)置换算法。由于要访问的页面的次序已经知道了(相当于我们能够看到未来),因此Optimal在题目中是可行的,它主要是看未来的内存访问情况,除此之外与LRU都相同。

Clock算法:最近没时间更,先咕咕咕了...

专题五 磁盘调度算法

难度:中等。最重要的就是找出距离当前访问到的进程最近的进程。N-Step系列算法的思维量和计算量稍微大一些。

常用磁盘调度算法

  • FCFS(先来先服务):这个没啥好说的。按照访问序列来就OK了。

  • SSTF(最短寻道时间优先):其要求访问的磁道与当前磁道所在的磁道距离最近,使得每次寻道时间最短,但不能保证平均寻道时间最短。

  • SCAN(扫描算法):SCAN算法考虑的下一个访问对象是其欲访问的磁道既在当前磁道之外,又是距离最近的。SCAN是双向的扫描算法,读取可以正着读也可以反着读。

  • CSCAN大致与SCAN一样但是是单向的扫描算法,读取只能按照一个方向来进行。

  • N-STEP-SCAN:把整个访问序列分成若干个大小为N的部分,一部分一部分的进行SCAN算法。

  • N-STEP-CSCAN:把整个访问序列分成若干个大小为N的部分,一部分一部分的进行CSCAN算法。

这么说可能有些生硬,我们直接来看题目,看完了题目你就明白了~

SCAN算法

SCAN算法

像这道题里面,使用SCAN算法,179->181,一开始按照磁道号增大的方向。继续向磁道号增大的方向扫描,扫描出202,215,232...一直到295,比181大的进程都扫描完了。然后开始往回扫描,因为读是双向的,所以从比181小最少的179开始,157、143...一直到47,序列就成功的写出来了。

这里求磁道访问序列我还有一个小技巧:179->181是增大的,就从FIFO序列中找出比181大的,按照从大到小的顺序排列。然后把比181小的,从大到小排列就能得到最终的访问序列了。

下面的ASL=(序列中单调性发生变化的两个点的和)/进程的总数,也不是很难计算。


再来看看这道CSCAN算法的题目。相较于SCAN算法,CSCAN算法只能按照一个顺序读取,这个顺序从题目中给出的信息可以获取到。

CSCAN算法

CSCAN算法

像这道题里面,使用CSCAN算法,181->166,一开始按照磁道号减小的方向,这就告诉我们,读取的方向只能按照从磁道的大到小来进行。继续向磁道号减小的方向扫描,扫描出160,109,79...一直到14,比166小的进程都扫描完了。然后开始往回扫描,因为是单向的,磁头只能先到最高位进行扫描,因此从比166大最多的278进行从大到小的扫描,245,241,233...直到167,就得到了访问序列。

刚刚提到的小技巧还是有效,只是右后半做出了改动,现在都是从大到小进行排列的。


N-STEP-SCAN和N-STEP-CSCAN都是把整个访问序列分成若干个大小为N的部分,然后一部分一部分的进行SCAN算法或者CSCAN算法。只要细致一些,也还是能做对的。

N-step-cscan算法

N-step-cscan算法

老鸽子持续更新中...

本文永久链接:https://blog.xmgspace.me/archives/sdut-operating-system-cats.html
本文文章标题:操作系统CATS典型题目大全
如文章内无特殊说明,只要您标明转载/引用自Xiaomage's Blog,您就可以自由的转载/引用文章。禁止CSDN/采集站采集转载。
授权协议:署名-非商业性使用-相同方式共享 4.0 国际(CC BY 4.0)
暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇