閱讀筆記--現代作業系統

1. 作業系統面試

1.https://www.nowcoder.com/discuss/325668?type=all&order=time&pos=&page=1&channel=1005&source_id=search_all

2. 同步、異步、阻塞與非阻塞

1. 同步與異步，阻塞與非阻塞的關系
2. 聊聊同步、異步、阻塞與非阻塞

2.1 基本概念

2.1.1 同步和異步

所謂同步就是一個任務的完成需要依賴另外一個任務時，隻有等待被依賴的任務完成後，依賴的任務才能算完成，這是一種可靠的任務序列。要麼成功都成功，失敗都失敗，兩個任務的狀态可以保持一緻。

所謂異步是不需要等待被依賴的任務完成，隻是通知被依賴的任務要完成什麼工作，依賴的任務也立即執行，隻要自己完成了整個任務就算完成了。至于被依賴的任務最終是否真正完成，依賴它的任務無法确定，是以它是不可靠的任務序列。

2.1.2 消息通知

異步的概念和同步相對。當一個同步調用發出後，調用者要一直等待傳回消息（結果）通知後，才能進行後續的執行；當一個異步過程調用發出後，調用者不能立刻得到傳回消息（結果）。實際處理這個調用的部件在完成後，通過狀态、通知和回調來通知調用者。

這裡提到執行部件和調用者通過三種途徑傳回結果：狀态、通知和回調。使用哪一種通知機制，依賴于執行部件的實作，除非執行部件提供多種選擇，否則不受調用者控制。

2.1.3 比喻

舉個例子，比如我去銀行辦理業務，可能會有兩種方式：

1. 選擇排隊等候；
2. 另種選擇取一個小紙條上面有我的号碼，等到排到我這一号時由櫃台的人通知我輪到我去辦理業務了；

第一種：前者(排隊等候)就是同步等待消息通知，也就是我要一直在等待銀行辦理業務情況；

第二種：後者(等待别人通知)就是異步等待消息通知。在異步消息進行中，等待消息通知者(在這個例子中就是等待辦理業務的人)往往注冊一個回調機制，在所等待的事件被觸發時由觸發機制(在這裡是櫃台的人)通過某種機制(在這裡是寫在小紙條上的号碼，喊号)找到等待該事件的人。

2.2 阻塞與非阻塞

阻塞和非阻塞這兩個概念與程式（線程）等待消息通知(無所謂同步或者異步)時的狀态有關。也就是說阻塞與非阻塞主要是程式（線程）等待消息通知時的狀态角度來說的。

2.2.1 概念描述

阻塞調用是指調用結果傳回之前，目前線程會被挂起，一直處于等待消息通知，不能夠執行其他業務。函數隻有在得到結果之後才會傳回。

2.3 舉個例子

小明下載下傳檔案的例子

1. 聊聊同步、異步、阻塞與非阻塞

2.4 總結

同步/異步和阻塞/非阻塞是完全不同的概念。同步不能和阻塞畫等号(隻能說同步往往是阻塞的)，是不是阻塞咱們可以通過判斷此刻主線程處于什麼狀态來判斷。比如：在NIO中，我們有一種的多路複用模式。概念就是：我們不是采用一個線程去負責一個socket的方式，如果那樣一定是阻塞的。我們采用一個線程管理多個socket的方式，該線程不斷輪詢所有socket，我們叫做Selector,通過select()方法，我們可以找到某一時刻真正需要io資源的socket，避免資源浪費。那麼此時，我們的主線程是一直處于running狀态的，因為他在不斷輪詢，但它同時又是非阻塞的，因為沒有處于等待狀态。

同時異步也不一定是非阻塞的（隻能說異步常常是非阻塞的），例如我們往線程池裡面送出任務的時候，調用Future.get()來試圖擷取處理結果時，由于結果還沒有運作出來，是以該方法會被阻塞。但是從多線程角度來看，此時它是異步執行的。

再用大白話解釋一下，不敢保證一定準确無誤，同步和異步我們描述的是多個線程之間的關系，而阻塞和非阻塞描述的是一個線程的屬性。我們既然選擇了多線程也就選擇了異步程式設計的方式，但是卻要解決同步的問題，而同步往往意味着性能的缺失和安全性的保障。而對于阻塞和非阻塞來說，傳統的方式大多是阻塞的，如果采用異步非阻塞往往意味着更多的代碼和資源投入。

3. IO模型

1. 聊聊Linux五種IO模型

3.1 幾個重要的知識

1. 使用者空間和核心空間

1. Linux使用者态和核心态

在 CPU 的所有指令中，有些指令是非常危險的，如果錯用，将導緻系統崩潰，比如清記憶體、設定時鐘等。如果允許所有的程式都可以使用這些指令，那麼系統崩潰的機率将大大增加。是以為了保護核心空間就設定了使用者空間。區分核心空間和使用者空間本質上是要提高作業系統的穩定性及可用性。

1. 如何從使用者空間進入核心空間？

   使用者态的程序必須切換成核心态才能使用系統的資源，從使用者态進入到核心态有三種方式：系統調用、軟中斷、硬體中斷和異常。

2. 程序切換

為了控制程序的執行，核心必須有能力挂起正在CPU上運作的程序，并恢複以前挂起的某個程序的執行。這種行為被稱為程序切換。是以可以說，任何程序都是在作業系統核心的支援下運作的，是與核心緊密相關的。從一個程序的運作轉到另一個程序上運作，這個過程中經過下面這些變化：

1. 儲存處理機上下文，包括程式計數器和其他寄存器。
2. 更新PCB資訊。
3. 把程序的PCB移入相應的隊列，如就緒、在某事件阻塞等隊列。
4. 選擇另一個程序執行，并更新其PCB。
5. 更新記憶體管理的資料結構。
6. 恢複處理機上下文。

