技術文章 » 作業系統原理OS複習總結

作業系統原理OS複習總結

2020-10-29 12:00:49

作業系統原理OS複習總結

寫在前面：此文章持續更新，對作業系統原理的學習進行復習總結。相關學習參考內容已列下方，目前水平有限，如有建議，歡迎指正！
References

  1. 作業系統原理[天津大學,李罡,2013]（B站、優酷）
  2. https://github.com/CyC2018/CS-Notes
  3. 公眾號：Java建設者----文章：寫給大忙人看的程序和執行緒

1. 程序管理

1.1 程序 process

CPU是多道系統，偽並行（單核單CPU）

程序：一段程式的正在被執行的一個範例（有「生命」的）

What is the difference between program and process ?

  1. Program is just the static text.
  2. Process is an dynamicentity being executed and has lifecycle.

A process consists of three parts:

  • Process Control Block (PCB) or Process Table Entry
  • Program (Text程式碼)
  • Data

Unix中除了祖先程序，其他都是fork(「克隆」)自身出來的。共用身子（程式碼、資料），頭不一樣（Block）

在這裡插入圖片描述

在這裡插入圖片描述
The fork() system call creates a child process. The exec() system call overlays the existing process with another program. The wait() system call allows the parent process to wait for a child process to terminate. The exit() system call terminates the process.

Process States:
在這裡插入圖片描述

  • scheduler(排程器)發起2，3(R和R的轉換)
    Running和Ready合起來叫Runnable(可執行態)
    scheduler(排程器)也可從n個Runnable挑一個去running
  • Running主動發生1
  • 其他程序引發4，Blocked醒了後重新排隊
  • scheduler優先順序很高

process termination:
Normal exit （自殺）
Error exit
Fatal error
Killed by another process （他殺）

1.2 執行緒 threads

程序是資源分配得最小單位，而程序中的執行緒共用擁有的資源。
執行緒是排程得最小單位。
程序的執行時排程內部的執行緒
Implementing Threads in User Space（使用者態、核心態）
執行緒池（待更新）

1.3 排程 scheduling

  • CPU密集型程序
  • IO密集型程序

批次處理系統：CPU利用率高好
互動式系統：CPU利用率較低好，在意response time
實時系統：達到條件時，立即響應（工業鍋爐）

批次處理系統的排程：

  • First Come First Served
    先來先服務
  • Shortest Job First
    短作業優先
  • Shortest Remaining-time Next
  • High Response-ratio First
    最高響應比優先
    turnaround time/executing time
    = (waiting time + executing time)/executing time
    = 1 + waiting time / executing time

互動式系統的排程：

  • 時間片輪轉
  • 優先順序排程
  • 多級反饋佇列（時間片輪轉排程演演算法和優先順序排程演演算法的結合）

1.4 競爭條件，PV與號誌 Race Conditions and Semaphore

臨界資源：可以共用使用，但不可以同時使用（eg. 印表機）。
臨界區（critical regions）：使用臨界資源的程式碼

大於2個程序的競爭條件：

  • 互斥（Mutex）：搶臨界資源，且互相無關
  • 同步：存在內在邏輯先後（如嚴格輪轉法）

Conditions required to avoid race condition:

  • No two processes nay be simultaneously insider their critical regions.
  • No assumptions may be made about speeds or the number of CPUs.
  • No process running outside its critical region may block other processes.
  • No process should have to wait forever to enter its critical region.

解決競爭條件也分為兩大類：

  • 忙等待 Busy waiting
  • 睡眠與喚醒（一般來說節省資源） Sleep and Wakeup

忙等待方案：TSL（Test and Set Lock）。該法關鍵字：「自旋鎖」 「忙等待」 「原子性，即不可打斷」

// TSL程式碼
enter_region
	// MOVE REGISTER, #1
	// XCHG REGISTER, LOCK |原子性操作
	
	TSL REGISTER, LOCK  |複製lock到暫存器，並將lock置為1 (這句話實現上面兩句話) 原子性操作
	
	CMP REGISTER, #0    | lock等於0嗎?
	
	JNE enter_region    |如果不等於0，已上鎖，再次迴圈
	
	RET                 |返回撥用程式，進入臨界區

leave_region

	MOVE LOCK, #0       |置lock為0
	
	RET                 |返回撥用程式

Semaphore can be operated by PV operation only.
號誌只有賦初值時可以直接賦，其他只能用P和V來操作它

（注意，號誌還有等待佇列部分，不止整數部分）

