操作系統(tǒng)課件：Chapter-02 Processes and Threads

1、1Processes and ThreadsChapter 22.1 Processes2.2 Threads2.3 Interprocess communication2.4 Classical IPC problems2.5 Scheduling2ProcessesThe Process Model Multiprogramming of four programs Conceptual model of 4 independent, sequential processes Only one program active at any instant為了描述程序在并發(fā)執(zhí)行時(shí)對(duì)系統(tǒng)資源的共

2、享，需要一個(gè)描述程序執(zhí)行時(shí)動(dòng)態(tài)特征的概念，這就是進(jìn)程。3多道程序設(shè)計(jì)與進(jìn)程管理 計(jì)算機(jī)中程序運(yùn)行模式的發(fā)展歷程 順序執(zhí)行模式：?jiǎn)蔚莱绦颡?dú)占CPU和其他資源 并發(fā)執(zhí)行模式：兩個(gè)/多個(gè)程序共享CPU和其他資源 多道程序設(shè)計(jì)：并發(fā)模式下的OS設(shè)計(jì)與實(shí)現(xiàn) 程序運(yùn)行模式的特征 順序執(zhí)行模式 順序性、封閉性、獨(dú)占性、確定性（結(jié)果可再現(xiàn)性） 并發(fā)執(zhí)行模式 并發(fā)性、間斷性、共享性、不確定性、獨(dú)立性和制約性 問(wèn)題1：并發(fā)與并行的區(qū)別是什么？ 問(wèn)題2：如何計(jì)算并發(fā)環(huán)境下的計(jì)算機(jī)工作效率？4并行與并發(fā)的概念差別 并行（Parallel） 同一時(shí)刻，兩個(gè)事物均處于活動(dòng)狀態(tài) 示例：CPU中的超流水線設(shè)計(jì)和超標(biāo)量設(shè)計(jì) 并

3、發(fā)（Concurrency） 宏觀上存在并行特征，微觀上存在順序性 同一時(shí)刻，只有一個(gè)事物處于活動(dòng)狀態(tài) 示例：分時(shí)操作系統(tǒng)中多個(gè)程序的同時(shí)運(yùn)行5并發(fā)所帶來(lái)的效率提升6并發(fā)所帶來(lái)的效率提升 順序執(zhí)行模式下的系統(tǒng)工作效率 系統(tǒng)總運(yùn)行時(shí)間：80 CPU使用效率：CPU占用時(shí)間 / 總時(shí)間 40/80 = 50% DEV1使用效率：15 / 80 18.75% DEV2使用效率：25 / 80 = 31.25% 并發(fā)執(zhí)行模式下的系統(tǒng)工作效率 系統(tǒng)總運(yùn)行時(shí)間：45 CPU使用效率：40 / 45 = 89% DEV1使用效率：15 / 45 = 33% DEV2使用效率：25 / 45 55.6%7并發(fā)

4、所帶來(lái)的設(shè)計(jì)難題 共享性帶來(lái)的問(wèn)題：如何調(diào)度或分配資源？ 最大限度的保證系統(tǒng)運(yùn)行效率：誰(shuí)首先獲得資源？ 最大限度的保證系統(tǒng)運(yùn)行安全：死鎖情況的預(yù)防 間斷性和不確定性帶來(lái)的問(wèn)題：如何保證互斥？ 互斥問(wèn)題示例：見(jiàn)下頁(yè)圖 經(jīng)典IPC問(wèn)題：進(jìn)程管理的重點(diǎn) 間斷性和獨(dú)立性帶來(lái)的問(wèn)題：如何調(diào)度和保護(hù)？ 每個(gè)程序運(yùn)行時(shí)都感覺(jué)不到間斷：上下文切換 復(fù)雜應(yīng)用帶來(lái)的問(wèn)題：如何進(jìn)行通信？ 多個(gè)程序間可動(dòng)態(tài)交換信息：進(jìn)程通信機(jī)制8互斥問(wèn)題 Get、Copy、Put為三個(gè)并發(fā)的程序 F、G為保存多條數(shù)據(jù)的緩沖區(qū)，S、T為臨時(shí)緩沖區(qū) 三個(gè)程序順序執(zhí)行，可將F的值經(jīng)過(guò)S、T保存到G中 正常情況下，不存在任何問(wèn)題 但是程序運(yùn)

5、行順序發(fā)生變化時(shí)，結(jié)果可能出錯(cuò)9互斥問(wèn)題con.初始狀態(tài)FSTG分析程序運(yùn)行順序3，4，5221，2G、C、P4，5331，2，3正確G、P、C4，5331，2，2錯(cuò)誤C、P、G4，5321，2，2錯(cuò)誤C、G、P4，5321，2，2錯(cuò)誤P、C、GP、G、C10進(jìn)程概念 進(jìn)程的核心思想 進(jìn)程是某個(gè)程序在某個(gè)數(shù)據(jù)集合上的運(yùn)行過(guò)程，它進(jìn)程是某個(gè)程序在某個(gè)數(shù)據(jù)集合上的運(yùn)行過(guò)程，它有程序、輸入、輸出和狀態(tài)。有程序、輸入、輸出和狀態(tài)。 在分時(shí)操作系統(tǒng)中，單個(gè)在分時(shí)操作系統(tǒng)中，單個(gè)CPU被若干進(jìn)程共享，它被若干進(jìn)程共享，它使用某種調(diào)度算法決定何時(shí)停止一個(gè)進(jìn)程的運(yùn)行，使用某種調(diào)度算法決定何時(shí)停止一個(gè)進(jìn)程的運(yùn)行