3 程序的阻塞

正在執行的程序，由于期待的某些事件未發生，如請求系統資源失敗、等待某種操作的完成、新資料尚未到達或無新工作做等，則由系統自動執行阻塞原語(Block)，使自己由運作狀态變為阻塞狀态。可見，程序的阻塞是程序自身的一種主動行為，也是以隻有處于運作态的程序（獲得CPU），才可能将其轉為阻塞狀态。當程序進入阻塞狀态，是不占用CPU資源的。

4. 緩存IO

緩存 IO 又被稱作标準 IO，大多數檔案系統的預設 IO 操作都是緩存 IO。在 Linux 的緩存 IO 機制中，作業系統會将 IO 的資料緩存在檔案系統的頁緩存（ page cache ）中，也就是說，資料會先被拷貝到作業系統核心的緩沖區中，然後才會從作業系統核心的緩沖區拷貝到應用程式的位址空間。

緩存 IO 的缺點：

資料在傳輸過程中需要在應用程式位址空間和核心進行多次資料拷貝操作，這些資料拷貝操作所帶來的 CPU 以及記憶體開銷是非常大的。

檔案描述

檔案描述符（File descriptor）是計算機科學中的一個術語，是一個用于表述指向檔案的引用的抽象化概念。

3.2 Linux IO模型

網絡IO的本質是socket的讀取，socket在linux系統被抽象為流，IO可以了解為對流的操作。對于一次IO通路（以read舉例），資料會先被拷貝到作業系統核心的緩沖區中，然後才會從作業系統核心的緩沖區拷貝到應用程式的位址空間。

一共有5種網絡IO模型

1. 同步模型（synchronous IO）
2. 阻塞IO（bloking IO）
3. 非阻塞IO（non-blocking IO）
4. 多路複用IO（multiplexing IO）
5. 信号驅動式IO（signal-driven IO）
6. 異步IO（asynchronous IO）

其中信号驅動式IO模型并不常用

3.2.1 同步阻塞 IO（blocking IO）

3.2.2 同步非阻塞IO

3.2.3 IO多路複用

1. 對select，poll，epoll非常好的講解

由于同步非阻塞方式需要不斷主動輪詢，輪詢占據了很大一部分過程，輪詢會消耗大量的CPU時間，而 “背景” 可能有多個任務在同時進行，人們就想到了循環查詢多個任務的完成狀态，隻要有任何一個任務完成，就去處理它。如果輪詢不是程序的使用者态，而是有人幫忙就好了。那麼這就是所謂的 “IO 多路複用”

3.2.3 信号驅動 IO （不是很重要）

3.2.4 異步非阻塞 IO

4. IO多路複用之select，poll，epoll

本質就是利用一個線程監聽多個Socket，誰有資料就處理誰。

整體的思想如下：

while(1){
	for Fdx in Fda~Fde{
		if(Fdx 有資料){
			讀取Fdx；處理
			}
		}
}
           

4.1 select

1. select函數的第一個參數的解釋

//   struct sockaddr_in addr = {0}; // 綁定套接字

 sockfd = socket(AF_INET, SOCK_STREAM, 0); // 建立套接字
 memset(&addr, 0, sizeof (addr)); // 初始化為0
 addr.sin_family = AF_INET; // 使用IP_V4位址
 addr.sin_port = htons(2000); // 端口
 addr.sin_addr.s_addr = INADDR_ANY;
 bind(sockfd,(struct sockaddr*)&addr ,sizeof(addr)); // 綁定到套接字
 listen (sockfd, 5); // 進入監聽狀态
 
/*以下就是select的執行過程*/
  for (i=0;i<5;i++) 
  {
    memset(&client, 0, sizeof (client));
    addrlen = sizeof(client);
    fds[i] = accept(sockfd,(struct sockaddr*)&client, &addrlen); // 為每一個client建立檔案描述符（也就是套接字描述符）
    if(fds[i] > max)
    	max = fds[i];
  }

/*通過while循環監視每一個socket，來了資料就處理*/
  while(1){
	FD_ZERO(&rset); // 置零
  	for (i = 0; i< 5; i++ ) {
  		FD_SET(fds[i],&rset); //置位
  	}
 
   	puts("round again");
	select(max+1, &rset, NULL, NULL, NULL);
 
	for(i=0;i<5;i++) {
		if (FD_ISSET(fds[i], &rset)){
			memset(buffer,0,MAXBUF);
			read(fds[i], buffer, MAXBUF);
			puts(buffer);
		}
	}	
  }
           

注意上述代碼中有一個rset，他其實就是一個bitmap。這了的bitmap最大時1024，他訓示了哪個檔案描述符被建立。比如我們上述代碼中建立了1，2，5，7，9五個描述符，那麼這個1024位的bitmap中的1，2，5，7，9的位置就為1，其他的全為0.

select的缺點：

• bitmap預設時1024，這就限制了可以監視的socket的數量
• 從使用者态到核心态的切換會産生開銷
• FD_set不可以重複使用
• while中O(n)的再次周遊

4.2 poll

poll主要解決了select中的前兩個缺陷，但是後續的工作原理時相似的，是以就兩個問題并沒有解決。

4.3 epoll

• epoll中核心态和使用者态共享epfd，是以也就解決了核心态和使用者态切換的開銷問題。
• epoll中并沒有類似于select和poll的置位，在epoll是一種變相的置位–重排。有資料的epfd會被放在前面，并且epoll_wait函數會傳回被置位的個數。while中的周遊隻需要周遊nfds次就可以，也就解決了select中的O(n)問題。

5. Socket建立的方式

5.1 S端

• 設定端口和IP
• 初始化socket，建立監聽socket
• bind 綁定IP位址端口
• listen 開始監聽
• 有事件進來就添加到時間表裡面（epoll模式的狀态）
• 伺服器使用結束就close

