0 前言

接上一篇文章：進(jìn)程調(diào)度（2b）：STCF（最短完成時(shí)間優(yōu)先） 算法 原理與實(shí)踐

1 前提鋪墊

除了與上一篇相同的，這里介紹新的基礎(chǔ)知識(shí)。

1.1 三種類型的程序

• 計(jì)算密集型（CPU導(dǎo)向）
• 輸入輸出密集型（I/O導(dǎo)向）
• 中間型

所謂計(jì)算密集型程序，就是大量時(shí)間都在占用CPU做運(yùn)算，例如科學(xué)計(jì)算。而輸入輸出密集型程序，則大量時(shí)間都在進(jìn)行輸入輸出，你很熟悉它，例如人機(jī)交互，我們每時(shí)每刻都在用計(jì)算機(jī)干這個(gè)事情。中間型就是二者都有，占比差不多。

那么介紹這個(gè)有什么用？

當(dāng)我們的目標(biāo)不同的時(shí)候，性能指標(biāo)的評(píng)價(jià)標(biāo)準(zhǔn)也不同，對(duì)于計(jì)算密集型程序，我們可能更關(guān)注它的Turnaround Time，而對(duì)于（交互型的）輸入輸出密集型程序，我們可能更關(guān)注它的Response Time。后續(xù)我們會(huì)對(duì)算法進(jìn)行性能評(píng)價(jià)，設(shè)計(jì)目標(biāo)很重要不是嗎？

1.2 響應(yīng)時(shí)間（Response Time）

這是一個(gè)新的性能指標(biāo)。

Response Time: the time a job spends waiting after arrival before first running.

所謂響應(yīng)時(shí)間，就是從任務(wù)到達(dá)后，到第一次被執(zhí)行的等待時(shí)間。這個(gè)概念在分時(shí)操作系統(tǒng)誕生后變得尤為重要，用戶是“獨(dú)占”計(jì)算機(jī)的，并且是交互式界面，所以對(duì)用戶來說，響應(yīng)時(shí)間非常重要，用戶必須等待很短的時(shí)間就能看到一部分結(jié)果。

試想一個(gè)場(chǎng)景，你敲擊了鍵盤的字母Z，然后在10s之后，才看見屏幕顯示了Z……這真的令人抓狂不是嗎？

我們需要做的，就是讓用戶快速看到自己的成果，此時(shí)，并不需要將程序執(zhí)行完成，將程序運(yùn)行一點(diǎn)點(diǎn)先給用戶顯示出來，這對(duì)于用戶來說是很棒的！

那么應(yīng)該如何做到這一點(diǎn)？答案就是充分使用上下文切換。還記得上一篇我們的搶占式調(diào)度嗎？它第一次打破了進(jìn)程順序執(zhí)行，實(shí)現(xiàn)了簡(jiǎn)易的進(jìn)程（上下文）切換，現(xiàn)在，我們要充分利用上下文切換，來讓用戶因?yàn)榭焖夙憫?yīng)而得到滿足了！

但是要警惕！沒有必要太快！上下文切換也是需要系統(tǒng)開銷的，它的占比應(yīng)該盡可能小，我們后續(xù)會(huì)深入談。現(xiàn)在，你只需要知道，響應(yīng)時(shí)間是1s還是0.1s，對(duì)用戶來說是沒有什么區(qū)別的，因此我們選擇1s即可，這樣將上下文切換的數(shù)量降低了10倍。

1.3 上下文切換（Context Switch）

好吧……上面說了這么多上下文切換，它到底是個(gè)啥？第一篇我提到了底層機(jī)制 + 上層策略，當(dāng)時(shí)只是提了一句，現(xiàn)在，我們?cè)龠M(jìn)一步說一說。

• 底層機(jī)制：上下文切換
• 上層策略：FIFO，SJF，STCF，RR……

在解釋這個(gè)之前，我們先來談?wù)劦栋伞?duì)的，就是刀！

你知道的，刀可以削水果，可以切菜，也可以雕刻……但是歸根結(jié)底，都是在刀足夠鋒利的前提下，這些事情才能完成，我們分析一下：

