---
title: Ch3:Processes Concept
---
# 作業系統Ch3: Processes Concept
###### tags: `Operating System` `Review` `Ch3`

## Process Concept

### Process
- Program - passive entity: binary stored in disk.
- Process - active entity: a program in execution in memory.

A process includes:

- <font color='red'>Code segment </font>(text section) - literal strings
- <font color='red'>Data section </font>- global variables、static variables
- <font color='red'>Stack </font>- temporary local variables and functions (遵守 LIFO)
- <font color='red'>Heap </font>- dynamic allocated variables or classes，執行時才會知道配置大小，由使用者分配/釋放 (不是 DS 中的 heap 而是 linked list)
- Current activity (<font color='red'>program counter</font>, register contents)
- A set of associated <font color='red'>resources</font> (e.g., open file handlers)

下圖的，BSS(Block started by symbol) 為未初始化的靜態變數


### Threads

- a.k.a <font color='red'>lightweight process</font>， OS 分配 CPU 時間的對象。
- 同一個 process 下的所有 threads 共享 code section、 data section and OS resources (e.g., open files and signals)。
> code section + data section = memory space
- 每一個 thread 都有屬於自己的 thread ID、 program counter、 register set and a stack。


### Process State


**States**
- New: the process is being created.
- Ready: the process is in the memory waiting to be assigned to a processor.
- Running: instructions are being executed by CPU.
- Waiting: the process is waiting for events to occur.
- Terminated: the process has finished execution.

在任一時刻，只會有一個 process 正在跑在 on any processor，其他 processes 可能在 ready or waiting。

**Process Control Block (PCB)**

Process 是由使用者用指令透過 OS 而產生出的，且 OS 的工作還包含紀錄每一個 process 相關資訊稱作 PCB

- Process state
- Program counter
- CPU registers
- CPU scheduling information (e.g., priority)
- Memory-management information (e.g., base/limit register)
- I/O status information
- Accounting information - provides the amount of time required by the CPU to complete the given process and the limits of it

### Context Switch
- Kernel saves the state of the old process and loads the saved state for the new process
- Context-switch time is purely <font color='red'>overhead</font>
- Switch time 取決於
- memory speed。
- 暫存器的數量。
- 特殊指令的存在。
- a single instruction to save/load all registers.
- HW support
- 多組暫存器可以在 CPU 上對於 PCB 進行保留，而不用存入記憶體，減少 Context Switch。


### Process Scheduling
- Multiprogramming: CPU 會一直 runs process 來最大化 CPU 使用率。
- Time sharing: 當頻繁地切換運行的 processes，使得使用者可以和每一個 process 互動。
- Processes 必須等待 CPU 空下來且可以被重複 scheduled。

:::spoiler **補充: Process Representation In Linux**
在 Linux 作業系統中的 PCB 是由 C 語言 structure **task_struct** 表示，並可在 \<include/linux/sched.h> 找到，這結構包含了所有用來表示 process 的必要資訊(包含 a list of its children and siblings)，以下為節錄其中一小部分。

long state; /* state of the process */
struct sched_entity se; /* scheduling information */
struct task_struct *parent; /* this process's parent */
struct list_head children; /* this process's children */
struct files_struct *files; /* list of open files */
struct mm_struct *mm; /* address space */

在 Linux kernel 中，所有 active processes 用 doubly linked list of task_struct ， 而 kernel 維護指向目前在系統上運作的 process 的指標 current。
:::

### Process Scheduling Queues

Processes 會有好幾種不同的 queues，在不同 state 下遷移
- Job queue (New State): 在系統中所有 processes 的集合。
- Ready queue (Ready State): 留在主記憶體中所有 processes 的集合且準備好等待執行。
- Device queue (Wait State): 等待 I/O 裝置處理結束的 processes 集合。
> Device queue 不是只有一個，不同的 I/O devices 會有不同的 Device queue，因此會有多個 Device queues。


> 由此圖看出至少 queue 會有 head、tail 紀錄 PCB 的頭尾(形成一種 Linked list)，而 PCB 本身的 Pointer 會指向紀錄下一個 Process 相關資訊的 PCB 。

### Process Scheduling Diagram


> 此圖主要是 Process 進入 CPU 執行後，什麼情況下會離開 CPU。

### Schedulers

- Short-term schedulers (CPU scheduler) - 選擇哪一個 process 可以被執行和分配給 CPU。 ($Ready\ state\ \rightarrow\ Run\ state$)
- 執行較頻繁。
- 必須要有效率，否則 overhead 會很高。
> 由於 time sharing 的關係，所以 CPU 很常進行切換到不同的 Process，因此稱作 Short-term。