什麼是作業系統

作業系統（operate system）就是綜合管理計算機硬體和軟體資源的程式，同是也是計算機系統的核心和基石。作業系統需要處理如管理與配置記憶體、決定系統資源供需的優先次序、控制輸入與輸出裝置、操作網絡與管理檔案系統等基本事務。作業系統也提供一個讓使用者與系統互動的操作界面。

第二章 程序與線程

1. 什麼是程序：

• 程序是對運作時程式的封裝，是系統進行資源排程和配置設定的基本機關，實作了作業系統的并發；
• 優點：記憶體隔離，單個程序的崩潰不會導緻這個系統的崩潰。而且程序友善測試以及程式設計簡單
• 缺點：建立銷毀比較麻煩，程序間資料的共享麻煩，并且消耗的資源比較多。

2. 什麼是線程：

• 線程是程序的子任務，是CPU排程和分派的基本機關，用于保證程式的實時性，實作程序内部的并發。（線程自身是不能擁有系統資源的，但是它可以擁有自己的堆、棧、局部變量以及程式電腦。）
• 優點：可以提高系統的并行性，資料共享比較友善，切換比較快。
• 缺點：沒有記憶體隔離，一個線程的崩潰會導緻整個程序的崩潰。程式設計複雜以及調試困難。

3. 程序包括什麼：

程序由程式、資料和程序控制塊組成。程序控制塊是記錄程序有關資訊的一塊主存，是程序存在的程式唯一辨別。

4. 程序組織方式

5. 阻塞和挂起的差別

• 了解一：挂起是一種主動行為，是以恢複也應該要主動完成，而阻塞則是一種被動行為，是在等待事件或資源時任務的表現，你不知道他什麼時候被阻塞(pend)，也就不能确切的知道他什麼時候恢複阻塞。而且挂起隊列在作業系統裡可以看成一個，而阻塞隊列則是不同的事件或資源（如信号量）就有自己的隊列。
• 了解二：阻塞（pend）就是任務釋放CPU，其他任務可以運作，一般在等待某種資源或信号量的時候出現。挂起（suspend）不釋放CPU，如果任務優先級高就永遠輪不到其他任務運作，一般挂起用于程式調試中的條件中斷，當出現某個條件的情況下挂起，然後進行單步調試。
• 了解三：pend是task主動去等一個事件,或消息.suspend是直接懸挂task,以後這個task和你沒任何關系,任何task間的通信或者同步都和這個suspended task沒任何關系了,除非你resume task;
• 了解四：任務排程是作業系統來實作的，任務排程時，直接忽略挂起狀态的任務，但是會顧及處于pend下的任務，當pend下的任務等待的資源就緒後，就可以轉為ready了。ready隻需要等待CPU時間，當然，任務排程也占用開銷，但是不大，可以忽略。可以這樣了解，隻要是挂起狀态，作業系統就不在管理這個任務了。
• 了解五：挂起是主動的，一般需要用挂起函數進行操作，若沒有resume的動作，則此任務一直不會ready。而阻塞是因為資源被其他任務搶占而處于休眠态。兩者的表現方式都是從就緒态裡“清掉”，即對應标志位清零，隻不過實作方式不一樣。

2.2 線程

2.2.1 線程存在的必要性

1. 為什麼要有線程

1）程序一時間隻能幹一件事，如果被阻塞，整個程序都會被挂起，線程有利于實作真正的并行；

2）線程的上下文切換的開銷更小；

3）如果是I/O密集型的處理，多線程會加快執行的速度。

2. 程序和線程的差別

1）一個線程隻能屬于一個程序，而一個程序可以有多個線程，但至少有一個線程。線程依賴于程序而存在。

2）程序在執行過程中擁有獨立的記憶體單元，而多個線程共享程序的記憶體。（資源配置設定給程序，同一程序的所有線程共享該程序的所有資源。同一程序中的多個線程共享代碼段（代碼和常量），資料段（全局變量和靜态變量），擴充段（堆存儲）。但是每個線程擁有自己的棧段，棧段又叫運作時段，用來存放所有局部變量和臨時變量。）

3）程序是資源配置設定的最小機關，線程是CPU排程的最小機關；

4）程序在進行上下文切換時，由于他們有自己的記憶體空間，系統要重新為其配置設定記憶體、I/O等資源，然後回收舊的程序的記憶體、I/O等資源，切換的開銷比較大。但是線程不存在這些問題，開銷比較小。

5）由于線程共享位址空間，是以線程之間的通信比較友善。但是程序間的通信比較麻煩

3. 程序間的通信/同步方式

方式: 套接字，管道，信号量，消息隊列，共享記憶體，信号

3.1 管道( pipe )：管道是一種半雙工的通信方式，資料隻能單向流動，而且隻能在具有親緣關系的程序間使用。程序的親緣關系通常是指父子程序關系。

3.2 有名管道 (namedpipe) ： 有名管道也是半雙工的通信方式，但是它允許無親緣關系程序間的通信。

3.3 信号量(semophore ) ： 信号量是一個計數器，可以用來控制多個程序對共享資源的通路。它常作為一種鎖機制，防止某程序正在通路共享資源時，其他程序也通路該資源。是以，主要作為程序間以及同一程序内不同線程之間的同步手段。

3.4 消息隊列( messagequeue ) ： 消息隊列是由消息的連結清單，存放在核心中并由消息隊列辨別符辨別。消息隊列克服了信号傳遞資訊少、管道隻能承載無格式位元組流以及緩沖區大小受限等缺點。

3.5 信号 (sinal ) ： 信号是一種比較複雜的通信方式，用于通知接收程序某個事件已經發生。

