今年十八，期末速刷（操作系统篇1）

马上期末了，想问问各位期末考几科

我家学校网安考7科呜呜呜

只能出点文章一把梭了。。。

争取只挂一科

先来先算法（FCFS）

算法思想

我今天学FCFS只有一个要求

公平、公平

还是tnd公平

算法规则

按照进程的先后顺序来进行服务。

是否会导致饥饿

不会（下面有解释）

是否可抢占

是非抢占式算法

个人理解

怎么说呢。。。

我个人的理解，就是食堂打饭。你先来，我就给你盛饭，不管你要多少菜，我都给你。

就算给你打饭需要1个小时，给别人打饭需要1秒，我也给你打，因为你是先来的。

不过这个打饭很有意思，我在看这个算法时有个疑问，就是：

明明我需要等前一个人打完饭我才可以打饭，那为什么我不会被饿死(导致饥饿)

当然放在现实里有点荒谬，不过注意，“饥饿”在算法里是这样解释的：

在操作系统中，饥饿问题是指由于高优先级请求的不断涌入导致低优先级进程长时间被停滞，无法获得处理器或资源。通常情况下，当一个任务被无限期地推迟时，就会出现饥饿问题。操作系统需要以下资源来响应进程请求

什么意思捏，是指我去排队打饭，马上快到我的时候，一群牛马过来亲切地问我：同学我可以站在你前面嘛

好好好

然后我就被饿死了。(bushi

那为什么在FCFS中不会出现这种情况呢，是因为他有一个规则，即：

优先处理等待时间长的任务

什么意思？

等待时间长，就说明来得早。先来先算法顾名思义

优缺点

优点：算法简单、公平
缺点：对长作业有利，对短作业不利

为啥？

劳资几秒的事，非得拖到最后一个处理？人多也就不说啥了，人少不就是明摆着恶心人嘛。

然后有几个算式哈，理解一下就可。

算法

周转时间（打饭花费时间）=完成时间（打完饭）-到达时间（开始排队）

平均周转时间（平均每个人打饭时间）=各作业周转时间之和（总共打饭时间） / 作业数（打饭人数）

带权周转时间=作业周转时间 / 作业实际运行的时间=（作业完成时间-作业提交时间）/ 作业实际运行的时间（编不下去了，自己理解吧qwq）

最后一个进程是p4哈

周转时间=运行时间-到达时间

p1=7-0

p2=4-2........

仔细想想，这么写是不是错了

p2必须等p1打完饭才能开始打饭，所以从它到食堂开始排队到开始打饭等了多长时间？

p2等待时间：7-2=5

p2打饭时间：4

p2一共花费时间：5+4=9

那它的带权周转时间呢

根据公式：作业周转时间/作业实际运行时间

什么叫实际运行时间？

我去食堂为了干啥，打饭捏。那我排队能拿到一粒米吗？不能

所以实际运行时间即运行时间即开始打饭时间。一个意思，别问我为啥强调，问就是忘了。。。

所以：

周转时间/实际运行时间=9/4=2.25

剩下几个平均的整体算出来加一下除一下就行了，咱把剩下几个p简单说说。

p3周转时间：

p3到食堂的时间是4，这个时候，p1还没打完饭，那还得等个3，等完3之后，p2说他先来的，还得等他打饭花费的一个4。

问题来了，p3等了多长时间？

3+4=7

那咱打饭要多长时间？

咱饭量小，一个1就够

那7+1=8

咱的周转时间就是8

剩下的不说了，开另一个算法

RR调度算法

RR调度算法，也称时间片轮转。

算法思想

公平、平均(个人理解)

算法规则

按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如100ms)。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。

是否会导致饥饿

不会（下面有解释）

是否可抢占

是抢占式算法

优缺点

优点：公平：响应快，适用于分时操作系统：
缺点：由于高频率的进程切换，因此有一定开销；不区分

不难，打个比方

我是一名班主任，带学生去做植树

分别有A,B,C,D,E,F六名学生，地面是这样的

我选择按一排一排的形式植树。

啥意思捏，

每个人都有一个自己的任务进度，完不成一个任务进度禁止回家。而且每个人的任务进度都不一样，有人要种一个，有人要种两个

我先让6个人中的三个人去植树，给他们设个时间，好比是10分钟一次，等10分钟结束，不管他种没种完，都下来歇着。

如果，他种完了自己的任务进度，他直接放学回家。

如果，他没种完自己的任务进度，换另一个人种。

双人合作种一个树任务进度分开算。

那开始思考一下：

我是A，我先种了10分钟，可我没有种完，换B上来，B的手脚很麻利，种了5分钟就种完自己的任务进度回家了。

我就直接上去接着种我自己的任务进度，这就是抢占式。

如果是非抢占式，我就要等属于B的十分钟过完才能接着种。

那再想想，如果有15个学生，每列分到5名学生种树，这时候如果我在规定的十分钟之内没种完，我就只能排在队伍的后面重新等待了呜呜呜

看习题

没啥好讲的吧

周转时间是完成时间-到达时间

带权是周转/服务时间

如果就绪队列有 n 个进程，并且时间片为 q，那么每个进程会得到 1/n 的 CPU 时间，而且每次分得的时间不超过 q 个时间单元。每个进程等待获得下一个 CPU 时间片的时间不会超过 (n-1)q 个时间单元。例如，如果有 5 个进程，并且时间片为 20ms，那么每个进程每 100ms 会得到不超过 20ms 的时间。

再来一个例题：