6、，轉(zhuǎn)而為其他進(jìn)程提供服務(wù)。轉(zhuǎn)而為其他進(jìn)程提供服務(wù)。進(jìn)程概念進(jìn)程概念11進(jìn)程的特征 動(dòng)態(tài)性：進(jìn)程具有動(dòng)態(tài)的地址空間（數(shù)量和內(nèi)容），地址空間上包括： 代碼（指令執(zhí)行和CPU狀態(tài)的改變） 數(shù)據(jù)（變量的生成和賦值） 系統(tǒng)控制信息（進(jìn)程控制塊的生成和刪除） 獨(dú)立性：各進(jìn)程的地址空間相互獨(dú)立，除非采用進(jìn)程間通信手段； 并發(fā)性、異步性：虛擬 結(jié)構(gòu)化：代碼段、數(shù)據(jù)段和核心段（在地址空間中）；程序文件中通常也劃分了代碼段和數(shù)據(jù)段，而核心段通常就是OS核心（由各個(gè)進(jìn)程共享，包括各進(jìn)程的PCB）進(jìn)程概念進(jìn)程概念12進(jìn)程與程序的區(qū)別 進(jìn)程是動(dòng)態(tài)的，程序是靜態(tài)的：程序是有序代碼的集合；進(jìn)程是程序的執(zhí)行。通常進(jìn)程不可在計(jì)

7、算機(jī)之間遷移；而程序通常對(duì)應(yīng)著文件、靜態(tài)和可以復(fù)制。 進(jìn)程是暫時(shí)的，程序的永久的：進(jìn)程是一個(gè)狀態(tài)變化的過(guò)程，程序可長(zhǎng)久保存。 進(jìn)程與程序的組成不同：進(jìn)程的組成包括程序、數(shù)據(jù)和進(jìn)程控制塊（即進(jìn)程狀態(tài)信息）。 進(jìn)程與程序的對(duì)應(yīng)關(guān)系：通過(guò)多次執(zhí)行，一個(gè)程序可對(duì)應(yīng)多個(gè)進(jìn)程；通過(guò)調(diào)用關(guān)系，一個(gè)進(jìn)程可包括多個(gè)程序。進(jìn)程概念進(jìn)程概念13進(jìn)程控制塊(PCB, process control block)進(jìn)程概念進(jìn)程概念進(jìn)程控制塊是由OS維護(hù)的用來(lái)記錄進(jìn)程相關(guān)信息的一塊內(nèi)存。 每個(gè)進(jìn)程在OS中的登記表項(xiàng)（可能有總數(shù)目限制），OS據(jù)此對(duì)進(jìn)程進(jìn)行控制和管理（PCB中的內(nèi)容會(huì)動(dòng)態(tài)改變），不同OS則不同 處于核心段，通

8、常不能由應(yīng)用程序自身的代碼來(lái)直接訪問(wèn)，而要通過(guò)系統(tǒng)調(diào)用，或通過(guò)UNIX中的進(jìn)程文件系統(tǒng)(/proc)直接訪問(wèn)進(jìn)程映象(image)。文件名為進(jìn)程標(biāo)識(shí)（如：00316），權(quán)限為創(chuàng)建者可讀寫(xiě)。14進(jìn)程控制塊的內(nèi)容進(jìn)程概念進(jìn)程概念 進(jìn)程描述信息： 進(jìn)程標(biāo)識(shí)符(process ID)，唯一，通常是一個(gè)整數(shù)； 進(jìn)程名，通常基于可執(zhí)行文件名（不唯一）； 用戶(hù)標(biāo)識(shí)符(user ID)；進(jìn)程組關(guān)系(process group) 進(jìn)程控制信息： 當(dāng)前狀態(tài)； 優(yōu)先級(jí)(priority)； 代碼執(zhí)行入口地址； 程序的外存地址； 運(yùn)行統(tǒng)計(jì)信息（執(zhí)行時(shí)間、頁(yè)面調(diào)度）； 進(jìn)程間同步和通信；阻塞原因 資源占用信息：虛擬地址

9、空間的現(xiàn)狀、打開(kāi)文件列表 CPU現(xiàn)場(chǎng)保護(hù)結(jié)構(gòu)：寄存器值（通用、程序計(jì)數(shù)器PC、狀態(tài)PSW，地址包括棧指針）15PCB的組織方式進(jìn)程概念進(jìn)程概念 鏈表：同一狀態(tài)的進(jìn)程其PCB成一鏈表，多個(gè)狀態(tài)對(duì)應(yīng)多個(gè)不同的鏈表 各狀態(tài)的進(jìn)程形成不同的鏈表：就緒鏈表、阻塞鏈表 索引表：同一狀態(tài)的進(jìn)程歸入一個(gè)index表（由index指向PCB），多個(gè)狀態(tài)對(duì)應(yīng)多個(gè)不同的index表 各狀態(tài)的進(jìn)行形成不同的索引表：就緒索引表、阻塞索引表PCB TableReadyBlockedPCB TableIndex TableReadyBlocked16進(jìn)程上下文進(jìn)程上下文是對(duì)進(jìn)程執(zhí)行活動(dòng)全過(guò)程的靜態(tài)描述。進(jìn)程上下文由進(jìn)程的用

10、戶(hù)地址空間內(nèi)容、硬件寄存器內(nèi)容及與該進(jìn)程相關(guān)的核心數(shù)據(jù)結(jié)構(gòu)組成。 用戶(hù)級(jí)上下文：進(jìn)程的用戶(hù)地址空間（包括用戶(hù)棧各層次），包括用戶(hù)正文段、用戶(hù)數(shù)據(jù)段和用戶(hù)棧； 寄存器級(jí)上下文：程序寄存器、處理機(jī)狀態(tài)寄存器、棧指針、通用寄存器的值； 系統(tǒng)級(jí)上下文： 靜態(tài)部分（PCB和資源表格） 動(dòng)態(tài)部分：核心棧（核心過(guò)程的棧結(jié)構(gòu)，不同進(jìn)程在調(diào)用相同核心過(guò)程時(shí)有不同核心棧） 17Process CreationPrincipal events that cause process creation1. System initialization2. Execution of a process creation s

11、ystem call by a running process3. User request to create a new process4. Initiation of a batch job18Process Creation System Call Unix: fork() -only one system call two process (the parent and the child) have: the same memory image, the same environment strings, and the same open files. use execve()

12、to change its memory image. Windows: CreateProcess() handles both process creation and loading the program into the new process.19Process TerminationConditions which terminate processes1. Normal exit (voluntary) ( Unix: exit(), Windows: ExitProcess() )2. Error exit (voluntary)3. Fatal error (involun

13、tary)4. Killed by another process (involuntary) ( Unix: kill(), Windows: TerminateProcess() )20Process Hierarchies Parent creates a child process, child processes can create its own process Forms a hierarchy UNIX calls this a process group Windows has no concept of process hierarchy all processes ar