3.6 共享記憶體(shared memory ) ：共享記憶體就是映射一段能被其他程序所通路的記憶體，這段共享記憶體由一個程序建立，但多個程序都可以通路。共享記憶體是最快的 IPC 方式，它是針對其他程序間通信方式運作效率低而專門設計的。它往往與其他通信機制，如信号兩，配合使用，來實作程序間的同步和通信。

3.7 套接字(socket ) ： 套解口也是一種程序間通信機制，與其他通信機制不同的是，它可用于不同及其間的程序通信。

3.4 線程之間的通信

臨界區、互斥量（mutex）、鎖機制（分為讀寫鎖和自旋鎖）、信号量（分為有名信号量和無名信号量）、事件等

2.2.4 使用者級線程和核心級線程

線程的實作可以分兩類：使用者級線程，核心級線程和混合式線程。

使用者級線程是指不需要核心支援而在使用者程式中實作的線程，它的核心的切換是由使用者态程式自己控制核心的切換，不需要核心的幹涉。但是它不能像核心級線程一樣更好的運用多核CPU。

優點：

（1） 線程的排程不需要核心直接參與，控制簡單。

（2） 可以在不支援線程的作業系統中實作。

（3） 同一程序中隻能同時有一個線程在運作，如果有一個線程使用了系統調用而阻塞，那麼整個程序都會被挂起，可以節約更多的系統資源。

缺點：

（1） 一個使用者級線程的阻塞将會引起整個程序的阻塞。

（2） 使用者級線程不能利用系統的多重處理，僅有一個使用者級線程可以被執行。

核心級線程:切換由核心控制，當線程進行切換的時候，由使用者态轉化為核心态。切換完畢要從核心态傳回使用者态。可以很好的運用多核CPU，就像Windows電腦的四核八線程，雙核四線程一樣。

優點：

（1）當有多個處理機時，一個程序的多個線程可以同時執行。

（2） 由于核心級線程隻有很小的資料結構和堆棧，切換速度快，當然它本身也可以用多線程技術實作，提高系統的運作速率。

缺點：

（1） 線程在使用者态的運作，而線程的排程和管理在核心實作，在控制權從一個線程傳送到另一個線程需要使用者态到核心态再到使用者态的模式切換，比較占用系統資源。（就是必須要受到核心的監控）

關聯性

（1） 它們之間的差别在于性能。

（2） 核心支援線程是OS核心可感覺的，而使用者級線程是OS核心不可感覺的。

（3） 使用者級線程的建立、撤消和排程不需要OS核心的支援。

（4） 使用者級線程執行系統調用指令時将導緻其所屬程序被中斷，而核心支援線程執行系統調用指令時，隻導緻該線程被中斷。

（5） 在隻有使用者級線程的系統内，CPU排程還是以程序為機關，處于運作狀态的程序中的多個線程，由使用者程式控制線程的輪換運作；在有核心支援線程的系統内，CPU排程則以線程為機關，由OS的線程排程程式負責線程的排程。

（6） 使用者級線程的程式實體是運作在使用者态下的程式，而核心支援線程的程式實體則是可以運作在任何狀态下的程式。

2.3 程序間通信/同步

程序間通信方式：管道、共享記憶體、socket、消息、信号量、共享隊列等

程序通信的方式也适用于線程

2.3.1 競争條件

2.3.2 臨界區

1. 什麼是臨界區

臨界區指的是一個通路共用資源（例如：共用裝置或是共用存儲器）的程式片段，而這些共用資源又無法同時被多個線程通路的特性。當有線程進入臨界區段時，其他線程或是程序必須等待（例如：bounded waiting 等待法），有一些同步的機制必須在臨界區段的進入點與離開點實作，以確定這些共用資源是被互斥獲得使用，例如：semaphore。隻能被單一線程通路的裝置

2.3.3 忙等待互斥

為了實作臨界區中的思想，需要确定如何使得一時間隻有一個程序進入到臨界區，在該臨界區被某一個程序占用後，其他程序都不可再進入臨界區：

1. 屏蔽中斷

一個程序進入臨界區後，把所有中斷都屏蔽，包括時鐘中斷，這樣就不可能發生程序之間的切換。但是如果該程序不再打開中斷，整個系統就會直接崩潰。

2.鎖變量

3. 嚴格輪換法（自旋鎖）

兩個程序輪流進入臨界區，輪流執行。

但是有一個問題是，如果程序0很快完成了一個時間片上的臨界區操作，并且需要再次進入臨界區。但是程序1還在忙着其他操作而沒有進入臨界區，這就會導緻0無法再次快速的進入臨界區并完成操作，這就會導緻效率的降低。

4. Peterson解法

5. TSL指令

備注：

Peterson和TSL的本質都是先檢查是否允許程序進入，如果不允許就在原地等待，直到允許為止。

2.3.4 睡眠和喚醒

1.生産者-消費者問題

