北京理工大學(xué)-計(jì)算機(jī)學(xué)院-計(jì)算機(jī)專(zhuān)業(yè)-大三-《操作系統(tǒng)》課件-第7-8章Linux進(jìn)程管理

1、1第7章 Linux進(jìn)程管理2 現(xiàn)代操作系統(tǒng)允許一個(gè)進(jìn)程有多個(gè)執(zhí)行流，即在相同的地址空間中可執(zhí)行多個(gè)指令序列。每個(gè)執(zhí)行流用一個(gè)線(xiàn)程表示，一個(gè)進(jìn)程可以有多個(gè)線(xiàn)程。Linux使用輕量級(jí)進(jìn)程實(shí)現(xiàn)對(duì)多線(xiàn)程應(yīng)用程序的支持，一個(gè)輕量級(jí)進(jìn)程就是一個(gè)線(xiàn)程。37.1 Linux進(jìn)程組成在用戶(hù)態(tài)運(yùn)行時(shí)，進(jìn)程映像包含代碼段、數(shù)據(jù)段、堆、用戶(hù)棧。進(jìn)程在核心態(tài)運(yùn)行時(shí)，訪(fǎng)問(wèn)內(nèi)核的代碼段和數(shù)據(jù)段，并使用各自的核心棧。進(jìn)程描述符（task_struct）：描述進(jìn)程的數(shù)據(jù)結(jié)構(gòu)。 P1464task_structthread_info當(dāng)前進(jìn)程基本信息mm_struct指向進(jìn)程的虛擬內(nèi)存描述符thread_struct保存進(jìn)程硬件

2、上下文files_struct指向該進(jìn)程打開(kāi)文件信息signal_struct所接收的信號(hào)tgid線(xiàn)程組標(biāo)識(shí)符，線(xiàn)程組領(lǐng)頭進(jìn)程的PID5進(jìn)程核心棧0 x015fbfff0 x015fb0000 x015fa8780 x015fa0340 x015fa000thread_info結(jié)構(gòu)thread_info進(jìn)程描述符(task_struct)核心棧esptask占用兩個(gè)連續(xù)物理頁(yè)框 進(jìn)程核心棧、thread_info結(jié)構(gòu)和進(jìn)程描述符之間的關(guān)系6 由于esp寄存器存放的是核心棧的棧頂指針，內(nèi)核很容易從esp寄存器的值獲得正在CPU上運(yùn)行進(jìn)程的thread_info結(jié)構(gòu)的地址。進(jìn)而獲得進(jìn)程描述符（PC

3、B）的地址。進(jìn)程剛從用戶(hù)態(tài)切換到核心態(tài)時(shí)，其核心棧為空，只要將棧頂指針減去8k，就能得到thread_info結(jié)構(gòu)的地址。7 進(jìn)程的狀態(tài)可運(yùn)行狀態(tài)：進(jìn)程正在或準(zhǔn)備在CPU上運(yùn)行的狀態(tài)?？芍袛嗟牡却隣顟B(tài)：進(jìn)程睡眠等待系統(tǒng)資源可用或收到一個(gè)信號(hào)后，進(jìn)程被喚醒。 不可中斷的等待狀態(tài)：進(jìn)程睡眠等待一個(gè)不能被中斷的事件發(fā)生。如進(jìn)程等待設(shè)備驅(qū)動(dòng)程序探測(cè)設(shè)備的狀態(tài)。暫停狀態(tài)；跟蹤狀態(tài) ；僵死狀態(tài) ；死亡狀態(tài) 87.2 Linux進(jìn)程鏈表傳統(tǒng)進(jìn)程鏈表 所有進(jìn)程鏈表：鏈表頭是0號(hào)進(jìn)程 可運(yùn)行進(jìn)程鏈表：按照它們的優(yōu)先級(jí)可構(gòu)建140個(gè)可運(yùn)行進(jìn)程隊(duì)列。子進(jìn)程鏈表 兄弟進(jìn)程鏈表等待進(jìn)程鏈表?；コ獾却L(fǎng)問(wèn)臨界資源的進(jìn)程；