14、e created equal21Process States (1) Possible process states running:運(yùn)行態(tài)，正在占用CPU運(yùn)行程序 blocked:阻塞態(tài)，等待外部事件發(fā)生，無(wú)法占用CPU ready:就緒態(tài)，可運(yùn)行，但其他進(jìn)程正在占用CPU，所有被暫時(shí)掛起 Transitions between states shown22Problem 問(wèn)題1：為什么不能從阻塞態(tài)變?yōu)檫\(yùn)行態(tài)呢？ 問(wèn)題2：為什么不能從就緒態(tài)變?yōu)樽枞麘B(tài)呢？ 提示： 三種狀態(tài)的變換體現(xiàn)了OS的資源管理作用 進(jìn)程的核心思想在于運(yùn)行CPU資源的分配23進(jìn)程的復(fù)雜狀態(tài) 其他復(fù)雜的進(jìn)程狀態(tài) 創(chuàng)建、中止

15、、掛起三種狀態(tài) 五種狀態(tài)模型增加了“創(chuàng)建”、“退出”兩種狀態(tài) 七種狀態(tài)模型針對(duì)進(jìn)程的存在位置（內(nèi)存或者外存），進(jìn)一步增加“阻塞掛起”和“就緒掛起”兩種狀態(tài) 進(jìn)程狀態(tài)模型的重要性 OS管理CPU資源的核心運(yùn)行機(jī)制 直接關(guān)系到進(jìn)程數(shù)據(jù)結(jié)構(gòu)與相關(guān)算法的設(shè)計(jì)24進(jìn)程的復(fù)雜狀態(tài)con.25進(jìn)程的復(fù)雜狀態(tài)con.活動(dòng)活動(dòng)掛起掛起事件事件發(fā)生發(fā)生事件事件發(fā)生發(fā)生等待等待事件事件掛起掛起調(diào)度調(diào)度超時(shí)超時(shí)釋放釋放活動(dòng)活動(dòng)掛起掛起26Process States (2) Lowest layer of process-structured OS handles interrupts, scheduling Abo

16、ve that layer are sequential processes27進(jìn)程管理 單個(gè)進(jìn)程的管理 進(jìn)程的創(chuàng)建、刪除：靜態(tài)與動(dòng)態(tài)概念的差別。 多個(gè)進(jìn)程的管理 樹(shù)狀進(jìn)程集合：父進(jìn)程和子進(jìn)程 進(jìn)程的調(diào)度：保持CPU效率的關(guān)鍵 進(jìn)程之間的通信 最簡(jiǎn)單：兩個(gè)進(jìn)程之間如何傳遞信息？ 中級(jí)：如何保持進(jìn)程之間的互斥？ 高級(jí)：如何維系進(jìn)程之間的依賴(lài)關(guān)系？28Implementation of Processes (1)Fields of a process table entry29Implementation of Processes (2)Skeleton of what lowest level

17、of OS does when an interrupt occurs30進(jìn)程小結(jié) 概念 CPU資源的管理載體OS通過(guò)進(jìn)程實(shí)現(xiàn)對(duì)CPU的管理 核心思想動(dòng)態(tài)概念進(jìn)程與程序的區(qū)別 進(jìn)程實(shí)現(xiàn)生存周期狀態(tài)的變遷 進(jìn)程管理 單個(gè)進(jìn)程進(jìn)程調(diào)度進(jìn)程通信 進(jìn)程序列進(jìn)程樹(shù)線程 數(shù)據(jù)傳遞共享與互斥依賴(lài)關(guān)系維護(hù) 術(shù)語(yǔ) Cocurrency & Parallel & MultiProgramming Program & Process & Thread Program & Process: 靜態(tài)和動(dòng)態(tài)的思想 MultiProgramming: 并發(fā)與互斥的思想31線程 進(jìn)程：資

18、源分配單位（存儲(chǔ)器、文件）和CPU調(diào)度（分派）單位。又稱(chēng)為任務(wù)(task) 線程：作為CPU調(diào)度單位，而進(jìn)程只作為其他資源分配單位。 只擁有必不可少的資源，如：線程狀態(tài)、寄存器上下文和棧 同樣具有就緒、阻塞和執(zhí)行三種基本狀態(tài)32線程 引入線程的目的是簡(jiǎn)化線程間的通信，以小的開(kāi)銷(xiāo)來(lái)提高進(jìn)程內(nèi)的并發(fā)程度。 線程的優(yōu)點(diǎn)：減小并發(fā)執(zhí)行的時(shí)間和空間開(kāi)銷(xiāo)（線程的創(chuàng)建、退出和調(diào)度），因此容許在系統(tǒng)中建立更多的線程來(lái)提高并發(fā)程度。 線程的創(chuàng)建時(shí)間比進(jìn)程短； 線程的終止時(shí)間比進(jìn)程短； 同進(jìn)程內(nèi)的線程切換時(shí)間比進(jìn)程短； 由于同進(jìn)程內(nèi)線程間共享內(nèi)存和文件資源，可直接進(jìn)行不通過(guò)內(nèi)核的通信33ThreadsThe Th

19、read Model (1)(a) Three processes each with one thread(b) One process with three threads34The Thread Model (2) Items shared by all threads in a process Items private to each thread35The Thread Model (3)Each thread has its own stack Every thread can access every memory address within the process addr

20、ess space. There is no protection between threads because 1) it is impossible, and 2) it should not be necessary.36Thread Call create new threads: thread_create() exit thread: thread_exit() one thread wait for a specific thread to exit: thread_wait() allow a thread to voluntarily give up the CPU to

21、let another thread run: thread_yield()37進(jìn)程和線程的比較 地址空間和其他資源（如打開(kāi)文件）：進(jìn)程間相互獨(dú)立，同一進(jìn)程的各線程間共享某進(jìn)程內(nèi)的線程在其他進(jìn)程不可見(jiàn) 通信：進(jìn)程間通信IPC，線程間可以直接讀寫(xiě)進(jìn)程數(shù)據(jù)段（如全局變量）來(lái)進(jìn)行通信需要進(jìn)程同步和互斥手段的輔助，以保證數(shù)據(jù)的一致性 調(diào)度：線程上下文切換比進(jìn)程上下文切換要快得多；38ThreadControlBlockUserStackUserStackKernelStackKernelStackUserAddressSpaceUserAddressSpaceProcessControlBlockPr

