2017年8月8日 星期二

OS - Ch3 行程 Process

於
標籤：
 


Process 相關知識介紹，上面這個狀態表很重要，fork 來 fork 去也滿常用的，enjoy it!

2015.1.13 初版
2017.8.8 二版





一、Process 簡介


行程(process)是電腦中已執行程式(program)的實體。現代面向執行緒設計的系統中，行程本身不是基本執行單位，而是執行緒的容器。行程需要一些資源才能完成工作，如CPU使用時間、記憶體、檔案以及I/O裝置。

名詞解釋：

  • 整批系統環境，行程稱為工作（jobs）。
  • 分時系統環境，行程稱為使用者程式（user progams）或任務（tasks）。
  • 在多數情況，工作與行程是同義詞，但行程（process）已較為人接受

行程在執行時，狀態(state)會改變。所謂狀態，就是指行程目前的動作：

  • new：行程新產生中。
  • running：正在執行。
  • waiting：等待某事發生，例如等待使用者輸入完成。亦稱「阻塞」（blocked）
  • ready：排班中，等待CPU。
  • terminated：完成執行。


[重要!] process 各狀態轉換關係圖。

process 在記憶體中的配置：

  • stack : 存放函數的參數、區域變數等。(會稱作 stack 是由於其配置遵守 LIFO)
  • heap : 一般由程式設計師分配釋放，執行時才會知道配置大小，如 malloc/new 和 free/delete。(注意其資料結構不是 DS 中的 heap 而是 link-list)
  • BSS : 未初始化的靜態變數
  • data : 全域變數、靜態變數
  • text/code : 常量字元串


[重要!] process 在記憶體中的配置圖


[例題] 配置練習

 
int a=0;   //global 初始化區
char *p1;  //global 未初始化區
main(){
    int b;             // stack
    char s[]="abc";    // stack
    char *p2;          // stack
    char *p3="123456"; // 123456\0 在常量區，p3在stack。
    static int c=0;   // global (static) 初始化區
    p1 = (char*)malloc(10);
    p2 = (char*)malloc(20);  //分配得來得10和20位元組的區域在heap
    strcpy(p1,"123456");  
    //123456\0 在常量區，編譯器可能會將它與 p3 中的 123456\0 優化成一個地方。
}





二、Context Switch


讓多個 process 可以分享單一個 CPU 資源的計算過程。當 CPU Context Switch 到另一個 process，系統會儲存舊 process 的狀態並載入新 process 的狀態。Context switch 的時間是 overhead，耗時根據硬體配備而不同。

交換的時機有以下幾種：

  • 多工
  • 中斷處理
  • 用戶態或者內核態的交換 (可能)

Process Control Block (PCB) : 作業系統核心中一種資料結構，當在切換 process 時，會把未做完的 process 相關資訊記錄在 PCB 裡。


PBC 紀錄的資訊結構圖。


Process Scheduling Queue：OS 在 Process Scheduling Queue 中維護所有的 PCB。

  • Job queue − This queue keeps all the processes in the system.
  • Ready queue – in main memory, ready and waiting to execute
  • Device queues – waiting for an I/O device




Process Scheduling Queue 示意圖。





三、Scheduler


1. Long-Term Scheduler (或稱 Job Scheduler)   [new—>ready]

  • 從 job queue 中挑選合適的 jobs，並將之載入到記憶體內準備執行。
  • 通常適用於 Batch System (大型機房)，但不適用於 Time-Sharing System。
  • 可調控 Multiprogramming Degree
  • 可調合 CPU-Bound 與 I/O Bound processes 之混合比例
  • 執行頻率最低


2. Short-Term Scheduler (或稱 CPU Scheduler)   [ready—>running]

  • 從 Ready Queue 挑選高優先度的 Process，使之獲得 CPU 控制權執行
  • Batch System 和 Time-Sharing 均需要
  • 執行頻率最高


3. Medium-Term Scheduler   [virtual memory]

  • 當記憶體空間不足，且又有其它 Process 欲進入記憶體執行，此時該 Scheduler 必須挑選某些 Process 將其 Swap Out 到磁碟中以空出記憶體空間，待記憶體有足夠空間再將其 swap in 記憶體中繼續執行。
  • 通常用在 Time Sharing System。
  • 減少 Multiprogramming Degree
  • 可調合 I/O Bound 與 CPU Bound 的比例


[重要] I/O bound vs CPU bound

  • I/O-bound process – spends more time doing I/O than computations, many short CPU bursts. ex : 等待鍵盤輸入的程式
  • CPU-bound process – spends more time doing computations; few very long CPU bursts. ex: 壓縮程式





四、對 Process 的操作


parent process 會建立 children processes，而 children processes 又可以成為 parent processes 建立其他 processes 而形成樹狀結構。


Each process has a unique PID, Some special PIDs :

  • 0 : scheduler 
  • 1 : init 
  • 2 : pageout


Process 建立的一些議題

  • 工作類型：與 parent 相同、與 parent 不同
  • Resource sharing : 全部分享、部分分享、全部不分享
  • Execution : parent child 同時執行、parent 等 child
  • Address space : 和 parent 相同、child 有其他 program 載入其中。