4、非互斥等待的進(jìn)程，所有進(jìn)程都被喚醒。9PID哈希表（為了加速對(duì)進(jìn)程的檢索）PID TGID PGID SID 0 1 2 3pid_hashTGID表 0 70 2047nr=4351pid_chainpid_listpids1進(jìn)程描述符nr=4351pid_chainpid_listpids1進(jìn)程描述符nr=4351pid_chainpid_listpids1進(jìn)程描述符線(xiàn)程組鏈表同一哈希表項(xiàng)的進(jìn)程鏈 表nr：線(xiàn)程組號(hào)，即線(xiàn)程組領(lǐng)頭進(jìn)程的PID pid_chain：鏈接同一哈希表項(xiàng)的進(jìn)程PID；進(jìn)程pidTGID：線(xiàn)程組領(lǐng)頭進(jìn)程的pidPGID：進(jìn)程組領(lǐng)頭進(jìn)程的pidSID：會(huì)話(huà)領(lǐng)頭進(jìn)程的pi

5、dnr=246pid_chainpid_listpids1進(jìn)程描述符107.3 Linux進(jìn)程控制創(chuàng)建進(jìn)程的函數(shù)fork()、clone()、vfork()。創(chuàng)建子進(jìn)程函數(shù)fork()：創(chuàng)建成功之后，子進(jìn)程采用寫(xiě)時(shí)復(fù)制技術(shù)讀共享父進(jìn)程的全部地址空間，僅當(dāng)父或子要寫(xiě)一個(gè)頁(yè)時(shí)，才為其復(fù)制一個(gè)私有的頁(yè)的副本。創(chuàng)建輕量級(jí)進(jìn)程函數(shù)clone()：實(shí)現(xiàn)對(duì)多線(xiàn)程應(yīng)用程序的支持。共享進(jìn)程在內(nèi)核的很多數(shù)據(jù)結(jié)構(gòu)，如頁(yè)表、打開(kāi)文件表等等。vfork()：阻塞父進(jìn)程直到子進(jìn)程退出或執(zhí)行了一個(gè)新程序?yàn)橹埂?10號(hào)、 1號(hào)0號(hào)進(jìn)程就是一個(gè)內(nèi)核線(xiàn)程，0號(hào)進(jìn)程是所有進(jìn)程的祖先進(jìn)程，又叫idle進(jìn)程或叫做swapper進(jìn)程。每

6、個(gè)CPU都有一個(gè)0號(hào)進(jìn)程。 1號(hào)進(jìn)程是由0號(hào)進(jìn)程創(chuàng)建的內(nèi)核線(xiàn)程init，負(fù)責(zé)完成內(nèi)核的初始化工作。在系統(tǒng)關(guān)閉之前，init進(jìn)程一直存在，它負(fù)責(zé)創(chuàng)建和監(jiān)控在操作系統(tǒng)外層執(zhí)行的所有用戶(hù)態(tài)進(jìn)程。12進(jìn)程撤銷(xiāo)exit()系統(tǒng)調(diào)用只終止某一個(gè)線(xiàn)程。exit_group()系統(tǒng)調(diào)用能終止整個(gè)線(xiàn)程組。父進(jìn)程先結(jié)束的子進(jìn)程會(huì)成為孤兒進(jìn)程，系統(tǒng)會(huì)強(qiáng)迫所有的孤兒進(jìn)程成為init進(jìn)程的子進(jìn)程。Init進(jìn)程在用wait()類(lèi)系統(tǒng)調(diào)用檢查并終止子進(jìn)程時(shí)，就會(huì)撤銷(xiāo)所有僵死的子進(jìn)程。137.4 Linux進(jìn)程切換進(jìn)程切換只發(fā)生在核心態(tài)。在發(fā)生進(jìn)程切換之前，用戶(hù)態(tài)進(jìn)程使用的所有寄存器值都已被保存在進(jìn)程的核心棧中。之后大部分寄

