一怔锌、導(dǎo)論

概念

操作系統(tǒng)極小化定義：內(nèi)核才是操作系統(tǒng)
中斷：當(dāng)出現(xiàn)需要時蹦锋，CPU暫時停止當(dāng)前進(jìn)程的執(zhí)行渣锦，轉(zhuǎn)而執(zhí)行處理新情況的中斷處理程序。當(dāng)執(zhí)行完該中斷處理程序后飞傀，則重新從剛才停下的位置繼續(xù)當(dāng)前進(jìn)程的運(yùn)行皇型。

設(shè)備控制器：
每個設(shè)備控制器有一個本地緩沖
CPU在內(nèi)存和本地緩沖之間傳輸數(shù)據(jù)
I/O控制器從設(shè)備到本地緩沖之間傳輸數(shù)據(jù)
協(xié)作：控制器通過調(diào)用中斷通知CPU完成操作

并行：同一時刻運(yùn)行
并發(fā)：同短時間內(nèi)依次運(yùn)行

雙重模式：用戶模式和內(nèi)核模式
由硬件提供模式位诬烹，特權(quán)指令即可能引起系統(tǒng)崩潰的指令，只能運(yùn)行在內(nèi)核模式

用戶程序需要用特權(quán)指令則執(zhí)行系統(tǒng)調(diào)用

1. CPU和設(shè)備控制器可以并行工作
2. 一次系統(tǒng)調(diào)用的完成需要進(jìn)行2次模式轉(zhuǎn)換
3. 批處理系統(tǒng)的主要缺點(diǎn)是缺乏交互性
4. 特權(quán)指令：獲取事件指令弃鸦、內(nèi)存訪問指令绞吁、I/O指令
5. 操作系統(tǒng)的最基本的設(shè)計(jì)目標(biāo)是 使應(yīng)用程序能夠順利運(yùn)行 ，在此基礎(chǔ)上唬格，還需要考慮 高效 （面向系統(tǒng)）和 易用 （面向用戶）

操作系統(tǒng)類型

• 大型機(jī)系統(tǒng)（目標(biāo)系統(tǒng)效率）
  簡單批處理系統(tǒng)：作業(yè)（單道程序設(shè)計(jì)）
  多道程序設(shè)計(jì)系統(tǒng)：相互穿插運(yùn)行
  分時系統(tǒng)：時間片輪轉(zhuǎn)
• 桌面系統(tǒng)
  Windows家破、Linux、MacOS
• 嵌入式系統(tǒng)
  IOS购岗、Android
• 手持系統(tǒng)
• 分布式系統(tǒng)
  支持分布式處理的軟件系統(tǒng)汰聋，又稱松耦合系統(tǒng)
• 虛擬系統(tǒng)
• 多處理器系統(tǒng)
  并行系統(tǒng)
  緊耦合系統(tǒng)

二、操作系統(tǒng)結(jié)構(gòu)

• 操作系統(tǒng)服務(wù)形式
  系統(tǒng)調(diào)用
  用戶接口
  系統(tǒng)程序

• 操作系統(tǒng)結(jié)構(gòu)

CLI(command-line interface)命令行界面
GUI(graphical user interface)用戶圖形界面

• 微內(nèi)核
  好處:
  便于擴(kuò)充微內(nèi)核
  便于移植操作系統(tǒng)到新架構(gòu)系統(tǒng)上
  更穩(wěn)定 (更少的代碼運(yùn)行在核心態(tài))
  更安全
  壞處:
  用戶空間和內(nèi)核空間通信的系統(tǒng)開銷增加
  解決方法：提出消息傳遞機(jī)制
• 模塊結(jié)構(gòu)

• 虛擬機(jī)

虛擬機(jī)：一種通過軟件模擬實(shí)現(xiàn)韭邓，具有完整硬件系統(tǒng)功能，并運(yùn)行在一個完全隔離環(huán)境中的完整計(jì)算機(jī)系統(tǒng)

宿主操作系統(tǒng)（Host OS）：安裝在硬件上的OS
客戶操作系統(tǒng)（Guest OS）安裝在操作系統(tǒng)上的操作系統(tǒng)

