操作系统XOSCATS典型题目大全

操作系统XOSCATS典型题目大全

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

啥是XOSCATS

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

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

专题一 信号量机制

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

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

P操作:请求某个资源。

V操作:释放某个资源。

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

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

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

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

img

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

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

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

专题二 时间片轮转算法

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

这个算法最重要的就是画甘特图,甘特图画对了,这个题就做对一大半了。其实还有很多CPU时间的分配算法,比如高响应比优先调度算法(HRRN),短作业优先算法(SPF)(Tip:这两个算法不经常考,但是考到就容易抓瞎,因为不熟悉),只要掌握了它们的基本规律,就很好画出它们的甘特图。这里就以最难画甘特图、考试经考到的时间片轮转算法来举个栗子,栗子中的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咯~

先来扫清一些概念:

  • Resource:系统的资源总量,包括已分配资源Allocation和可用资源Available.
  • Max:最大需求矩阵,一个进程向系统申请的最大资源量。拿到Max所需的资源后进程便可以执行完成。
  • Allocation:已经分配给该进程的资源量。
  • Need:还需要分配给该进程的资源量,进程在得到这些资源后,将能正常运行,运行后释放所有占用的资源。对于某种资源,Need = Max - Allocation.
  • Available:当前系统中剩余的可用资源。对于某种资源,Available = Resource - 各个进程的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
Tip:内存在从上到下放置的情况下,物理地址是从低到高的。

访问串从头开始,进程访问第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算法

专题六 文件索引

专题六是文件索引算法,单纯做题的话难度比较简单,想要完全理解为什么这么做,还是需要想那么一下的。直接索引就是直接到文件所在地址去寻找文件;一级间接地址索引是指先要经过一个一级索引,再拿到文件地址;二级间接地址索引是指先要经过一级索引,达到二级索引,再从二级索引找到文件的地址。

做题需要注意的就是熟记2的次方表,2的10次方是1K;2的20次方是1M;2的30次方是1G。 还要注意有的题目中磁盘索引块和数据块大小不相同。

L0 = 地址项数 * 数据块大小
L1 = 地址项数 * (磁盘索引块大小/地址项大小) * 数据块大小
L2 = 地址项数 * (磁盘索引块大小/地址项大小)^2 * 数据块大小
MaxL = L0+L1+L2
MaxP = pow(2, 地址项大小 * 8 - 磁盘ID占位) * 数据块大小 其中的8是字节和字位的转换。

文件索引
文件索引

专题九 基础算法

专题九是一些基础算法的大合集,以BA开头,一共有9个。整理的顺序按照CATS中专题的顺序,而非老师讲课的顺序哦!这些算法掌握一些简单的公式就能基本掌握,我会用最简单的语言来进行描述,建议你配合CATS中的真题来食用。

BA-1 快表

M=内存访问时间 h=缓存命中概率 R=快表访问时间 EAT=CPU的有效访问时间

CPU要从内存中取资源,先到快表中找,找到了(命中)之后就能得到资源在内存中的地址,所需时间就是R+M
然而如果没有命中,则还要去内存中再获取一边资源在内存中的地址,最终的时间就是R+2M

只需要记住公式就能解决这类问题:EAT = (R+M)*h + (R+M+M)*(1-h)

BA-2 发生死锁的条件判断

在极端情况下,如果7个进程,每个进程需要11个资源。现在给所有进程分配10个资源,只需要再来一个资源就能运行其中的一个进程。这个进程运行完毕,释放了资源再给其他的,如此循环下去就都能执行完毕,不会发生死锁。这样最少需要(11-1)*7+1=71个资源,就不会产生死锁。

m=提供的总资源 n=n个进程 r=每个进行运行需要的资源

可以得到不发生死锁的条件:(r - 1)*n + 1<= m

BA-3

很见到,只需要记住:逻辑地址 = 页号*页面大小 + 页内地址

就像你只需要知道那个字在书的那一页 第几行 就能很快找到书中的那个字

注意单位,是KB还是B!

BA-4 位示图

D=磁盘容量 C=簇大小 n=位图大小