7、存器值存放在PCB的類(lèi)型為thread_struct的 thread字段（進(jìn)程硬件上下文P147）里，一小部分仍在核心棧中。進(jìn)程切換：第一步，切換頁(yè)目錄表以安裝一個(gè)新的地址空間；第二步，切換核心棧和硬件上下文。由schedule()函數(shù)完成進(jìn)程切換。P155147.5 Linux進(jìn)程調(diào)度系統(tǒng)采用可搶先式的動(dòng)態(tài)優(yōu)先級(jí)調(diào)度方式。無(wú)論進(jìn)程處于用戶(hù)態(tài)還是核心態(tài)運(yùn)行，都可能被搶占CPU。進(jìn)程調(diào)度類(lèi)型：先進(jìn)先出的實(shí)時(shí)進(jìn)程、時(shí)間片輪轉(zhuǎn)的實(shí)時(shí)進(jìn)程、普通的分時(shí)進(jìn)程。實(shí)時(shí)進(jìn)程的基本優(yōu)先數(shù)為199，而分時(shí)進(jìn)程和批處理進(jìn)程的基本優(yōu)先數(shù)為100139。15進(jìn)程調(diào)度所涉及的數(shù)據(jù)結(jié)構(gòu)每個(gè)處理機(jī)都有自己的可運(yùn)行進(jìn)程隊(duì)列，存放

8、在一維數(shù)組runqueues中。每個(gè)處理機(jī)對(duì)應(yīng)數(shù)組中的一項(xiàng)。P157-158活動(dòng)進(jìn)程鏈表：沒(méi)有用完自己的時(shí)間片。過(guò)期進(jìn)程鏈表：已經(jīng)用完了自己的時(shí)間片。當(dāng)活動(dòng)進(jìn)程都過(guò)期后，過(guò)期進(jìn)程才可運(yùn)行。避免低優(yōu)先級(jí)進(jìn)程沒(méi)有機(jī)會(huì)運(yùn)行（進(jìn)程饑餓）?；顒?dòng)進(jìn)程有140個(gè)優(yōu)先級(jí)隊(duì)列，和隊(duì)列位圖。過(guò)期進(jìn)程也有140個(gè)優(yōu)先級(jí)隊(duì)列，和隊(duì)列位圖。167.6 內(nèi)核同步UNIX內(nèi)核的各個(gè)組成部分并不是嚴(yán)格按照順序依次執(zhí)行的，而是采用交錯(cuò)方式執(zhí)行的，以響應(yīng)來(lái)自運(yùn)行進(jìn)程的請(qǐng)求和來(lái)自外部設(shè)備的中斷請(qǐng)求?；コ庠L(fǎng)問(wèn)內(nèi)核共享數(shù)據(jù)結(jié)構(gòu)。內(nèi)核使用的同步技術(shù)包括：每CPU變量、原子操作、優(yōu)化和內(nèi)存屏障、自旋鎖、讀拷貝更新、信號(hào)量、禁止本地中斷、禁

9、止和激活可延遲函數(shù)。17第8章 Linux 存儲(chǔ)器管理 北京理工大學(xué)計(jì)算機(jī)學(xué)院188.1 進(jìn)程地址空間的管理32位機(jī)，每個(gè)進(jìn)程的地址空間為4GB。進(jìn)程的私有地址空間是前3G，進(jìn)程的公有地址空間是后1G的內(nèi)核虛空間。內(nèi)核1GB虛空間中的前896MB用來(lái)映射物理內(nèi)存的前896MB，因此前896MB的內(nèi)存物理地址等于內(nèi)核虛地址減去0 xc0000000。后128MB的虛空間實(shí)現(xiàn)對(duì)超過(guò)896MB的物理內(nèi)存的映射。198.1.2 虛擬內(nèi)存區(qū)域需用一組虛擬內(nèi)存區(qū)域描述符vm_area_struct來(lái)描述進(jìn)程地址空間的使用情況。類(lèi)似于Windows的虛擬地址描述符VAD20vm_area_struct P1

10、65struct vm_area_struct struct mm_struct * vm_mm; 虛擬內(nèi)存描述符unsigned long vm_start; /*起始地址*/unsigned long vm_end; /*結(jié)束地址*/struct vm_area_struct *vm_next; /*單鏈表*/struct rb_node vm_rb; /*紅-黑樹(shù)*/struct file * vm_file; 映射文件時(shí)指向文件對(duì)象21紅黑樹(shù)紅黑樹(shù)是一棵排好序的平衡二叉樹(shù)。必須滿(mǎn)足四條規(guī)則：樹(shù)中的每個(gè)節(jié)點(diǎn)或?yàn)榧t或?yàn)楹?；?shù)的根節(jié)點(diǎn)必須為黑；紅節(jié)點(diǎn)的孩子必須為黑；從一個(gè)節(jié)點(diǎn)到后代諸葉子節(jié)點(diǎn)

