程序與線程
程序将一個單獨的CPU變成多個虛拟的CPU
2.1 程序
●僞并行：一個瞬間隻能運作一個程序，但一段時間内運作多個程序，産生并行的錯覺
●多處理器系統：兩個或更多CPU，真正的并行
2.1.1程序模型
一個程序是某種類型的活動，有程式，輸入，輸出，狀态。單個處理器被若幹程序共享，處理器使用某種排程算法決定程序的切換。
●多道程式設計：(僞)并行中CPU在不同程序中快速的切換
2.1.2程序的建立
4種主要事件會導緻程序建立
1.系統初始化
2.正在運作的程式執行了建立程序的系統調用
3.使用者請求建立新程序
4.批處理作業的初始化
上面的情形中，新程序都是由于已存在的程序執行了一個用于建立程序的系統調用而建立的，這個程序可以是運作的使用者程序，滑鼠鍵盤啟動的系統程序等
UNIX中，fork用來建立新程序，父程序會建立一個與調用程序相同的副本(子程序)，兩個程序擁有相同的記憶體映象、環境字元串、打開檔案。通常子程序執行execve改變記憶體映像并運作新的程式。
Windows中，win32函數調用CreateProcess建立程序，把正确的程式裝入新的程序。父程序和子程序一開始位址空間就不同。
●守護程序：停留在背景等待被喚醒的程序，如列印
2.1.3程序的終止
程序的終止情況
●自願：1.正常退出 2.出錯退出
●非自願：1.嚴重錯誤 2.被其他程序殺死
2.1.4程序的層次結構
每個程序隻有一個父程序，但可以有任意個子程序
●UNIX啟動時建立init程序，所有程序都由init建立，整個系統的所有程序都屬于以init為根的一棵樹。
●Windows中沒有程序層次的概念，父程序得到句柄，可以用來控制子程序，但可以傳給其他程序。
2.1.5程序的狀态
程序的三種狀态：
1.運作态(占用CPU)
2.就緒态(可以運作，但是CPU被其他程序占用)
3.阻塞态(等待外部事件轉為就緒态)
排程程式決定應當運作哪個程序，何時運作，以及運作多長時間
2.1.6程序的實作
●程序表：由作業系統維護，包含程序狀态的重要資訊，包括程序由運作态轉出必須儲存的資訊如程式計數器，堆棧指針等等，進而保證程序随後能再次啟動，像從未被中斷。
2.1.7多道程式設計模型
增加記憶體來增加同時運作的程序數可以提高CPU使用率。
2.2線程
2.2.1 線程的使用
使用多線程的理由
1.多線程共享同一個位址空間和可用資料，多程序不行
2.線程更輕量級，比程序更容易建立與撤銷
3.性能更好，如果存在大量計算和I/O處理，多線程允許這些活動彼此重疊進行，加快速度。
●多線程：可以一邊磁盤操作一邊運作别的線程
●單線程：Web伺服器等待磁盤操作時，伺服器就阻塞，不處理任何到來的其它請求。
●有限狀态機：啟動非阻塞的磁盤操作，磁盤操作時伺服器可以接收請求，磁盤的回答和請求哪個先來處理哪個。
阻塞：動作完成之前必須等待，如read阻塞模式，有效輸入來之前必須一直等，read非阻塞模式就是就算沒有輸入也可以立即讀。
2.2.2 經典的線程模型
程序把資源集合到一起，線程是CPU上被排程執行的實體。
程序之間是競争關系，而線程是合作關系，共享資源，互相信任，之間沒有保護。
線程的狀态轉換和程序一樣，有阻塞，就緒，運作
每個線程有自己的堆棧，因為每個線程會調用不同的過程，有自己的執行曆史，是以需要堆棧。
通常所有的線程都是平等的，有時有父子關系。
線程庫過程
●thread_exit：完成工作後退出
●thread_join：阻塞直到特定線程退出
●thread_yield：允許線程放棄CPU讓另一個線程運作，因為線程不同于程序，無法利用時鐘中斷強制讓出CPU，隻能主動讓出CPU。
2.2.3POSIX線程
2.2.4 在使用者空間實作線程
2.2.5 在核心中實作線程
使用者級線程優點：
1.切換線程比陷入核心切換快很多
2.允許每個程序有自己的排程算法
3.擴充性強
缺點：
1.不能處理好阻塞，阻塞系統調用時會停止所有線程
2.缺頁中斷問題：程式跳轉到不在記憶體的指令上，核心負責記憶體，但不知道有使用者級線程存在。
3.程序内部沒有時鐘中斷，排程線程難，調用系統時鐘中斷開銷大
4.核心可以運作不同程序内的線程，使用者級線程始終運作自己線程中的程序，直到被剝奪CPU
2.2.7 2.2.8 2.2.9未看
2.3程序間通信
進/線程通信考慮的問題
1.如何傳遞資訊(線程中較簡單)
2.兩個或更多程序在關鍵活動中不會交叉
3.保持正确的順序
2.3.1 競争條件
競争條件：兩個或多個程序讀寫共享資料，最後的結果取決于程序運作的精确時序。
2.3.2 臨界區
●互斥：確定一個程序使用共享變量或檔案時，其他程序不能做同樣操作。
●臨界區：對共享記憶體進行通路的程式片段稱作臨界區。兩個程序不同時處于臨界區就能避免競争條件。
●好的解決競争條件的方案：
1.任何兩個程序不能同時處于臨界區
2.不應對CPU的速度和數量做任何假設
3.臨界區外運作的程序不能阻塞其他程序
4.不得使程序無限期等待進入臨界區
2.3.3忙等待的互斥
1.屏蔽中斷
對于作業系統有用，對于使用者不合适
2.鎖變量
還會出現和假脫機目錄一樣的疏漏。
3.嚴格輪換法
違反了上面的條件3
4.peterson解法
對程序調用enter_region與leave進入與離開臨界區。
5.TSL指令/XCHG指令
TSL RX，LOCK稱為測試并加鎖，該指令結束前其他處理器不允許通路該記憶體字。執行TSL的CPU将鎖住記憶體總線，防止其他CPU在本指令結束前通路記憶體。
Peterson與TSL/XCHG解法都是正确的，但都有忙等待的缺點，本質都是：當一個程序想進入臨界區時，先檢查是否允許進入，若不允許，則該程序将原地等待，直到允許為止。
忙等待浪費CPU時間，也可能引起預想不到的結果。
2.3.4 睡眠與喚醒
sleep和wakeup是程序間通信原語，在無法進入臨界區時将阻塞，而不是忙等待。sleep是引起調用程序阻塞的系統調用，即被挂起，wakeup喚醒程序。
生産者-消費者問題中可能出現競争條件，消費者剛讀取count還未判斷進入睡眠時切換到了生産者，于是生産者生産并喚醒消費者，消費者并未睡眠，丢失了wakeup信号，下次進入消費者時，從判斷進入睡眠開始執行，進入睡眠，生産者生産滿了也進入睡眠。
問題的本質在于尚未睡眠程序的wakeup丢失,可以加喚醒等待位彌補。wakeup發給清醒程序時置1，該程序将要睡眠時，如果為1，置0并保持清醒。
2.3.5信号量
用一個整型變量累計喚醒次數供以後使用，信号量的取值可以為0(無儲存下來的喚醒操作)或者正值(一個或多個喚醒操作)。
用down和up代替sleep和wakeup，對程序執行down操作時，信号量為0才睡眠，不為0減一。整個down過程的檢查數值修改變量以及是否睡眠為原子操作。
●原子操作：不可分割，要麼都執行，要麼都不執行。單CPU可以屏蔽系統中斷來實作，多CPU可以用TSL/XCHG指令來實作。(這裡使用指令隻需幾ms，而使用指令忙等待解決2.3.3的問題需要很長時間)。
●二進制信号量：如mutex，初值為1，供兩個或多個程序使用，保證同時隻有一個程序可以進入臨界區，用于互斥。
2.3.6互斥量mutex
互斥量隻需一位，有兩種狀态，解鎖和加鎖，可以用TSL或XCHG指令實作。
有兩個過程，lock與unlock，通路臨界區時，調用mutex_lock，如果互斥量解鎖，調用成功，可以進入，如果加鎖，阻塞，知道臨界區内的進/線程調用mutex_unlock。
mutex與enter_region的差別就是進入臨界區失敗時，前者阻塞，将CPU讓出，而後者始終重複測試鎖(忙等待)。
程序間如何共享資料？
1.共享資料結構如信号量放在核心中，并且隻能通過系統調用通路
2.多數作業系統提供一種方法，讓程序間共享部分位址空間。
●快速使用者區互斥量futex
實作了基本的鎖(像互斥鎖)，但避免陷入核心，改善了性能。
程序間共享通用鎖變量為一個對齊的32位幀數鎖。
●pthread中的互斥量
鎖定和解鎖的互斥量保護臨界區
條件變量：允許線程阻塞，等待一些條件
2.3.7管程
●死鎖：使用信号量和互斥量時，很小的錯誤容易造成大麻煩，如程序一直阻塞下去。
●管程：任一時刻管程中隻能有一個活躍程序，這一特性使得管程能有效完成互斥。
2.3.8消息傳遞
用消息傳遞的方法而不是共享記憶體。
設計要點：1.确認，因為消息可能丢失 2.身份認證
2.3.9屏障
應用中劃分了若幹階段，除非所有程序都就緒準備下一階段，否則任何程序都不能進入下一個階段。可以通過在每個階段安裝屏障來實作。
2.3.10避免鎖：讀-複制-更新
最快的鎖是根本沒有鎖，沒有鎖時也不能對共享資料結構進行并發讀寫進行通路。
讀-複制-更新是寫操作時複制一份副本對其進行操作，在适當的時機将原資料用副本替換。
2.4 排程
●排程程式：從就緒的程序/線程中選擇合适的運作
程序行為：
●計算密集型：大部分時間花在計算上
●I/O密集型：等待I/O上話費很多時間
何時排程：
●搶占式：時鐘中斷時進行排程
●非搶占式：時鐘中斷時不會發生排程
排程算法分類：批處理、互動式、實時
線程排程
使用者級線程性能更好：不同程序間的線程切換代價高于相同程序的線程切換。
使用者級線程可以使用為應用程式定制的線程排程程式。如web伺服器中優先運作分派線程。而核心不了解每個線程的作用。
2.5經典的IPC問題
2.5.1哲學家就餐(有限資源競争)
流行的局域以太網中，兩台計算機同時發包，那麼每台計算機等待一段随機時間後再嘗試，該方案工作良好但不完全穩定，如核電站安全系統中。
使用互斥量時，有性能的局限，5把叉子可以讓兩位哲學家進餐，而使用互斥量隻能允許一位。
2.5.2讀者-寫者問題(資料庫模型)
2.6 有關程序與線程的研究
程序問題已經有了成熟的方案，幾乎所有系統都把程序視為容器，用以管理相關資源，如位址空間、線程、打開的檔案、權限保護等。
2.7小結