一.進(jìn)程的基本概念

• 馮諾依曼體系的計(jì)算機(jī)在運(yùn)行時(shí),內(nèi)存中會(huì)預(yù)加載許多程序(數(shù)據(jù)+運(yùn)算指令集),然而CPU同一時(shí)刻只能執(zhí)行一個(gè)程序(多個(gè)程序競(jìng)爭(zhēng)CPU資源),此時(shí)就需要操作系統(tǒng)對(duì)內(nèi)存中的諸多程序進(jìn)行管理,讓CPU資源得到合理的分配,于是便有了進(jìn)程的概念:

  • 進(jìn)程:描述程序的結(jié)構(gòu)體對(duì)象(PCB結(jié)構(gòu)體)和其所指向的程序(數(shù)據(jù)與運(yùn)算指令集)
  • 在Linux中PCB結(jié)構(gòu)體被命名為task_struct

• 進(jìn)程的PCB結(jié)構(gòu)體在操作系統(tǒng)中會(huì)被組織進(jìn)各種數(shù)據(jù)結(jié)構(gòu),同一個(gè)PCB結(jié)構(gòu)體對(duì)象會(huì)同時(shí)位于多個(gè)數(shù)據(jù)結(jié)構(gòu)中,比如：

• 操作系統(tǒng)對(duì)進(jìn)程進(jìn)行管理是通過(guò)對(duì)PCB結(jié)構(gòu)體對(duì)象形成的數(shù)據(jù)結(jié)構(gòu)進(jìn)行增刪查改實(shí)現(xiàn)的

• Linux中進(jìn)程的PCB通過(guò)PID(一個(gè)數(shù)字)唯一地標(biāo)識(shí):

進(jìn)程間的基本關(guān)系:父子關(guān)系

• Linux系統(tǒng)中,一個(gè)進(jìn)程可以通過(guò)庫(kù)函數(shù)fork()創(chuàng)建子進(jìn)程
  • pid_t fork(void);
  • 一個(gè)進(jìn)程通過(guò)fork函數(shù)創(chuàng)建子進(jìn)程后,父子進(jìn)程共享fork()函數(shù)所在的代碼語(yǔ)句以及其后的代碼段
  • fork函數(shù)返回值說(shuō)明:若子進(jìn)程創(chuàng)建成功,frok函數(shù)在父進(jìn)程中返回子進(jìn)程的PID,在子進(jìn)程中返回0,若子進(jìn)程創(chuàng)建失敗,則fork函數(shù)在父進(jìn)程中返回-1
  • 子進(jìn)程剛被創(chuàng)建時(shí),會(huì)共享父進(jìn)程的所有數(shù)據(jù),后續(xù)子進(jìn)程對(duì)于父進(jìn)程的數(shù)據(jù)會(huì)進(jìn)行寫(xiě)時(shí)拷貝
  • 根據(jù)父子進(jìn)程中fork()返回值的不同,我們便可以令父子進(jìn)程后續(xù)執(zhí)行不同的代碼段

int main()
{
  printf("hello world\n");
  size_t childPid = fork();//創(chuàng)建子進(jìn)程
  if(childPid == 0)
  {
    //子進(jìn)程執(zhí)行的代碼段
    while(1)
    {
       printf("我是子進(jìn)程,Pid:%d,PPid:%d\n",getpid(),getppid());
       sleep(1);
    }
  }
  else
  {
    //父進(jìn)程執(zhí)行的代碼段
    while(1)
    {
       printf("我是父進(jìn)程,Pid:%d,PPid:%d\n",getpid(),getppid());
       sleep(1);
    }
  }

  return 0;
}

• 運(yùn)行狀態(tài):
  
• 一個(gè)父進(jìn)程可以有多個(gè)子進(jìn)程,而一個(gè)子進(jìn)程只有唯一的父進(jìn)程,在操作系統(tǒng)中,依據(jù)父子進(jìn)程的關(guān)系,PCB結(jié)構(gòu)體對(duì)象會(huì)形成一個(gè)樹(shù)形數(shù)據(jù)結(jié)構(gòu)
• 總之,在操作系統(tǒng)中,PCB結(jié)構(gòu)體對(duì)象處于眾多數(shù)據(jù)結(jié)構(gòu)交織成的網(wǎng)中

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