11、的每條路經(jīng)，都包含相同數(shù)量的黑節(jié)點(diǎn)，在統(tǒng)計(jì)黑節(jié)點(diǎn)個(gè)數(shù)時(shí)，空指針也算作黑節(jié)點(diǎn)。這四條規(guī)則保證：具有n個(gè)節(jié)點(diǎn)的紅黑樹(shù)，其高度至多為2*log(n+1)。22紅黑樹(shù)502010(a)紅節(jié)點(diǎn)黑節(jié)點(diǎn)806550(b)10515407020907090805154023紅黑樹(shù)050208010400070090000rb_parentvm_startrb_leftrb_rightvm_nextmm_rbmmap65001500500單鏈表紅黑樹(shù)圖中的各節(jié)點(diǎn)描述248.1.3 虛擬內(nèi)存描述符struct task_struct / PCB struct mm_struct *mm; 25mm_struct

12、P168struct mm_struct struct vm_area_struct *mmap; struct rb_root mm_rb; /*指向紅-黑樹(shù)的根*/pgd_t *pgd; /*指向頁(yè)目錄表*/atomic_t mm_users; /*次使用計(jì)數(shù)器*/atomic_t mm_count; /*主使用計(jì)數(shù)器*/struct list_head mmlist; 雙向鏈表unsigned long start_code, end_code; /*可執(zhí)行代碼所占用的地址區(qū)間*/;26主、次使用計(jì)數(shù)器mm_users記錄共享mm_struct的輕量級(jí)進(jìn)程數(shù)。內(nèi)核線(xiàn)程不擁有mm_stru

13、ct 。若把mm_struct暫時(shí)借給一個(gè)內(nèi)核線(xiàn)程使用，則mm_count值增1。進(jìn)程結(jié)束，mm_users和mm_count都為0時(shí)，這個(gè)mm_struct才能被釋放。278.2 物理內(nèi)存管理頁(yè)框0由BIOS使用，存放加電自檢期間檢查到的系統(tǒng)硬件配置。從0 x000a0000到0 x000fffff的物理地址通常留給BIOS例程。Linux跳過(guò)RAM的第一個(gè)MB的空間。頁(yè)框大小為4KB。所有頁(yè)框描述符struct page存放在mem_map數(shù)組中。28頁(yè)框描述符 P171struct page unsigned long flags; /*頁(yè)框狀態(tài)標(biāo)志P172*/atomic_t _cou

14、nt; /*頁(yè)框的引用計(jì)數(shù)*/atomic_t _mapcount; /*對(duì)應(yīng)的頁(yè)表項(xiàng)數(shù)目*/unsigned long private; /*空閑時(shí)由伙伴系統(tǒng)使用*/struct address_space *mapping;用于頁(yè)高速緩存pgoff_t index; 在頁(yè)高速緩存中以頁(yè)為單位偏移struct list_head lru; 鏈入活動(dòng)頁(yè)框鏈表或非活動(dòng).void *virtual; /*頁(yè)框所映射的內(nèi)核虛地址*/; P17129mappingmapping字段的結(jié)構(gòu)類(lèi)型為address_space，它是頁(yè)高速緩存的核心數(shù)據(jù)結(jié)構(gòu)，和文件的inode結(jié)構(gòu)有關(guān)聯(lián)。屬于同一個(gè)文件的緩存頁(yè)

15、被鏈入同一個(gè)address_space對(duì)象中。圖11.3 實(shí)現(xiàn)文件內(nèi)存映射的各數(shù)據(jù)結(jié)構(gòu)之間的關(guān)系address_space對(duì)象inode對(duì)象file對(duì)象structpagestructpagestructpagestructvm_area_structfile對(duì)象i_mapping頁(yè)框f_mapping頁(yè)框頁(yè)框f_mappingpage_treei_mmap文件映像vm_filevm_filevm_pgoffvm_pgoffmappingindexmappingindexindexhoststructvm_area_struct31內(nèi)存的3個(gè)管理區(qū)Linux把內(nèi)存劃分為3個(gè)管理區(qū)zone。 Z

