[Operating System Cheat sheat] — Process

1. Process def. and Process contain
2. PCB context
3. The stage diagram of Process
4. Scheduler
5. Unix Fork() function
6. Context Swithing
7. Dispatcher
8. Interprocess Communication
9. Message Passing issue

Process

A Process is program in execution

一個執行中的program即為process，是OS分配Resource [CPU、Memory…]的對象單位。又稱為Jobs、Task …

Note Thread是OS分配CPU Time的對象單位

Program v.s Process

Process Control Block (PCB)

PCB

OS 為了管理所有的Processes，會在Kernel memory area中，針對每一個Process分別建立一個表格(Block)，稱為Process Control Block(PCB)紀錄關於該Process的所有資訊

Note : PCB的實作是linked list

• Process ID (PID)
• Program Counter(P.C)
• Process State
• CPU Register
• Stack …[local variable、return address、function parameter]
• Code Sections
• Data Sections …[global variable、static variable]
• Heap … [dynamic allocation memory space、malloc]

Process State Transition Diagram

一個Process從出生(New)到死亡(Exit)，可能會因為某些Event而經歷許多的State，我們將其使用像是有限狀態機的方式畫出，依照切分大小有3種State Transion Diagram(5個State、7個State、UNIX STD)。

Scheduler

基本上就是在不同的Queue中使用不同的Priortiy挑選Process的功能單元便稱為Scheduler。

Long term scheduler

又稱為Job Scheduler，目的是從Job Queue中挑選一些Job進入Memory中等待執行。

<特點>

1. 執行的頻率最低(通常個人電腦沒有，server才有可能有)
2. 可以調整Multiprogramming Degree(在Memory等待執行的Process數量)
3. 可調控I/O Bound 以及CPU Bound之混和比例
4. Batch System採用，但是Real Time以及Time Sharing System不採用

Short term scheduler

又叫CPU Scdeuler 或Process Scheduler，目的是從Ready Queue中，挑出一個高優先權的Process ，Dispatch(分派)CPU給它執行。

<特點>

1. 執行的頻率最高
2. 無法調整Multiprogramming Degree(在Memory等待執行的Process數量)
3. 無法調控I/O Bound 以及CPU Bound之混和比例
4. 所有System皆可採用

Medium term scheduler

Time Sharing System採用。

目的：當記憶體空間不足且又有其他高優先權Process需要記憶體空間時，此 scheduler會啟動，它會挑選一些Process：(ex:Blocked process、低優先權的Process)將其swap out到Disk中保存，以空出記憶體空間，供其他Process使用。將來等到有足夠的記憶體空間Realeased後，此scheduler可再將它們swap回記憶體，ready for execution

<特點>

1. 執行的頻率居中
2. 可以調整Multiprogramming Degree(在Memory等待執行的Process數量)
3. 可以調控I/O Bound 以及CPU Bound之混和比例
4. Time Sharing System採用

Context Switch

當CPU要從Running Process切給另一個Process使用之前，Kernel必須保存(Store) Running Process之前狀態 (ex：PC之值、Stack、CPU register，其實就是該process在PCB的內容) ，而且要載入另一個Process在PCB的狀態資訊 。此一工作稱為Context Switching。
Context Switching的overhead時間長短大都取決於硬體因素。ex:register數目、記憶體空間存取指令速度…

p.s . page fault 會trigger context switch ???????

降低Context Switch Overhead

1. 增加register數量

Process Control Operation

這邊講述了Process建立、暫停、終止、恢復執行Child Process的操作。

Parent 建立 Child Process 的目的便是分配工作給它，而工作內容可能與

• Parent Process 相同 (沒有call exec()系列函數)
• Parent Process 不同 (有call exec()系列函數)

而Child Process基本上所有的Resource都與Parent共享，除了以下幾項

1. PID
2. Process address space
3. Data section (static variable、global variable)

fork()

Parent process fork 建立出Child process，OS會配置 new frames 給
child process [也就是 Child 與 Process 占用不同的memory space]。
同時，OS也會複製copy parent process 內容 (i.e. Code section、Data section)
給child process。

這樣會使得 fork() function 有以下問題 :

1. 耗費 memory space (frames)大增
2. Slower Child Process Creation ，而且這種fork如果child直接執行exec之類的function時，此種浪費memory space去fork顯得相當無用。

Note : 一旦fork()成功，fork() function的回傳值即為Child Process的 PID

fork() with “copy-on-write”