1. 采用簡單結(jié)構(gòu)的操作系統(tǒng)是MS-DOS
2. 微內(nèi)核操作系統(tǒng)效率更高（X）
3. 大多數(shù)線代操作系統(tǒng)采用的是模塊結(jié)構(gòu)
4. 用戶接口和系統(tǒng)調(diào)用是操作系統(tǒng)提供給用戶（程序）的服務(wù)形式
5. 系統(tǒng)調(diào)用之間往往會相互調(diào)用，但這不涉及模式轉(zhuǎn)換（√）
6. 服務(wù)器虛擬機(jī)主要功能是使得代碼能夠跨平臺運(yùn)行（X）
7. 模塊結(jié)構(gòu)更加安全（X）
8. 操作系統(tǒng)的結(jié)構(gòu)有多種辜御，其中采用微內(nèi)核結(jié)構(gòu)的有 Windows XP Mach QNX 等鸭你；采用模塊化結(jié)構(gòu)有 Solaris Linux Mac 等

三、進(jìn)程

概念

• 進(jìn)程包括
  • 代碼(Text)
  • 當(dāng)前活動
    程序計(jì)數(shù)器(PC)：指向當(dāng)前要執(zhí)行的指令
    堆棧(Stack)：存放函數(shù)參數(shù)擒权、臨時變量等臨時數(shù)據(jù)
    數(shù)據(jù)(Data)：全局變量袱巨，處理的文件
    堆(Heap)：動態(tài)內(nèi)存分配
• PCB
  進(jìn)程狀態(tài)
  程序計(jì)數(shù)器
  CPU寄存器
  CPU調(diào)度信息
  內(nèi)存管理信息
  計(jì)賬信息
  I/O狀態(tài)信息

CPU在進(jìn)程間切換

五狀態(tài)圖

1. 如果系統(tǒng)中有N個進(jìn)程，運(yùn)行的進(jìn)程最多1個碳抄，最少0個愉老；就緒進(jìn)程最多N-1個最少0個；等待進(jìn)程最多N個剖效，最少0個嫉入。
2. 一個進(jìn)程退出等待隊(duì)列而進(jìn)入就緒隊(duì)列是因?yàn)檫M(jìn)程獲得了所等待的資源
3. 等待只能到就緒，就緒只能到運(yùn)行
4. 進(jìn)程和程序是一一對應(yīng)的（X）

進(jìn)程創(chuàng)建

1. 進(jìn)程創(chuàng)建原語的任務(wù)是為進(jìn)程創(chuàng)建PCB表
2. 進(jìn)程操作的原語有創(chuàng)建璧尸、撤銷咒林、喚醒、阻塞原語

請從資源共享爷光、進(jìn)程創(chuàng)建和進(jìn)程結(jié)束三個方面談?wù)劯高M(jìn)程和子進(jìn)程的關(guān)系垫竞。
資源共享方面：父進(jìn)程創(chuàng)建子進(jìn)程時，子進(jìn)程可能從操作系統(tǒng)那里直接獲得資源蛀序，也可以從父進(jìn)程那里獲得欢瞪。父進(jìn)程可能必須在子進(jìn)程之間共享資源活烙。 進(jìn)程創(chuàng)建方面：子進(jìn)程被父進(jìn)程創(chuàng)建時，除了得到各種物理和邏輯資源外遣鼓，初始化數(shù)據(jù)（或輸入）由父進(jìn)程傳遞給子進(jìn)程瓣颅。
進(jìn)程結(jié)束方面：子進(jìn)程使用了超過它所分配的資源，或者分配給子進(jìn)程的任務(wù)已不再需要譬正，父進(jìn)程將終止子進(jìn)程宫补。父進(jìn)程退出，如果父進(jìn)程終止曾我，那么操作系統(tǒng)（處特殊的操作系統(tǒng)）不允許子進(jìn)程繼續(xù)粉怕。

進(jìn)程間通信

• 兩種基本形式
  共享內(nèi)存
  消息傳遞

采用間接通信的方法有剪貼板、系統(tǒng)消息隊(duì)列抒巢、信箱