16、ONE_DMA：包含低于16MB的常規(guī)內(nèi)存頁(yè)框。用于對(duì)老式的基于ISA設(shè)備的DMA支持。ZONE_NORMAL：包含高于16MB且低于896MB的常規(guī)內(nèi)存頁(yè)框。ZONE_HIGHMEM：包含從896MB開(kāi)始的高端物理頁(yè)框。內(nèi)核不能直接訪(fǎng)問(wèn)這部分頁(yè)框。在64位體系結(jié)構(gòu)上，該區(qū)總是空的。32內(nèi)存區(qū)描述符 P173struct zone unsigned long free_pages; 空閑頁(yè)框數(shù)struct per_cpu_pageset pagesetNR_CPUS;/*每CPU頁(yè)框高速緩存,以滿(mǎn)足CPU對(duì)單個(gè)頁(yè)框的請(qǐng)求*/struct free_area free_area11; /*伙伴系

17、統(tǒng)中的11個(gè)空閑頁(yè)框鏈表*/struct list_head active_list; /*活動(dòng)頁(yè)框鏈表，存放最近正被訪(fǎng)問(wèn)的頁(yè)框*/ struct list_head inactive_list; /*非活動(dòng)頁(yè)框鏈表，存放最近未被訪(fǎng)問(wèn)的頁(yè)框*/.;33 頁(yè)框分配器負(fù)責(zé)處理對(duì)連續(xù)物理頁(yè)框的分配請(qǐng)求?；锇樗惴ò芽臻e頁(yè)框組織成11個(gè)鏈表，分別鏈有大小為1，2，4，8，16，32，64，128，256，512和1024個(gè)連續(xù)空閑頁(yè)框。 34伙伴系統(tǒng)lruprivate=312481632641282565121024lru起始頁(yè)框描述符private=3lru起始頁(yè)框描述符private=335伙伴系

18、統(tǒng)假設(shè)要請(qǐng)求一個(gè)具有8個(gè)連續(xù)頁(yè)框的塊，該算法先在8個(gè)連續(xù)頁(yè)框塊的鏈表中檢查是否有，如果沒(méi)有，就在16個(gè)連續(xù)頁(yè)框塊的鏈表中找，如果找到，就把這16個(gè)連續(xù)頁(yè)框分成兩等份，一份用來(lái)滿(mǎn)足請(qǐng)求，另一份插入到具有8個(gè)連續(xù)頁(yè)框塊的鏈表中；如果在16個(gè)連續(xù)頁(yè)框塊的鏈表中沒(méi)有找到，就在更大的塊鏈表中查找。直到找到為止。368.3 slab管理伙伴系統(tǒng)以頁(yè)框?yàn)閱挝唬m合于對(duì)大塊內(nèi)存的分配請(qǐng)求。slab分配器為只有幾十或幾百個(gè)字節(jié)的小內(nèi)存區(qū)分配內(nèi)存。如，file對(duì)象。37slab分配器從頁(yè)框分配器獲得幾組連續(xù)空閑頁(yè)框slab分配器為不同類(lèi)型的對(duì)象生成不同的高速緩存，每個(gè)高速緩存存儲(chǔ)相同類(lèi)型的對(duì)象。高速緩存由一連串的slab構(gòu)成，每個(gè)slab包含了若干個(gè)同類(lèi)型的對(duì)象。對(duì)象slab對(duì)象slab高速緩存高速緩存388.5 地址轉(zhuǎn)換32位處理機(jī)普遍采用二級(jí)頁(yè)表模式，為每個(gè)進(jìn)程分配一個(gè)頁(yè)目錄表，頁(yè)表一直推遲到訪(fǎng)問(wèn)頁(yè)時(shí)才建立，以節(jié)約內(nèi)存。 虛地址分成3個(gè)域：頁(yè)目錄索引（前10位）、頁(yè)表索引（中10位）和頁(yè)內(nèi)偏移（后12位）。Linux系統(tǒng)的頁(yè)目錄項(xiàng)和頁(yè)表項(xiàng)的數(shù)據(jù)結(jié)構(gòu)相同。 頁(yè)目錄表頁(yè)框頁(yè)表Cr33122 21012 11虛擬地址OffsetTableDirect