進(jìn)程基礎(chǔ)

進(jìn)程基本概念

<font color = #0099ff> 進(jìn)程組：只包括祖先進(jìn)程，子孫進(jìn)程，兄弟進(jìn)程
進(jìn)程樹：所有進(jìn)程
僵尸進(jìn)程：在父進(jìn)程中經(jīng)常會(huì)調(diào)用waitpid來等待子進(jìn)程終止，如果在父進(jìn)程調(diào)用waitpid之前子進(jìn)程就終止了，那么子進(jìn)程就會(huì)成為僵尸進(jìn)程，（因?yàn)檫@個(gè)時(shí)候子進(jìn)程必須要等到父進(jìn)程waitpid之后才能真正結(jié)束）
孤兒進(jìn)程：父進(jìn)程在子進(jìn)程終止之前自己先終止了</font>

• 進(jìn)程間通信只能在同一個(gè)進(jìn)程組之間通信

進(jìn)程的狀態(tài)

進(jìn)程誕生（此時(shí)進(jìn)程還沒有準(zhǔn)備好）
進(jìn)程init （進(jìn)程初始化）
Active （活躍區(qū)）
僵尸態(tài) （進(jìn)程結(jié)束，開始收尸）

Active

在 Active中，存在三中不同的狀態(tài)

• Running 運(yùn)行態(tài)，當(dāng)進(jìn)程已獲得處理機(jī)，其程序正在處理機(jī)上執(zhí)行，此時(shí)的進(jìn)程狀態(tài)稱為執(zhí)行狀態(tài)。
• Blocked 這個(gè)進(jìn)程不具備繼續(xù)運(yùn)行下去的條件
• Ready 當(dāng)進(jìn)程已分配到除CPU以外的所有必要的資源，只要獲得處理機(jī)便可立即執(zhí)行，這時(shí)的進(jìn)程狀態(tài)稱為就緒狀態(tài)。（進(jìn)程準(zhǔn)備好了，但是缺少資源
  running 和 ready 兩種狀態(tài)統(tǒng)稱為runnable
  在操作系統(tǒng)進(jìn)行中，通過scheduler 控制進(jìn)程在ready 和 running之間轉(zhuǎn)換 執(zhí)行 1 2 操作
  當(dāng)程序發(fā)現(xiàn)自己運(yùn)行不下去了的時(shí)候，進(jìn)程會(huì)主動(dòng)去睡覺，執(zhí)行 3
  當(dāng)其他進(jìn)程使用完資源，叫醒sleep的線程，完成過程 4

進(jìn)程的生命周期

進(jìn)程創(chuàng)建

• 所有的進(jìn)程的公共父進(jìn)程是init，所有進(jìn)程都直接或者間接被init進(jìn)程創(chuàng)建
• 子進(jìn)程通過父進(jìn)程調(diào)用fork()函數(shù)創(chuàng)造，此時(shí)子進(jìn)程享有的數(shù)據(jù)空間和指令指針和父親完全一樣，但是調(diào)用一次fork函數(shù)，有兩個(gè)返回值，一個(gè)返回給父親，如果創(chuàng)建成功返回子進(jìn)程的pid，創(chuàng)建失敗返回錯(cuò)誤碼。另一個(gè)返回給子進(jìn)程，直接返回0。子進(jìn)程繼承到了父親的大部分資源，但也不是全部繼承，子進(jìn)程不繼承附近的子進(jìn)程，但是父進(jìn)程的堆棧，內(nèi)存環(huán)境等都會(huì)繼承。

進(jìn)程結(jié)束

• 當(dāng)一個(gè)父進(jìn)程結(jié)束的時(shí)候，他的子進(jìn)程也會(huì)被同時(shí)殺死

結(jié)束的可能情況

• 正常死亡 （自愿）完成任務(wù)之后死亡
• 出錯(cuò)退出 （自愿）遇到問題，程序自行結(jié)束生命
• 嚴(yán)重錯(cuò)誤 （非自愿）出現(xiàn)嚴(yán)重錯(cuò)誤，直接死亡
• 被殺死 （非自愿）一般是被族親進(jìn)程殺死或者root進(jìn)程殺死