四贫贝、線程

概念

• 線程
  可在CPU上運(yùn)行的基本執(zhí)行單位
  進(jìn)程內(nèi)的一個代碼片段可以被創(chuàng)建稱為一個線程
  線程狀態(tài)：就緒、運(yùn)行蛉谜、等待等
  線程操作：創(chuàng)建稚晚、撤銷、等待型诚、喚醒等
  進(jìn)程依舊是資源分配的基本單位
  線程自己不擁有系統(tǒng)資源客燕，通過進(jìn)程申請資源
• 線程結(jié)構(gòu)

• 線程優(yōu)點(diǎn)

• 線程和進(jìn)程比較
  

什么是用戶態(tài)線程和核心態(tài)線程？它們之間的映射關(guān)系有哪些狰贯？

• 用戶態(tài)線程：用戶態(tài)線程的管理過程全部由用戶程序完成也搓，操作系統(tǒng)內(nèi)核只對進(jìn)程進(jìn)行管理。
• 核心態(tài)線程：核心態(tài)線程由操作系統(tǒng)內(nèi)核進(jìn)行管理涵紊。操作系統(tǒng)內(nèi)核給應(yīng)用程序提供相應(yīng)的系統(tǒng)調(diào)用和應(yīng)用程序接口API傍妒，以使用戶程序可以創(chuàng)建、執(zhí)行摸柄、撤銷進(jìn)程颤练。
• 用戶態(tài)線程與和核心態(tài)線程之間的映射關(guān)系有1對1、多對1驱负、多對多嗦玖。

1. 一對一模型最得益于多處理器架構(gòu)
2. Win32線程調(diào)用會產(chǎn)生系統(tǒng)調(diào)用

多線程模型

線程庫

image.png

五、調(diào)度

概念

（可選）長程調(diào)度：新建->就緒
（必需）短程調(diào)度：選擇下一個執(zhí)行的進(jìn)程

將CPU切換到另一個進(jìn)程需要保存當(dāng)前進(jìn)程的狀態(tài)并恢復(fù)另一個進(jìn)程的狀態(tài)的任務(wù)為上下文切換电媳。

• CPU調(diào)度可能發(fā)生的時機(jī)
  從運(yùn)行轉(zhuǎn)到等待（非搶占式）
  運(yùn)行轉(zhuǎn)到就緒（搶占式）
  從等待轉(zhuǎn)到就緒（搶占式）
  終止運(yùn)行（非搶占式）

并行：同一時刻運(yùn)行
并發(fā)：同短時間內(nèi)依次運(yùn)行

CPU調(diào)度可發(fā)生在哪些情況下庆亡？哪些情況是可搶占式調(diào)度匾乓？哪些是非搶占式調(diào)度？
（1） 正在執(zhí)行的進(jìn)程執(zhí)行完畢又谋。
（2） 執(zhí)行中進(jìn)程自己調(diào)用阻塞原語拼缝。
（3） 執(zhí)行中進(jìn)程調(diào)用了P原語操作娱局，從而因資源不足而被阻塞；或調(diào)用了V原語操作激活了等待資源的進(jìn)程隊(duì)列咧七。
（4） 執(zhí)行中進(jìn)程提出I/O請求后被阻塞衰齐。
（5） 在分時系統(tǒng)中時間片已經(jīng)用完。
（6） 在執(zhí)行完系統(tǒng)調(diào)用继阻，在系統(tǒng)程序返回用戶進(jìn)程時耻涛，可認(rèn)為系統(tǒng)進(jìn)程執(zhí)行完畢，從而可調(diào)度選擇一新的用戶進(jìn)程執(zhí)行瘟檩。
（7） 就緒隊(duì)列中的某進(jìn)程的優(yōu)先級變的高于當(dāng)前執(zhí)行進(jìn)程的優(yōu)先級抹缕，從而也將引發(fā)進(jìn)程調(diào)度。
可搶占式調(diào)度：（7） 非搶占式調(diào)度：（1）墨辛、（2）卓研、（3）、（4）睹簇、（5）奏赘、（6）