• 進(jìn)程狀態(tài)總覽(Linux操作系統(tǒng)):

(1)進(jìn)程的運(yùn)行狀態(tài)R

• CPU一次只執(zhí)行一個(gè)進(jìn)程,一個(gè)CPU對(duì)應(yīng)唯一一個(gè)運(yùn)行隊(duì)列(Linux中實(shí)質(zhì)上是一個(gè)哈希桶),處于運(yùn)行狀態(tài)的進(jìn)程的PCB結(jié)構(gòu)體會(huì)被鏈入運(yùn)行隊(duì)列中,操作系統(tǒng)會(huì)依次調(diào)度運(yùn)行隊(duì)列中PCB結(jié)構(gòu)體所指向的程序,將其交給CPU執(zhí)行運(yùn)算.
• 進(jìn)程的PCB會(huì)記錄該進(jìn)程的調(diào)度優(yōu)先級(jí)(一個(gè)整數(shù)),進(jìn)程的調(diào)度優(yōu)先級(jí)會(huì)影響其在運(yùn)行隊(duì)列中的位置.
• Linux中的進(jìn)程優(yōu)先級(jí)分為140個(gè)等級(jí),其中0級(jí)到99級(jí)分給實(shí)時(shí)進(jìn)程,100級(jí)到139級(jí)分給非實(shí)時(shí)進(jìn)程
  • 140個(gè)等級(jí)對(duì)應(yīng)140條運(yùn)行隊(duì)列分支(140條運(yùn)行隊(duì)列分支以哈希桶的結(jié)構(gòu)進(jìn)行組合)
  • 進(jìn)程task_struct在運(yùn)行隊(duì)列中的位置由其動(dòng)態(tài)優(yōu)先級(jí)決定

Linux進(jìn)程調(diào)度的大O(1)算法數(shù)據(jù)結(jié)構(gòu)模型(運(yùn)行隊(duì)列哈希桶):

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-618451.html

• 在Linux內(nèi)核中還有一個(gè)160個(gè)比特位大小的位圖用于記錄run哈希桶中的各個(gè)隊(duì)列是否為空,一旦run哈希桶中的隊(duì)列都為空,就交換指向run和tem兩個(gè)數(shù)組的指針,然后繼續(xù)執(zhí)行進(jìn)程調(diào)度
• 得益于上圖所示的數(shù)據(jù)結(jié)構(gòu),Linux操作系統(tǒng)無(wú)須對(duì)各個(gè)task_struct結(jié)構(gòu)體進(jìn)行依據(jù)優(yōu)先級(jí)的快速排序,同時(shí)可以在任意時(shí)刻以O(shè)(1)的時(shí)間復(fù)雜度快速定位某個(gè)優(yōu)先級(jí)的進(jìn)程所在的分支運(yùn)行隊(duì)列(同時(shí)進(jìn)行O(1)的隊(duì)列判空),task_struct結(jié)構(gòu)體對(duì)象的入隊(duì)出隊(duì)操作也是O(1)的時(shí)間復(fù)雜度,實(shí)現(xiàn)了Linux操作系統(tǒng)高效的進(jìn)程調(diào)度機(jī)制

進(jìn)程的運(yùn)行時(shí)間片

• 每個(gè)進(jìn)程都有一個(gè)運(yùn)行時(shí)間片(比如20ns),進(jìn)程的時(shí)間片決定了CPU對(duì)其執(zhí)行運(yùn)算的單次最長(zhǎng)時(shí)間,一個(gè)進(jìn)程在CPU中完成了一個(gè)時(shí)間片的運(yùn)算后就會(huì)暫時(shí)退出運(yùn)行隊(duì)列等待下一次調(diào)度
• 有了時(shí)間片的限制,在一定時(shí)間段內(nèi)(比如20ms),所有在運(yùn)行隊(duì)列中的進(jìn)程都會(huì)被CPU執(zhí)行運(yùn)算一次,形成了進(jìn)程的并發(fā)執(zhí)行,CPU資源因此得到了合理的分配和充分地使用
• 我們感覺(jué)到電腦同時(shí)運(yùn)行著多個(gè)程序,其實(shí)本質(zhì)上是CPU在根據(jù)進(jìn)程時(shí)間片極速地遍歷執(zhí)行著每一個(gè)進(jìn)程而形成的進(jìn)程并發(fā)的結(jié)果.