Semaphore中整數部分物理含義：

  • 正數 Positive：the number of resources available.（號誌所代表的資源的可用的個數）
  • 0 Zero：no resource available, no waiting process.（沒有空閒資源，也沒有等著的程序）
  • 負數 Negative：the number of process waiting to use the resources.（等待使用該資源的程序個數）

P與V源語不可打斷（P下降，V上升）。源語：非常迅速，非常快，不可打斷，少量。

// 方案1：PV in Sleep abd Wakeup
P(Semaphore s)
{
	s = s - 1;
	if (s < 0)
	{
		add to the semaphore's queue and sleep;
	}
}

V(Semaphore s)
{
	s = s + 1;
	if (s <= 0)
	{
		wake up the waiting process in the semaphore's queue;
	}
}

// 方案2：PV in Busy Waiting
P(Semaphore s)
{
	while (!s>0)
	{
		yield the CPU;
	}
	s--;
}

V(Semaphore s)
{
	s++;
}

以上兩個PV均可用印表機例子來思考
方案1，佔了，就去睡覺，然後有人叫醒
方案2，忙等待，一直測一直測有沒有資源
管程 Monitors
管程可以保證不同時執行。用編譯器去編出管程，如Java中給一段程式碼加synchronized，給另一段程式碼也加synchronized，這兩段程式碼就不會同時執行。

1.5 程序同步之經典同步問題

同步問題：先檢查，後修改，中間有可能被打斷，前面檢查無效，會出錯（TSL，PV都是避免了這樣的問題）

1.5.1 生產者消費者問題 The Producer-Consumer Problem

#define N 100
typedef int semaphore;
semaphore mutex = 1; // 生產者消費者互斥存取臨界區
semaphore empty = N; // 當前空格子的個數（生產者的）
semaphore full = 0;  // 滿格子的個數（消費者的）
					 // empty、full可以叫做通行證
void producer(void)
{
	int item;
	
	while(TRUE)
	{
		item = produce_item();
		p(&empty);
		p(&mutex);
		insert_item(item);
		v(&mutex);
		v(&full);
	}
}

void consumer(void)
{
	int item;
	
	while(TRUE)
	{		
		p(&full);      //這兩個p顛倒 + 生產者兩個p也顛倒，會發生死鎖
		p(&mutex);
		item = remove_item();
		v(&mutex);
		v(&empty);
		consume_item(item);
	}
}

1.5.2 哲學家就餐問題 Dining Philosophers Problem

// Mutex保護操作
int state[N]
semaphore mutex=1; // 在這種用PV的解決問題的型別中，int這種全域性變數，需加Mutex一下

1.5.3 讀者寫者問題 The Readers and Writers Problem

讀者優先的讀寫者問題:
1.寫者、讀者互斥存取檔案資源。
2.多個讀者可以同時存取檔案資源。
3.只允許一個寫者存取檔案資源。

typedef int semaphore;
void reader(void)
{
	while(TRUE)
	{
		down(&mutex);
		rc = rc + 1;
		if (rc == 1) { down(&db); }
		up(&mutex);
		read_data_base();
		down(&mutex);
		rc = rc - 1;
		if (rc == 0) { up(&db); }
		up(&mutex);
	}
	void writer(void)
	{
		while(TRUE)
		{
			down(&db);
			write_data_base();
			up(&db);
		}
	}
}

1.6 程序間通訊 IPC Inter-Process Communications

程序同步：控制多個程序按一定順序執行；
程序通訊：程序間傳輸資訊。
程序通訊是一種手段，而程序同步是一種目的。也可以說，為了能夠達到程序同步的目的，需要讓程序進行通訊，傳輸一些程序同步所需要的資訊。

  • 管道
  • FIFO(命名管道)
  • 訊息佇列
  • 號誌
  • 共用儲存
  • 通訊端

1.7 死鎖 deadlocks

可搶佔資源、不可搶佔資源(eg. 印表機)
死鎖的四個條件：

  1. Mutual exclusion condition 互斥使用
  2. Hold and wait condition 擁有並等待（部分擁有，期待更多）
  3. No preemption condition 不可搶奪
  4. Circular wait condition 迴圈等待

解決死鎖（忽略、檢測、避免、預防）

  • Just ignore the problem
    鴕鳥演演算法，假設不發生死鎖
  • Detection and recovery.
    Detection: 矩陣、資源有向圖. Recovery: 殺死年輕程序
  • Dynamic avoidance by careful resource allocation
    銀行家演演算法（安全序列、安全狀態）
  • Prevention by structurally negating one of the four required conditions.
    破壞死鎖的條件1。程序把這個送到某個佇列（spool），等待這個臨界資源，相當於送到佇列就認為任務完成。（eg. 印表機、送郵件）。該方法和鴕鳥常用廣用，其他的無法確定或預期程序需要哪些資源。