• 底層機(jī)制：刀足夠鋒利
• 上層策略：削水果，切菜，雕刻……

也就是說，在刀鋒利這個(gè)底層機(jī)制滿足的前提下，我們才能切菜削水果。

好吧現(xiàn)在我們回來，對(duì)于進(jìn)程調(diào)度算法而言，也是一樣的，我們在能夠?qū)崿F(xiàn)上下文切換（進(jìn)程切換）的前提下，才能使用各種各樣的方法進(jìn)行進(jìn)程調(diào)度。

你要問我Context Switch是什么樣的？我來畫張圖。

我想你明白了，只是切換而已。如果說更關(guān)鍵的，可能是

• 保存現(xiàn)場(chǎng)和恢復(fù)現(xiàn)場(chǎng)是如何實(shí)現(xiàn)的？
• 上下文切換的系統(tǒng)開銷是多少?

我們先不回答這個(gè)問題，你只需要知道，每次上下文切換的時(shí)間 / 每個(gè)時(shí)間片的時(shí)間 這個(gè)比例應(yīng)該小一點(diǎn)！（時(shí)間片下面就會(huì)談）

2 RR原理

RR（Round - Robin）輪轉(zhuǎn)，輪轉(zhuǎn)算法下，多個(gè)進(jìn)程不再是順序執(zhí)行，而是切換式執(zhí)行，這樣對(duì)于交互式程序來說，用戶就能快速感受到自己執(zhí)行的操作得到了響應(yīng)，響應(yīng)時(shí)間短。

2.1 算法

舉個(gè)例子

• A：20s
• B：20s
• C：20s

在順序執(zhí)行下，上述3個(gè)進(jìn)程按照A、B、C的順序依次執(zhí)行，如下圖：

這樣一來，響應(yīng)時(shí)間分別是

• A：0s
• B：20s
• C：40s

對(duì)于執(zhí)行C程序的用戶來說，他可能會(huì)非常崩潰……響應(yīng)太慢總是讓人發(fā)瘋的，不是嗎？

如果我們采用輪轉(zhuǎn)算法，假定一個(gè)時(shí)間片為10s，結(jié)果就不一樣了，所謂時(shí)間片，就是指某進(jìn)程在CPU執(zhí)行10s，就要被中斷，然后讓其他進(jìn)程執(zhí)行（也就是每隔10s就進(jìn)行上下文切換）。

我們看看會(huì)發(fā)生什么：

這樣一來，響應(yīng)時(shí)間分別為

• A：0s
• B：10s
• C：20s

響應(yīng)時(shí)間縮短很多了，但是好像還是慢，如果時(shí)間片設(shè)置為1s呢？響應(yīng)時(shí)間就是0s，1s和2s，這就很棒了！

2.1.1 思考1：時(shí)間片可以無限小下去嗎？

我們的用戶當(dāng)然想要更快獲得響應(yīng)，但是對(duì)于用戶來說，1s和0.1s可能沒什么差別，所以我們完全可以選擇1s，那么，選擇更大值的理由是什么？不選0.1s的理由是什么?

答案就是切換上下文需要系統(tǒng)開銷，切換上下文的時(shí)候，要保存當(dāng)前程序的狀態(tài)，我們切換越頻繁，系統(tǒng)的額外開銷就越多，要之前，順序執(zhí)行的時(shí)候我們根本不需要這樣做，所以，切換上下文帶來的開銷應(yīng)該盡可能小一點(diǎn)。

例如，時(shí)間片是10ms，切換上下文需要1ms，那么我們需要浪費(fèi)10%的時(shí)間去切換上下文，如果時(shí)間片是100ms，就占1%，這還可以接受，物極必反的道理就在于此了。

• 擴(kuò)展：可以思考下奔騰4的失敗，CPU的流水線深度越深性能就越好嗎？奔騰4使用了31級(jí)流水線，性能反而下降了，現(xiàn)代CPU的流水線也不過十幾級(jí)，例如i7是14級(jí)。
• 推薦閱讀：面向流水線的指令設(shè)計(jì)：奔騰4是怎么失敗的？

