---
# System prepended metadata

title: Unix V6 on PDP-11 architecture - Process
tags: [unix_v6, kernel]

---

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


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