22、ocessControlBlockThreadSingle-ThreadedProcess ModelMultithreadedProcess ModelThreadControlBlockUserStackKernelStackThreadThreadControlBlockUserStackKernelStackThread線程切換和進(jìn)程切換39Reason for thread In many applications, multiple activities are going on at once. By decomposing it into multiple sequential

23、 threads, the programming model becomes simpler. Threads do not have any resources attached to them, they are easier to create and destroy than processes. When there is substantial computing and also substantial I/O, having threads allows these activities to overlap, thus speeding up the application

24、. Threads are useful on systems with multiple CPUs, where real parallelism is possible.40Thread Usage (1)A word processor with three threads threads: one interacts with user, another handles reformatting in the background, a third thread automatically save the entire file to disk during a specific t

25、ime (handle the disk backups without interfering with the other two).41Thread Usage (2)A multithreaded Web server42Thread Usage (3) Rough outline of code for previous slide(a) Dispatcher thread(b) Worker thread43Thread Usage (4)Three ways to construct a server44用戶(hù)線程(user-level thread)不依賴(lài)于OS核心，應(yīng)用進(jìn)程利用

26、線程庫(kù)提供創(chuàng)建、同步、調(diào)度和管理線程的函數(shù)來(lái)控制用戶(hù)線程。如：數(shù)據(jù)庫(kù)系統(tǒng)informix，圖形處理Aldus PageMaker。調(diào)度由應(yīng)用軟件內(nèi)部進(jìn)行，通常采用非搶先式和更簡(jiǎn)單的規(guī)則，也無(wú)需用戶(hù)態(tài)/核心態(tài)切換，所以速度特別快。一個(gè)線程發(fā)起系統(tǒng)調(diào)用而阻塞，則整個(gè)進(jìn)程在等待。時(shí)間片分配給進(jìn)程，多線程則每個(gè)線程就慢。 用戶(hù)線程的維護(hù)由應(yīng)用進(jìn)程完成； 內(nèi)核不了解用戶(hù)線程的存在； 用戶(hù)線程切換不需要內(nèi)核特權(quán)； 用戶(hù)線程調(diào)度算法可針對(duì)應(yīng)用優(yōu)化；45Implementing Threads in User SpaceA user-level threads package46Implementing Th

27、reads in User Space: Advantage A user-level threads package can be implemented on an operating system that does not support threads. Doing thread switching is faster than trapping to the kernel, no trap is needed, no context switch is needed, the memory cache need not be flushed, and so on. This mak

28、es thread scheduling very fast. Allow each process to have its own customized scheduling algorithm. Scale better, since kernel threads invariably require some table space and stack space in the kernel, which can be a problem if there are a very large number of threads.47Implementing Threads in User

29、Space: Problems the problem of how blocking system calls are implemented: 1) one blocking call may stop all the threads, 2) nonblocking system call changing require changes to the OS, 3) to tell in advance if a call will block: do the call if it is safe, if the call will block, the call is not made.

30、 Instead, another thread is run. the problem of page faults: block even though other runnable threads. Within a single process, there are no clock interrupts, Unless a thread enters the run-time system of its own free will, the scheduler will never get a chance. Programmers generally want threads in

31、 applications where the threads block often. Block vs computing. 48內(nèi)核線程(kernel-level thread)依賴(lài)于OS核心，由內(nèi)核的內(nèi)部需求進(jìn)行創(chuàng)建和撤銷(xiāo)，用來(lái)執(zhí)行一個(gè)指定的函數(shù)。Windows NT和OS/2支持內(nèi)核線程； 內(nèi)核維護(hù)進(jìn)程和線程的上下文信息； 線程切換由內(nèi)核完成； 一個(gè)線程發(fā)起系統(tǒng)調(diào)用而阻塞，不會(huì)影響其他線程的運(yùn)行。 時(shí)間片分配給線程，所以多線程的進(jìn)程獲得更多CPU時(shí)間。49Implementing Threads in the KernelA threads package managed by th

32、e kernel50Implementing Threads in the KernelAdvantage No run-time system is needed Kernel threads do not require any new, nonblocking system calls. The kernel can easily check which thread (in the same process) when page fault.Disadvantage The cost of a system call is substantial, so if thread opera

33、tions (creation, termination, etc.) are common, much more overhead will be incurred.51Hybrid Implementations Multiplexing user-level threads onto kernel- level threads52Scheduler Activations Goal mimic functionality of kernel threads gain performance of user space threads Avoids unnecessary user/ker

34、nel transitions eg. block by synchronizing thread in user space Kernel assigns virtual processors to each process lets runtime system allocate threads to processors Problem: Fundamental reliance on kernel (lower layer) calling procedures in user space (higher layer)53Pop-Up Threads Creation of a new

35、 thread when message arrives(a) before message arrives(b) after message arrives54Making Single-Threaded Code Multithreaded (1)Conflicts between threads over the use of a global variable55Making Single-Threaded Code Multithreaded (2)Threads can have private global variables56SUN Solaris 線程舉例 Solaris支

36、持內(nèi)核線程(Kernel threads)、輕權(quán)進(jìn)程(Lightweight Processes)和用戶(hù)線程(User Level Threads)。一個(gè)進(jìn)程可有大量用戶(hù)線程；大量用戶(hù)線程復(fù)用少量的輕權(quán)進(jìn)程，不同的輕權(quán)進(jìn)程分別對(duì)應(yīng)不同的內(nèi)核線程。Timesliceor PreemptWakeupStopBlockingSystemCallWakeupDispatchRunnableRunningActiveStoppedContinueStopStopStopSleepDispatchStopWakeupContinuePreemptStoppedRunnableActiveSleeping用