#define N 100
int countor = 0;
void producer(void):
{
	int item;
	while(True){
		item=produce_item();
		if(countor==N) sleep();
		insert_item(item);
		countor++;
		if(countor==1) wakeup(consumer);
	}
void consumer(void):
{
	int item;
	while(True){
		if(countor==0) sleep();
		item=remove_item();
		countor--;
		if(countor==N-1) wakeup(producer);
		consume_item(item)
	}
}
           

2.3.5 信号量

1. 程序同步之信号量機制（pv操作）及三個經典同步問題

信号量機制即利用pv操作來對信号量進行處理。

（1）什麼是信号量？

信号量（semaphore）的資料結構為一個值和一個指針，指針指向等待該信号量的下一個程序。信号量的值與相應資源的使用情況有關。當它的值大于0時，表示目前可用資源的數量；當它的值小于0時，其絕對值表示等待使用該資源的程序個數。注意，信号量的值僅能由PV操作來改變。

一般來說，信号量S>=0時，S表示可用資源的數量。執行一次P操作意味着請求配置設定一個機關資源，是以S的值減1；當S<0時，表示已經沒有可用資源，請求者必須等待别的程序釋放該類資源，它才能運作下去。而執行一個V操作意味着釋放一個機關資源，是以S的值加1；若S<=0，表示有某些程序正在等待該資源，是以要喚醒一個等待狀态的程序，使之運作下去。

（2）什麼是PV操作

p操作（wait）：申請一個機關資源，程序進入。

wait(S){
	while(s<=0)	//如果沒有資源則會循環等待；
		;
	S-- ;
}
           

v操作（signal）：釋放一個機關資源，程序出來。

signal(S){
	S++ ;
}
           

PV操作的含義：PV操作由P操作原語和V操作原語組成（原語是不可中斷的過程），對信号量進行操作，具體定義如下：

• P（S）：
  • 将信号量S的值減1，即S=S-1；
  • 如果S<=0，則該程序繼續執行；否則該程序置為等待狀态，排入等待隊列。
• V（S）：
  • 将信号量S的值加1，即S=S+1；
  • 如果S>0，則該程序繼續執行；否則釋放隊列中第一個等待信号量的程序。

PV操作的意義：我們用信号量及PV操作來實作程序的同步和互斥。PV操作屬于程序的低級通信。

2.3.6.互斥量（Mutex）

一個程序中的多個線程通路同一個互斥量是沒有問題的，因為線程共享位址空間，可以很輕松的通路同一個互斥量。但是程序間如何共同通路一個互斥量呢？

1）把一些共享資料結構放在核心中

2）讓程序和其他程序共享部分位址空間

2.3.7 管程

2.3.8 消息傳遞

在消息傳遞系統中，程序間的資料交換是以格式化的消息(Message)為機關的。若通信的程序之間不存在可直接通路的共享空間，則必須利用作業系統提供的消息傳遞方法實作程序通信。程序通過系統提供的發送消息和接收消息兩個原語進行資料交換。

1. 直接通信方式：發送程序直接把消息發送給接收程序，并将它挂在接收程序的消息緩沖隊列上，接收程序從消息緩沖隊列中取得消息。
2. 間接通信方式：發送程序把消息發送到某個中間實體中，接收程序從中間實體中取得消息。這種中間實體一般稱為信箱，這種通信方式又稱為信箱通信方式。該通信方式廣泛應用于計算機網絡中，相應的通信系統稱為電子郵件系統。

2.4 排程

2.4.1 排程簡介

排程算法有三種

• 批處理
• 互動式
• 實時

2.4.2 批處理系統中的排程

先來先服務

最短作業時間優先

剩餘最短時間優先

2.4.3 互動式系統中的排程

1. 輪轉排程

程序挨個執行，未獲得CPU時間片的程序先被阻塞。

2. 優先級排程

3. 多級隊列

4. 最短程序優先

5. 保證排程

6. 彩票排程

7. 公平分享排程

2.3.4 實時系統中的排程

2.3.5 政策和機制

第三章 記憶體管理

3.2 一種存儲器抽象：位址空間

知乎解釋一：

1. 位址空間是一個程序可用于尋址記憶體的一套位址集合。

2. 為什麼要尋址，尋址的目的是找到指令中操作數所在的位址（位置）。好比我要聯系你，我得知道你的手機号碼一樣。

知乎解釋二：

• 所謂尋址，就是要找存放某個東西的位置。以下用日常生活中的情形來打比方，雖然不是很精準，但還是能友善了解。
• 隐含尋址：就是說存放東西的位置是相對固定的，東西a永遠存在A處，東西b永遠存在B處，以此類推。是以不用你費勁找，做事要用到某個東西時，會自動去固定的地方取。
• 立即尋址：就是在讓你做事的時候，同時把你要用的東西也給你，也是不用你忙活着去找。
• 直接尋址：就是告訴你儲物櫃的号碼，你自己去該儲物櫃裡把東西拿出來用。
• 寄存器尋址：就是有幾個固定的門房收發室，你找門房問，就能告訴你儲物櫃的号碼，然後就能從儲物櫃拿到東西。寄存器間接尋址：還是去找門房，問到儲物櫃号碼，然後去打開儲物櫃一看，裡面是個紙條，紙條上說東西在另一個儲物櫃，号碼是XXX。
• 偏移尋址：去找門房，門房告訴你一個儲物櫃号碼，但是實際東西放在離告訴你的儲物櫃的左邊或右邊一個偏移量的儲物櫃裡。
• 堆棧尋址：有個門房名字比較奇怪，叫堆棧。

什麼是邏輯位址空間與實體位址空間？

編譯後，每個目标子產品都是從0号單元開始編址，稱為該目标子產品的相對位址（或邏輯位址)。當連結程式将各個子產品連結成一個完整的可執行目标程式時，連結程式順序依次按各個子產品的相對位址構成統一的從0号單元開始編址的邏輯位址空間。使用者程式和程式員隻需知道邏輯位址，而記憶體管理的具體機制則是完全透明的，它們隻有系統程式設計人員才會涉及。不同程序可以有相同的邏輯位址，因為這些相同的邏輯位址可以映射到主存的不同位置。

實體位址空間是指記憶體中實體單元的集合，它是位址轉換的最終位址，程序在運作時執行指令和通路資料最後都要通過實體位址從主存中存取。當裝入程式将可執行代碼裝入記憶體時，必須通過位址轉換将邏輯位址轉換成實體位址，這個過程稱為位址重定位。

什麼是重定位？

3.3 虛拟記憶體

