Unix V6 on PDP-11 architecture - Process
===
###### tags: `unix_v6` `kernel`
## 目錄
[TOC]
## process lifetime
```flow
st1=>start: Parent process
st2=>start: Child process
e1=>end: Parent process keep exec
e2=>end: Child process end
sub1=>subroutine: System Call: fork()
cond1=>condition: Parent?
cond2=>condition: Child end?
op1_0=>operation: Parent exec
op1_1=>operation: Parent wait
op2_1=>operation: Child exec
op2_2=>operation: Child exit
st1->op1_0->sub1->cond1->op1_1->cond2->e1
st2->op2_1->op2_2->e2
cond1(yes)->op1_1
cond1(no)->st2
cond2(yes)->e1
cond2(no)->op1_1
```
## process creation
- 透過將 parent process 的 Data 複製到 child process，來創建新的 process，這個過程透過 system call - `fork()` 來完成
- 被複製的 data 有：
1. proc\[\] 裡的 elements，並把新複製出來的其中一個 element: proc.p_ppid point 到舊的 proc.p_pid。(即把 child parent_pid 欄位設為 parent 的 pid)
2. WHOLE Data Segment
- including PPDA
- 讓 Child process 的 `struct user` 的 `user.u_procp` points to 對應的 `struct proc`
- Text Segment 不會被複製，Parent and Child share the same Text Segment
- 若 Child process 執行了其他 process，那會解除共享 Text Segment 的關係。
### How do parent find his children?
Iterate all the elements in proc\[\] to check the proc.p_ppid，若這個有指到自己的 proc.p_pid，那他就是自己的 child。
### 實際上的 creation 以及 kernel 裡的運作
整體流程：
```graphviz
digraph dfd
{
node[shape=record]
call1 [label="<f0> user invoked\n fork()"];
proc2 [label="{<f0> \n\nsystem call \nfork()\n\n\n | {<f1> subroutuine:\nnewproc() | <f2> subroutine:\npanic()} }" shape=Mrecord];
return [label="<f1> return back to user space \n and head for next instruction."];
call1:f0->proc2;
proc2->return:f1;
}
```
### System call - `fork()`
先看以下程式碼：
**list 1.** C語言呼叫 fork 的 assembly, is at user space
```clike=
.globl _fork, cerror, _par_uid
_fork:
mov r5,-(sp)
mov sp,r5
sys fork
br 1f
bec 2f
jmp cerror
1:
mov r0,_par_uid
clr r0
2:
mov (sp)+,r5
rts pc
.bss
_par_uid: .=.+2
```
=======================================
**list 2.** system call fork(), is at kernel mode
```c=
fork()
{
register struct proc *p1, *p2;
p1 = u.u_procp;
for(p2 = &proc[0]; p2 < &proc[NPROC]; p2++)
if(p2->p_stat == NULL)
goto found;
u.u_error = EAGAIN;
goto out;
found:
if(newproc()) {
u.u_ar0[R0] = p1->p_pid;
u.u_cstime[0] = 0;
u.u_cstime[1] = 0;
u.u_stime = 0;
u.u_cutime[0] = 0;
u.u_cutime[1] = 0;
u.u_utime = 0;
return;
}
u.u_ar0[R0] = p2->p_pid;
out:
u.u_ar0[R7] =+ 2;
}
```
=======================================
先看 list 1 & 2
1. 首先在 list_1:line_6，使用了 assembly 指令 -> `sys fork` 這個指令會呼叫 system call fork(), 透過這個指令呼叫 system call，切換到 kernel space 來做事。
2. 再來看 list_2。 這裡就是 fork() 主要在做的事了，這邊要分成 parent process 跟 child process 來看
- Parent，從第一行開始執行
1. line_5: `p1 = u.u_procp` 這是把 p1 設為指到 parent 的 struct proc
2. line_6 ~ line_10: Iterate proc[] to find 尚未使用的 element，找到後讓 p2 指向他，若是沒有找到則設置 error code。
3. 所以，p1 -> parent process; p2 -> child process
4. line_13: invoke `newproc()` to create a new process. **NOTE: In parent, the `newproc()` return 0, so the if-block won't be executed.**
5. 接著，來到了 line_23，此行將 parent process 的 r0 暫存器設置為 child process's pid。Note: 透過 u.u_ar0 可以 access user space process 的 register。
6. line_26: move to next instruction，相當於 ARM or MIPS 裡的 PC+4 (因為在 pdp-11 每一條指令長度為 16-bits = 2 bytes)
- Child，從 line_13 開始執行
1. `newproc()` 對 child process return 1，所以會執行 if-block
2. line_14 ~ 21: 將一些執行時間的欄位 init to 0， **並將 user space process 的 r0 設為 parent pid**，作為 system call fork() 對 child 的回傳值，**不是 user space 的 fork() !**
3. 到這裡，list_1 的 `sys fork` 已經執行結束了，以下再根據 parent / child 的不同，分別探討。
- Parent
1. 由與前面有做 `pc += 2`，所以接著會做 list_1:line_8 的指令
2. line_8: `bec 2f` 這是用來檢查 PSW register 的第 0 位 (carry) 為是否為 0，system call 出錯時這位會被設為 1 ， if (PSW~\[0\]~ == 0) goto line_13
3. 接著透過 `rts pc` 的指令返回到 C 語言函式庫呼叫的地方。**Return Value = 保存在 r0 的 child pid.**
- Child
1. 跟 parent 不同，照順序做，接著要做的是 list_1:line_7
2. `br lf` 無條件的直接跳到 label 1 (line 11)
3. line_11 ~ 12: `_par_uid = r0; r0 = 0` 這段的意義主要在使得 invoke C 語言函式庫的 user space process 可以取得 parent process pid，**最後將 r0 set to 0**
4. 接著執行 line_15 的 `rst pc` 指令返回到 C 語言函式庫呼叫的地方，**Return Value = 0 (r0 = 0, 被 `clr r0` clear 成 0 了)**
4. 統整一下 user space(C library) 和 kernel space(system call) 的 fork() 的回傳值:
- | Parent / Child | Parent | Child |
| -------------- | ------ | ----- |
| user space | child's pid | **0** |
| kernel space | child's pid | **parent's pid** |
### system call fork() 內部 procedure - `newproc()`
在 list_2 (system call fork()) 裡面有呼叫到 `newproc()`，這是主要用來產生新的 process 的 procedure。
**list 3.** newproc(), invoked at list 2.
```c=
newproc()
{
int a1, a2;
struct proc *p, *up;
register struct proc *rpp;
register *rip, n;
p = NULL;
/*
* First, just locate a slot for a process
* and copy the useful info from this process into it.
* The panic "cannot happen" because fork has already
* checked for the existence of a slot.
*/
retry:
mpid++;
if(mpid < 0) {
mpid = 0;
goto retry;
}
for(rpp = &proc[0]; rpp < &proc[NPROC]; rpp++) {
if(rpp->p_stat == NULL && p==NULL)
p = rpp;
if (rpp->p_pid==mpid)
goto retry;
}
if ((rpp = p)==NULL)
panic("no procs");
/*
* make proc entry for new proc
*/
rip = u.u_procp;
up = rip;
rpp->p_stat = SRUN;
rpp->p_flag = SLOAD;
rpp->p_uid = rip->p_uid;
rpp->p_ttyp = rip->p_ttyp;
rpp->p_nice = rip->p_nice;
rpp->p_textp = rip->p_textp;
rpp->p_pid = mpid;
rpp->p_ppid = rip->p_pid;
rpp->p_time = 0;
/*
* make duplicate entries
* where needed
*/
for(rip = &u.u_ofile[0]; rip < &u.u_ofile[NOFILE];)
if((rpp = *rip++) != NULL)
rpp->f_count++;
if((rpp=up->p_textp) != NULL) {
rpp->x_count++;
rpp->x_ccount++;
}
u.u_cdir->i_count++;
/*
* Partially simulate the environment
* of the new process so that when it is actually
* created (by copying) it will look right.
*/
savu(u.u_rsav);
rpp = p;
u.u_procp = rpp;
rip = up;
n = rip->p_size;
a1 = rip->p_addr;
rpp->p_size = n;
a2 = malloc(coremap, n);
/*
* If there is not enough core for the
* new process, swap out the current process to generate the
* copy.
*/
if(a2 == NULL) {
rip->p_stat = SIDL;
rpp->p_addr = a1;
savu(u.u_ssav);
xswap(rpp, 0, 0);
rpp->p_flag =| SSWAP;
rip->p_stat = SRUN;
} else {
/*
* There is core, so just copy.
*/
rpp->p_addr = a2;
while(n--)
copyseg(a1++, a2++);
}
u.u_procp = rip;
return(0);
}
```
1. Line 16 ~ 20:
這段是用來分配 pid 給 child。
`mpid` 是一個 global variable, declared at system.h `int mpid;` int type 會 overflow ，若 overflow(變成負數) 則 reset to 0 然後再 increment
Note: 當時的 C 語言還沒有 unsigned type
2. Line 21 ~ 28:
尋找 proc\[\] 中尚未使用的 element，並檢查已存在的 process 的 pid 是否和當前要被分配的 mpid 一樣，若相同則 goto retry，重新生成 ID
若尋找完，發現沒有空的元素，代表 proc\[\] 空間已經耗盡，呼叫 `panic()` 來處理，後面會介紹。
3. Line 34 ~ 35:
開始對 child process 的 struct proc 做 initialize。
先透過 u.u_procp 取得當前執行 process (that is, the parent process)，assign 到 rip
4. Line 36 ~ 44:
複製 parent's struct proc 的 element 值到 child's struct proc ，大部分的值一樣，有些不一樣。
- SRUN: 可執行狀態
- SLOAD: 指該 process 位於 memory 中
- **Line 42: 將 child's struct proc 的 p_pid element 設為 mpid**
- **Line 43: 同上，只是這次是設定 p_ppid，將 child 的 p_ppid 設為 parent's pid (即 current execute process's p_pid)，用以表示 child 的 "parent" 是誰。**
- | p | rpp (register) | up | rip (register) | u.u_procp |
| ----- | ------ | --- | --- | -- |
| proc\[\] 中尚未被使用的元素，即 child's struct proc | 同 p | parent's struct proc | 同 up | parent's struct procp |
5. Line 51 ~ 58:
Counter increment. 因為 child 繼承了 parent 開過的文件，所以這些用來記錄文件 reference 的 counter 都要 +1
parent & child share TEXT SEGMENT, Line 54 ~ 57 就是在做 TEXT SEGMENT 方面的 counter increment
Line 58: inode 方面的 coutner increment
有關 counter increment 的，後面會解釋，這邊先帶過。
6. Line 64:
invoke `savu()` 將 r5 (fp), r6 (sp) 當前的值暫存進 user.u_rsav; Note: savu(), assembler routine
7. Line 65 ~ 67:
rpp, rip 在前面都當作 for-loop 的 iterator，所以把他們值 assign 回 p, up (child's, parent's struct proc, respectivly)
接著，還有很重要的一步 **Line 66: `u.u_procp = rpp;`** 這行暫時把 u.u_procp 指到 child's struct proc，從原本指到 parent's struct proc，換成 child 的，原本的值備份在 rip 中。
- | p | rpp | up | rip | u.u_procp |
| -- | -- | -- | -- | -- |
| child's struct proc | same as `p` | parent's struct proc | same as `up` | **child's struct proc** |
8. Line 68 ~ 70:
先拿到 parent process's data segment size，並將 child process's 的設成跟他一樣; `a1` 指到的是 parent process data segment 的 address
9. Line 71:
`malloc(), size = n = parent data segment size`
10. Line 77 ~ 83:
這段主要是在做 malloc failed 時的處理。
失敗時，parent 的 data segment 會被複製出一段存在 swap 裡，作為 child 的 data segment。
1. Line 78: 將 parent process 設為 SIDL。在這個狀態的 process 不會被選為 current execute process，也不會被 swapped out。這是避免在進行 data segment 複製時，parent process 出意外。
2. Line 79: Assign child's data segment address to the same as parent's data segment address
3. Line 80: save r5(fp), r6(sp) to u.u_ssav，因為 data segment 包含 u.u_ssav，所以 u.u_ssav 也會被複製到 child process
4. Line 81: invoke `xswap`，去把 memory 中的 data segment 複製一個到 swap。重點是前兩個參數，第一個是要複製的東西的 source address (rpp, 即 parent's data segment address, set at Line 79)，第二個是 0，代表複製結束後不會去 release 在 memory 中的 data segment，讓其保留在那邊。
5. Line 82: set child process to SSWAP
6. Line 83: Restore parent process to SRUN
11. Line 84 ~ 91:
`malloc()` 成功，將 child process 的 data segment address assign to 新 malloc 的 address(a2)，並使用 `copyseg()` 來複製。
12. Line 92: Restore `u.u_procp` to parent's struct proc
13. Line 93: **return 0**，前面有說過，`newproc()` 對 parent 的回傳值是 0
14. Note: newproc() 對 child 的回傳值是 **1** ，詳情請參考 `swtch()`
### `newproc()` 內，資源耗盡時處理的 procedure - `panic()`
**list 4.** panic(), invoked at list 3.
```c=
/*
* Panic is called on unresolvable
* fatal errors.
* It syncs, prints "panic: mesg" and
* then loops.
*/
panic(s)
char *s;
{
panicstr = s;
update();
printf("panic: %s\n", s);
for(;;)
idle();
}
```
**list 5.** idle(), invoked at list 4.
```asm=
.globl _idle
_idle:
mov PS,-(sp)
bic $340,PS
wait
mov (sp)+,PS
rts pc
```
在資源耗盡時， `panic()` 透過 invoke `idel()` 來把處理器的優先級調為 0 ，並進入 `wait` 等待 interrupt 的狀態。
## Process Switch - 切換 current execute process
### Overview
- 現在正在執行的 process，在執行 kernel function `sleep()` 後會進入休眠狀態並中斷當前的處理，再透過 `swtch()` 去把當前執行的 process 切換到別的 process。
- `sleep()` 一般在以下情況被調用
1. user process invoke `wait()`
2. 等待週邊設備處理完畢
3. wait for resource release
- Process 的狀態由 `proc.p_stat` 來表示，有 SRUN, SSLEEP, SWAIT 三種
| state | meaning | 要用哪個 function 切換到這個狀態 |
| ----- | ------- | -------- |
| SRUN | exectutable | wakeup() |
| SSLEEP, SWAIT | 休眠狀態，兩個狀態的差別在於被喚醒時的執行 priority 不同 | sleep() |
```graphviz
digraph process_FSM {
rankdir=LR;
size="8,5"
node [shape = circle];
S1[label="SRUN"];
S2[label="SSLEEP / SWAIT"];
S1 -> S2 [label="sleep()"];
S2 -> S1 [label="wakeup()"];
}
```
- `swtch()` 是用來選擇下一個 execute process 是哪一個的 procedure，被選擇的 process 要滿足一下三個條件:
1. proc.p_stat == SRUN
2. 擁有最高的執行 priority (proc.p_pri 的值最小)
3. process didn't be swapped out
- 將某個 process 指定為下一個 current execute process 是無法做到的，因為無法確定在切換時是否有比該 process priority 更高的 process
- process 的 priority 是由 `setpri()` 所設定的，佔用 CPU 時間越久的 process 他的 priority 就會被降低，**所以，`setpri()` 中對 process priority 設定的方法影響了到底是哪一個 process 會被選為 current execute process。**
- process 的執行被中斷後，會將當前的狀態存進 `struct user` ，當該 process 再次被選為 current execute process 時，會再去從 `struct user` 中把資料 load 出來，恢復到被中斷時的狀態。這種處理就叫做 **context switch 上下文交換**，主要是由以下 assembly procedure 所實現：
1. `savu()` \/\/ save the status to struct user
2. `retu()` \/\/ load status from struct user
3. `aretu()` \/\/ load status from struct user
### `sleep()` - switch process state from SRUN to SSLEEP / SWAIT
- Prototype: `sleep(chan, pri)`
- Arguments:
1. @chan: address, 將會執行`current_execute_proc.p_wchan = chan;` wchan 代表的是 waiting channel，代表該 process 正在等待其所指到的位置的資源釋放。
2. @pri: priority，將會執行 `current_execute_proc.p_pri = pri;` 根據 value 的大小，在 **process switch** 前和**該 process 再次被選為 current execute process 後**，會對 signal 進行 or 不進行處理。
- | pri value | 狀態 |
| ------- | ---- |
| >=0 | 設為 SWAIT，對 signal 進行處理 |
| <0 | 設為 SSLEEP，**不**對 signal 進行處理 |
**list 6.** sleep()
```c=
/*
* Give up the processor till a wakeup occurs
* on chan, at which time the process
* enters the scheduling queue at priority pri.
* The most important effect of pri is that when
* pri<0 a signal cannot disturb the sleep;
* if pri>=0 signals will be processed.
* Callers of this routine must be prepared for
* premature return, and check that the reason for
* sleeping has gone away.
*/
sleep(chan, pri)
{
register *rp, s;
s = PS->integ;
rp = u.u_procp;
if(pri >= 0) {
if(issig())
goto psig;
spl6();
rp->p_wchan = chan;
rp->p_stat = SWAIT;
rp->p_pri = pri;
spl0();
if(runin != 0) {
runin = 0;
wakeup(&runin);
}
swtch();
if(issig())
goto psig;
} else {
spl6();
rp->p_wchan = chan;
rp->p_stat = SSLEEP;
rp->p_pri = pri;
spl0();
swtch();
}
PS->integ = s;
return;
/*
* If priority was low (>=0) and
* there has been a signal,
* execute non-local goto to
* the qsav location.
* (see trap1/trap.c)
*/
psig:
aretu(u.u_qsav);
}
```
:::info
NOTE: 接下來下面的解說，有些提到的 function 會先帶過，後面會再解說
:::
1. Line 16: `PS` points to the address of register PSW, see the follow code (defined at param.h) `#define PS 0177776 // octal, physical address`; 此行目的為保存 PSW 當前值。
2. Line 17: let `rp` points to current process's `struct proc`, one of the element of `proc[]`.
3. Line 18 ~ 32: 處理傳進來的參數: `pri` >= 0 的情況。
- 入睡，檢查是否有 signal，透過 `issig()` 來檢查，若有，`goto psig` (Line 51, 52) 交給那個 label 處理。
- Line 21: set CPU priority to '6'，因為此處可能會發生 iterrupt，處理時會呼叫 `wakeup()`，為避免下面三行的 data 被修改，所以提升 priority，詳細的以後文章再會說明。
- Line 22 ~ 24: set wchan, stat, pri; 其中在 `pri >= 0` 的情況可以看到 `stat = SWAIT;`
- Line 25: data 設定結束，CPU priority restore to '0'
- Line 26 ~ 29: `runin` is a flag variable. `if(runin == 1)` 表示**不存在**要被 swapped 到 swap space 的對象。詳細的後面會再說。
- Line 30: invoke `swtch()` to switch process.
- Line 31 ~ 32: 喚醒，檢查 signal。
4. Line 33 ~ 40: `pri` < 0 的情況。基本上處理同上，少了對 signal 的處理以及狀態是改為 SSLEEP 而非 SWAIT。
5. Line 41 ~ 42: 為了再次執行被中斷的 process，restore the value we stored at Line 16.
### `swtch()` - The main procedure of process switch
其主要的做法是 iterate `proc[]` 找出處於 SRUN 狀態且 priority 最高的，將該 process 選為 current execute process。
Iterate `proc[]`，找出符合條件的 process 然後再去做事是 kernel 常做的方法，但是 `swtch()` 比較不一樣，他不是從頭 (`proc[0]`) 開始 iterate 的，而是從 current execute process 的 element 位置開始找的。
如果有兩個處於 SRUN 狀態且 priority 相同的 process，那麼下一個被選到的 process 會是在 current execute process element 後面，且離他比較近的那個會被選到。
- 選出下一個 process 是哪一個 process 後，接下會做以下動作 (以下簡稱原本的 process 為 p1, 新的被選為的 process 為 p2)：
1. Modify kernel APR 使得 p2 的 struct user 可以透過 global variable `_u` 來 access。(參見：[前一篇文章](https://hackmd.io/96Y70AqnTPyA3O8t4fHtQQ#How-to-access-current-process’s-“struct-user”))
2. Access p2 的 struct user，裡面有之前保存的 r5, r6 的值，把他們恢復成 fp, sp
3. 恢復在 p2 的 struct user 中保存的 user APR 值。
Sign in with Wallet
Connect another wallet