2020 作業系統第零天複習（知識點總結）

文章目錄

• • 1：概論
  • 2：處理器管理

1：概論

• 批處理系統
  • 是第一個使用多道程式設計的系統
  • 缺少互動性 但是效率提升
• 分時處理系統
  • 把一台計算機按照時間片輪轉的方式配置設定給多個使用者，使得使用者覺得是自己獨占計算機
  • 必須在規定的時間進行響應
  • 互動性增加 響應的時間和CPU的性能，聯機終端的數目，所用時間片的長短，系統排程開銷和兌換資訊的多少
• 實時處理系統
  • 能夠實時的查詢并且更新資料
  • 機票系統 實時查詢系統 飛機 飛彈

2：處理器管理

• 處理器狀态
  • 核心态和使用者态，又叫管态和目态
  • 核心态可以執行所有的指令，目态隻能執行使用者指令
  • X86 一種有四個特權級，0最高，3最低 但是Windows 中隻有兩個特特權級
  • 模式切換
  • 使用者态到核心态：系統調用，中斷或者異常
  • 程式狀态字的模式為設定為核心态
  • 核心态到使用者态：加載程式狀态字特權指令
• 程式狀态字
  • 訓示處理器的狀态，控制指令的執行順序，并且訓示與運作程式有關的資訊，主要作用是實作程式狀态的保護和恢複
  • 在X86總 PWS由标志寄存器和EIP組成
• 中斷的處理
  • 發現中斷源
  • 保護現場
  • 轉向中斷/ 異常時間的處理程式
  • 恢複現場
• 時鐘中斷是肯定是在使用者使用的哈 中斷程式是在核心
• 可再入 和可再用
  • 可再入：隻讀的代碼，能夠被多個程式同時調用 編譯程式
  • 可再用：一次隻能一個程式調用
• 程序的特征
  • 【并發性 制約性】【 獨立性 共享性】【 結構性】【 動态性】
• 作業系統的特性
  • 異步性 共享性 并發性

并發制約獨立動态結構共享

• 程序的狀态和轉換
  • 三态模型
  • 五态模型
  • 七态模型
• 程序映像
  • 程序控制塊
    • 表示資訊
    • 現場資訊
    • 控制資訊
  • 程序程式塊
  • 程序核心快
  • 程序資料塊
• 上下文切換和模式切換
  • 上下文是不同的程序之間的轉換
  • 模式切換是同一個程序下的 核心和使用者之間的轉變
  • 上下文切換，程序切換一定是在核心空間中的

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-CgfwqGsg-1610355301000)(C:%5CUsers%5CAdministrator.DESKTOP-CGIO78B%5CAppData%5CRoaming%5CTypora%5Ctypora-user-images%5Cimage-20210111095717447.png)]

• 程序的管理和控制
  • 原語 關中斷，不能并發執行 是哦那個房管指令
• 線程
  • 使用者級線程：無需模式切換，節省開銷
  • 大多數系統調用是阻塞的，一個的阻塞導緻整個程序的阻塞
  • 核心級線程：能夠利用多個CPU
  • 并且一個線程阻塞之後，也不會導緻整個的堵塞
  • 線程在使用者時，模式切換的開銷太大。使用者——核心——使用者

typedef struct semaphore{
	int value;
	struct pcb* list;
};

void P(semaphore &s){
	s.value--;
	if(s.value<0){
		W(s.list);   //利用W（s.list)來阻塞自己
	}
}

void V(semaphore &s){
	s.value++;
	if(s.value<=0){
		R(s.list);
	}
}	
           

管程的實作代碼

type struct InterfaceModule{
	semaphore mutex;
	semaphore next;
	int next_count;
}

//enter
mutex=1;
next=0;
next_count=0;

process enter(){
	P(IM.mutex);
}

process leave(){
	if(IM.next_count>0){
		V(IM.next);
	}
	else{
		V(IM.NEXT);
	}
}

process singal(semaphore & x_sem, int & x_count,IM){
	next_count++;
	//喚醒目前信号量上的
	if(x_count>0){
		V(x_sem);
		P(IM.next);
		next_count--;
	}
}


process wait(semaphore & x_sem,int & x_count,IM){
	x_count++;
	if(IM.next_count>0){
		V(IM.next);
	}
	else{
		V(IM.mutex);
	}
	P(x_sem);
	x_count--;
}


哲學家就餐問題
   
    
typedef philiosopher_dinner=monitor
    
enum {hungry,eating,thinking} state[5];    
semaphore self[5];
int selft[5]_count;
for(int i=0;i<5;i++){
    state[i]=thinking;
}
define pickup,putdown;
use enter,leave,putdown,singal

void puton(int i){
    enter(IM);
    state[i]=hungry;
    test(i);
    if(state[i]!=eating){
        wait(self[i],self_count[i],IM);
    }
    拿到左右的兩邊筷子
    
    leave(IM);
}