中斷 （待完善）

進(jìn)程的實(shí)現(xiàn) （待完善）

維護(hù)了一張進(jìn)程表（通過數(shù)組實(shí)現(xiàn)）在這個(gè)進(jìn)程表當(dāng)中保存了進(jìn)程的重要信息

管理進(jìn)程 （待完善）

shell

<font color = #0099ff>shell 是用戶和計(jì)算機(jī)內(nèi)核交互的接口</font>

前臺(tái)進(jìn)程和后臺(tái)進(jìn)程

前臺(tái)進(jìn)程主要和用戶交互，優(yōu)先級(jí)高些，后臺(tái)進(jìn)程基本不用和用戶交互，優(yōu)先級(jí)低一些。

進(jìn)程調(diào)度

一 背景知識(shí)

調(diào)度策略

• 進(jìn)程響應(yīng)時(shí)間盡可能快
• 后臺(tái)作業(yè)的吞吐量盡可能高
• 盡可能避免進(jìn)程的饑餓現(xiàn)象
• 低優(yōu)先級(jí)和高優(yōu)先級(jí)進(jìn)程的需要盡可能調(diào)和

進(jìn)程饑餓

<font color= "#0099ff">進(jìn)程饑餓：等待時(shí)間給進(jìn)程推進(jìn)和響應(yīng)帶來明顯影響
饑餓死亡：饑餓到一定程度，使得進(jìn)程即使完成了它本該完成的任務(wù)也無實(shí)際意義的時(shí)候稱為饑餓死亡</font>

產(chǎn)生饑餓的主要原因

當(dāng)資源分配不公平，無法保證等待時(shí)間上界的存在，即使系統(tǒng)沒有發(fā)生死鎖，但是有些進(jìn)程仍需長(zhǎng)時(shí)間等待，舉個(gè)例子，當(dāng)有多個(gè)進(jìn)程需要打印文件時(shí)，如果系統(tǒng)分配打印機(jī)的策略是最短文件優(yōu)先，那么長(zhǎng)文件的打印任務(wù)將由于短文件的源源不斷到來而被無限期推遲，導(dǎo)致最終的饑餓甚至餓死。

二 進(jìn)程分類

進(jìn)程分類

第一種

第二種

實(shí)時(shí)進(jìn)程與普通進(jìn)程

普通進(jìn)程

上面表格當(dāng)中的交互式進(jìn)程和批處理進(jìn)程統(tǒng)稱為普通進(jìn)程。普通進(jìn)程的調(diào)度策略較為復(fù)雜

實(shí)時(shí)進(jìn)程

實(shí)時(shí)進(jìn)程采用FIFO的調(diào)度策略

調(diào)度器設(shè)計(jì)

進(jìn)程調(diào)度器框架

兩個(gè)調(diào)度器

可以用兩種方法來激活調(diào)度

• 直接的，比如進(jìn)程打算睡眠或者其他原因放棄CPU
• 通過周期性機(jī)制，以固定的頻率運(yùn)行，不時(shí)的檢測(cè)是否有必要

linux的調(diào)度程序目前由兩個(gè)調(diào)度器組成：主調(diào)度器，周期性調(diào)度器，兩者統(tǒng)稱為通用調(diào)度器或核心調(diào)度器
并且每個(gè)調(diào)度器都包含兩個(gè)內(nèi)容：調(diào)度框架，調(diào)度器類

六種調(diào)度策略

五個(gè)調(diào)度器類

依據(jù)不同的調(diào)度策略實(shí)現(xiàn)了五個(gè)調(diào)度器類，一個(gè)調(diào)度器類可以用一種或者多種調(diào)度策略調(diào)度某一類進(jìn)程

所屬進(jìn)程的優(yōu)先級(jí)為
stop_sched_class -> dl_sched_class -> rt_sched_class -> fair_sched_class -> idle_sched_class