37、戶(hù)級(jí)線程輕權(quán)進(jìn)程57SUN Solaris 線程(con.) 用戶(hù)級(jí)線程在使用系統(tǒng)調(diào)用時(shí)（如文件讀寫(xiě)），需要“捆綁(bound)”在一個(gè)LWP上。 永久捆綁：一個(gè)LWP固定被一個(gè)用戶(hù)級(jí)線程占用，該LWP移到LWP池之外 臨時(shí)捆綁：從LWP池中臨時(shí)分配一個(gè)未被占用的LWP 在使用系統(tǒng)調(diào)用時(shí)，如果所有LWP已被其他用戶(hù)級(jí)線程所占用（捆綁），則該線程阻塞直到有可用的LWP例如6個(gè)用戶(hù)級(jí)線程，而LWP池中有4個(gè)LWP 如果LWP執(zhí)行系統(tǒng)調(diào)用時(shí)阻塞（如read()調(diào)用），則當(dāng)前捆綁在LWP上的用戶(hù)級(jí)線程也阻塞。58SUN Solaris 線程(con.) 用戶(hù)線程、輕權(quán)進(jìn)程和核心線程的關(guān)系Process

38、 1PermanentlyBoundThreadsProcess 1KTKTKTKTKTKTCPU 1CPU 1LWPUTUTUTUTLWPLWPUnboundThreadsPool of LWPs forUnbound ThreadsKernalUTLWP59Windows NT線程 就緒狀態(tài)(Ready)：進(jìn)程已獲得除處理機(jī)外的所需資源，等待執(zhí)行。 備用狀態(tài)(Standby)：特定處理器的執(zhí)行對(duì)象，系統(tǒng)中每個(gè)處理器上只能有一個(gè)處于備用狀態(tài)的線程。 運(yùn)行狀態(tài)(Running)：完成描述表切換，線程進(jìn)入運(yùn)行狀態(tài)，直到內(nèi)核搶先、時(shí)間片用完、線程終止或進(jìn)行等待狀態(tài)。 等待狀態(tài)(Waiting)：線

39、程等待對(duì)象句柄，以同步它的執(zhí)行。等待結(jié)束時(shí)，根據(jù)優(yōu)先級(jí)進(jìn)入運(yùn)行、就緒狀態(tài)。 轉(zhuǎn)換狀態(tài)(Transition)：線程在準(zhǔn)備執(zhí)行而其內(nèi)核堆棧處于外存時(shí)，線程進(jìn)入轉(zhuǎn)換狀態(tài)；當(dāng)其內(nèi)核堆棧調(diào)回內(nèi)存，線程進(jìn)入就緒狀態(tài)。 終止?fàn)顟B(tài)(Terminated)：線程執(zhí)行完就進(jìn)入終止?fàn)顟B(tài)；如執(zhí)行體有一指向線程對(duì)象的指針，可將線程對(duì)象重新初始化，并再次使用。 初始化狀態(tài)(Initialized)：線程創(chuàng)建過(guò)程中的線程狀態(tài)；60Windows NT線程(con.)運(yùn)行終止就緒等待描述表切換搶先或時(shí)間片結(jié)束等待對(duì)象句柄執(zhí)行完成初始化轉(zhuǎn)換備用選擇執(zhí)行搶先放入就緒隊(duì)列等待完成等待完成換出的內(nèi)核堆棧換入的內(nèi)核堆棧重新初始化創(chuàng)建

40、和初始化線程對(duì)象61Windows NT線程(con.) CreateThread()函數(shù)在調(diào)用進(jìn)程的地址空間上創(chuàng)建一個(gè)線程，以執(zhí)行指定的函數(shù)；返回值為所創(chuàng)建線程的句柄。 ExitThread()函數(shù)用于結(jié)束本線程。 SuspendThread()函數(shù)用于掛起指定的線程。 ResumeThread()函數(shù)遞減指定線程的掛起計(jì)數(shù)，掛起計(jì)數(shù)為0時(shí)，線程恢復(fù)執(zhí)行。62進(jìn)程通信（IPC） 進(jìn)程間的關(guān)系 完全無(wú)關(guān)（異步）：不同進(jìn)程間無(wú)任何關(guān)聯(lián) 使用共享數(shù)據(jù)（互斥）：有效保護(hù)各個(gè)進(jìn)程的正確運(yùn)行 存在先后順序（同步）：保證進(jìn)程運(yùn)行順序的正確 進(jìn)程通信需要考慮的問(wèn)題 如何實(shí)現(xiàn)兩個(gè)進(jìn)程間的信息傳遞 如何協(xié)調(diào)兩個(gè)

41、或者多個(gè)進(jìn)程之間的互斥和同步情況 問(wèn)題難點(diǎn)分析 金字塔法則：20的簡(jiǎn)單問(wèn)題80的困難問(wèn)題 難點(diǎn)：臨界區(qū)的保護(hù)63Interprocess Communication How one process can pass information to another Making sure two or more process do not get into each others way when engaging in critical activities. Proper sequencing when dependencies are present.Note: passing infor

42、mation is easy for threads since they share a common address space. However, keeping out of each others hair and proper sequencing apply equally well to threads64Interprocess CommunicationRace ConditionsTwo processes want to access shared memory at same time65Spooler目錄問(wèn)題（互斥）6667Interprocess Communic

43、ation 進(jìn)程調(diào)度機(jī)制的深入理解 何時(shí)發(fā)生進(jìn)程調(diào)度時(shí)鐘中斷 進(jìn)程切換時(shí)的操作壓棧，進(jìn)入就緒隊(duì)列 邊界情況的進(jìn)程通信困難 互斥情況調(diào)度順序影響運(yùn)行結(jié)果 同步情況運(yùn)行過(guò)程影響應(yīng)用效果 多進(jìn)程分時(shí)運(yùn)行的臨界情況 正常情況下不存在任何問(wèn)題 臨界情況下將產(chǎn)生不可預(yù)知的后果（墨菲法則） 解決的關(guān)鍵 保持進(jìn)程之間正確的運(yùn)行順序 OS與普通應(yīng)用程序設(shè)計(jì)都需要考慮 解決機(jī)制：提升系統(tǒng)運(yùn)行的穩(wěn)定性68一些IPC概念 競(jìng)爭(zhēng)條件 兩個(gè)或者多個(gè)進(jìn)程讀寫(xiě)共享數(shù)據(jù)，而運(yùn)行結(jié)果取決于進(jìn)程運(yùn)行時(shí)的精確時(shí)序，則這種情況稱(chēng)之為競(jìng)爭(zhēng)條件 當(dāng)競(jìng)爭(zhēng)條件存在時(shí)，進(jìn)程處理結(jié)果可能失效甚至發(fā)生錯(cuò)誤 臨界區(qū) 對(duì)共享內(nèi)存（數(shù)據(jù)）進(jìn)行訪問(wèn)的程序片