void putdown(int i){
    enter(IM);
    state[i]=thinking;
    test((i-1)%5);
    test((i+1)%5);
    
    leave(IM);
}


void test(int i){
    if(state[i]== hungry && state[(i-1)%4]!=eating && state[(i+1)%5]!=eating){
        state[i]=eating;
        singal(self[i],self[i]_count,IM);
    }
}

生産者消費者問題
   process enter(){
	P(IM.mutex);
}

process leave(){
	if(IM.next_count>0){
		V(IM.next);
	}
	else{
		V(IM.NEXT);
	}
}

process singal(semaphore & x_sem, int & x_count,IM){
	next_count++;
	//喚醒目前信号量上的
	if(x_count>0){
		V(x_sem);
		P(IM.next);
		next_count--;
	}
}


process wait(semaphore & x_sem,int & x_count,IM){
	x_count++;
	if(IM.next_count>0){
		V(IM.next);
	}
	else{
		V(IM.mutex);
	}
	P(x_sem);
	x_count--;
}
 
    
typedef produce_customer=monitor
    
semaphore notfull,notempty;
int notfull_count,not_empty;
notfull=0,notempty=0;
notfull_count=0;not_empty_count=0;
int count = 0;


void put(){
    enter(IM);
    if(count==M){
        wait(notfull,notfull_count,IM);
    }
    //進行産品的制作
    count++;
    singal(notempty,notempty_count,IM);
    leave(IM);
}


void putdown(){
    enter(IM);
    if(count==0){
        wait(notempty,notempty_count,IM);
    }
    
    count--;
    singal(notfull,notfull_count,IM);
    leave(IM);
}


讀者寫者問題
    
typedef reader_writer=monitor
    

semaphore R,W;
int R_count,W_count;
int readcount,writecount;


void startread(){
    enter(IM);
    if(writecount>0){
        wait(R,R_count,IM);
    }
    readcount++;
    
    leave(IM);
}


void endread(){
    enter(IM);
    readcount--;
    if(readcount==0) singal(W,W_count,IM);
    leave(IM);
}


void startwrite(){
    enter(IM);
    writecount++;
    if(writecount>1 || readcount>0 ){
        wait(W,W_count,IM);
    }
    leave(IM);
}

void endwrite(){
    enter(IM);
    writecount--;
    if(writecount>0){
        singal(W,W_count,IM);
    }
    else{
        singal(R,R_count,IM);
    }
    leave(IM);
}
           

• 程序通信
• 信号
• 管道
• 共享記憶體
• 消息傳遞
• 共享記憶體

死鎖防止：

破壞四個必要條件

互斥 保持與申請 不剝削 循環等待

保持與申請：靜态配置設定

不剝削：剝削

循環等待：按需配置設定 俺層次配置設定

死鎖避免 銀行家算法

如果可以收回來，那我才借給你

死鎖檢測和接觸 資源配置設定圖 和死鎖定理

裝置管理 I/O 硬體原理

• I/O控制方法
  • 輪詢
  • 中斷
  • DMA
  • 通道
  • 對CPU的影響程度越來越小
• I/O 軟體的設計目标 高效率和通用性
  • 考慮的問題
    • 裝置通用性
    • 出錯處理
    • 同步/異步傳輸
    • 緩沖技術
  • IO軟體的四個層次
    • I/O 中斷處理程式
    • I/O 裝置驅動程式
    • 獨立于裝置的 I/O軟體
    • 使用者空間中的I/O 軟體
  • 驅動程式的三功能
    • 裝置初始化
    • 執行裝置驅動曆程
    • 執行中斷處理曆程
  • 獨立于裝置的 I/O軟體
    • 裝置命名和裝置保護
    • 提供與裝置無關的塊尺寸
    • 緩沖技術
    • 裝置配置設定和狀态跟蹤
    • 錯誤處理與報告
  • 使用者空間的 I/O軟體
    • 庫函數
    • SPOOLING
      • 作業排程程式 井管理程式 運作作業
• 緩沖技術
  • 單緩沖
  • 雙緩沖
  • 多緩沖
• 移動臂排程
  • FCFS 先進先出
  • elevator 電梯排程
  • SSTF 最短查詢時間 可能被黏
  • 掃描算法 scan 需要 到頭
  • circular scan 循環掃描 單方向
• 檔案管理
• 檔案的存取方式
  • 順序
  • 直接
  • 索引
• 檔案的邏輯結構
  • 流失 無結構
  • 記錄
• 檔案的實體結構
  • 順序
  • 連接配接
  • 直接檔案
  • 索引
• 标準化的操作接口
  • 檔案共享
    • 靜态共享
    • 動态共享
    • 檔案符号連結共享
• 硬碟空間管理
  • 連續配置設定
  • 非連續配置設定
• 付村管理方法
  • 位示圖
  • 空閑區表
  • 空閑塊鍊
  • 成組連結發