Process 操作有關的 system call

  1. fork() : 此 system call 用以建立 child process，child process 與 parent 占用不同的記憶體，但最初 child 的 code section、data section 內容均自 parent copy。
  2. exit() : 此 system call 即終止process，exit() return 0 為正常終止，-1 為不正常終止。
  3. execlp() : 此system call 用以載入特定的 Binary code file 讓 process 執行，即 process之code section 為此 Binary code content。
  4. wait() : 此 system call 用以強制 process 暫停知道某事件發生後才往下執行。


建立 process 流程圖。


Process Termination

  • child 執行完要求 OS 刪除自己 (exit)，child 傳輸結果給 parent (via wait)，資源由OS回收。 
  • parent 終止執行中的 child process (abort) 
  • parent 比 child 先終止 : 則 child 可能一並終止或由 OS/祖先 供應資源而存活下來。


[注意] 孤兒與殭屍

parent 死了，child 會變 orphan(孤兒)，parent 睡了，child 事情做完會變 zombie(殭屍)!!


[用心去感覺] fork() vs vfork()

Linux 程式設計下常用到的 fork()，功能是從 parent process 複制一個 child process，這是在有支援 MMU 的環境下才能使用。像 uclinux，就不能用 fork() 只能用 vfork()，因為 fork 的實作是利用 copy-on-write，因此一定要有 MMU。

  • fork() : process 內容整份複製，呼叫 fork() 後的 parent process 會和新產生的 child process concurrent 執行。
  • vfork() : call、data 和 stack 都是看 parent 原有的，呼叫 vfork() 後的 parent process 會被暫停，直到被複製出來的 child process 執行了 exec() 或 exit()。


[例題] C Program Forking Separate Process

int main(){
 Pid_t pid; 
 /* fork another process */
 pid = fork();

 if (pid < 0){ /* 錯誤發生：傳回-1(負值)給kernel parent */  
  fprintf(stderr, "Fork Failed"); 
  exit(-1); 
 } 
 else if (pid == 0){ /* child 收到 fork 傳回值是 0 */ 
  execlp("/bin/ls", "ls", NULL);   
  /* (目錄, 檔名, 參數) ，若 child 要做特定工作則必須執行 execlp() 載入需要的工作。*/
 }
 else { /* parent 收到傳回值是 child 的編號  */ 
   wait (NULL);  
   /* parent 等 child 直到 child 做完 */
  printf ("Child Complete”);  
  /* parent 有 child 的 pid 所以有權力殺了 child */
  exit(0); 
 }

}





五、Inter-Process Communication, IPC


一般 processes 可以分成不互相影響的 independent process 和可互相影響的 cooperating process。實際上使用 multiple process 的時機大多是處理事件或在背景做其他事。

  • ex1 : 等使用者輸入時可繼續計算
  • ex2 : 在背景執行磁碟重組作業 

常見的 IPC 有以下兩種：

  • shared memory
  • message Passing



兩個常見的 IPC。


1. IPC - Shared memory - Producer Consumer Problem 


To synchronize a producer and a consumer via shared memory.


Shared data : 

#define BUFFER_SIZE 10
Typedef struct{
 ...
}item;

item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;

只能使用 BUFFER_SIZE - 1 個元素。 (要空一個buffer以區別全空與全滿)

  • 全空：in, out 指向同一空元素
  • 全滿：in 指向 out 前一空元素，(in + 1) % BUFFER SIZE == out

答案在 concurrent 時正確，但 busy waiting 效能不好，尤其在單一 CPU 上 。


2. IPC - Message Passing


Processes communicate with each other without resorting to shared variables .


Direct communication

Processes must name each other explicitly : send (P, message), receive(Q, message). exactly one pair link, usually bi-directional.


Indirect communication 

不是直接寄給其他 process 而是寄到他家信箱 (also referred to as ports)，每個 mailbox 有一個特殊 id，一次可以連多個 process 但只能寄給一個 process，系統會自動選一個寄，然後告訴寄件者收件者是誰。

傳回給寄件者的信有三種情況：

  • 0 : 等
  • bounded : 滿了就要等
  • unbound : 無限 buffer 不用等

信件者間的同步問題：

  • Blocking is considered synchronous : Blocking send has the sender block until the message is received.
  • Non-blocking is considered asynchronous : Non-blocking send has the sender send the message and continue. 





References


 Gabriele Tolomei- In-Memory Layout of a Program (Process)
https://gabrieletolomei.wordpress.com/miscellanea/operating-systems/in-memory-layout/

wiki - 行程
https://zh.wikipedia.org/wiki/%E8%A1%8C%E7%A8%8B

tutorialspoint - Operating System - Process Scheduling
https://www.tutorialspoint.com/operating_system/os_process_scheduling.htm

Abraham Silberschatz, Peter B. Galvin, Greg Gagne - Operating System Concepts 8th Edition
https://www.amazon.com/Operating-System-Concepts-Abraham-Silberschatz/dp/0470128720

聯合大學陳士杰教授課程教材
http://web.nuu.edu.tw/~sjchen/

洪逸 - 作業系統金寶典
http://m.sanmin.com.tw/product/index/001601057





技術提供：Blogger.
 
© 2023 Mr. Opengate