- Long-term schedulers (job scheduler) - 選擇哪些 process 應該載入到 memory 且帶入到 ready queue。 ($New\ state\ \rightarrow\ Ready\ state$)
- 控制 **multiprogramming 的程度**。
- 執行頻率較少。
- 選擇良好 CPU-bound / I/O-bound processes 組合可以提高系統整體效能。
- UNIX/ NT 沒有 long-term scheduler。
> 由於這邊會跟使用者有關係，所以是比較慢的，因此稱作 long-term。
> Long-term schedulers 跟早期電腦因記憶體不足(太貴)時比較有關，因為沒辦法一次把所有在 disk 上的 jobs load 到 memory 裡面去，但是現在記憶體很多且有虛擬記憶體機制，不用太過擔心排程的問題。

- Medium-term schedulers - 選擇哪些 processes 應該 swapped in/out memory。
($Ready\ state\ \rightarrow\ Wait\ state$ )
- swap out: 從記憶體中移出 processes，並搬到 virtual memory (in a disk)，減少 multiprogramming的程度。
- swap in: 重新移入被移出的 processes 進入記憶體。
- 目的: 改善 process mix，空出記憶體。
- 現代 OS 沒有 medium-term schedulers，因為有足夠的記憶體和虛擬記憶體。


## Operations on Processes

### Tree of Processes
- 每一個 process 都有一個唯一的 process identifier (pid) 可以識別。


`ps -el` 用來列出對於所有 processes 目前還在系統上活動的完整資訊。

### Process Creation
建立 Process 可以從不同方向來看，會有不同的可能性。

- Resource sharing
- Parent and child 共享所有資源。
- Child 共享 parent 的一部分資源。
- Parent and child 沒有共享資源。
- 執行上的可能性
- Parent and children 並行執行。
- Parent 等待到 child 到執行結束。
- address space 的可能性
- Child 複製 parent，藉由共享變數來溝通。
- Child 有新程式載入進去，藉由 message passing 來溝通。

**fork()** system call
- 建立一個新的 child process。
- new process 會複製 parent 的 address space。
- 在 fork 後， child & parent 並行執行。
- Child: fork 的回傳值為 0。
- Parent: fork 的回傳值為 child 的 pid。

**execlp()** system call
- 載入新的 binary file 到記憶體 - 摧毀舊的 code。

**wait()** system call
- parent 會等待到它的其中一個 child 完成執行。

Memory space of fork()
- 過去實作: A's child is an <font color = red>exact copy</font> of parent
- 目前實作: 使用 <font color = red>**copy-on-write**</font> 技巧來儲存差異在 A's child address space。
> 也就是容易變動的、執行必須要有的那些會複製到 child，剩下的會有指標指向 parent process 那一塊空間，只有在 runtime 時有需要寫入時，才會透過指標進行操作並分家，變成兩塊獨立的，大小一樣，但裡面值不一樣。


使用 fork() system call 例子

#include<stdio.h>
#include<sys/types.h>
#include<unistd.h>
#include <sys/wait.h>

int main()
{
    pid_t pid;
    
    /* fork a child process*/
    pid = fork();
    
    if (pid < 0) { /* error occurred */
        fprintf(stderr, "Fork Failed");
        return 1;
    } else if (pid == 0) { /* child process */
        execlp("/bin/ls", "ls", NULL);
    } else { /* parent process */
        /* parent will wait for the child to complete */
        wait(NULL);
        printf("Child Complete");
    }
    
    return 0;
}


### Process Termination

Terminate 當最後一行被執行時或者呼叫 exec()
- 所有 process 的資源包含物理和虛擬記憶體，打開的檔案和 I/O buffers 都會被 OS 取消分配。

Parent 可以藉由指定 child 的 pid 中止 child 的執行。(abort())
- Child 超過分配的資源。
- 分配給 child 的 task 不再需要。

Cascading termination (瀑布式結束):
- killing (exiting) parent $\rightarrow$ killing (exiting) all its children

**Zombie Process**:
- 當一個 process 中止時，它的資源被歸還給 OS，然而它的入口 (entry) 仍然在 process table 直到它的 parent 呼叫 wait( )(釋放掉 zombie process 的 pid 和 entry)，因為 process table 會包含 process's exit status。如果 parent 尚未呼叫 wait() 的話， 此時已經中止的 process 稱作 Zombie process。