1.8 補充

makefile
system call: fork()…and others
多執行緒

2. 記憶體管理 memory management

2.1 概述

在這裡插入圖片描述
Primary Memory(aka RAM)
Secondary Memory(ie. hard disk)
CPU只和記憶體打交道，不和硬碟打交道

  • 程序記憶體模型 Process Memory Layout
    在這裡插入圖片描述

程式碼段(Text Segment)：一般唯讀不可變的。
資料段(Data Segment)：（靜態）大小固定。
堆區(Heap Storage)：大小可變。特點是隨機存取。
棧段(Stack Segment)：大小可變。特點是先進後出。高地址固定，向低地址方向擴大或縮小。
環境變數區(Environment Variables)：由外部，一般為作業系統，設定的變數。

2.2 分割區

分割區管理是把整體的、連續的放進記憶體空間，帶來無法使用不連續的小空間問題（碎片）。

  • Fixed-Partition example 固定分割區（有內部碎片）
  • Variable-Partition example 可變分割區（有外部碎片）

分割區管理定位需要基址暫存器 Base register

Memory Manager Strategies MM策略

  • Overlaying 覆蓋技術（記憶體小，沒法裝下全部）
  • Swapping 交換技術

分頁管理可以分散的放。

2.3 分頁 paging

虛擬記憶體 Virtual Memory
虛擬記憶體的目的是為了讓實體記憶體擴充成更大的邏輯記憶體，從而讓程式獲得更多的可用記憶體。
為了更好的管理記憶體，作業系統將記憶體抽象成地址空間。每個程式擁有自己的地址空間，這個地址空間被分割成多個塊，每一塊稱為一頁。這些頁被對映到實體記憶體，但不需要對映到連續的實體記憶體，也不需要所有頁都必須在實體記憶體中。當程式參照到不在實體記憶體中的頁時，由硬體執行必要的對映，將缺失的部分裝入實體記憶體並重新執行失敗的指令。

頁表

  • 頁 page （比如一個頁4K，可以自己設定）
  • 頁幀 page frame
    在這裡插入圖片描述

管理頁表：

  1. 加速
    Translation Lookaside Buffers, TLB. 放在快取記憶體裡，又叫快表（故外面的叫慢表）。
    A TLB to speed up paging.
    如果把頁表全放記憶體裡，存取頁表也需要很多時間，故把部分項放在Cache裡，提高查錶速度。
  2. 變小
    分級頁表 Multilevel Page Tables
    把大頁表分成小份，因為一般很多頁表項空著
    倒排頁表 Inverted Page Tables
    雜湊

兩點注意：
中斷：恢復現場後執行被中斷點的下一條語句。
缺頁中斷：恢復現場後回來執行被中斷的這條語句。

分頁存在的問題：

  1. 剩下沒分滿的頁不好操作
  2. 機械式按大小分頁，把一段程式可能包括main, 子函數，把這些分的不好，如一個頁有main和部分子函數
  3. 與2相同，遇到迴圈程式碼，記憶體還只剩一塊，不停存取（極特殊情況），大量時間在換頁，而不是執行語句，叫「顛簸」

2.4 分段 segmentation

分段式管理解決了分頁管理沒有邏輯內在，但又引入了分割區管理的問題（碎片）
分段，段內再分頁，即段頁式管理 Segmentation with Paging

2.5 頁面置換演演算法 page replacement

真實實體記憶體耗盡，需要把一部分東西換出去，產生了問題，換誰？
在程式執行過程中，如果要存取的頁面不在記憶體中，就發生缺頁中斷從而將該頁調入記憶體中。此時如果記憶體已無空閒空間，系統必須從記憶體中調出一個頁面到磁碟對換區中來騰出空間。頁面置換演演算法和快取淘汰策略類似，可以將記憶體看成磁碟的快取。在快取系統中，快取的大小有限，當有新的快取到達時，需要淘汰一部分已經存在的快取，這樣才有空間存放新的快取資料。頁面置換演演算法的主要目標是使頁面置換頻率最低（也可以說缺頁率最低）。

頁表中的標誌位：

  • P位（protection，在不在記憶體裡）
  • R位（referenced，有沒有被用過）-----週期性清0
  • M位（modified，是不是髒的）

頁面置換演演算法：