(2)進(jìn)程的睡眠狀態(tài)(S和D)

• Linux系統(tǒng)中進(jìn)程的睡眠狀態(tài)對(duì)應(yīng)著操作系統(tǒng)學(xué)科理論中的進(jìn)程阻塞狀態(tài)
• CPU的運(yùn)算速度和數(shù)據(jù)流動(dòng)速度是不對(duì)等的,因此進(jìn)行數(shù)據(jù)交互的進(jìn)程時(shí)常會(huì)處于等待反饋信息的狀態(tài)
• 當(dāng)一個(gè)進(jìn)程處在等待某種資源的狀態(tài)時(shí),其PCB結(jié)構(gòu)體就會(huì)退出運(yùn)行隊(duì)列并進(jìn)入到阻塞隊(duì)列中,比如某個(gè)進(jìn)程需要鍵盤(pán)輸入數(shù)據(jù),這時(shí)它就會(huì)進(jìn)入到鍵盤(pán)的阻塞隊(duì)列中
• 操作系統(tǒng)中,阻塞隊(duì)列的數(shù)量是不確定的,系統(tǒng)中有多少種通信過(guò)程,就存在多少種阻塞隊(duì)列:
• Linux中位于阻塞隊(duì)列中的進(jìn)程處于可中斷睡眠狀態(tài)(S狀態(tài)),當(dāng)系統(tǒng)內(nèi)存不足時(shí),操作系統(tǒng)會(huì)將一些處于阻塞隊(duì)列中的進(jìn)程對(duì)應(yīng)的程序(數(shù)據(jù)和指令集)暫時(shí)存放到swap磁盤(pán)分區(qū)中,進(jìn)程進(jìn)入掛起狀態(tài)
• Linux操作系統(tǒng)在內(nèi)存不足時(shí),還會(huì)選擇性地殺死一些位于阻塞隊(duì)列中的進(jìn)程,如果某個(gè)進(jìn)程執(zhí)行的是非常重要的任務(wù)(比如向磁盤(pán)中寫(xiě)入重要數(shù)據(jù)時(shí),等待磁盤(pán)反饋),那么就需要將該進(jìn)程標(biāo)記為不可中斷睡眠狀態(tài)(D狀態(tài)),處于不可中斷睡眠狀態(tài)的進(jìn)程在被執(zhí)行結(jié)束前不會(huì)相應(yīng)操作系統(tǒng)的請(qǐng)求

(3)進(jìn)程的僵尸狀態(tài)和死亡狀態(tài)

• Linux系統(tǒng)中,當(dāng)一個(gè)父進(jìn)程的子進(jìn)程終止時(shí),該子進(jìn)程就會(huì)進(jìn)入僵尸狀態(tài)(Z狀態(tài)),Z狀態(tài)的進(jìn)程會(huì)等待其父進(jìn)程來(lái)回收其PCB結(jié)構(gòu)體中的終止信息(以便判斷它是正常終止還是異常終止),只有當(dāng)父進(jìn)程處理了它的終止信息,子進(jìn)程才會(huì)由Z狀態(tài)進(jìn)入死亡狀態(tài)(X狀態(tài)),這時(shí),操作系統(tǒng)才會(huì)將子進(jìn)程所占用的內(nèi)存資源完全回收
• 如果父進(jìn)程一直不處理僵尸子進(jìn)程的終止信息,那么僵尸子進(jìn)程的PCB結(jié)構(gòu)體以及相關(guān)數(shù)據(jù)就會(huì)一直留在內(nèi)存中,造成內(nèi)存泄漏
• 如果父子進(jìn)程中的父進(jìn)程率先終止了,其子進(jìn)程就會(huì)被托孤給操作系統(tǒng),成為操作系統(tǒng)的子進(jìn)程,這樣的進(jìn)程稱為孤兒進(jìn)程
  

到了這里，關(guān)于操作系統(tǒng)理論:Linux進(jìn)程與進(jìn)程狀態(tài)(進(jìn)程調(diào)度的大O(1)算法數(shù)據(jù)結(jié)構(gòu)模型)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！