Linux操作系統分析,主講：陳香蘭 助教：賈永泉、毛熠璐 3606864-83（西區電三421） Autumn 2007,Linux的進程,xlanchen2007.9.18,xlanchen2007.9.25,Linux Operating Systems Analysis,3,主要內容,進程描述符 進程切換 進程的創建和刪除 進程調度,xlanchen2007.9.25,Linux Operating Systems Analysis,4,進程的概念,進程是執行程序的一個實例 進程和程序的區別 幾個進程可以并發的執行一個程序 一個進程可以順序的執行幾個程序,xlanchen2007.9.25,Linux Operating Systems Analysis,5,進程描述符,為了管理進程，內核必須對每個進程進行清晰的描述。 進程描述符提供了內核所需了解的進程信息 include/linux/sched.h struct task_struct 數據結構很龐大 基本信息 管理信息 控制信息,xlanchen2007.9.25,Linux Operating Systems Analysis,6,xlanchen2007.9.25,Linux Operating Systems Analysis,7,Linux進程的狀態,可運行狀態(TASK_RUNNING) 可中斷的等待狀態(TASK_INTERRUPTIBLE) 不可中斷的等待狀態(TASK_UNINTERRUPTIBLE) 暫停狀態(TASK_STOPPED) 僵死狀態(TASK_ZOMBIE) 狀態值的改變通常是一個簡單的賦值 內核也提供set_task_state 和set_current_state 宏,xlanchen2007.9.25,Linux Operating Systems Analysis,8,進程狀態轉換圖,xlanchen2007.9.25,Linux Operating Systems Analysis,9,標識一個進程,使用進程描述符地址 進程和進程描述符之間有非常嚴格的一一對應關系，使得用32位進程描述符地址標識進程非常方便 使用PID (Process ID，PID) 每個進程的PID都存放在進程描述符的pid域中 032767 新pid的產生：get_pid +1 循環,xlanchen2007.9.25,Linux Operating Systems Analysis,10,獲得一個進程的pid,系統調用getpidsys_getpid 關于進程組 使用組鏈表 所有進程共享組內第一個進程的pid 數據：tgpid 單獨一個進程可以看成只有一個進程的組 getpid返回組pid,xlanchen2007.9.25,Linux Operating Systems Analysis,11,進程描述符和進程的內核堆棧,Linux為每個進程分配一個8KB大小的內存區域，用于存放該進程兩個不同的數據結構： 進程描述符 進程的內核堆棧 進程處于內核態時使用， 不同于用戶態堆棧 內核控制路徑所用的堆棧 很少，因此對棧和描述符 來說，8KB足夠了,xlanchen2007.9.25,Linux Operating Systems Analysis,12,Task_union,C語言允許用如下的一個union結構來方便的表示這樣的一個混合體 進程描述符的分配/回收/訪問 alloc_task_struct free_task_struct get_task_struct,=2048,xlanchen2007.9.25,Linux Operating Systems Analysis,13,current宏進程描述符,從剛才看到的進程描述符和內核態堆棧之間的配對，內核可以很容易的從esp寄存器的值獲得當前在CPU上運行的進程的描述符指針 因為這個內存區是8KB=213大小，內核必須做的就是讓esp有13位的有效位，以獲得進程描述符的基地址 這個工作由current宏來完成,8191=8192-1=0x2000-1=0x1fff 取反：0xffffe000（最后13位為0）,xlanchen2007.9.25,Linux Operating Systems Analysis,14,Current宏的使用,Current宏可以看成當前進程的進程描述符指針，在內核中直接使用 比如current-pid返回在CPU上正在執行的進程的PID,xlanchen2007.9.25,Linux Operating Systems Analysis,15,進程鏈表,為了對給定類型的進程(比如所有在可運行狀態下的進程)進行有效的搜索，內核維護了幾個進程鏈表 所有進程鏈表,在進程描述符中：,xlanchen2007.9.25,Linux Operating Systems Analysis,16,SET_LINKS和REMOVE_LINKS宏用來分別在進程鏈表中插入和刪除一個進程描述符。,xlanchen2007.9.25,Linux Operating Systems Analysis,17,for_each_task宏掃描整個進程鏈表,xlanchen2007.9.25,Linux Operating Systems Analysis,18,TASK_RUNNING狀態的進程鏈表,當內核調度程序尋址一個新的進程在cpu上運行時，必須只考慮可運行進程，因為掃描整個進程鏈表效率很低 引入了可運行狀態的雙向循環鏈表，也叫運行隊列 進程描述符使用 用來實現運行隊列,xlanchen2007.9.25,Linux Operating Systems Analysis,19,對可運行隊列的一些操作函數,增加/刪除一個可運行進程,可運行隊列的長度，可運行進程的個數,喚醒一個進程，使一個進程可運行,xlanchen2007.9.25,Linux Operating Systems Analysis,20,pidhash表及鏈接表,在一些情況下，內核必須能從進程的PID得出對應的進程描述符指針。例如kill系統調用 為了加速查找，引入了pidhash散列表 用pid_hashfn宏把PID轉換成表的索引,xlanchen2007.9.25,Linux Operating Systems Analysis,21,pidhash表及鏈接表,xlanchen2007.9.25,Linux Operating Systems Analysis,22,進程之間的親屬關系,程序創建的進程具有父子關系，在編程時往往需要引用這樣的父子關系。進程描述符中有幾個域用來表示這樣的關系,xlanchen2007.9.25,Linux Operating Systems Analysis,23,等待隊列,當要把除了TASK_RUNNING狀態之外的進程組織在一起時，linux使用了等待隊列 TASK_STOPPED和TASK_ZOMBIE不在專門的鏈表中 TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE狀態的進程再分成很多類，每一類對應一個特定的事件。在這種情況下，進程狀態提供的信息滿足不了快速檢索，因此，內核引進了另外的進程鏈表，叫做等待隊列 等待隊列在內核中有很多用途，尤其是對中斷處理、進程同步和定時用處很大,xlanchen2007.9.25,Linux Operating Systems Analysis,24,等待隊列使得進程可以在事件上的條件等待，并且當等待的條件為真時，由內核喚醒它們 等待隊列由循環鏈表實現 在等待隊列上內核實現了一些操作函數 Add_wait_queue remove_wait_queue,xlanchen2007.9.25,Linux Operating Systems Analysis,25,等待隊列的鏈表,xlanchen2007.9.25,Linux Operating Systems Analysis,26,進程等待,等待一個特定事件的進程能調用下面幾個函數中的任一個 sleep_on sleep_on_timeout interruptible_sleep_on interruptible_sleep_on_timeout 進程等待由需要等待的進程自己進行（調用）,xlanchen2007.9.25,Linux Operating Systems Analysis,27,sleep_on,xlanchen2007.9.25,Linux Operating Systems Analysis,28,進程的喚醒,利用wake_up或者wake_up_interruptible等一系列的宏，都讓插入等待隊列中的進程進入TASK_RUNNING狀態,xlanchen2007.9.25,Linux Operating Systems Analysis,29,進程切換(process switching),為了控制進程的執行，內核必須有能力掛起正在CPU上執行的進程，并恢復以前掛起的某個進程的執行，這叫做進程切換，任務切換，上下文切換,xlanchen2007.9.25,Linux Operating Systems Analysis,30,進程上下文,包含了進程執行需要的所有信息 用戶地址空間 包括程序代碼，數據，用戶堆棧等 控制信息 進程描述符，內核堆棧等 硬件上下文,xlanchen2007.9.25,Linux Operating Systems Analysis,31,硬件上下文,盡管每個進程可以有自己的地址空間，但所有的進程只能共享CPU的寄存器。 因此，在恢復一個進程執行之前，內核必須確保每個寄存器裝入了掛起進程時的值。這樣才能正確的恢復一個進程的執行 硬件上下文： 進程恢復執行前必須裝入寄存器的一組數據 包括通用寄存器的值以及一些系統寄存器 通用寄存器如eax，ebx等 系統寄存器如eip，esp，cr3等等,xlanchen2007.9.25,Linux Operating Systems Analysis,32,在linux中 一個進程的硬件上下文主要保存在thread_struct中 其他信息放在內核態堆棧中,xlanchen2007.9.25,Linux Operating Systems Analysis,33,thread_struct,xlanchen2007.9.25,Linux Operating Systems Analysis,34,上下文切換,switch_to宏執行進程切換，schedule()函數調用這個宏一調度一個新的進程在CPU上運行 在schedule()中找到調用switch_to宏的位置 switch_to利用了prev和next兩個參數： prev：指向當前進程 next：指向被調度的進程,xlanchen2007.9.25,Linux Operating Systems Analysis,35,當前進程仍然是prev 這個push操作針對的是 當前進程的堆棧,保存esi，edi，ebp,保存esp到%0中,嵌入式匯編中 用這種方法表 示輸入、輸出 參數，可以從 0開始編號,%0是什么？,保存esp到當前進程的上下文中,從next的上下文中取出堆棧的位置，將其作為當前堆棧,堆棧被切換,在prev進程的上下文中設置返回地址，返回到下面標號為1處,從next進程的上下文中取得該進程的返回地址，放入堆棧中,調用_switch_to函數,xlanchen2007.9.25,Linux Operating Systems Analysis,36,進程切換的關鍵語句,堆棧的切換 從此，內核對next的內核態堆棧操作，因此，這條指令執行從prev到next真正的上下文切換，因為進程描述符和內核態堆棧緊密聯系在一起，改變內核態堆棧就意味改變當前進程,xlanchen2007.9.25,Linux Operating Systems Analysis,37,什么時候next進程真正開始執行呢？ call=保存返回地址+跳轉到target處執行 ret=從堆棧上獲得返回地址，并跳轉到該返回地址處執行 ？當_switch_to正常返回時，發生了什么事情？,xlanchen2007.9.25,Linux Operating Systems Analysis,38,標號為1的執行代碼處,一個進程被正常切換出時，保存的eip總是標號為1的那個位置 當這個進程再次被調度運行時，恢復在堆棧上的返回地址總是這個1 1: popl %ebp popl %edi popl %esi,xlanchen2007.9.25,Linux Operating Systems Analysis,39,_switch_to,_switch_to用來處理其他上下文的切換 此時，使用的堆棧是next進程的堆棧，這個堆棧上沒有_switch_to需要的參數prev和next 怎么傳參呢？ 找到_switch_to的函數定義和函數聲明 找到FASTCALL的定義,xlanchen2007.9.25,Linux Operating Systems Analysis,40,_switch_to的關鍵操作,unlazy_fpu() 處理數學協處理器 保存和恢復fs、gs 等等,xlanchen2007.9.25,Linux Operating Systems Analysis,41,？哪里切換了進程的地址空間,從執行switch_to的位置往前找,xlanchen2007.9.25,Linux Operating Systems Analysis,42,Project：進程的切換,對Linux中進程的切換過程進行分析，提交分析報告,xlanchen2007.9.25,Linux Operating Systems Analysis,43,進程的創建,許多進程可以并發的運行同一程序，這些進程共享內存中程序正文的單一副本，但每個進程有自己的單獨的數據和堆棧區 一個進程可以在任何時刻可以執行新的程序，并且在它的生命周期中可以運行幾個程序 又如，只要用戶輸入一條命令，shell進程就創建一個新進程,xlanchen2007.9.25,Linux Operating Systems Analysis,44,傳統的UNIX操作系統采用統一的方式來創建進程 子進程復制父進程所擁有的資源 缺點： 創建過程慢、效率低 事實上，子進程復制的很多資源是不會使用到的 現代UNIX內核通過引入三種不同的機制來解決這個問題,xlanchen2007.9.25,Linux Operating Systems Analysis,45,1、寫時復制技術，Copy-On-Writing，COW 寫時復制技術允許父子進程能讀相同的物理頁。 只要兩者有一個進程試圖寫一個物理頁，內核就把這個頁的內容拷貝到一個新的物理頁，并把這個新的物理頁分配給正在寫的進程,xlanchen2007.9.25,Linux Operating Systems Analysis,46,2、輕量級進程允許父子進程共享許多數據結構 頁表 打開的文件列表 信號處理 3、vfork 使用vfork創建的新進程能夠共享父進程的內存地址空間。父進程在這個過程中被阻塞，直到子進程退出或者執行一個新的程序,xlanchen2007.9.25,Linux Operating Systems Analysis,47,Linux的進程創建,Linux提供了幾個系統調用來創建和終止進程，以及執行新程序 Fork，vfork和clone系統調用創建新進程 其中，clone創建輕量級進程，必須指定要共享的資源 exec系統調用執行一個新程序 exit系統調用終止進程（進程也可以因收到信號而終止）,xlanchen2007.9.25,Linux Operating Systems Analysis,48,fork,fork系統調用創建一個新進程 調用fork的進程稱為父進程 新進程是子進程 子進程幾乎就是父進程的完全復制。它的地址空間是父進程的復制，一開始也是運行同一程序。 fork系統調用為父子進程返回不同的值,xlanchen2007.9.25,Linux Operating Systems Analysis,49,exec,很多情況下，子進程從fork返回后很多會調用exec來開始執行新的程序 這種情況下，子進程根本不需要讀或者修改父進程擁有的所有資源。 所以fork中地址空間的復制依賴于Copy On Write技術，降低fork的開銷,xlanchen2007.9.25,Linux Operating Systems Analysis,50,使用fork和exec的例子,If (result = fork() = 0) /* 子進程代碼 */ if (execve(“new_program”,)0) perror(“execve failed”); exit(1); else if (result0) perror(“fork failed”) /* result=子進程的pid，父進程將會從這里繼續執行*/ ,xlanchen2007.9.25,Linux Operating Systems Analysis,51,分開這兩個系統調用是有好處的 比如服務器可以fork許多進程執行同一個程序 有時程序只是簡單的exec，執行一個新程序 在fork和exec之間，子進程可以有選擇的執行一系列操作以確保程序以所希望的狀態運行 重定向輸入輸出 關閉不需要的打開文件 改變UID或是進程組 重置信號處理程序 若單一的系統調用試圖完成所有這些功能將是笨重而低效的 現有的fork-exec框架靈活性更強 清晰，模塊化強,xlanchen2007.9.25,Linux Operating Systems Analysis,52,do_fork,不論是fork，vfork還是clone，在內核中最終都調用了do_fork,xlanchen2007.9.25,Linux Operating Systems Analysis,53,xlanchen2007.9.25,Linux Operating Systems Analysis,54,閱讀do_fork，了解大致程序流程 ？子進程從哪里開始執行，它的返回值是什么？ 觀察子進程的初始上下文是怎么設置的 內核堆棧的內容 Thread_struct的內容,xlanchen2007.9.25,Linux Operating Systems Analysis,55,注意：childregs指針指向哪里,eax寄存器用作返回值，這里強制為0,在上下文中，設置用戶態堆棧指針,設置內核態堆棧指針,被調度后，執行入口 強制從ret_from_fork返 回用戶態,此后，由于子進程處于調度隊列上，因此在合適的時候會被調度， 調度時根據這里設置的上下文返回 用戶態,xlanchen2007.9.25,Linux Operating Systems Analysis,56,子進程的內核態堆棧,進程描述符,子進程的8K union,esp,返回值eax被強制寫0,用戶態堆棧esp的值,用戶態下eip的值,子進程恢復到用戶態時需要的上下文,eip,esp,子進程的硬件上下文,ret_from_fork,低地址,高地址,xlanchen2007.9.25,Linux Operating Systems Analysis,57,子進程的執行,fork后，子進程處于可運行狀態，由調度器決定何時把CPU交給這個子進程 進程切換后因為eip指向ret_from_fork，所以CPU立刻跳轉到ret_from_fork()去執行。 接著這個函數調用ret_from_sys_call()，此函數用存放在棧中的值裝載所有寄存器，并強迫CPU返回用戶態,xlanchen2007.9.25,Linux Operating Systems Analysis,58,內核線程,系統把一些重要的任務委托給周期性執行的進程 刷新磁盤高速緩存 交換出不用的頁框 維護網絡鏈接等待 內核線程與普通進程的差別 每個內核線程執行一個單獨指定的內核函數 只運行在內核態 只使用大于PAGE_OFFSET的線性地址空間,xlanchen2007.9.25,Linux Operating Systems Analysis,59,線程和進程的比較,Linux內核中沒有線程的概念 沒有針對所謂線程的調度策略 沒有數據結構用來表示一個線程 一般線程的概念在linux中只是表現為一組共享資源的進程(每個這樣的進程都有自己的進程描述符) 在其他系統中(比如windows) 線程是實實在在的一種運行抽象，提供了比進程更輕更快的調度單元 在linux中“線程”僅僅是表示多個進程共享資源的一種說法,xlanchen2007.9.25,Linux Operating Systems Analysis,60,創建內核線程,Kerenl_thread()創建一個內核線程，并且只能由另一個內核線程來執行這個調用,xlanchen2007.9.25,Linux Operating Systems Analysis,61,進程樹,進程0 進程1 ,xlanchen2007.9.25,Linux Operating Systems Analysis,62,進程0,所有進程的祖先叫做進程0 在系統初始化階段由start_kernel()函數從無到有手工創建的一個內核線程 存放在init_task_union變量中的一個進程描述符和一個內核態堆棧（回憶一下啟動時，堆棧的初始化） 用INIT_MM, INIT_MMAP, INIT_FS, INIT_FILES, INIT_SIGNALS宏初始化進程描述符的各個對應域 頁全局目錄，swapper_pg_dir變量 進程0最后的初始化工作創建init內核線程，此后運行cpu_idle，成為idle進程,xlanchen2007.9.25,Linux Operating Systems Analysis,63,進程1,又稱為init進程 由進程0在start_kernel調用rest_init創建 init進程PID為1，當調度程序選擇到init進程時，init進程開始執行init()函數,xlanchen2007.9.25,Linux Operating Systems Analysis,64,init() 為常規內核任務初始化一些必要的內核線程，如: kflushd 刷新臟緩沖區中的內容到磁盤以歸還內存 kswapd 執行內存回收功能的線程 最后init()函數調用execve()系統調用裝入可執行程序init。從此，init內核線程變成一個普通的進程。但init進程從不終止，因為它創建和監控操作系統外層的所有進程的活動,xlanchen2007.9.25,Linux Operating Systems Analysis,65,撤銷進程,進程終止 進程終止的一般方式是exit()系統調用。 這個系統調用可能由編程者明確的在代碼中插入 另外，在控制流到達主過程C中的main()函數的最后一條語句時，執行exit()系統調用 內核可以強迫進程終止 當進程接收到一個不能處理或忽視的信號時 當在內核態產生一個不可恢復的CPU異常而內核此時正代表該進程在運行,xlanchen2007.9.25,Linux Operating Systems Analysis,66,進程終止使用exit系統調用 刪除進程 在父進程調用wait()類系統調用檢查子進程是否合法終止以后，就可以刪除這個進程,xlanchen2007.9.25,Linux Operating Systems Analysis,67,Project：進程的創建,使用C語言編寫一段用戶程序 調用fork創建一個子進程 然后讓子進程和父進程分別輸出fork的返回值 目的：從用戶態體驗進程的創建 對Linux中進程的創建進行分析，提交分析報告,xlanchen2007.9.25,Linux Operating Systems Analysis,68,進程調度,調度策略 調度算法,xlanchen2007.9.25,Linux Operating Systems Analysis,69,調度策略（scheduling policy）,決定什么時候以怎樣的方式選擇一個新進程運行的一組規則 Linux的調度基于分時技術 允許多個進程“并發”運行 CPU的時間被劃分成“片”，給每個可運行進程分配一片 在單處理器上，任何時刻只能運行一個進程，當一個并發執行的進程時間片用完時（到期）還沒有終止，就可以進行進程調度 分時依賴于時鐘中斷，對進程透明,xlanchen2007.9.25,Linux Operating Systems Analysis,70,Linux進程的優先級 根據特定的算法計算出進程的優先級，用一個值表示 這個值表示把進程如何適當的分配給CPU Linux中進程的優先級是動態的 調度程序會根據進程的行為周期性的調整進程的優先級 較長時間未分配到CPU的進程，通常 已經在CPU上運行了較長時間的進程，通常,xlanchen2007.9.25,Linux Operating Systems Analysis,71,進程的分類,不同類型的進程有不同的調度需求 第一種分類： I/O-bound 頻繁的進行I/O 通常會花費很多時間等待I/O操作的完成 CPU-bound 計算密集型 需要大量的CPU時間進行運算,xlanchen2007.9.25,Linux Operating Systems Analysis,72,第二種分類 交互式進程（interactive process） 需要經常與用戶交互，因此要花很多時間等待用戶輸入操作 響應時間要快，平均延遲要低于50150ms 典型的交互式程序：shell、文本編輯程序、圖形應用程序等,xlanchen2007.9.25,Linux Operating Systems Analysis,73,批處理進程（batch process） 不必與用戶交互，通常在后臺運行 不必很快響應 典型的批處理程序：編譯程序、科學計算 實時進程（real-time process） 有實時需求，不應被低優先級的進程阻塞 響應時間要短、要穩定 典型的實時進程：視頻/音頻、機械控制等,xlanchen2007.9.25,Linux Operating Systems Analysis,74,與調度相關的系統調用,nice getpriority/setpriority sched_getscheduler/sched_setscheduler sched_getparam/sched_setparam sched_yield sched_get_priority_min/sched_get_priority_max sched_rr_get_interval,xlanchen2007.9.25,Linux Operating Systems Analysis,75,時間片的選擇,時間片的長短對系統性能非常關鍵，它既不能太長也不能太短 太短： 頻繁的切換會造成系統開銷過大 假如切換時間為1ms，時間片設置為1ms，那就沒空執行進程了,xlanchen2007.9.25,Linux Operating Systems Analysis,76,太長 幾乎每個進程都一次運行完 并發的概念基本消失 普通進程需要等待很長時間才能運行 時間片大小的選擇總是一種折衷。Linux采取單憑經驗的方法，即選擇盡可能長的時間片，同時能保持良好的響應時間,xlanchen2007.9.25,Linux Operating Systems Analysis,77,調度算法,epoch linux調度算法把CPU時間劃分為時期（epoch） 在一個單獨的時期內，每個進程有一個指定的時間片 一個進程用完它的時間片時，就會被強占 只要進程的時間片沒有用完，就可以被多次調度運行 當所有的進程用完它的時間片的時候，一個時期才結束