三個(gè)調(diào)度實(shí)體

調(diào)度器不只限于調(diào)度進(jìn)程，還可以實(shí)現(xiàn)組調(diào)度：可用的CPU時(shí)間現(xiàn)在進(jìn)程組之間分配，再由進(jìn)程組在組內(nèi)二次分配
這就要求調(diào)度器不直接操作進(jìn)程，而是處理可調(diào)度實(shí)體
這個(gè)調(diào)度實(shí)體可以是一個(gè)進(jìn)程，也可以是一個(gè)進(jìn)程組，用一個(gè)通用的數(shù)據(jù)結(jié)構(gòu)來描述這個(gè)調(diào)度實(shí)體，下面是三種用于描述的調(diào)度實(shí)體

競(jìng)爭(zhēng)條件和實(shí)現(xiàn)方式討論

<font color= "#0099ff">
臨界資源：該資源同一時(shí)間只能由一個(gè)進(jìn)程使用（進(jìn)程間不共享，如打印機(jī)）但是是共享資源，其他進(jìn)程也可以用，只是不能同時(shí)用
臨界區(qū)：訪問臨界資源的一段代碼
競(jìng)爭(zhēng)條件：兩個(gè)進(jìn)程訪問同一個(gè)共享資源區(qū)，當(dāng)一個(gè)進(jìn)程先占用該資源區(qū)之后，其他進(jìn)程無法訪問該資源區(qū)。
</font>

進(jìn)程間關(guān)系

• 互斥 不能同時(shí)使用，兩個(gè)毫不相關(guān)的進(jìn)程可能會(huì)因?yàn)閾屨纪毁Y源而發(fā)生關(guān)系
• 同步 兩個(gè)進(jìn)程之間在邏輯上存在先后關(guān)系，一個(gè)進(jìn)程由于邏輯上等待另一個(gè)進(jìn)程而發(fā)生關(guān)系

進(jìn)程間其實(shí)就這兩種基本關(guān)系，之后我們?cè)诳紤]IPC問題的時(shí)候，首先就要分析進(jìn)程之間是這兩種關(guān)系當(dāng)中的哪一種，然后再設(shè)計(jì)金成問題的解決方案。

實(shí)現(xiàn)方案討論

解決方案應(yīng)該滿足的原則

• 任何兩個(gè)進(jìn)程不能同時(shí)處于臨界區(qū)
• 不應(yīng)對(duì)CPU的速度和數(shù)量做任何假設(shè)
• 臨界區(qū)外的進(jìn)程不得阻塞其他進(jìn)程
• 不得使進(jìn)程無限期的等待進(jìn)入臨界區(qū)

屏蔽中斷

首先我們要清楚什么是中斷，中斷是cpu產(chǎn)生的用于暫停一個(gè)進(jìn)程的運(yùn)行，并且開啟另一個(gè)線程的運(yùn)行的指令。
屏蔽掉中斷之后一個(gè)進(jìn)程就會(huì)持續(xù)運(yùn)行而不受CPu的管制，直到該進(jìn)程放棄對(duì)CPu的占用。
通常情況下我們都不會(huì)屏蔽掉中斷，我們也不會(huì)把屏蔽中斷的權(quán)利交給普通的用戶進(jìn)程，因?yàn)檫@樣可能會(huì)導(dǎo)致用戶持續(xù)占用CPU。
但是在這里，我們假設(shè)我們的普通進(jìn)程也可以屏蔽中斷。這樣我們就可以完美解決資源同時(shí)使用的問題。
但是把屏蔽中斷的能力交個(gè)普通進(jìn)程簡(jiǎn)直就是傻屌操作。

鎖變量