算法分類

• 先來先服務(wù)調(diào)度算法FCFS

• 短作業(yè)優(yōu)先調(diào)度算法SJF

通常用于長程調(diào)度
優(yōu)點(diǎn)：最短的平均等待時間
缺點(diǎn)：存在饑餓問題
一般來說，搶占式SJF算法比非搶占式SJF算法的系統(tǒng)開銷大太惠。

• 優(yōu)先級調(diào)度算法PR

默認(rèn)：小優(yōu)先數(shù)具有高優(yōu)先級
目前主流的操作系統(tǒng)調(diào)度算法
存在問題：饑餓（解決方法為老化）

• 時間片輪轉(zhuǎn)調(diào)度算法RR

時間片磨淌，為每個進(jìn)程分配不超過一個時間片的CPU響應(yīng)時間
時間片小=>增加上下文切換時間
時間片大=>FCFS

• 多級隊(duì)列調(diào)度MLQ
  要素：1.隊(duì)列數(shù)2.每個隊(duì)列的調(diào)度算法3.決定新進(jìn)程進(jìn)哪個隊(duì)列
• 多級反饋隊(duì)列調(diào)度MLFQ
  和多級隊(duì)列調(diào)度算法相比，多級反饋隊(duì)列調(diào)度算法還需要考慮升級凿渊、降級的方法
• 多隊(duì)列調(diào)度方法MQMP和單隊(duì)列調(diào)度方法SQMP

甘特圖以及計(jì)算***************
非搶占式調(diào)度*******
搶占式調(diào)度********待寫

1. 存在饑餓問題的調(diào)度算法有 優(yōu)先級調(diào)度伦糯、最短作業(yè)優(yōu)先調(diào)度
2. SJF有利短進(jìn)程而不利于長進(jìn)程
   RR系統(tǒng)開銷大
   交互進(jìn)程需要短的響應(yīng)時間
   批處理進(jìn)程需要短的等待時間

六、進(jìn)程同步

概念

競爭條件：多個進(jìn)程并發(fā)訪問同一共享數(shù)據(jù)的情況
同步：協(xié)調(diào)執(zhí)行次序
互斥：只讓一者排他的運(yùn)行
臨界區(qū)：涉及臨界資源的代碼段

• 同步應(yīng)遵循的基本準(zhǔn)則
  互斥：Pi在某臨界區(qū)執(zhí)行嗽元，其他進(jìn)程將被排除在臨界區(qū)外敛纲，有相同臨界資源的臨界區(qū)都需要互斥，沒有相同臨界資源的臨界區(qū)不需要互斥
  有空讓進(jìn)：臨界區(qū)內(nèi)無進(jìn)程執(zhí)行剂癌，不能無限期地延長下個要進(jìn)臨界區(qū)的進(jìn)程的等待時間
  有限等待：進(jìn)入前的等待時間必須有限淤翔，不能無限等待
  無空等待：不允許兩個以上的進(jìn)程同時進(jìn)入互斥區(qū)。

1. 實(shí)現(xiàn)有空讓進(jìn)準(zhǔn)則可以在退出區(qū)

信號量

• 整型信號量（最初始原型如下佩谷，有忙等待的問題旁壮，實(shí)際應(yīng)用不這樣）

wait(S){
  while(S<=0)
    ;//no-op
  S--;
}

signal(S){
  S++;
}

忙等：如果S<=0 該進(jìn)程將不斷重復(fù)執(zhí)行while語句

• 記錄型信號量（增加了一個等待隊(duì)列l(wèi)ist，消除了忙等谐檀，先減再判斷）

P(S) {
    value--;
    if (value < 0) {
        add this process to list
        block//阻塞
    }
}

V(S) {
    value++;
    if (value <= 0) {
        remove a process P from list
        wakeup(P);//喚醒一個
    }
}

• 操作系統(tǒng)區(qū)分計(jì)數(shù)（同步）信號量和二值（互斥）信號量：
  計(jì)數(shù)信號量值域不受限制
  二值信號量的值只能為0或1
  S初始值不能為負(fù)數(shù)且只能必須置一次初始值