虛拟存儲器基于局部性原理，在程式裝入時，可以将程式的一部分裝入記憶體，而将其餘部分留在外存，就可以啟動程式執行。在程式執行過程中，當所通路的資訊不在記憶體時，由作業系統将所需要的部分調入記憶體,然後繼續執行程式。另一方面，作業系統将記憶體中暫時不使用的内容換出到外存上，進而騰出空間存放将要調入記憶體的資訊。這樣，系統好像為使用者提供了一個比實際記憶體大得多的存儲器，稱為虛拟存儲器。

虛拟記憶體 使得應用程式認為它擁有連續的可用的記憶體（一個連續完整的位址空間），而實際上，它通常是被分隔成多個實體記憶體碎片，還有部分暫時存儲在外部磁盤存儲器上，在需要時進行資料交換。與沒有使用虛拟記憶體技術的系統相比，使用這種技術的系統使得大型程式的編寫變得更容易，對真正的實體記憶體（例如RAM）的使用也更有效率。目前，大多數作業系統都使用了虛拟記憶體，如Windows家族的“虛拟記憶體”；Linux的“交換空間”等。

頁：将程序劃分的塊，對應的大小就叫頁面大小。

頁框：将記憶體劃分的塊。頁和頁框二者一一對應，一個頁放入一個頁框，（理論上）頁的大小和頁框的大小相等。

頁表：就是一個頁和頁框一一對應的關系表。【存放在記憶體中】 關系表隻是起到一個索引的作用，說白了就是能根據關系表能查到某一個頁面和哪一個頁框所對應。

3.3.1 分頁

參考清華大學的筆記來了解

先說說為什麼會有虛拟記憶體和實體記憶體的差別。正在運作的一個程序，他所需的記憶體是有可能大于記憶體條容量之和的，比如你的記憶體條是256M，你的程式卻要建立一個2G的資料區，那麼不是所有資料都能一起加載到記憶體（實體記憶體）中，勢必有一部分資料要放到其他媒體中（比如硬碟），待程序需要通路那部分資料時，在通過排程進入實體記憶體。是以，虛拟記憶體是程序運作時所有記憶體空間的總和，并且可能有一部分不在實體記憶體中，而實體記憶體就是我們平時所了解的記憶體條。有的地方呢，也叫這個虛拟記憶體為記憶體交換區。

那麼，什麼是虛拟記憶體位址和實體記憶體位址呢。假設你的計算機是32位，那麼它的位址總線是32位的，也就是它可以尋址00xFFFFFFFF（4G）的位址空間，但如果你的計算機隻有256M的實體記憶體0x0x0FFFFFFF（256M），同時你的程序産生了一個不在這256M位址空間中的位址，那麼計算機該如何處理呢？回答這個問題前，先說明計算機的記憶體分頁機制。

計算機會對虛拟記憶體位址空間（32位為4G）分頁産生頁（page），對實體記憶體位址空間（假設256M）分頁産生頁幀（page frame），這個頁和頁幀的大小是一樣大的，是以呢，在這裡，虛拟記憶體頁的個數勢必要大于實體記憶體頁幀的個數。在計算機上有一個頁表（page table），就是映射虛拟記憶體頁到實體記憶體頁的，更确切的說是頁号到頁幀号的映射，而且是一對一的映射。但是問題來了，虛拟記憶體頁的個數 > 實體記憶體頁幀的個數，豈不是有些虛拟記憶體頁的位址永遠沒有對應的實體記憶體位址空間？不是的，作業系統是這樣處理的。作業系統有個頁面失效（page fault）功能。作業系統找到一個最少使用的頁幀，讓他失效，并把它寫入磁盤，随後把需要通路的頁放到頁幀中，并修改頁表中的映射，這樣就保證所有的頁都有被排程的可能了。這就是處理虛拟記憶體位址到實體記憶體的步驟。

現在來回答什麼是虛拟記憶體位址和實體記憶體位址。虛拟記憶體位址由頁号（與頁表中的頁号關聯）和偏移量組成。頁号就不必解釋了，上面已經說了，頁号對應的映射到一個頁幀。那麼，說說偏移量。偏移量就是我上面說的頁（或者頁幀）的大小，即這個頁（或者頁幀）到底能存多少資料。舉個例子，有一個虛拟位址它的頁号是4，偏移量是20，那麼他的尋址過程是這樣的：首先到頁表中找到頁号4對應的頁幀号（比如為8），如果頁不在記憶體中，則用失效機制調入頁，否則把頁幀号和偏移量傳給MMC（CPU的記憶體管理單元）組成一個實體上真正存在的位址，接着就是通路實體記憶體中的資料了。總結起來說，虛拟記憶體位址的大小是與位址總線位數相關，實體記憶體位址的大小跟實體記憶體條的容量相關。

1. 什麼是缺頁中斷？

3.3.3 加速分頁過程

3.4 頁面置換算法

功能: 當缺頁中斷發生時,需要調入新的頁面而記憶體已滿時, 選擇記憶體當中哪個實體頁面被置換。

目标: 盡可能地減少頁面的換進換出次數(即缺頁中斷的次數).具體的說,把未來不再使用的或者短期内較少使用的頁面換出,通常隻能在局部性原理指導下依據過去統計資料來進行預測。

頁面鎖定: 用于描述必須常駐記憶體的作業系統的關鍵部分或時間關鍵的應用程序.實作方法是: 在頁表中添加鎖定标志位.

3.4.1 最優頁面置換算法

基本思路: 當一個缺頁中斷發生時, 對于儲存在記憶體中的每一個邏輯頁面.計算他的下一次通路前,還需要等待多長時間.從中選擇等待時間最長的那個,作為被置換頁面.

但是這隻是理想情況,因為作業系統無法知道一個頁面需要等多長時間才能被通路。然而這個想法可以作為其他算法的一個評價名額。

3.4.2 最近未使用頁面置換算法（NRU）

3.4.3 先進先出算法（FIFO）

