---
# System prepended metadata

title: 'Ch3:Processes Concept'
tags: [Operating System, Review, Ch3]

---

---
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) 為未初始化的靜態變數

![](https://i.imgur.com/tJdDPmj.png)

### 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。

![](https://i.imgur.com/pIVkGlL.png)

### Process State

![](https://i.imgur.com/78U63QE.png)

**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
![](https://i.imgur.com/pocHfwH.png)


### 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。

![](https://i.imgur.com/SSIlSJb.png)



### 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)，以下為節錄其中一小部分。
```c=
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。

![](https://i.imgur.com/v75kS04.png)

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

### Process Scheduling Diagram

![](https://i.imgur.com/SAAyrpn.png)

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

### Schedulers

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

![](https://i.imgur.com/zDf1vv1.png)


- 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，因為有足夠的記憶體和虛擬記憶體。

![](https://i.imgur.com/baBhUKu.png)
![](https://i.imgur.com/Y4My09h.png)

## Operations on Processes

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

![](https://i.imgur.com/58NRPm5.png)

`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 時有需要寫入時，才會透過指標進行操作並分家，變成兩塊獨立的，大小一樣，但裡面值不一樣。

![](https://i.imgur.com/ljC3U4H.png)

使用 fork() system call 例子
```c=
#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;
}
```

![](https://i.imgur.com/YHXtAOC.png)


### 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。

![](https://i.imgur.com/H1QOLIs.png)

**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


![](https://i.imgur.com/hVwEtTs.png)

### 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 的**環狀陣列**
![](https://i.imgur.com/XOdu2Wj.png)

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

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

```c=
/* 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
```c=
#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
```c=
#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

```c=
/* producer */
while (1) {
    send(consumer, nextProduced);
}
/* consumer */
while (1) {
    receive(producer, nextConsumed);
}
```
#### Indirect communication
- Mailbox sharing

![](https://i.imgur.com/4dGvAp2.png)

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
    
![](https://i.imgur.com/ly4Zqr8.png)

### 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

![](https://i.imgur.com/UK2eeo8.png)

![](https://i.imgur.com/MoQpUNU.png)


### 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
    ![](https://i.imgur.com/NI2msCh.png)

![](https://i.imgur.com/t3J5DU7.png)


## 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)