**Orphan Process**:
- 如果一個 Process 還在時， 它的 parent 沒有呼叫 wait( ) 反而是自己中止了，它的 child 稱作 Orphan process。
- 在 Unix 中，會把這些 Orphan processes 指定 `init` process 為它們的 new parent，並且 init process 會週期性的呼叫 wait()，從而達到釋放它們資源和 entry。
- 在 Linux 中， 只是 `init` process 換成 `systemd` process，但是做法是一樣的。

## Interprocess Communication

IPC: 用於一個或多個 processes 中的多個 threads 之間的 exchange of data 方法集合。

Independent process: 不能影響或被其他 processes 影響。
Cooperating process: 其餘。

Purpose
- 資訊共享
- 計算上提升
- 方便
- 模塊化

### Communication Methods


### Shared memory

對於 user synchronization 要求更高，實作上有較快記憶體存取速度。
Process 負責:
- 建立共享記憶體區域
- 通常，共享記憶體區域位於 process 創造的 shared-memory segment 的 address space 中。
- 參與的 processes 必須要被允許從 OS 手上移除存取記憶體限制。
> 透過 system call shm_open()來創造 shared memory object。
- 決定 data 的形式和 location。
- 確保 data 不會同時被 processes 寫入。

**Consumer & Producer Problem**

Producer process: 產生資訊。
Consumer process: 消耗資訊。

Buffer 作為 size 為 B 的**環狀陣列**

- next free: in
- first available: out
- emtpy: in = out
- full: (in + 1) % B = out

最多有 $(B - 1)$ item 在 buffer 中，否則會難以判斷是滿還是空的。
> 可透過 lock 去解決。

/* pseudocode */
/* global data structure */
#define BUFFER_SIZE 10
item buffer[BUFFER_SIZE];
int in = out = 0;

/* producer */
while (1) {
    while (((in + 1) % BUFFER_SIZE) == out)
        ; // wait if buffer is full
    buffer[in] = nextProduced;
    in = (in + 1) % BUFFER_SIZE; // "in" only modified by producer
}

/* consumer */
while (1) {
    while (in == out)
        ; // wait if buffer is empty
    nextConsumed = buffer[out];
    out = (out + 1) % BUFFER_SIZE; // "out" only modified by Consumer
}

Producer process illustrating POSIX shared-memory API

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<fcntl.h>
#include<sys/shm.h>
#include<sys/stat.h>
#include<sys/mman.h>