44、斷稱(chēng)為臨界區(qū) 互斥 防止多個(gè)進(jìn)程同時(shí)操作相同共享數(shù)據(jù)的手段(多個(gè)進(jìn)程不能同時(shí)使用同一個(gè)資源)死鎖多個(gè)進(jìn)程互不相讓?zhuān)嫉貌坏阶銐虻馁Y源饑餓一個(gè)進(jìn)程一直得不到資源（其他進(jìn)程可能輪流占用資源）69Interprocess Communication 同步關(guān)系分析 兩個(gè)或者多個(gè)進(jìn)程在運(yùn)行順序上存在固定的規(guī)則 由于分時(shí)操作系統(tǒng)的不確定性，導(dǎo)致同步關(guān)系無(wú)法保持 必須進(jìn)行顯式的程序控制，保證同步關(guān)系的正確 同步與互斥的差別 互斥：體現(xiàn)為排他性，可表現(xiàn)為“01”關(guān)系(保護(hù)臨界區(qū)，防止多個(gè)進(jìn)程同時(shí)進(jìn)入) 同步：體現(xiàn)為時(shí)序性，比互斥更加復(fù)雜和多變(保證進(jìn)程運(yùn)行的順序合理) 解決思路 保證解決辦法對(duì)互斥和同步的適用

45、性70Critical Regions (1)Four conditions to provide mutual exclusion1.No two processes simultaneously in critical region2.No assumptions made about speeds or numbers of CPUs3.No process running outside its critical region may block another process4.No process must wait forever to enter its critical re

46、gion互斥原則：任何兩個(gè)進(jìn)程不能同時(shí)處于臨界區(qū)通用性原則：不應(yīng)對(duì)CPU的速度和數(shù)目進(jìn)行任何假設(shè)有效性原則：臨界區(qū)外的進(jìn)程不應(yīng)阻塞其他進(jìn)程合理性原則：不得使進(jìn)程在臨界區(qū)外無(wú)限制的等待；當(dāng)進(jìn)程無(wú)法進(jìn)入臨界區(qū)時(shí)，應(yīng)放棄CPU資源71Critical Regions (2)Mutual exclusion using critical regions72IPC機(jī)制 忙等待模型（只解決互斥問(wèn)題） 進(jìn)程進(jìn)入臨界區(qū)時(shí)進(jìn)行嚴(yán)格的檢查 睡眠和喚醒模型（互斥與同步） 通過(guò)改變進(jìn)程的狀態(tài)來(lái)實(shí)現(xiàn)互斥和同步 消息傳遞模型（復(fù)雜的IPC機(jī)制） 以公共的通信機(jī)制來(lái)控制進(jìn)程狀態(tài)變化，實(shí)現(xiàn)同步和互斥73忙等待模型 模型思想

47、設(shè)定一個(gè)變量，標(biāo)識(shí)臨界區(qū)的狀態(tài) 互斥進(jìn)程均檢查這個(gè)變量，只有當(dāng)其滿(mǎn)足條件時(shí)方可進(jìn)入臨界區(qū) 模型方法 關(guān)中斷 鎖變量 嚴(yán)格輪轉(zhuǎn) Peterson解決方案74關(guān)中斷 解決思想 在臨界區(qū)中防止發(fā)生進(jìn)程調(diào)度 保證臨界區(qū)操作的完整性 方法分析 用戶(hù)控制系統(tǒng)中斷是非常危險(xiǎn)的 本方法對(duì)多個(gè)CPU系統(tǒng)將失去作用75鎖變量 解決思想 設(shè)定監(jiān)控變量（lock），通過(guò)其值變化控制進(jìn)程操作 方法分析 依然存在競(jìng)爭(zhēng)條件，不能根本解決互斥問(wèn)題 致命缺陷：不具有操作的原子性76鎖變量的缺陷示例發(fā)生進(jìn)程調(diào)度，互發(fā)生進(jìn)程調(diào)度，互斥的進(jìn)程開(kāi)始運(yùn)行斥的進(jìn)程開(kāi)始運(yùn)行發(fā)生進(jìn)程調(diào)度，發(fā)生進(jìn)程調(diào)度，A并不并不知道知道B也進(jìn)入臨界區(qū)也進(jìn)入臨

48、界區(qū)發(fā)生進(jìn)程調(diào)度，發(fā)生進(jìn)程調(diào)度，B并不并不知道知道A也進(jìn)入臨界區(qū)也進(jìn)入臨界區(qū)77Mutual Exclusion with Busy WaitingProposed solution to critical region problem(a) Process 0. (b) Process 1.嚴(yán)格輪轉(zhuǎn)法：忙等待浪費(fèi)CPU時(shí)間；存在邊界情況，違反解決原則第三條78嚴(yán)格輪轉(zhuǎn)法的缺陷示例第一次運(yùn)行時(shí)，可第一次運(yùn)行時(shí)，可嚴(yán)格保證互斥關(guān)系嚴(yán)格保證互斥關(guān)系進(jìn)程進(jìn)程B需要第二次進(jìn)入臨需要第二次進(jìn)入臨界區(qū)時(shí)，必須等待進(jìn)程界區(qū)時(shí)，必須等待進(jìn)程A將將turn值改為值改為1。但是進(jìn)。但是進(jìn)程程A的非臨界區(qū)操作很慢的

49、非臨界區(qū)操作很慢79Mutual Exclusion with Busy Waiting (2)Petersons solution for achieving mutual exclusion80Use Petersons solution81Mutual Exclusion with Busy Waiting (3)Entering and leaving a critical region using the TSL instruction測(cè)試并加鎖：硬件TSL指令硬件實(shí)現(xiàn)提高速度，適用于多處理機(jī); 依然存在忙等待的問(wèn)題TSL RX LOCK: 硬件實(shí)現(xiàn)鎖變量機(jī)制, 保證LOCK讀寫(xiě)原子

