Operating Systems
進(jìn)程（Process）和線程（Thread）
進(jìn)程是系統(tǒng)進(jìn)行資源分配和調(diào)度的獨立單位，每個進(jìn)程都有獨立的地址空間
-
進(jìn)程控制塊/進(jìn)程描述符 Process Control Block：操作系統(tǒng)管理進(jìn)程的一個專門數(shù)據(jù)結(jié)構(gòu)，記錄進(jìn)程的各種屬性，描述其動態(tài)變化過程。進(jìn)程與PCB一一對應(yīng)。進(jìn)程表：所有進(jìn)程的PCB集合。PCB包含：
進(jìn)程描述信息：標(biāo)識符(process ID)、進(jìn)程名、用戶標(biāo)識符、進(jìn)程組關(guān)系
進(jìn)程控制信息：狀態(tài)、優(yōu)先級、入口地址、磁盤地址...
資源情況
CPU現(xiàn)場信息：指針、寄存器值...
進(jìn)程的三種狀態(tài)：運行態(tài)：占有CPU并運行、就緒：具備運行條件但是無CPU資源、等待（阻塞）：等待某一事件而暫時不能運行，不能直接由等待到運行
-
進(jìn)程控制：
創(chuàng)建：分配標(biāo)識符和PCB、地址空間；初始化PCB；設(shè)置相應(yīng)的隊列指針
撤銷：回收資源、撤回PCB
阻塞：進(jìn)程自己運行阻塞原語
Runtime System：用戶級線程的管理，不需要內(nèi)核管理
核心級線程：內(nèi)核進(jìn)行線程管理
調(diào)度策略
先來先服務(wù)（FCFS）
最短作業(yè)優(yōu)先（Shortest Job First）
最短剩余時間優(yōu)先（Shortest Remaining Time Next）（搶占式）
最高響應(yīng)比優(yōu)先（Highest Response Ratio Next）：響應(yīng)比 = 1+ 等待時間/處理時間
-
交互式系統(tǒng)中的調(diào)度算法:
時間片輪轉(zhuǎn)：類似于隊列，用完時間片的進(jìn)程排到隊列最后
虛擬輪轉(zhuǎn)法：I/O型進(jìn)程進(jìn)入輔助隊列，輪轉(zhuǎn)時首先從輔助隊列中選擇，為空時從就緒隊列中選
最高優(yōu)先級調(diào)度算法：系統(tǒng)進(jìn)程高于用戶進(jìn)程，前臺進(jìn)程高于后臺進(jìn)程
多級反饋隊列調(diào)度算法：設(shè)置多個就緒隊列，第一個優(yōu)先級最高，不同隊列時間片不同，第一個時間片最小
優(yōu)先級反轉(zhuǎn)問題：高優(yōu)先級的進(jìn)程等待被一個低優(yōu)先級進(jìn)程占用的資源
同步機(jī)制
進(jìn)程互斥：各進(jìn)程需要共享資源，而這些資源需要排他性使用。這樣的資源叫做臨界資源/互斥資源/共享變量：一次只能給一個進(jìn)程使用
臨界區(qū)：各個進(jìn)程中對臨界資源進(jìn)行操作的程序片段
進(jìn)程互斥的軟件解；硬件解：開關(guān)中斷（不能用于多處理器）/測試并加鎖（寄存器是否為0）/交換指令（交換寄存器和鎖變量的值）
進(jìn)程同步：某個進(jìn)程需要另一個進(jìn)程提供的消息，獲得消息之前進(jìn)入阻塞態(tài)，消息到達(dá)之后被喚醒進(jìn)入就緒態(tài)；
生產(chǎn)者/消費者問題（有界緩沖問題）：生產(chǎn)者向緩沖區(qū)送數(shù)據(jù)，消費者從緩沖區(qū)取數(shù)據(jù)，不能同時對緩沖區(qū)操作。存在問題：緩沖區(qū)為空或為滿；避免忙等待：睡眠/喚醒（生產(chǎn)者<->消費者）
信號量（用于信號同步）：操作：初始化、P、V操作；P：信號量-1，檢測是否小于0，小于則進(jìn)入阻塞狀態(tài)；V：信號量+1，若小于等于0，則從隊列中喚醒一個等待的進(jìn)程進(jìn)入就緒態(tài)
信號量解決生產(chǎn)者/消費者問題：消費者執(zhí)行：P(full),V(empty)；生產(chǎn)者執(zhí)行：P(empty),V(full)；empty：空緩沖區(qū)個數(shù)
讀者寫者問題：只讀和只寫數(shù)據(jù)區(qū)的數(shù)據(jù)，只允許多個讀者同時操作。只需要第一個讀者做P(w)，最后一個讀者做V(w)
管程monitor（不適用于多處理器情況）：互斥進(jìn)入，互斥性由編譯器保證；管程中設(shè)置條件變量及等待/喚醒操作實現(xiàn)同步，可以讓一個線程或進(jìn)程先在條件變量上等待（先釋放管程使用權(quán)）。只能通過管程提供的某個過程才能訪問管程中的資源
HOARE管程：若P進(jìn)程喚醒了Q進(jìn)程，則Q進(jìn)程先執(zhí)行，P在管程中的緊急等待隊列中等待。當(dāng)一個進(jìn)程試圖進(jìn)入管程時，在入口等待隊列等待。wait操作：執(zhí)行wait操作的進(jìn)程進(jìn)入條件變量鏈末尾，喚醒緊急等待隊列或者入口隊列中的進(jìn)程；signal操作：喚醒條件變量c鏈中的進(jìn)程，自己進(jìn)入緊急等待隊列，若c鏈為空，則繼續(xù)執(zhí)行
MESA管程：將HOARE中的signal換成了notify（或者broadcast通知所有滿足條件的），進(jìn)行通知而不是立馬交換管程的使用權(quán)，在合適的時候，條件隊列首位的進(jìn)程可以進(jìn)入，進(jìn)入之前必須用while檢查條件是否合適。優(yōu)點：沒有額外的進(jìn)程切換
PTHREAD中的同步機(jī)制：互斥量保護(hù)臨界區(qū)，條件變量實現(xiàn)同步
-
進(jìn)程間通信IPC：
信號量、管程
消息傳遞 send/receive：發(fā)送進(jìn)程將消息（消息頭，消息體）發(fā)送到操作系統(tǒng)空間中設(shè)置的消息緩沖區(qū)（陷入內(nèi)核，復(fù)制消息），接受隊列的PCB中消息隊列的指針指向消息緩沖區(qū)中消息所在位置
共享內(nèi)存：兩個進(jìn)程分別有自己的地址空間。在物理內(nèi)存中建立共享內(nèi)存，將該共享內(nèi)存空間映射到兩個進(jìn)程的地址空間。讀寫數(shù)據(jù)時在自己的地址空間中寫或讀，由于有映射，所以相當(dāng)于寫到了共享內(nèi)存中
管道PIPE：利用某個傳輸介質(zhì)（內(nèi)存或文件），連接兩個相互通信的進(jìn)程。先進(jìn)先出，字符流方式讀寫。必須提供協(xié)調(diào)能力：判斷對方進(jìn)程是否存在/同步/互斥
套接字/遠(yuǎn)程過程調(diào)用：網(wǎng)絡(luò)/分布式系統(tǒng)
存儲模型
地址重定位（Relocation）/地址映射/地址轉(zhuǎn)換；不能用邏輯地址在物理內(nèi)存中讀取程序信息，邏輯地址首地址為0，其余地址都相對于首地址編址；物理地址可直接尋址。地址重定位：將程序中的邏輯地址轉(zhuǎn)換為可以直接尋址的物理地址
靜態(tài)重定位：由軟件完成，程序加載到內(nèi)存時，一次性實現(xiàn)邏輯到物理地址的轉(zhuǎn)換
動態(tài)重定位：在進(jìn)程執(zhí)行過程中，逐條執(zhí)行指令時進(jìn)行地址變換，需要硬件支持（內(nèi)存管理單元）
物理內(nèi)存管理：等長劃分（位圖，空閑/占用），不等長劃分（空閑區(qū)表/已分配區(qū)表）
內(nèi)存分配算法：首次適配first fit：在空閑區(qū)表中找第一個滿足進(jìn)程要求的空閑區(qū)；下次適配next fit：從上次找到的空閑區(qū)開始往下找；最佳適配best fit：整個空閑區(qū)表搜索，找到滿足要求的最小空閑區(qū)；最差適配...；
內(nèi)存回收算法：歸還后合并空閑區(qū)，修改空閑區(qū)表，情況：上/下相鄰，上下都相鄰/都不相鄰
伙伴系統(tǒng)（Linux內(nèi)存分配算法）：內(nèi)存按2的冪劃分，組成若干塊，組成鏈表，在該鏈表中找滿足要求的空閑塊。匹配進(jìn)程要求大小時就比較在2的哪次方之間，如果塊太大就劃分一半繼續(xù)比較；釋放之后，小的可以結(jié)合成大的（都是2的次方）
-
內(nèi)存管理方案（裝載：進(jìn)程）
單一連續(xù)區(qū)：一段時間只有一個進(jìn)程在內(nèi)存
固定分區(qū)：把內(nèi)存分為若干固定的區(qū)域，大小可不同，每個分區(qū)只能裝一個進(jìn)程
可變分區(qū)：根據(jù)進(jìn)程需要，分割出一定空間分配給進(jìn)程，剩余部分成為空閑區(qū)域；缺點：產(chǎn)生很小的不易利用的空閑區(qū)，成為外碎片，利用率下降；解決方案：緊縮技術(shù)：在內(nèi)存移動程序，將小的空閑區(qū)合并成大的空閑區(qū)
-
以上三種方案都是進(jìn)程進(jìn)入內(nèi)存的連續(xù)區(qū)域，下面三種都是進(jìn)程進(jìn)入若干個不連續(xù)的區(qū)域，地址轉(zhuǎn)換都需要硬件支持
頁式存儲：用戶空間劃分為大小相等的部分稱為頁，內(nèi)存空間劃分為同樣大小的區(qū)域稱為頁框，分配時以頁為單位，按進(jìn)程需要的頁數(shù)分配，邏輯上相鄰的頁物理上不一定相鄰。從0開始編號。邏輯地址：頁號+頁內(nèi)地址（偏移）。通過數(shù)據(jù)結(jié)構(gòu)頁表記錄了邏輯頁號對應(yīng)的物理的頁框號，每個進(jìn)程一個頁表，放在內(nèi)存，頁表起始地址在PCB/寄存器中。內(nèi)碎片
段式存儲：用戶進(jìn)程地址空間按照自身邏輯關(guān)系劃分為若干個程序段，內(nèi)存空間被動態(tài)劃分為長度不同的區(qū)域，分配時以段為單位，每段在內(nèi)存中占據(jù)連續(xù)空間，各段可以不相鄰。邏輯地址：段號+段內(nèi)地址。段表：段長、段地址
段頁式存儲：用戶進(jìn)程先按段劃分，段內(nèi)再按頁劃分，內(nèi)存劃分和分配按頁。
覆蓋技術(shù)Overlaying：程序大小超過物理內(nèi)存總和：程序運行時，不同部分在內(nèi)存中相互替代，需要在編程時聲明覆蓋結(jié)構(gòu)
交換技術(shù)Swapping：系統(tǒng)將內(nèi)存中某些進(jìn)程暫時移動到磁盤上，再把外存中某些進(jìn)程換進(jìn)內(nèi)存
存儲模型（2)--虛擬存儲技術(shù)
虛擬存儲技術(shù)：進(jìn)程運行時，將一部分裝入內(nèi)存，當(dāng)需要執(zhí)行某些指令或訪問數(shù)據(jù)時，再將那些裝入內(nèi)存
虛擬地址：虛擬內(nèi)存中指令或數(shù)據(jù)的位置，可以被訪問，仿佛是內(nèi)存的一部分
虛擬內(nèi)存：內(nèi)存和磁盤結(jié)合起來使用
-
虛擬頁式存儲管理
頁表項設(shè)計：硬件實現(xiàn)。包含頁框號、有效位（是在內(nèi)存還是磁盤）、訪問位（是否被訪問過）、修改位（內(nèi)存中是否被修改過）、保護(hù)位（只讀還是可讀寫）
頁目錄：頁表的地址
反轉(zhuǎn)頁表：從物理地址出發(fā)系統(tǒng)建立頁表，記錄虛擬地址與物理地址的對應(yīng)
快表（TLB）：CPU中引入的高速緩存cache，保存正在運行的程序的頁表的子集，快表中沒有時再查頁表
頁錯誤page fault：地址轉(zhuǎn)換過程中硬件異常。缺頁異常：頁面還未讀入內(nèi)存，由操作系統(tǒng)執(zhí)行異常處理，將該頁調(diào)入內(nèi)存，直接用空閑頁框或者置換某個頁框；頁面訪問違反了權(quán)限；錯誤的訪問地址。
駐留集：給每個進(jìn)程多少頁框：固定分配策略（進(jìn)程創(chuàng)建時確定）；可變分配策略（根據(jù)缺頁率）
置換問題：置換范圍：局部置換（在產(chǎn)生缺頁的進(jìn)程的駐留集中選擇）/全局置換（內(nèi)存中所有未鎖定的頁框作為置換的選擇）；置換策略（置換哪一個頁框）：不能用鎖定的頁框
清除策略：從駐留集中收回頁框。最佳狀態(tài)：系統(tǒng)中始終有一定數(shù)量的空閑頁框；分頁守護(hù)進(jìn)程。頁緩沖技術(shù)：不丟棄置換出的頁，仍然在內(nèi)存中，一旦進(jìn)程又要訪問該頁，則加入駐留集中
-
頁面置換算法
最佳頁面置換算法OPT：置換以后不需要或者最遠(yuǎn)的將來才需要的頁面
先進(jìn)先出FIFO：置換在內(nèi)存中駐留時間最長的頁面。會產(chǎn)生BELADY現(xiàn)象：分配給進(jìn)程的頁框增多，缺頁情況也增多
第二次機(jī)會算法SCR：按FIFO選擇某一頁面，若其訪問位為1，給第二次機(jī)會，并將訪問位置0
時鐘算法：將SCR中的隊列以時鐘表示而不是鏈表，就不用移動隊列，開銷小
最近未使用算法NRU：檢查訪問位、修改位
最近最少使用算法LRU：置換出未使用時間最長的一頁（最后一次訪問），開銷大，要維護(hù)時間戳
最不經(jīng)常使用算法NFU：訪問次數(shù)最少
老化算法：計數(shù)器在加R前先右移一位，R加在最左端
工作集算法：進(jìn)程在一段時間內(nèi)集中訪問的頁面稱為活躍頁面，為進(jìn)程提供與活躍頁面數(shù)相等的物理頁面數(shù)。工作集：一個進(jìn)程當(dāng)前正在使用的頁框集合。找出一個在時間T內(nèi)不在工作集中的頁面并置換它。通過查看R位（訪問位）
內(nèi)存映射文件：進(jìn)程通過一個系統(tǒng)調(diào)用將一個文件映射到虛擬地址空間，訪問這個文件就像訪問內(nèi)存而不是通過文件操作
寫時復(fù)制技術(shù)：多個進(jìn)程共享頁框，每頁都標(biāo)記成寫時復(fù)制
文件與文件系統(tǒng)
-
文件系統(tǒng)：操作系統(tǒng)中統(tǒng)一管理信息資源的一種軟件，管理文件的存儲，檢索，更新
統(tǒng)一管理磁盤空間
實現(xiàn)文件的按名存取，名字空間到磁盤空間的映射
方便用戶使用的接口
提供共享、保護(hù)手段
提高文件系統(tǒng)的性能
提供與IO系統(tǒng)統(tǒng)一的接口
文件結(jié)構(gòu)：流式文件；記錄式文件。順序存??；隨機(jī)存取
物理塊：信息存儲分配傳輸?shù)莫毩挝?/p>
磁盤讀取信息：磁頭（磁盤）、磁道、扇區(qū)--傳輸?shù)絻?nèi)存
用位圖反應(yīng)磁盤中空間使用情況，若物理塊未被使用則為1?？臻e塊表
文件控制塊FCB：保存文件屬性，為管理文件設(shè)置的數(shù)據(jù)結(jié)構(gòu)
文件目錄：文件名到文件物理地址轉(zhuǎn)換，將所有文件的管理信息組織在一起。目錄項可以是FCB
目錄結(jié)構(gòu)：一級目錄結(jié)構(gòu)；二級；樹形
目錄文件：文件目錄以文件形式存在磁盤上
順序結(jié)構(gòu)：文件信息存儲在連續(xù)的物理塊中
鏈接結(jié)構(gòu)：不連續(xù)的物理塊中，各塊之間通過指針連接
新型鏈接結(jié)構(gòu)：文件分配表FAT，所有物理塊的指針集中存放在FAT中，而不是分布存在物理塊末尾。文件的起始塊號存放在FCB
索引結(jié)構(gòu)：不連續(xù)物理塊。系統(tǒng)為每個文件建立索引表，將物理塊的號存放在表中，第i個條目指向文件的第i塊。索引表的位置放在FCB