比起一般的fork，OS會配置一個memory frame給child process。
但是 使用 "copy-on-write" 技術會使child process 共享Parent process的memory frame。

如此，可降低frame的需求量以及Speed up process creation。

但是任何一方改變了某Page內容，則另一方會受到影響(此為 risk)。

因此，“Copy-on-Write技術”確保 :

若 Child Process想要更改某Page之內容(ex:Stack內容),則OS會配置一個 Memory Frame 給 Child, 且 copy Page 內容到 Memory Frame中,
供Child使用/修改(且修改 Child 的 Page Table指向 New Frame),如此一來,
則不會影響 Parent那些有Modified 可能的Page,需標示 Copy-on-Write
而有些不會 Modified Page(ex : Read-only Code/Data),即可共享。

Vfork() … virtual Memory fork

Parent生出 Child之初,也是讓Child共享Parent相同的Frame,但
是它並未提供”Copy-on-Write”技術。

所以任何一方改變了某Page內容,則另一方會受到影響,故務必小心使用

因此特別適用在當生出Child後,Child立刻執行execlp、去作其他工作時 vfork()非常有效率

Execlp()、Exec()、Execve()

此種 System Call 用以載入特定的binary code 執行 ，並且
"覆寫"掉現在process本身的code section

fork() example

#include <stdio.h>
#include <unistd.h>
void main(){
    pid_t pid;
    int a;
    int i;
    a = 5;
    for(i=0; i<2; i++ ){
        pid = fork();
        if(pid<0) 
            return ;
        else if(pid==0) {
            a-=2;
            printf("%d\n", a);
        } 
        else {
            a--;
            printf("%d\n", a);
        }
    }
}

執行結果 : 4,3,2,1,3,2

Interprocess Communication

Process之間的溝通稱為Interprocess Communication (IPC)。

主要有兩種方式 :

1. Shared Memory
2. Message-passing

Share Memory

Process 透過對共享變敷(Share variables)之存取(Write/Read)，達到溝
通(Information exchange)之目的。

<分析>

1. 適用於大量Data(Message)傳輸之狀況
2. 傳輸速度較快 (因為不需kernel支持 : send()、recv()...)
3. 不適合用於 Distributed System Kernel
4. 不需提供額外的支援 (頂多供應Shared Memory Space)
5. “是Programmer的負擔”
   →必須寫額外的控制程式碼，防止"Race Condition"
   (更多info 參考同步章節)

Message-passing

Process雙方要溝通，必須遵循下列步驟 :

1. 建立 Communication Link
2. 訊息可以雙向傳輸
3. 傳輸完畢，釋放Communication Link

<分析>

1. 不適用於大量 Data 傳輸
2. 速度較慢 (因為需kernel支持)
3. 適合Distributed System
4. Kernel需提供額外支援 :
   e.g. Send/Receive 之 System Call 、Communication Link 管理，Message Lost之偵測，例外狀況處理
5. Programmer沒什麼負擔( 會使用OS提供的API即可 )
6. 是OS較常使用的方式。

Message Passing issue

Message Passing需要由OS提供System Call來執行，意味者我們在設計如Send()、Recv()…等等系統API時，可能需要更多的設計方法來避免效能上的瓶頸。

溝通方式

1. Direct Communication
2. Indirect Communication

Direct Communication

1. Symmetric
   雙方必須互相指定對方的process ID，才能建立Communication Link
   (e.g. OS 提供的 send 、 receive 之 system call)
2. Asymmetric
   只有送方需指名收方ID，但收方無需指名送方，從任何 Process 皆可以
   (e.g. Email)

Note . In direct communication , link between send/recv is “automatically" build

Indirect Communication

收、送雙方是透過Shared Mailbox才能建立Communication Link。

比較表

Lnk Capacity

假若收方一律是:”若未收到訊息則暫停,直到收到訊息後,才往下執行”，而對於送方，就看”Link Capacity”
→在每條Communication Link皆附有一個message Queue，用以保存除正在停輸中的訊息以外之其他訊息，而Queue size = Link Capacity

Link Capacity有下列 3 種 size

1. Zero capacity :(no message buffer)
   [sender view]
   送方送出訊息後則暫停，直到收方收到訊息後，送方才可往下執行。
   [receiver view]
   收方一律是 ”若未收到訊息則暫停，直到收到訊息後，才往下執行”。
2. Bounded capacity:當 Queue滿了，則送方被迫暫停。
3. Unbounded capacity: 送方無需被迫暫停