• 同步信號量的簡單使用

semaphore S=0
P1:
  C1;
  signal(S);
P2:
  wait(S);
  C2;
//這樣表示了P1和P2進(jìn)程運(yùn)行時讓C1段優(yōu)先于C2段代碼運(yùn)行

S>0: 有資源可用抡谐；
S=0:沒有資源可用；
S<0:有進(jìn)程在等待資源桐猬；
P(S):當(dāng)有S資源可用時麦撵，S減一；如果沒有S資源可用時，阻塞當(dāng)前進(jìn)程免胃；
V(S):當(dāng)資源不再使用時音五，S加一；如果有進(jìn)程因?yàn)榈却?dāng)前資源而阻塞羔沙，需要喚醒他們躺涝。
用V操作可以喚醒一個進(jìn)程，被喚醒的進(jìn)程狀態(tài)是就緒
二值信號量的值區(qū)間是0-1（X） 0和1

信號量的應(yīng)用

• 1.找到臨界區(qū)（即用到共享資源的代碼）加上互斥的機(jī)制
  加互斥信號量實(shí)際上是最簡單的扼雏，只要在你覺得這個操作是原子的部分上下加P坚嗜、V(mutex)
• 2.同步分析（即分析運(yùn)行次序）
• 3.給信號量寫初始值
  互斥信號量初始值一般為1
  同步信號量初始值0~N

• 生產(chǎn)者-消費(fèi)者問題：共享有限緩沖區(qū)

我覺得empty是NumOfEmpty，full是NumOfFull诗充，所以empty初始值為N惶傻，full初始值為0，這兩個英文的使用讓人理解困難
生產(chǎn)者-消費(fèi)者問題解決的是共享資源的問題其障，在資源使用over的時候需要一者和另一者按順序執(zhí)行所以產(chǎn)生了信號量的應(yīng)用银室，其中有三種情況參考ppt
signal（full）其實(shí)就是增加一個full的單位，那么消費(fèi)者就可以去消費(fèi)了那就是喚醒了消費(fèi)者
signal（empty）就是增加一個空的單位励翼，那么生產(chǎn)者就可以去往這個空的單位生產(chǎn)東西了

• 讀者寫者問題：數(shù)據(jù)讀寫操作

如果單純的讓讀寫互斥無法滿足多個讀者一起讀蜈敢！
此處其實(shí)共同的資源已經(jīng)是個次要問題了，最關(guān)鍵的是能否用一個計(jì)數(shù)器來表明是否是第一個讀者以及最后一個讀者汽抚，這個計(jì)數(shù)器必須要用一個互斥的信號量來維護(hù)抓狭，所以臨界區(qū)如圖所示

• 哲學(xué)家就餐問題：資源競爭

現(xiàn)在有5個信號量分別是從ph[0]~ph[4]，初始值都是0
test字如其名就是測試他能不能拿筷子造烁，如果左右哲學(xué)家都沒吃飯那這個i就是有能力吃飯的
在test函數(shù)內(nèi)部就V(ph[i])就是這個哲學(xué)家i的信號量變成1啦
然后開始P(ph[i])否过，就是看看這個哲學(xué)家的信號量有沒有1，因?yàn)槲覀兊拇笄疤崾沁@5個進(jìn)程在并發(fā)運(yùn)行
恰巧我們這個哲學(xué)家在資源競爭中運(yùn)氣好信號量變成1了惭蟋，此時左右兩個肯定變不成1了
所以他吃完之后要幫助旁邊兩個人測試下是否能吃苗桂，助推一把
整個過程就是這些進(jìn)程都準(zhǔn)備開始運(yùn)行，實(shí)際上物理運(yùn)行的時候會有人隨機(jī)先走告组，這個人先走之后順序也就定好了煤伟。

管程

一個管程定義了一個數(shù)據(jù)結(jié)構(gòu)和一組操作（操作可以同步進(jìn)程和改變管程中的數(shù)據(jù)）
應(yīng)該如何理解管程
深入理解l操作系統(tǒng)的管程，進(jìn)程木缝，線程（一）