這個(gè)時(shí)候我們想到我們用一個(gè)變量a，來表示該資源是否被占用，這樣我們只需要在需要使用資源的時(shí)候查詢a變量的狀態(tài)就可以了。
看起來天衣無縫，但是我們考慮一下情況。
進(jìn)程1先查詢了鎖變量，鎖變量顯示無人使用資源，
突然CPU開始執(zhí)行進(jìn)程2，進(jìn)程2也開始查詢，鎖變量顯示資源無人使用，然后進(jìn)程2把鎖變量置為1，并且使用了資源。
在進(jìn)程2還沒有放棄使用資源的時(shí)候，cpu開始執(zhí)行了進(jìn)程1，進(jìn)程一并不知道自己剛才睡著了，直接就去使用了資源。
在這種情況下雖然設(shè)置了鎖變量，但是還是存在兩個(gè)進(jìn)程同時(shí)使用資源的情況。

嚴(yán)格輪轉(zhuǎn)法

上面的嘗試解決方法因?yàn)闆]有明確誰可以使用資源，誰不能使用資源產(chǎn)生了沖突。
嚴(yán)格輪轉(zhuǎn)法維護(hù)了一個(gè)數(shù)組，需要使用該資源的進(jìn)程pid存入數(shù)組，使用完資源的進(jìn)程pid移除數(shù)組。
之后鎖變量按照數(shù)組中的pid嚴(yán)格輪轉(zhuǎn)，如何嚴(yán)格輪轉(zhuǎn)呢？
假如說數(shù)組中的進(jìn)程有，1，2，3，資源的使用順序就按照1，2，3循環(huán)，每個(gè)進(jìn)程使用一段時(shí)間，直到有進(jìn)程執(zhí)行完他要執(zhí)行的任務(wù)。
但是！
這種方法也有他的缺點(diǎn)，假如說輪到2進(jìn)程使用資源，但是2進(jìn)程在等待另外一個(gè)資源的釋放，結(jié)果2進(jìn)程就等著另一個(gè)資源，這個(gè)時(shí)候1，3進(jìn)程也得跟著一起等，因?yàn)?進(jìn)程不用，也輪不到他倆用，于是違反了** 臨界區(qū)外的進(jìn)程不得阻塞其他進(jìn)程 **的規(guī)則。導(dǎo)致這個(gè)資源雖然
很搶手，但是也一直沒人能使用該資源。
<font color = "#0099ff">補(bǔ)充兩個(gè)定義
忙等待：連續(xù)測(cè)試一個(gè)變量值知道某個(gè)值出現(xiàn)為止，例如上面出現(xiàn)的1，3進(jìn)程一直在查詢鎖變量是否到他們可以用的時(shí)候了。
自旋鎖：用于忙等待的鎖，稱為自旋鎖</font>

最終解決方案

信號(hào)量

信號(hào)量S表示一個(gè)資源被使用的情況，一個(gè)資源的份數(shù)是S的最大值，S的實(shí)際值表示現(xiàn)在有多少資源剩余.
而且信號(hào)量當(dāng)中維護(hù)了一個(gè)存儲(chǔ)等待使用資源的隊(duì)列。當(dāng)V原語喚醒的時(shí)候就會(huì)從這個(gè)隊(duì)列中尋找激活誰。
對(duì)信號(hào)量的操作只有PV原語可以
當(dāng)我們不需要信號(hào)量表示資源數(shù)量的功能的時(shí)候，即資源只有一份的時(shí)候我們使用互斥信號(hào)量。

PV原語

P原語和V原語
P原語是阻塞原語：當(dāng)調(diào)用P原語時(shí)，如果信號(hào)量還有空閑，那么繼續(xù)執(zhí)行，如果信號(hào)量沒有空閑，那么阻塞，直到V原語通知有新的資源可用。
V原語是喚醒原語：如果調(diào)用V原語之后，信號(hào)量不為滿，即還有空位置可以放資源，那么喚醒一個(gè)P原語，如果全部占滿，那么阻塞
其實(shí)PV原語本質(zhì)是代碼執(zhí)行單元，在P原語和V原語的內(nèi)部，在執(zhí)行過程中是不會(huì)被打斷的，所以這彌補(bǔ)了上面嘗試的方法中鎖變量的缺點(diǎn)。
PV原語代碼。