50、性82忙等待模型分析 優(yōu)點(diǎn)分析 實(shí)現(xiàn)機(jī)制簡(jiǎn)單易懂，可有效保證互斥 缺點(diǎn)分析 只適用于兩個(gè)進(jìn)程間互斥，不具有通用性 忙等待嚴(yán)重浪費(fèi)CPU資源，降低硬件效率 “優(yōu)先級(jí)調(diào)度”“忙等待” 優(yōu)先級(jí)反轉(zhuǎn) 進(jìn)程H和L，H優(yōu)先級(jí)比L優(yōu)先級(jí)高 L先進(jìn)入臨界區(qū)，H后進(jìn)入臨界區(qū) H開(kāi)始忙等待，而L由于無(wú)法獲得CPU也不能離開(kāi)臨界區(qū)83睡眠-喚醒模型 模型思想 OS提供系統(tǒng)調(diào)用原語(yǔ)（Atomic Action），改變進(jìn)程狀態(tài) 無(wú)法進(jìn)入臨界區(qū)的進(jìn)程轉(zhuǎn)為阻塞態(tài)，條件滿(mǎn)足則被喚醒 可有效克服忙等待造成的資源浪費(fèi) 更重要的優(yōu)點(diǎn)：可同時(shí)實(shí)現(xiàn)同步與互斥 模型方法 簡(jiǎn)單的睡眠喚醒方法 信號(hào)量機(jī)制 管程方法84簡(jiǎn)單的睡眠喚醒方法 操

51、作系統(tǒng)原語(yǔ)設(shè)計(jì) Sleep()：調(diào)用該原語(yǔ)的進(jìn)程將變?yōu)樽枞麘B(tài) Wakeup(ID)：該原語(yǔ)將喚醒ID標(biāo)識(shí)的進(jìn)程 原語(yǔ)使用思想 進(jìn)入臨界區(qū)前檢查競(jìng)爭(zhēng)條件，如不滿(mǎn)足則睡眠 離開(kāi)臨界區(qū)后喚醒互斥進(jìn)程85生產(chǎn)者消費(fèi)者問(wèn)題 問(wèn)題描述 一個(gè)有限空間的共享緩沖區(qū)，負(fù)責(zé)存放貨物 生產(chǎn)者向緩沖區(qū)中放物品，緩沖區(qū)滿(mǎn)則不能放 消費(fèi)者從緩沖區(qū)中拿物品，緩沖區(qū)空則不能拿86Sleep and WakeupProducer-consumer problem with fatal race condition87潛在的競(jìng)爭(zhēng)條件發(fā)生進(jìn)程調(diào)度，導(dǎo)致發(fā)生進(jìn)程調(diào)度，導(dǎo)致C進(jìn)進(jìn)程并未進(jìn)行程并未進(jìn)行SleepP進(jìn)程認(rèn)為進(jìn)程認(rèn)為C在睡眠

52、，試在睡眠，試圖喚醒圖喚醒C由于錯(cuò)過(guò)了由于錯(cuò)過(guò)了Wakeup信號(hào)，信號(hào)，C進(jìn)入了睡眠狀態(tài)進(jìn)入了睡眠狀態(tài)P進(jìn)程一直運(yùn)行下去，填進(jìn)程一直運(yùn)行下去，填滿(mǎn)緩沖區(qū)后也睡眠了滿(mǎn)緩沖區(qū)后也睡眠了88 臨界情況 count的訪問(wèn)未加限制，形成競(jìng)爭(zhēng)條件 必須增加喚醒等待位，以解決互斥問(wèn)題 方法分析 較忙等待更進(jìn)一步，有效節(jié)省CPU資源 存在競(jìng)爭(zhēng)條件，需要額外處理 當(dāng)互斥進(jìn)程數(shù)增加時(shí)，方法有效性下降 改進(jìn)辦法 由OS提供宏觀調(diào)控管理機(jī)制 徹底消除調(diào)度順序引起的錯(cuò)亂 OS實(shí)現(xiàn)更高層次的原語(yǔ)級(jí)操作89信號(hào)量機(jī)制 基本概念 信號(hào)量：表示累積的睡眠或者喚醒操作 Down與Up原語(yǔ)（P/V、S/W原語(yǔ)） Dijkstra于

53、1965年提出Probern和Verhogen原語(yǔ) 核心思想 引入新的數(shù)據(jù)結(jié)構(gòu)定義：信號(hào)量 利用信號(hào)量，提供更為復(fù)雜的原語(yǔ)級(jí)操作 從根本上解決“潛在競(jìng)爭(zhēng)條件”問(wèn)題 可以方便的推廣到一般情況，適用于多進(jìn)程的互斥與同步90信號(hào)量與Down/Up原語(yǔ) 基本概念 對(duì)于一種互斥或者同步關(guān)系，用一個(gè)整型變量來(lái)描述 當(dāng)信號(hào)量大于0時(shí)，說(shuō)明“環(huán)境安全”，可繼續(xù)運(yùn)行 當(dāng)信號(hào)量小于0時(shí)，說(shuō)明“互斥等待”，只能阻塞 推廣到一般情況，信號(hào)量可解決復(fù)雜的同步互斥問(wèn)題原語(yǔ)：OS以關(guān)中斷形式實(shí)現(xiàn)的不可打斷操作91最基本互斥機(jī)制的實(shí)現(xiàn)92SemaphoresThe producer-consumer problem usin

54、g semaphores93 互斥信號(hào)量 mutex：防止多個(gè)進(jìn)程同時(shí)進(jìn)入臨界區(qū) 讀者和寫(xiě)者不能同時(shí)進(jìn)入共享數(shù)據(jù)區(qū) 多個(gè)寫(xiě)者不能同時(shí)進(jìn)入共享數(shù)據(jù)區(qū) 多個(gè)讀者可以同時(shí)進(jìn)入共享數(shù)據(jù)區(qū) 同步信號(hào)量 empty和full：保證事件發(fā)生的順序 緩沖區(qū)滿(mǎn)時(shí)，Producer停止運(yùn)行 緩沖區(qū)空時(shí)，Consumer停止運(yùn)行 讀者進(jìn)入緩沖區(qū)，寫(xiě)者必須等待 寫(xiě)者進(jìn)入緩沖區(qū)，讀者必須等待 讀者優(yōu)先：一旦有讀者進(jìn)入，則后續(xù)讀者均可進(jìn)入 合理順序：讀者在先來(lái)的寫(xiě)者之后 寫(xiě)者優(yōu)先：只要有寫(xiě)者等待，則后續(xù)讀者必須等待94MutexesImplementation of mutex_lock and mutex_unlock