所以說，時(shí)間片是不能無限小下去，它的占比應(yīng)該小一點(diǎn)，小到什么程度那就與具體需求和實(shí)現(xiàn)有關(guān)了。

假設(shè)切換上下文1s，時(shí)間片10s，上面的例子就成了這樣：

相關(guān)分析請(qǐng)讀者自行完成。

2.1.2 思考2：時(shí)間片的設(shè)置可以是任意的嗎？

對(duì)于上下文切換這個(gè)底層機(jī)制的實(shí)現(xiàn)，是由軟硬件協(xié)同完成的，這里有一個(gè)重要的概念時(shí)鐘中斷，時(shí)鐘每隔一段時(shí)間，就會(huì)中斷程序，把控制權(quán)從正在執(zhí)行的程序交還給OS。

因此說，我們的時(shí)間片應(yīng)該是時(shí)鐘中斷周期的整倍數(shù)，這樣，我們就能保證每個(gè)時(shí)間片在執(zhí)行的時(shí)候不會(huì)被時(shí)鐘中斷所打斷（被程序本身的系統(tǒng)調(diào)用打斷就是另一回事了……）

2.2 缺點(diǎn)：大鍋飯式分配 & 增長(zhǎng)的周轉(zhuǎn)時(shí)間

RR算法下，對(duì)所有就緒進(jìn)程都是一視同仁的，不管你是誰，都會(huì)被執(zhí)行，切斷，切換，恢復(fù)，再執(zhí)行，就像大鍋飯一樣，不管你干活多少，吃的飯都一樣。

但是我們知道，不同的程序，重要程度和緊急程度是不一樣的，但是RR全忽略了，這顯然不合理。

另外，響應(yīng)時(shí)間確實(shí)是改進(jìn)了，但是此時(shí)程序周轉(zhuǎn)時(shí)間表現(xiàn)不佳，這是顯而易見的。

因此我們的算法仍需要進(jìn)一步改進(jìn)。

3 RR實(shí)踐

我們來進(jìn)行幾個(gè)模擬，體會(huì)上一小節(jié)的幾個(gè)觀點(diǎn)吧。

我們先試一下SJF，3個(gè)進(jìn)程都是100s，同時(shí)到達(dá)

./scheduler.py -p SJF -l 100,100,100 -c

得到的結(jié)果是

Average -- Response: 100.00 Turnaround 200.00 Wait 100.00

再試試RR，3進(jìn)程都是100s，時(shí)間片是1s，忽略上下文切換時(shí)間

./scheduler.py -p RR -q 1 -l 100,100,100 -c

得到的結(jié)果是

Average -- Response: 1.00 Turnaround 299.00 Wait 199.00

你可以充分體會(huì)到，SJF的響應(yīng)時(shí)間是RR是100倍，RR的周轉(zhuǎn)時(shí)間是SJF是1.5倍，而在更極端的情況下，差距可能會(huì)更大。

4 核心思想

目前我們接觸到的都是計(jì)算密集型程序，而且是100%占用CPU，我們關(guān)注了兩大性能指標(biāo)，周轉(zhuǎn)時(shí)間和響應(yīng)時(shí)間。

• 關(guān)注周轉(zhuǎn)時(shí)間的算法：FIFO，SJF和STCF
• 關(guān)注響應(yīng)時(shí)間的算法：RR

目前來說，我們還

• 沒有同時(shí)兼顧周轉(zhuǎn)時(shí)間和響應(yīng)時(shí)間的算法
• 沒有考慮包含輸入輸出的程序的算法

這也是接下來我們要改進(jìn)的。

5 預(yù)告：進(jìn)程調(diào)度（4）：I/O、不可預(yù)測(cè)的運(yùn)行時(shí)間

接下來，我們初步為程序引入I/O，并且談?wù)勛畛醯囊粋€(gè)假設(shè)運(yùn)行時(shí)間已知是否現(xiàn)實(shí)。

鏈接：進(jìn)程調(diào)度（4）：I/O、不可預(yù)測(cè)的運(yùn)行時(shí)間

總結(jié)

以上是生活随笔為你收集整理的【操作系统】进程调度（3）：RR（轮转） 算法 原理与实践的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。