P (Semaphore s)
{
    s=s-1;
    if (s<0)
    {
        added to the semaphore's queue and sleep;
    }
}

V (Semaphore s)
{
    s=s+1;
    if (s<=0)
    {
        wakeup the waiting process in the semaphore's queue;
    }
}

PV原語的使用

實(shí)現(xiàn)過程：
P(resource); // resource的初始值為該資源的個(gè)數(shù)N
使用該資源；
V(resource);
非臨界區(qū)

IPC問題

我們上面討論了一堆如何解決進(jìn)程間同步和使用互斥資源的解決方案，但是我們?cè)趯?shí)際當(dāng)中都會(huì)遇到哪些問題呢？
接下來這部分我們討論的是如何解決IPC問題即（I）進(jìn)程間通信問題

生產(chǎn)者消費(fèi)者問題

問題描述

一組生產(chǎn)者進(jìn)程和一組消費(fèi)者進(jìn)程共享一個(gè)初始為空、大小為n的緩沖區(qū)，只有緩沖區(qū)沒滿時(shí)，生產(chǎn)者才能把消息放入到緩沖區(qū)，否則必須等待；只有緩沖區(qū)不空時(shí)，消費(fèi)者才能從中取出消息，否則必須等待。由于緩沖區(qū)是臨界資源，它只允許一個(gè)生產(chǎn)者放入消息，或者一個(gè)消費(fèi)者從中取出消息。

問題分析

生產(chǎn)者和消費(fèi)者不能同時(shí)訪問臨界區(qū)，這是互斥關(guān)系
只有當(dāng)生產(chǎn)者生產(chǎn)出來產(chǎn)品之后，消費(fèi)者才能購(gòu)買，這說明兩者之間還有同步關(guān)系。

解決代碼

用兩對(duì)PV原語去解決問題，一組申請(qǐng)臨界區(qū)資源，一組申請(qǐng)單獨(dú)訪問權(quán)限

semaphore mutex=1; //臨界區(qū)互斥信號(hào)量
semaphore empty=n;  //空閑緩沖區(qū)
semaphore full=0;  //緩沖區(qū)初始化為空
producer () { //生產(chǎn)者進(jìn)程
    while(1){
        produce an item in nextp;  //生產(chǎn)數(shù)據(jù)
        P(empty);  //獲取空緩沖區(qū)單元
        P(mutex);  //進(jìn)入臨界區(qū).
        add nextp to buffer;  //將數(shù)據(jù)放入緩沖區(qū)
        V(mutex);  //離開臨界區(qū),釋放互斥信號(hào)量
        V(full);  //滿緩沖區(qū)數(shù)加1
    }
}

consumer () {  //消費(fèi)者進(jìn)程
    while(1){
        P(full);  //獲取滿緩沖區(qū)單元
        P(mutex);  // 進(jìn)入臨界區(qū)
        remove an item from buffer;  //從緩沖區(qū)中取出數(shù)據(jù)
        V (mutex);  //離開臨界區(qū)，釋放互斥信號(hào)量
        V (empty) ;  //空緩沖區(qū)數(shù)加1
        consume the item;  //消費(fèi)數(shù)據(jù)
    }
}

哲學(xué)家就餐問題

問題描述

一張圓桌上坐著5名哲學(xué)家，每?jī)蓚€(gè)哲學(xué)家之間的桌上擺一根筷子，桌子的中間是一碗米飯，如圖所示。哲學(xué)家們傾注畢生精力用于思考和進(jìn)餐，哲學(xué)家在思考時(shí)，并不影響他人。只有當(dāng)哲學(xué)家饑餓的時(shí)候，才試圖拿起左、 右兩根筷子（一根一根地拿起）。如果筷子已在他人手上，則需等待。饑餓的哲學(xué)家只有同時(shí)拿到了兩根筷子才可以開始進(jìn)餐，當(dāng)進(jìn)餐完畢后，放下筷子繼續(xù)思考。