int main()
{
    /* the size (in bytes) of shared memory object */
    const int SIZE = 4096;
    /* name of the shared memory object */
    const char *name = "OS";
    /* strings written to shared memory */
    const char *message_0 = "Hello";
    const char *message_1 = "World!";
    
    /* shared memory file descriptor */
    int fd;
    /* pointer to shared memory object */
    char *ptr;
    
    /* create the shared memory object */
    fd = shm_open(name, O_CREAT | O_RDWR, 0666);
    
    /* configure the size of the shared memory object */
    ftruncate(fd, SIZE);
    
    /* memory map the shared memory object */
    ptr = (char *)mmap(0, SIZE, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
    
    /* write to the shared memory object */
    sprintf(ptr, "%s", message_0);
    ptr += strlen(message_0);
    sprintf(ptr, "%s", message_1);
    ptr += strlen(message_1);
    
    return 0;
}

編譯時需加入`-lrt`，也就是跟`librt`連結，rt的全名是 `RealTime extension`。

透過 function prototype `int shm_open(const char *name, int oflag, mode_t mode);` 以及[其 DESCRIPTION](https://man7.org/linux/man-pages/man3/shm_open.3.html)，上述程式碼的 shm_open 會先創造一個 shared-memory object 如果它還不存在的話，接著賦予它讀寫權限，最後回傳為 int 型態的 file descriptor。

而 function prototype `void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);` 以及[其 DESCRIPTION](https://man7.org/linux/man-pages/man2/mmap.2.html)，上述程式碼的 mmap 會建立一個包含 share-memory object 的 memory-mapped file (記憶體對映檔案)，接著可以讀寫的 page 權限，然後再設立 flag MAP_SHARED ，意思是改變 shared-memory object 的話， 對於所有共享這個 object 的 process 是可見的 (visible)。

Consumer process illustrating POSIX shared-memory API

#include<stdio.h>
#include<stdlib.h>
#include<fcntl.h>    /* For O_* constants */
#include<sys/shm.h>
#include<sys/stat.h> /* For mode constants */
#include<sys/mman.h>

int main()
{
    /* the size (in bytes) of shared memory object */
    const int SIZE = 4096;
    /* name of the shared memory object */
    const char *name = "OS";
    /* shared memory file descriptor */
    int fd;
    /* pointer to shared memory object */
    char *ptr;
    
    /* open the shared memory object */
    fd = shm_open(name, O_RDONLY, 0666);
    
    /* memory map the shared memory object */
    ptr = (char *)mmap(0, SIZE, PROT_READ, MAP_SHARED, fd, 0);
    
    /* read from the shared memory object */
    printf("%s", (char *)ptr);
    
    /* remove the shared memory object */
    shm_unlink(name);
    
    return 0;
}

編譯時需加入`-lrt`，也就是跟`librt`連結，rt的全名是 `RealTime extension`。

### Message passing
- No conflict (同步): 對 small data 更有效率。
- 使用 send/recv message。
- 以 **system call** 實作: 速度較慢。

有機制去 communicate and synchronize processes 的動作，且溝通不需要透過共同變數的情況下才能達成。

為了溝通
- Establish a communication link
- physical (e.g., shared memory, HW bus, or network)
- logical (e.g., logical properties)
- Direct or indirect communication
- Blocking or non-blocking
- ...
- Exchange a message via send/receive

#### Direct communication
- Processes 一定要詳細「叫名」彼此。
- Send(P, message) - process Q 寄 message 給 process P
- Receive (Q, message) - 從Q 那邊收到 message
- Properties of communication link
- links 通常自動建立。
- one-to-one relationship 在 links 和 processes。
- link 可能是單向，但是通常是雙向的。
- 有限的 modularity: 如果 process 改名的話，所有舊名都要進行更改。

Solution for producer-consumer problem

/* producer */
while (1) {
    send(consumer, nextProduced);
}
/* consumer */
while (1) {
    receive(producer, nextConsumed);
}

#### Indirect communication
- Mailbox sharing


Sender 寄 message 給 Mailbox 後，可能會產生很多個 Receiver 從Mailbox 收 message，此時如果要保證一個 message 只能有一個 receiver 讀到的話，那麼就會有 Syncronization 的問題，到底是 P2 還是 P3 ?

Solution:
- Allow a link to be associated with at most two processes.
> 類似 Direct communication
- Allow only one process at a time to execute a receive operation.
> 同一時間，只能有 receiver 來拿資料，類似 lock。
- Allow the system to select arbitrarily a single receiver. The system define an algorithm for selecting which process will receive the message (for example, round robin)
> 系統會任意選擇一個 process，並且向發送方確認是不是這個 process 作為收信方。

Synchronization
- Message passing 不是 blocking (synchronous) 就是 non-blocking (asynchronous)
- Blocking send: sender is blocked until the message is received by receiver or by the mailbox
> Sender 會被暫停直到 message 被收到。
- Nonblocking send: sender sends the message and resumes operation
> Sender 寄出 message ， 馬上就 return function call。
- Blocking receive: receiver is blocked until the message is available
- Nonblocking receive: receiver receives a valid message or a null
> 在 Sender 和 Receiver 中間會有 buffer， call receive，可能 buffer 還是原來的 content，因為 Sender 還沒寄，因此會是舊的。
> 會有 token 事後檢查是不是真的收到 message
- Buffer implementation
- Zero capacity: blocking send/receive
- Bounded capacity: if full, sender will be blocked
- Unbounded capacity: sender never blocks


### Sockets
- A network connection identified by **IP & port**.
- Exchange <font color=red> unstructured stream of bytes</font>.
> 因為是 unstructured stream of bytes，所以 data parsing 責任落到 server and client applications
- Communication consists between a pair of sockets
- Use 127.0.0.1 to refer itself



### Remote Procedure Calls
- 使 procedure 在另一個 address space 執行。
- Parameters and return values are passed by message.
- Stubs – client-side proxy for the actual procedure on the server
- Client stub:
- Packs parameters into a message (i.e. parameter marshaling)
- 呼叫 OS 直接傳給 server
- 等待從 server 端回傳結果
- Server stub:
- Receives a call from a client
- Calls the corresponding procedure
- 解包裝 parameter
- 回傳結果給 caller


## Ref

[1] [上課影片 link](https://www.youtube.com/playlist?list=PLS0SUwlYe8czigQPzgJTH2rJtwm0LXvDX)
[2] [投影片 link](https://ocw.nthu.edu.tw/ocw/index.php?page=course_news_content&cid=141&id=999)