基本思路: 選擇在記憶體中駐留時間最長的頁面并淘汰.具體來說,系統維護着一個連結清單,記錄了所有位于記憶體中的邏輯頁面.從連結清單的排列順序來看.鍊首的頁面駐留時間最長,鍊尾的駐留時間最短, 當一個缺頁中斷發生時,把鍊首頁面淘汰出局, 把新的頁面加入到連結清單。性能比較差, 調出的頁面可能是要經常通路的頁面,并且有bBelady現象.

3.4.4 第二次機會頁面是換置換算法

該算法相當于FIFO算法的改進版本。

3.4.5 時鐘頁面置換算法（Clock）

3.4.6 最近最少使用頁面置換算法（LRU）

選擇最久未使用的那個頁面淘汰掉. 這是對最優置換算法的近似,以過去推測未來。根據局部性原理,如果最近一段時間内某些頁面被頻繁通路,那麼在将來還可能被頻繁通路. 反之未被通路的将來也不會被通路.

3.4.8 工作集頁面置換算法

工作集是指在某段時間間隔内，程序要通路的頁面集合。經常被使用的頁面需要在工作集中，而長期不被使用的頁面要從工作集中被丢棄。為了防止系統出現抖動現象，需要選擇合适的工作集大小。

工作集模型的原理是讓作業系統跟蹤每個程序的工作集，并為程序配置設定大于其工作集的實體塊。如果還有空閑實體塊，則可以再調一個程序到記憶體以增加多道程式數。如果所有工作集之和增加以至于超過了可用實體塊的總數，那麼作業系統會暫停一個程序，将其頁面調出并且将其實體塊配置設定給其他程序，防止出現抖動現象。

————————————————————————————————

工作集模型:

如果局部性原理不成立，那各種算法都沒啥差別，比如是單調遞增，那不管哪種都會缺頁中斷。如果局部性原理成立, 那麼如何來證明他的存在, 如何對它進行定量的分析?這就是工作集模型!

工作集: 一個程序目前正在使用的邏輯頁面的集合,可以用一個二進制函數 W ( t , Δ ) W(t, \Delta) W(t,Δ)來表示:

• t是目前的執行時刻
• Δ \Delta Δ稱為工作集視窗, 即一個定長的頁面通路時間視窗
• W ( t , Δ ) W(t, \Delta) W(t,Δ)=在目前時刻t之前的 Δ \Delta Δ時間視窗當中的所有頁面所組成的集合(随着t的變化, 該集合也在不斷的變化);
• | W ( t , Δ ) W(t, \Delta) W(t,Δ)|指工作集的大小, 即頁面數目

  

3.4.9 工作集時鐘頁面置換算法

3.4.10 算法小結

3.5 分頁系統的設計問題

3.5.1 局部配置設定政策和全局配置設定政策

3.5.7 記憶體映射檔案

1. 記憶體映射檔案詳解–C++實作

1. 什麼是記憶體映射檔案

記憶體映射檔案，是由一個檔案到一塊記憶體的映射。 Win32提供了允許應用程式把檔案映射到一個程序的函數 (CreateFileMapping)。記憶體映射檔案與虛拟記憶體有些類似，通過記憶體映射檔案可以保留一個位址空間的區域，同時将實體存儲器送出給此區域，記憶體檔案映射的實體存儲器來自一個已經存在于磁盤上的檔案，而且在對該檔案進行操作之前必須首先對檔案進行映射。使用記憶體映射檔案處理存儲于磁盤上的檔案時，将不必再對檔案執行I/O操作，使得記憶體映射檔案在處理大資料量的檔案時能起到相當重要的作用。

3.7 分段

以下為清華大學OS課程筆記

• 程式的分段位址空間
• 分段尋址方案

段通路機制：

• 一個段：一個記憶體“塊”
  • 一個邏輯位址空間
• 程式通路記憶體位址需要
  • 一個2維的二進制組（s, addr）
  • s–段号
  • addr–段内偏址

    

    

    

第六章 死鎖

1. ​死鎖的産生、防止、避免、檢測和解除

什麼是死鎖：

死鎖是指兩個或兩個以上的程序在執行過程中，由于競争資源或者由于彼此通信而造成的一種阻塞的現象，若無外力作用，它們都将無法推進下去。此時稱系統處于死鎖狀态，這些在互相等待的程序稱為死鎖程序。

産生死鎖的必要條件：

• 互斥條件：一個資源一次隻能被一個程序使用
• 請求與保持條件：一個程序因請求資源而阻塞時，對已獲得資源保持不放
• 不可剝奪條件：程序獲得的資源，在未完全使用完之前，不能強行剝奪
• 循環等待條件：若幹程序之間形成一種頭尾相接的環形等待資源關系

死鎖避免：

系統對程序發出每一個系統能夠滿足的資源申請進行動态檢查，并根據檢查結果決定是否配置設定資源，如果配置設定後系統可能發生死鎖,則不予配置設定，否則予以配置設定。這是一種保證系統不進入死鎖狀态的動态政策。

死鎖預防：

隻要打破四個必要條件之一就能有效預防死鎖的發生。

• 打破互斥條件： 改造獨占性資源為虛拟資源，大部分資源已無法改造。
• 打破不可搶占條件： 當一程序占有一獨占性資源後又申請一獨占性資源而無法滿足，則退出原占有的資源。
• 打破占有且申請條件： 采用資源預先配置設定政策，即程序運作前申請全部資源，滿足則運作，不然就等待，這樣就不會占有且申請。
• 打破循環等待條件： 實作資源有序配置設定政策，對所有裝置實作分類編号，所有程序隻能采用按序号遞增的形式申請資源。

死鎖避免和死鎖預防的差別：

死鎖預防是設法至少破壞産生死鎖的四個必要條件之一，嚴格的防止死鎖的出現；而死鎖避免則不那麼嚴格的限制産生死鎖的必要條件的存在，因為即使死鎖的必要條件存在，也不一定發生死鎖。死鎖避免是在系統運作過程中注意避免死鎖的最終發生。