55、95管程方法 死鎖的危險(xiǎn) 一旦信號(hào)量的處理代碼發(fā)生錯(cuò)誤，則會(huì)引起進(jìn)程死鎖 核心思想 實(shí)現(xiàn)一種包含過(guò)程、變量、數(shù)據(jù)結(jié)構(gòu)的獨(dú)立模塊 任何時(shí)刻，只能有一個(gè)活躍進(jìn)程在管程內(nèi) 由編譯器提供支持，實(shí)現(xiàn)進(jìn)程間的互斥 方法分析 優(yōu)點(diǎn)：實(shí)現(xiàn)了進(jìn)程互斥的自動(dòng)化 缺點(diǎn)：依賴(lài)于編譯器，無(wú)法通用或普及96管程的引入 1973年，由Hoare和Hansen提出的一種高級(jí)同步原語(yǔ)，將共享變量以及對(duì)共享變量能夠進(jìn)行的所有操作集中在一個(gè)模塊中。 管程的定義：一個(gè)管程是一個(gè)由過(guò)程、變量及數(shù)據(jù)結(jié)構(gòu)等組成的集合，它們組成一個(gè)特殊的模塊或軟件包。進(jìn)程可在任何需要的時(shí)候調(diào)用管程中的過(guò)程，但它們不能在管程之外聲明的過(guò)程中直接訪問(wèn)管程內(nèi)的數(shù)

56、據(jù)結(jié)構(gòu)。97管程的主要特性 為了保證管程共享變量的數(shù)據(jù)完整性，規(guī)定管程互斥進(jìn)入，即：任一時(shí)刻管程中只能有一個(gè)活躍進(jìn)程，這一特性使管程能有效地完成互斥。 進(jìn)入管程時(shí)的互斥由編譯器負(fù)責(zé)，而不是由程序員來(lái)安排互斥，出錯(cuò)的可能性小。98管程的多個(gè)進(jìn)程進(jìn)入 管程提供了實(shí)現(xiàn)互斥的途徑，此時(shí)，還需要一種辦法使得進(jìn)程在無(wú)法繼續(xù)運(yùn)行時(shí)被阻塞，其解決的辦法是：引入條件變量和wait、signal兩個(gè)操作。 當(dāng)一個(gè)管程過(guò)程無(wú)法繼續(xù)運(yùn)行時(shí)，將在某個(gè)條件變量上執(zhí)行wait 被阻塞 條件變量不能象信號(hào)量那樣積累信號(hào)，為了防止信號(hào)丟失，規(guī)定： wait操作必須在signal操作之前。99管程中的多個(gè)進(jìn)程進(jìn)入 當(dāng)一個(gè)進(jìn)入管程

57、的進(jìn)程執(zhí)行wait操作時(shí)，它應(yīng)當(dāng)釋放管程的互斥權(quán)；當(dāng)一個(gè)進(jìn)入管程的進(jìn)程執(zhí)行signal操作時(shí)（如喚醒），管程中便存在兩個(gè)同時(shí)處于活動(dòng)狀態(tài)的進(jìn)程。 Brinch Hansen的處理方法：執(zhí)行signal操作的進(jìn)程必須立即退出管程，即，signal語(yǔ)句只可作為管程過(guò)程的最后一條語(yǔ)句。 如果在一個(gè)條件變量上有多個(gè)進(jìn)程正在等待，則對(duì)該條件變量的signal后，系統(tǒng)調(diào)度程序只能在其中選擇一個(gè)使其恢復(fù)運(yùn)行。100Monitors (1)Example of a monitor101Monitors (2) Outline of producer-consumer problem with monitors

58、 only one monitor procedure active at one time buffer has N slots102Monitors (3)Solution to producer-consumer problem in Java (part 1)103Monitors (4)Solution to producer-consumer problem in Java (part 2)104信號(hào)量模型分析 優(yōu)點(diǎn)分析 徹底解決忙等待弊端，提高OS的管理層次 可實(shí)現(xiàn)復(fù)雜的同步與互斥情況，特別是多進(jìn)程間通信 可最大限度的保證并發(fā)效率 缺點(diǎn)分析 實(shí)現(xiàn)機(jī)制復(fù)雜，互斥和同步關(guān)系分析困難

59、存在死鎖陷阱，需要謹(jǐn)慎小心嚴(yán)密的設(shè)計(jì)105消息傳遞模型 模型思想 提供Send和Receive原語(yǔ)，用來(lái)傳遞消息 進(jìn)程通過(guò)發(fā)送和接收消息來(lái)實(shí)現(xiàn)互斥與同步 重要的優(yōu)點(diǎn)：不僅實(shí)現(xiàn)了同步，還能夠傳送大容量信息 設(shè)計(jì)要點(diǎn) 如何保證消息傳遞中不丟失？（ACK機(jī)制） 如何命名進(jìn)程，使得其地址唯一并確認(rèn)身份 如何規(guī)范消息格式，降低處理時(shí)間106Message PassingThe producer-consumer problem with N messages107Barriers Use of a barrier processes approaching a barrier all processes

60、 but one blocked at barrier last process arrives, all are let through108Dining Philosophers (1) Philosophers eat/think Eating needs 2 forks Pick one fork at a time How to prevent deadlock 互斥分析 筷子：同一時(shí)刻只能有一個(gè)哲學(xué)家拿起筷子同步分析 就餐：只有獲得兩個(gè)筷子后才能進(jìn)餐特殊情況 死鎖：如果每個(gè)哲學(xué)家都拿起一只筷子，都餓死 并行程度：五只筷子允許兩人同時(shí)進(jìn)餐109Dining Philosophers (2)A nonsolution t