只需记住公式:n=D/8(C^2) 咋来的有点复杂,以后再补充吧~

BA-5 二级页表

逻辑地址空间大小 = (页面大小/页表项大小)*PT1中页表项个数(一项=一页)

通过 页面大小/页表项大小 就能得出一页所能存储的页表项的个数,乘以有多少个页就能得到逻辑地址空间大小咯

就相当于:一本书的总字数 = (一页纸的大小/一个字的大小) *目录中标示的页面数目

BA-6 CPU中断频率与响应时间

v=传输速率,单位KBps n=位数

中断频率:f = v/n

单缓冲响应时间:Pt = (1/v)

双缓冲响应时间:Pt = (1/v)*n

BA-7

传输速率 = 磁道容量*转速

磁道容量 = 容量/磁道数

7200rpm=每分钟7200转 而其他单位是以秒为单位的,因此要化成每秒钟的,要除以60才能用哦

BA-8 缓冲区结构

直接上公式,课本上有对这一段算法有详细的叙述,在课本P225页。

处理时间C <-- 传送时间M <-- 输入时间T

单缓冲区:

Δt1 = Max(C, T)+M

Tsn = n*Δt1 + Min(C, T)

多缓冲区:

Δt2 = Max(C+M, T)

Tdn = n*Δt2 + Min(C+M, T)

BA-9

首次满足 => 选择所碰到的第一块满足要求的内存/硬盘进行分配。

最佳满足 => 选择所有满足要求的块中最小的一块内存/硬盘进行分配。

最大满足 => 选择满足要求的最大内存/硬盘块进行分配。

【完】

后记

现在是2022年的6月21日,两天前的19日我离开了理工大顺利毕业,成为了一名校友。现在觉得能成为谢老师的学生,跟着他学习操作系统是一件幸事,操作系统是我掌握最好的一门专业课,他的课给我考研复习操作系统奠定了很好的基础。也感谢当时的自己整理出来这篇文章,不断地收到来自学弟学妹们地评论能,帮助到他们,把老师所教地知识传承下去。幸甚至哉。

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

评论

  1. 123
    Windows Edge
    2年前
    2022-6-19 20:50:07

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

    • 博主
      123
      Windows Edge
      2年前
      2022-6-21 10:55:11

      确实有错误,谢谢指正,已经更新了。(熟悉的IP地址,倍感亲切。

  2. future
    Windows Chrome
    2年前
    2022-4-30 14:45:36

    说实话学长讲的真的是不错,值得学习,收藏了

  3. 三年级小弟
    Windows Chrome
    2年前
    2021-11-16 10:48:27

    我去你们也用cats啊,我以为只有我们用

  4. CCY
    Windows Edge
    2年前
    2021-11-15 20:51:34

    BA-2不发生死锁的是不是(r-1)*n+1<=m?

    • 博主
      CCY
      Macintosh Safari
      2年前
      2021-11-16 20:42:47

      确实应该是 (r-1)*n+1<=m 应该是笔误了 上面的讲解里的是对的
      晚上回宿舍修改一下 感谢指正~

  5. 19小学弟
    Windows Chrome
    3年前
    2021-5-16 16:40:14

    做题之前怎么备份啊,求指教!

    • 博主
      19小学弟
      Windows Edge
      3年前
      2021-5-16 21:59:35

      就是把C盘下面的XOSCATS文件夹复制一份,复制到其他硬盘里面去,需要恢复再拷回来。

  6. nikou
    Windows Chrome
    3年前
    2021-4-29 21:07:56

    刀客塔

    • 博主
      nikou
      Android Chrome
      3年前
      2021-4-30 15:49:10

      您还有许多事情需要处理。现在还不能休息哦。

  7. 嘿嘿
    Linux Chrome
    3年前
    2021-3-10 8:04:22

    写的很清楚,学到了

  8. 佛佛谢
    Windows Edge
    3年前
    2020-11-15 10:27:24

    很有帮助,感谢!

    • 四年级老大哥
      佛佛谢
      Windows Chrome
      3年前
      2020-11-30 16:16:26

      小伙汁你不对劲.jpg

发送评论 编辑评论


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