與進(jìn)程有關(guān)的時(shí)間##
與過(guò)程有關(guān)的各種時(shí)間梆暖，如下圖所示 -
- 到達(dá)時(shí)間
進(jìn)程進(jìn)入就緒隊(duì)列的時(shí)間稱為到達(dá)時(shí)間。 - 突發(fā)時(shí)間
CPU執(zhí)行整個(gè)過(guò)程所需的總時(shí)間稱為突發(fā)時(shí)間疆前。 這不包括等待時(shí)間货徙。 即使在執(zhí)行之前計(jì)算一個(gè)過(guò)程的執(zhí)行時(shí)間也是令人困惑的区拳，因此基于突發(fā)時(shí)間的調(diào)度問(wèn)題無(wú)法在現(xiàn)實(shí)中實(shí)現(xiàn)浅蚪。 - 完成時(shí)間進(jìn)程進(jìn)入完成狀態(tài)的時(shí)間或進(jìn)程完成其執(zhí)行的時(shí)間稱為完成時(shí)間。
- 周轉(zhuǎn)時(shí)間該過(guò)程從抵達(dá)到完成所花費(fèi)的時(shí)間總量稱為周轉(zhuǎn)時(shí)間烫罩。
- 等待時(shí)間進(jìn)程等待CPU分配的總時(shí)間稱為等待時(shí)間惜傲。
- 響應(yīng)時(shí)間到達(dá)時(shí)間和進(jìn)程首次獲取CPU的時(shí)間之間的差異稱為響應(yīng)時(shí)間。
操作系統(tǒng)CPU調(diào)度##
在像MS DOS這樣的單編程系統(tǒng)中贝攒，當(dāng)進(jìn)程等待任何I/O操作完成時(shí)盗誊，CPU仍然是空閑的。 這是一個(gè)開(kāi)銷(xiāo)隘弊，因?yàn)樗速M(fèi)時(shí)間并導(dǎo)致饑餓問(wèn)題哈踱。 但是，在多程序系統(tǒng)中梨熙，CPU在進(jìn)程的等待時(shí)間內(nèi)不會(huì)保持空閑狀態(tài)开镣，而是開(kāi)始執(zhí)行其他進(jìn)程。 操作系統(tǒng)必須定義CPU將被給予哪個(gè)進(jìn)程咽扇。
在多程序系統(tǒng)中邪财，操作系統(tǒng)調(diào)度CPU上的進(jìn)程以獲得最大的利用率，此過(guò)程稱為CPU調(diào)度质欲。 操作系統(tǒng)使用各種調(diào)度算法來(lái)調(diào)度過(guò)程卧蜓。
這是短期調(diào)度程序的一項(xiàng)任務(wù)，用于調(diào)度CPU以查找作業(yè)池中存在的進(jìn)程數(shù)量把敞。 每當(dāng)運(yùn)行進(jìn)程請(qǐng)求某個(gè)I/O操作時(shí)弥奸，短期調(diào)度程序就會(huì)保存進(jìn)程的當(dāng)前上下文(也稱為PCB)并將其狀態(tài)從運(yùn)行狀態(tài)更改為等待狀態(tài)。 在此期間奋早，進(jìn)程處于等待狀態(tài); 短期調(diào)度程序從就緒隊(duì)列中選擇另一個(gè)進(jìn)程并將CPU分配給此進(jìn)程盛霎。 這個(gè)過(guò)程被稱為上下文切換。
進(jìn)程控制塊中保存了什么耽装？
操作系統(tǒng)在進(jìn)程的生命周期中維護(hù)一個(gè)進(jìn)程控制塊愤炸。 進(jìn)程終止或終止時(shí)，進(jìn)程控制塊將被刪除掉奄。 有以下信息保存在過(guò)程控制塊中规个，并隨過(guò)程狀態(tài)而變化。
為什么需要調(diào)度姓建？
在多道程序中诞仓，如果長(zhǎng)期調(diào)度程序選擇更多的I/O綁定進(jìn)程，那么大多數(shù)時(shí)候CPU仍然是空閑的速兔。 操作系統(tǒng)的任務(wù)是優(yōu)化資源的利用墅拭。
如果大多數(shù)正在運(yùn)行的進(jìn)程將其狀態(tài)從運(yùn)行狀態(tài)更改為等待狀態(tài)，那么系統(tǒng)中可能始終存在死鎖涣狗。 因此谍婉，為了減少這種開(kāi)銷(xiāo)舒憾，操作系統(tǒng)需要調(diào)度作業(yè)以獲得CPU的最佳利用率并避免死鎖的可能性。
操作系統(tǒng)調(diào)度算法###
操作系統(tǒng)使用各種算法來(lái)有效地調(diào)度處理器上的進(jìn)程穗熬。
調(diào)度算法的目的
最大CPU利用率
公平分配CPU
最大吞吐量
最短周轉(zhuǎn)時(shí)間
最短的等待時(shí)間
最短響應(yīng)時(shí)間
有以下算法可用于計(jì)劃作業(yè)镀迂。
1. 先來(lái)先服務(wù)
這是最簡(jiǎn)單的算法。 最短到達(dá)時(shí)間的過(guò)程將首先獲得CPU唤蔗。 到達(dá)時(shí)間越少招拙，進(jìn)程得到CPU的速度越快。 這是非搶先式的調(diào)度措译。
2. 輪循
在循環(huán)調(diào)度算法中别凤，操作系統(tǒng)定義了一個(gè)時(shí)間片(片)。 所有的進(jìn)程將以循環(huán)方式執(zhí)行领虹。 每個(gè)進(jìn)程都會(huì)獲得CPU一小段時(shí)間(稱為時(shí)間片)规哪，然后返回就緒隊(duì)列等待下一個(gè)回合。 這是一種搶先式調(diào)度塌衰。
3. 最短作業(yè)第一具有最短爆發(fā)時(shí)間的作業(yè)將首先獲得CPU诉稍。 突發(fā)時(shí)間越短，進(jìn)程得到CPU的速度越快
這是非搶先式的調(diào)度最疆。
4. 首先剩余時(shí)間最短這是SJF的搶先形式杯巨。 在該算法中，操作系統(tǒng)根據(jù)執(zhí)行的剩余時(shí)間安排作業(yè)
5. 基于優(yōu)先級(jí)的調(diào)度
在這個(gè)算法中努酸，優(yōu)先級(jí)將被分配給每個(gè)進(jìn)程服爷。 優(yōu)先級(jí)越高，進(jìn)程得到CPU的速度越快获诈。 如果兩個(gè)進(jìn)程的優(yōu)先級(jí)相同仍源，則會(huì)根據(jù)他們的到達(dá)時(shí)間進(jìn)行安排。
6. 最高響應(yīng)率下一個(gè)
在這種調(diào)度算法中舔涎，下一步將調(diào)度響應(yīng)比率最高的進(jìn)程笼踩。 這減少了系統(tǒng)中的饑餓。
操作系統(tǒng)FCFS調(diào)度####
先來(lái)先服務(wù)(FCFS)調(diào)度算法根據(jù)其到達(dá)時(shí)間簡(jiǎn)單地調(diào)度作業(yè)亡嫌。 就緒隊(duì)列中第一個(gè)工作將首先獲得CPU嚎于。 工作到達(dá)時(shí)間越少，工作得到的CPU就越快挟冠。 如果第一個(gè)進(jìn)程的突發(fā)時(shí)間是所有作業(yè)中最長(zhǎng)的于购，則FCFS調(diào)度可能會(huì)導(dǎo)致饑餓問(wèn)題。
FCFS的優(yōu)勢(shì)
簡(jiǎn)單
容易
先到先得
FCFS的缺點(diǎn)
調(diào)度方法是非搶先式的圃郊，該進(jìn)程將運(yùn)行到完成价涝。
由于算法的非搶先性，可能會(huì)出現(xiàn)饑餓問(wèn)題持舆。
盡管實(shí)現(xiàn)起來(lái)很容易色瘩，但由于平均等待時(shí)間比其他調(diào)度算法更高，因此性能較差逸寓。
示例
我們來(lái)看一個(gè)FCFS調(diào)度算法的例子居兆。 在下面的時(shí)間表中，有5個(gè)進(jìn)程的進(jìn)程ID為P0竹伸，P1泥栖，P2，P3和P4勋篓。 P0到達(dá)時(shí)間0吧享，P1在時(shí)間1，P2在時(shí)間2譬嚣，P3到達(dá)時(shí)間3钢颂，處理P4在時(shí)間4到達(dá)就緒隊(duì)列。 下表給出了過(guò)程及其各自的到達(dá)時(shí)間和爆發(fā)時(shí)間拜银。
周轉(zhuǎn)時(shí)間和等待時(shí)間通過(guò)使用以下公式計(jì)算殊鞭。
Waiting Time = Turnaround time - Burst Time
平均等待時(shí)間通過(guò)將所有過(guò)程的各個(gè)等待時(shí)間相加并且將總和除以過(guò)程的總數(shù)來(lái)確定。
| 進(jìn)程ID | 到達(dá)時(shí)間 | 突發(fā)時(shí)間 | 完成時(shí)間 | 轉(zhuǎn)換時(shí)間 | 等待時(shí)間 |
|---|---|---|---|---|---|
| 0 | 0 | 2 | 2 | 2 | 0 |
| 1 | 1 | 6 | 8 | 7 | 1 |
| 2 | 2 | 4 | 12 | 8 | 4 |
| 3 | 3 | 9 | 21 | 18 | 9 |
| 4 | 4 | 12 | 33 | 19 | 17 |
平均等待時(shí)間= 31/5
平均等待時(shí)間= 31/5
操作系統(tǒng)FCFS護(hù)航效果###
如果第一個(gè)作業(yè)的爆發(fā)時(shí)間是最高的尼桶，F(xiàn)CFS可能會(huì)受到隊(duì)列影響操灿。 就像在現(xiàn)實(shí)生活中一樣，如果隊(duì)列在路上經(jīng)過(guò)泵督，那么其他人可能會(huì)被堵塞趾盐，直到完全通過(guò)。 這也可以在操作系統(tǒng)中進(jìn)行模擬小腊。
如果CPU在就緒隊(duì)列的前端獲得較高突發(fā)時(shí)間的進(jìn)程谤碳，則較低突發(fā)時(shí)間的進(jìn)程可能被阻塞，這意味著如果執(zhí)行中的作業(yè)具有非常高的突發(fā)時(shí)間溢豆，則它們可能永遠(yuǎn)不會(huì)獲得CPU蜒简。 這被稱為隊(duì)列效應(yīng)或饑餓。
示例
在這個(gè)例子中漩仙，我們有3個(gè)進(jìn)程被命名為P1搓茬，P2和P3。 進(jìn)程P1的暴發(fā)時(shí)間最高队他。
下表中的周轉(zhuǎn)時(shí)間和等待時(shí)間通過(guò)公式計(jì)算卷仑，
Turn Around Time = Completion Time - Arrival Time
Waiting Time = Turn Around Time - Burst Time
在第一種情況下，雖然流程P1到達(dá)隊(duì)列中的第一個(gè)麸折， 該過(guò)程的爆發(fā)時(shí)間是最高的锡凝。 由于調(diào)度算法，我們所遵循的是FCFS垢啼，因此CPU將首先執(zhí)行Process P1窜锯。
在這個(gè)時(shí)間表中张肾，系統(tǒng)的平均等待時(shí)間將非常高。 這是因?yàn)檐?chē)隊(duì)的影響锚扎。 其他進(jìn)程P2吞瞪，P3必須等待40個(gè)單位時(shí)間，盡管他們的爆發(fā)時(shí)間非常短驾孔。 這個(gè)時(shí)間表遭受饑餓芍秆。
| 進(jìn)程ID | 到達(dá)時(shí)間 | 突發(fā)時(shí)間 | 完成時(shí)間 | 轉(zhuǎn)換時(shí)間 | 等待時(shí)間 |
|---|---|---|---|---|---|
| 1 | 0 | 40 | 40 | 40 | 0 |
| 2 | 1 | 3 | 43 | 42 | 39 |
| 2 | 2 | 4 | 12 | 8 | 4 |
| 3 | 3 | 9 | 21 | 18 | 9 |
| 3 | 1 | 1 | 44 | 43 | 42 |
平均等待時(shí)間= 81/3
在第二種情況下，如果進(jìn)程P1本來(lái)就已經(jīng)到達(dá)隊(duì)列的最后翠勉，而其他過(guò)程P2和P3早于那么饑餓問(wèn)題就不存在了妖啥。
以下示例顯示了這兩種情況的等待時(shí)間的偏差。 雖然時(shí)間表的長(zhǎng)度是相同的对碌，即44個(gè)單位荆虱，但是在這個(gè)時(shí)間表中等待時(shí)間將會(huì)減少
操作系統(tǒng)FCFS與開(kāi)銷(xiāo)###
在上面的例子中，我們假設(shè)所有的進(jìn)程只是CPU綁定進(jìn)程俭缓。但是也忽略了上下文切換時(shí)間克伊。
然而，如果考慮調(diào)度器在上下文切換中花費(fèi)的時(shí)間华坦，則系統(tǒng)的平均等待時(shí)間將增加愿吹，這也影響系統(tǒng)的效率。
上下文切換始終是開(kāi)銷(xiāo)惜姐。以下示例描述如果在系統(tǒng)中考慮上下文切換時(shí)間犁跪，效率將受到影響。
示例
在下面的例子中歹袁，假設(shè)有五個(gè)進(jìn)程:P1坷衍，P2，P3条舔，P4枫耳，P5和P6。 他們的到達(dá)時(shí)間和爆發(fā)時(shí)間如下孟抗。
| 進(jìn)程ID | 到達(dá)時(shí)間 | 突發(fā)時(shí)間 |
|---|---|---|
| 1 | 0 | 3 |
| 2 | 1 | 2 |
| 3 | 2 | 1 |
| 4 | 3 | 4 |
| 5 | 4 | 5 |
| 6 | 5 | 2 |
如果系統(tǒng)的上下文切換時(shí)間為1個(gè)單位迁杨，那么系統(tǒng)的甘特圖將按如下準(zhǔn)備。
給定δ= 1個(gè)單位;
在執(zhí)行每個(gè)進(jìn)程之后凄硼，系統(tǒng)將花費(fèi)額外的1個(gè)單位時(shí)間(開(kāi)銷(xiāo))來(lái)安排下一個(gè)過(guò)程铅协。
Inefficiency= (6/23) X 100 %
Efficiency? = (1-6/23) X 100 %