頁面置換演演算法內容最好多看線上課程來理解，容易忘

  1. FIFO, First In First Out
    選擇換出的頁面是最先進入的頁面。該演演算法會將那些經常被存取的頁面也被換出，從而使缺頁率升高。
  2. Second Chance Algorithm
    FIFO 演演算法可能會把經常使用的頁面置換出去，為了避免這一問題，對該演演算法做一個簡單的修改：當頁面被存取 (讀或寫) 時設定該頁面的 R 位為 1。需要替換的時候，檢查最老頁面的 R 位。如果 R 位是 0，那麼這個頁面既老又沒有被使用，可以立刻置換掉；如果是 1，就將 R 位清 0，並把該頁面放到連結串列的尾端，修改它的裝入時間使它就像剛裝入的一樣，然後繼續從連結串列的頭部開始搜尋。
  3. The Clock Page Replacement Algorithm
    第二次機會演演算法需要在連結串列中移動頁面，降低了效率。時鐘演演算法使用環形連結串列將頁面連線起來，再使用一個指標指向最老的頁面。
  4. (Least Recently used, LRU) Page Replacement Algorithm
    最近最少使用（過去厲害的不一定不淘汰，有優先順序，該演演算法最好，但幾乎無法實現）
    該演演算法考慮到了時間和效率，在最近時間內，用的最少。
    1.N*N矩陣，行置1，列置0
    2.Simulating LRU in software （aging演演算法）
    (00000000)8位元，用過置1，下一個時鐘週期後移，最後比誰小（高位比地位重要，因為算出數大）相比正宗的LRU缺點：一個週期用了幾次不統計，8個週期後就頂出去了。
  5. Working set page replacement 工作集演演算法
    若R為1，很近一段時間用過。R為0，最近一段時間沒用，比年齡，扔掉。（記錄時間點）
  6. The WSClock Page replacement algorithm

Not Frequency Used
page stealer, 若頁面空間小於Min，開始偷（換），到達到Max為止。不能讓其太滿，保證記憶體空閒量處在min和max之間。

2.6 補充

分頁與分段的比較：

  • 對程式設計師的透明性：分頁透明，但是分段需要程式設計師顯示劃分每個段。
  • 大小是否可以改變：頁的大小不可變，段的大小可以動態改變。
  • 出現的原因：分頁主要用於實現虛擬記憶體，從而獲得更大的地址空間；分段主要是為了使程式和資料可以被劃分為邏輯上獨立的地址空間並且有助於共用和保護。

3. 儲存管理 storage management

記憶體 — memory
外存 — storage
記憶體資料掉電即丟，需要有些放在外存裡。

3.1 檔案與目錄 files and directories

檔案包括：

  • 普通檔案
  • 目錄檔案
  • 特殊檔案（裝置檔案，有硬體裝置，邏輯裝置。把外部裝置當檔案來管理。others：sockets）

檔案結構包括（unix裡檔名和屬性分開存放）：

  • 檔名（一個檔案可有多個名字（共用檔案））
  • 屬性（判斷檔案有幾個用inode，不用名字）
  • 內容

file permission 檔案許可權（之後Linux總結複習文章會總結這裡的相關內容）

目錄記錄的是檔案名字和inode對應關係

檔案系統 The Unix File System：多級索引

3.2 檔案系統 file systems

檔案系統：
在這裡插入圖片描述
在這裡插入圖片描述

3.3 磁碟 disks

Components of storage（由小到大）：

  • Files
  • Directories
  • File systems
  • Physical storage & logical storage
  • Logical Volume Manager (LVM)

面、柱(track，也稱磁軌)、磁區 -------->定位到data

磁碟排程演演算法：
讀寫一個磁碟塊的時間的影響因素有：

  • 旋轉時間（主軸轉動盤面，使得磁頭移動到適當的磁區上）
  • 尋道時間（制動手臂移動，使得磁頭移動到適當的磁軌上）
  • 實際的資料傳輸時間

其中，尋道時間最長，因此磁碟排程的主要目標是使磁碟的平均尋道時間最短。

演演算法包括：
電梯演演算法
…
…
…

LVM
在這裡插入圖片描述

3.4 補充

Redundant Array of Independent Disk.
RAID：更快、更可靠、映象化
RAID0、RAID1、RAID5…

RAM disks 記憶體中磁碟（為了快，如Cache）

4. 裝置管理 Input/Output Devices

Interrupts 中斷 ------->現代計算機必備
DMA, Direct Memory Access，用於控制一些高速的傳輸
Buffering 快取

5. 字元集

ASCII(American Standard Code for Information Interchange)，7位，7個bit（一個位元組8個bit）
GBK：國標碼
UTF8：保證了ASCII大小不變，還避免瞭如截斷某半個字問題，擴充套件了其他語言編碼。範圍最廣。

寫在結尾：
之後還會陸續更新作業系統相關知識的學習和總結
Linux相關會另外總結一篇文章
目前水平有限，如有建議，歡迎指正！