避免死鎖的算法

銀行家算法(分為單資源和多資源)等等。

什麼是記憶體抖動

記憶體抖動一般是記憶體配置設定算法不好，記憶體太小或者程式的算法不佳引起的頁面頻繁地從記憶體調入/調出的行為。

6.1 資源

6.1.2 資源擷取

6.2 死鎖簡介

什麼是死鎖：

死鎖是指兩個或兩個以上的程序在執行過程中，由于競争資源或者由于彼此通信而造成的一種阻塞的現象，若無外力作用，它們都将無法推進下去。此時稱系統處于死鎖狀态，這些在互相等待的程序稱為死鎖程序。

産生死鎖的必要條件：

• 互斥條件：一個資源一次隻能被一個程序使用
• 請求與保持條件：一個程序因請求資源而阻塞時，對已獲得資源保持不放
• 不可剝奪條件：程序獲得的資源，在未完全使用完之前，不能強行剝奪
• 循環等待條件：若幹程序之間形成一種頭尾相接的環形等待資源關系

以上四個條件必須是同時滿足的，否則便不會發生死鎖

6.3 鴕鳥算法

6.4 死鎖檢測和死鎖恢複

對資源的配置設定加以适當限制可防止或避免死鎖發生，但不利于程序對系統資源的充分共享。

6.4.1 每種類型一個資源的死鎖檢測

(1) 如果程序 - 資源配置設定圖中無環路，此時系統沒有發生死鎖。

(2) 如果程序 - 資源配置設定圖中有環路，則可分為以下兩種情況：

• 每種資源類中僅有一個資源，則系統發生了死鎖。此時，環路是系統發生死鎖的充分必要條件，環路中的程序就是死鎖程序。
• 每種資源類中有多個資源，則環路的存在隻是産生死鎖的必要不充分條件，系統未必會發生死鎖。

上圖為資源配置設定圖，其中方框表示資源，圓圈表示程序。資源指向程序表示該資源已經配置設定給該程序，程序指向資源表示程序請求擷取該資源。圖 a 可以抽取出環，如圖 b，它滿足了環路等待條件，是以會發生死鎖。

比如：程序D需要的資源是U、T；程序G需要的資源是V、U；程序E需要的資源是T、V；此時程序D占有資源U，程序E占有資源T，程序G占有資源V；是以此時導緻程序D、E、G所申請的資源不能得到全部滿足，陷入死鎖。

死鎖檢測算法

每種類型一個資源的死鎖檢測算法是通過檢測有向圖是否存在環來實作，從一個節點出發進行深度優先搜尋，對通路過的節點進行标記，如果通路了已經标記的節點，就表示有向圖存在環，也就是檢測到死鎖的發生。

6.4.2 每種類型一個資源的死鎖檢測

6.4.3 死鎖恢複算法

• 資源剝奪法

  剝奪陷于死鎖的程序所占用的資源，但并不撤銷此程序，直至死鎖解除。

• 程序回退法

  根據系統儲存的檢查點讓所有的程序回退，直到足以解除死鎖，這種措施要求系統建立儲存檢查點、回退及重新開機機制。

• 程序撤銷法

  1.撤銷陷入死鎖的所有程序，解除死鎖，繼續運作；2.逐個撤銷陷入死鎖的程序，回收其資源并重新配置設定，直至死鎖解除。

  可選擇符合下面條件之一的先撤銷： 1.CPU消耗時間最少者； 2.産生的輸出量最小者；3.預計剩餘執行時間最長者； 4.分得的資源數量最少者後優先級最低者

• 系統重新開機法

  結束所有程序的執行并重新啟動作業系統。這種方法很簡單，但先前的工作全部廢棄，損失很大。

6.5 死鎖避免

6.5.3 單個資源的銀行家算法

1. 作業系統——銀行家算法（Banker’s Algorithm）

銀行家算法是死鎖檢測算法的擴充

總結：單個資源的銀行家算法就是對每一個程序的請求進行檢查如果滿足這個請求是否會達到安全狀态，如果可以達到安全狀态就滿足其資源請求，在滿足後其他程序在得到時間片的時候可能會進入阻塞狀态，否則就推遲滿足其請求。

6.5.4 多個資源的銀行家算法

和單個資源的銀行家算法接近，隻不過可配置設定的資源的有增加。

6.6 死鎖預防

就是破壞四個必要條件（互斥條件、占有和等待條件、不可搶占條件、環路等待條件）中的一個或者多個。

6.7 其他問題

6.7.4 饑餓

什麼是死鎖

死鎖是指一組線程被阻塞的情況，因為擁有資源的每個程序都試圖通路另一個程序所擁有的其他資源，進而最終阻止了公平的系統排程。 當以下四個條件成立時，就會出現死鎖情況：互斥意味着一次隻能有一個程序通路資源； 沒有搶占條件意味着資源隻能由擁有該資源的程序自願釋放； 保留并等待意味着擁有資源的程序可以請求其他程序擁有的其他資源； 循環等待意味着将兩個或多個程序卡在循環鍊中，等待每個程序釋放各自的資源。

　

什麼是饑餓

饑餓是這樣一種情況,當程序無限期地進入等待期時，由于高優先級程序不斷通路同一資源，是以低優先級程序從未獲得通路資源的機會。 這是資源管理問題，因為拒絕程序通路其所需的資源，進而将程序推入不确定的等待時間。 之是以會發生這種情況，是因為它所需要的資源從未配置設定給程序，進而導緻該程序缺少資源，是以得不到名稱。 避免饑餓的最佳方法是使用老化技術，該技術會逐漸增加長時間處于等待期的程序的優先級，以確定公平的排程系統。