問題分析

同一個(gè)哲學(xué)家必須同時(shí)有能拿到左右兩側(cè)的筷子的權(quán)限，再拿起，如果只有一側(cè)，那么先不拿起。
下面的這種實(shí)現(xiàn)方法在同一時(shí)間只有一個(gè)哲學(xué)家在嘗試拿筷子。雖然造成了一定程度上的性能浪費(fèi)。
哲學(xué)家的左右筷子具有同步性，哲學(xué)家與哲學(xué)家之間具有互斥性。

解決代碼

semaphore chopstick[5] = {1,1,1,1,1}; //初始化信號(hào)量
semaphore mutex=1; //設(shè)置取筷子的信號(hào)量
Pi(){ //i號(hào)哲學(xué)家的進(jìn)程
while(1)
{
P (mutex) ; //在取筷子前獲得互斥量 通過這一步使取左右筷子時(shí)不會(huì)被其他人打斷，如果只有取左右筷子的代碼，很容易發(fā)生死鎖。
P (chopstick [i]) ; //取左邊筷子
P (chopstick[ (i+1) %5]) ; //取右邊筷子
V (mutex) ; //釋放取筷子的信號(hào)量
eat; //進(jìn)餐
V(chopstick[i] ) ; //放回左邊筷子
V(chopstick[ (i+l)%5]) ; //放回右邊筷子
think; // 思考
}
}

讀者寫者問題

問題描述

一個(gè)作者在寫的時(shí)候，讀者不能讀，其他作者不能寫
讀者在讀的時(shí)候作者不能寫，但是其他讀者也可以讀。

問題分析

作者和讀者以及作者和作者之間都是互斥且同步的關(guān)系.
讀者和讀者之間沒有關(guān)系。

解決代碼

Semaphore mutex, wrt=1,1;
int readcount=0;
void Writer(void)
{
    Down(wrt);
    Perform writing;
    Up(wrt);
}
void Reader(void)
{
    Down(mutex);    //這個(gè)防止了兩個(gè)Reader同時(shí)給wrt加鎖的問題。
    readcount=readcount+1;
    if(readcount == 1)
        Down(wrt);    //這解決了與讀者之間的互斥關(guān)系。
    Up(mutex);
    Perform reading;
    Down(mutex);
    readcount=readcount-1;
    if(readcount == 0)
        Up(wrt);
    Up(mutex);
}

睡眠的理發(fā)師問題

問題描述

1、5把供顧客等候的椅子
2、一個(gè)理發(fā)師同時(shí)只能給一個(gè)顧客理發(fā)
3、沒有顧客，理發(fā)師進(jìn)入睡眠狀態(tài)。

問題分析

顧客和顧客之間是互斥的
只有一個(gè)理發(fā)師，理發(fā)師的資源是1
理發(fā)師和顧客的關(guān)系是同步。

解決代碼

int waiting=0 ； //等候理發(fā)的顧客數(shù)
int chairs=n； //為顧客準(zhǔn)備的椅子數(shù)
semaphore customers=0, barbers=0,mutex=1;
barber()
{
while(TRUE); //理完一人,還有顧客嗎?
P(cutomers); //若無顧客,理發(fā)師睡眠
P(mutex); //進(jìn)程互斥
waiting := waiting – 1; //等候顧客數(shù)少一個(gè)
V(barbers); //理發(fā)師去為一個(gè)顧客理發(fā)
V(mutex); //開放臨界區(qū)
cut-hair( ); //正在理發(fā)}
customer()
{
P(mutex); //進(jìn)程互斥
if (waiting)
{ waiting := waiting+1; // 等候顧客數(shù)加1
V(customers); //必要的話喚醒理發(fā)師
V(mutex); //開放臨界區(qū)
P(barbers); //無理發(fā)師, 顧客坐著養(yǎng)神
get-haircut( ); //一個(gè)顧客坐下等理/ }
else
V(mutex); //人滿了,走吧!}