作業系統作業一 - 項目一

B10402113 四電子四乙鄭和軒

目標：紀錄 kernel 執行到 0x7c00 當下暫存器與Stack 上面的值

操作流程

一、開啟qemu - gdb

指令： make qemu-gdb

二、開啟另一個終端remote進去

指令：
- gdb
- target remote localhost:26000

三、設定斷點位址與執行

指令：
- br *0x7c00 >>設定斷點至0x7c00
- c (continue) >>讓程式開始執行

四、紀錄暫存器的值

指令：
- info reg

作業系統作業一 - 項目二

目標：
零、一章節運作原理、基本流程介紹

Chapter 0

Operating system interfaces

本節重點：

作業系統提供使用者一個可以運行程式的介面，管理且虛擬化低層的硬體元件。
xv6是提供Unix作業系统中的基本介面，也模仿了Unix的內部設計。
kernel - 核心，用來控制硬體，提供服務來執行程式
process - 每個程式執行時的過程，包含著data , stack,instructions 的內存空間。
- instructions - 執行程式的運算
- data - 用於運算過程中的變量
- stack - 管理程式的過程與調用

當一個行程需要調用到系統函數時，它會在作業系統的介面中呼叫系統函數（System call），system call再進入kernal並運行服務再回傳。所以process是在使用者空間和kernal的空間交替運行。

Kernal 使用了保護機制來規定每個process只能訪問自己的內存空間，kernal擁有實現保護機制的硬體權限（hardware privileges）而使用者的程式並沒有此權限。
以下是xv6中的kernal提供的system call

Shell - 主要的使用者介面，接受來自使用者的指令，並與kernal溝通。shell是一般的使用者程式，並不屬於kernal中的一部分，這也代表shell很容易被替換，因此，Unix擁有許多種不同的shell與各自的腳本與屬性。

Processes and memory

Process(行程)：
xv6的process由兩部分組成：
- user-space memory（Stack,data,instructions）
- 僅有內核可見的process狀態

xv6能夠time-share 行程，意思就是說，它可在 CPU 之間不斷切換，決定哪一個等待中的行程被执行，當一個行程沒有被執行時，將會被保存到暫存器中，直到他們再被執行時再恢復。kernal將每個process和一個 pid (process identifier) 關聯起来。

Pid: 行程識別元（英語：process identifier，又略稱為行程ID（英語：process ID）、PID）是大多數作業系統的內核用於唯一標識行程的一個數值。這一數值可以作為許多函式呼叫的參數，以使調整行程優先級、殺死行程之類的行程控制行為成為可能。 – 維基百科

Fork: 是一個system call，讓行程呼叫出子行程，稱為child process，它的內存的內容與原行程（parent process）相同。
- fork在父和子都會返回值
- fork函數在父行程return pid，在子行程return 0











int pid = fork(); //創建process
if(pid > 0){
printf("parent: child=%d\n", pid); //執行fork函式並返回子行程的pid 
pid = wait(); // 返回一個當前行程中已退出的子行程
printf("child %d is done\n", pid);
} else if(pid == 0){
printf("child: exiting\n");
exit();
} else {
printf("fork error\n");
}

輸出為：
1234為pid,並執行子行程的fork()

parent: child=1234

此時執行子行程的fork() , pid為0，執行exit()

child: exiting

由於exit()被執行，子行程退出，wait()函式執行完畢並輸出下一行。

parent: child 1234 is done

由上面程式碼可知，改變一個行程的變量並不會影響另一個行程。

系統調用exec
- 需要兩個參數：可執行的文件名、字符串的陣列
- 執行成功後並不會返回到原來的程式，而是執行文件中加載的指令。

以下是exec的範例程式，這段程式將調用程式更改為/bin/echo，echo hello 為/bin/echo的參數：






char *argv[3];
argv[0] = "echo";
argv[1] = "hello";
argv[2] = 0;
exec("/bin/echo", argv);
printf("exec error\n");

xv6的shell使用以上的system call來執行程式，以下是shell中的main的運作流程（參考第8700~8728行）

I/O and File descriptors

file descriptor（文件描述符）
- 是一個整數
- 代表被kernal管理且可以被讀寫的物件
- 我們常把這個物件叫做文件（file)

xv6 中，每個process都有一張對應的表，kernal會根據file descriptor來當作這張表的索引，0為input，1為輸出2為輸出錯誤，由下列程式碼可知，shell 保證在任何時候都有3個打開的文件描述符







8706 // Ensure that three file descriptors are open.
8707 while((fd = open("console", O_RDWR)) >= 0){
8708 if(fd >= 3){
8709 close(fd);
8710 break;
8711 }
8712 }

Read and Write
read 和 write會從文件描述符所指的文件中讀或者寫 n 個字節。



read(fd, buf, n)
//從fd中至多讀出n個字節，再拷貝到buf中，返回讀出的字符數量。
//當没有資料可讀時，read 就會返回0，這就表示文件结束了。


write(fd, buf, n)
//寫入buf中的n個字節到fd中， 並且返回實際寫出的字節數量。

以下這段程式碼，類似實現cat的功能，將資料從輸入複製到輸出，若遇到了錯誤則會在標準輸出中印出錯誤訊息。
















char buf[512];
int n;

for(;;){
    n = read(0, buf, sizeof buf);//0為標準輸入
    if(n == 0)
        break;
    if(n < 0){
        fprintf(2, "read error\n");
        exit();
    }
    if(write(1, buf, n) != n){//1為標準輸出
        fprintf(2, "write error\n");
        exit();
    }
}

Close
這個system call釋放了file descripter的空間，讓他可以被open , pipe , dup等調用。
Cat
透過fork和file descripter的交互使用，我們就可以重新定址I/O
下面是一個簡化版的shell執行 cat<input.txt 的代碼








char *argv[2];
argv[0] = "cat";
### argv[1] = 0;
if(fork() == 0) {//進入子行程
    close(0);//關閉fd 0
    open("input.txt", O_RDONLY);//使用0作為新打開的文件
    exec("cat", argv);//cat在標準輸入中執行
}

dup
dup這個指令是複製出一個已有的描述符，返回一個指向同一個輸入/輸出的新物件描述符，他會共享一個文件的偏移量（offset）

Pipes

pipes是一個小型的kernal緩衝區，以一對的文件描述符來提供給process使用，一個用於寫操作，一個用於讀取操作，pipes提供了一種process之間交互溝通的方式。




















int p[2];//1代表讀端口 2代表寫端口
char *argv[2];
argv[0] = "wc";
argv[1] = 0;
pipe(p); //創造一個pipe
if(fork() == 0) {//進入子行程
//fork之後父行程和子行程都有了指向管道的文件描述符。
close(0);//子行程關閉了0這個描述符
dup(p[0]);//子行程將管道的讀端口拷貝在描述符0上
//關閉 p 中的描述符
close(p[0]);
close(p[1]);
exec("/bin/wc", argv);//執行wc程式
//當wc從標準輸入讀取時，它實際上是從管道讀取的。
} else {
//父行程向管道的寫端口（１）寫入然後關閉它的兩個文件描述符。
close(p[0]);
write(p[1], "hello world\n", 12);
close(p[1]);
}

Pipes的好處：
1. 管道會進行自我清掃，如果是shell重定向的話，我們必須要在任務完成後刪除/tmp/xyz
2. 管道可以傳輸任意長度的數據。
3. 管道允許同步：兩個行程可以使用一對管道來進行二者之間的信息傳遞，每一個讀操作都阻塞調用行程，直到另一個行程用write完成數據的發送。

File system

xv6擁有文件系統，包含文件與目錄，目錄是一種特殊文件root，像是一棵樹，例如:/a/b/c，c是b目錄裡的文件，b又是a目錄裡的文件。

通過chdir這個系統的調用指令，可以改變當前的目錄




chdir("/a");//將當前目錄切換到/a/b
chdir("b");//對當前目錄不做任何改變
open("c", O_RDONLY);
open("/a/b/c", O_RDONLY);

mkdir這個指令可以創建一個新的目錄
open加上O_CREATE標誌打開一個新的文件
mknod創建一個新的設備文件




mkdir("/dir");
fd = open("/dir/file", O_CREATE|O_WRONLY);
close(fd);
mknod("/console", 1, 1);

fstat
獲取一個文件描述符指向的文件的信息。
int fstat(int fildes, struct stat *buf);
fstat()用來將參數fildes所指的文件狀態,複製到參數buf所指的結構中(struct stat).
結構：

#define T_DIR  1
#define T_FILE 2
#define T_DEV  3
// Directory
// File
// Device
     struct stat {
       short type;  // 文件的型態
       int dev;     // File system’s disk device
       uint ino;    // Inode number
       short nlink; // Number of links to file
       uint size;   // Size of file in bytes
};

一個文件inode可能有許多不同的名字，稱為link(連結)，link這個指令可以創建另一個文件系統的名稱，指向同一個inode。
下面的代碼創建了一個既叫做a又叫做b的新文件。

open("a", O_CREATE|O_WRONGLY);
link("a", "b");

讀寫a等同於讀寫b。在上面這段代碼中，我們可以通過fstat知道a和b都指向同樣的內容：a和b都會返回同樣的inode號碼（ino），並且nlink數會設置為2。

unlink
系統調用unlink從文件系統移除一個文件名。
一個文件的inode和磁盤空間只有當它的link數變為0的時候才會被清空，也就是沒有一個文件再指向它。因此在上面的代碼最後加上


unlink("a")

我們依然可以用b來訪問它。
另外，我們可以透過unlink來創造一個臨時的inode，它會在關閉fd或退出時被清空。

fd = open("/tmp/xyz", O_CREATE|O_RDWR);
unlink("/tmp/xyz");

Chapter 1 Operating system organization

作業系統需要支持同時多個程序運行，且每個程序運行時，若一個出現bug或異常，也不影響其他的程序，此稱為isolation，想要滿足isolation需要以下三個條件：multiplexing, isolation, 和interaction。
本章主要是介紹作業系統如何達到這三個條件。我們必須去trace當xv6開始運行後的第一個程式，我們得以一窺 xv6 提供的各個抽象概念是如何實現和互相運作的。

isolation
time-share
monolithic kernel

Abstracting physical resources

為什麼我們需要抽象化實際的資源呢？因為如果每個程序都直接跟實際的硬體進行交互，每個程序都必須沒有bug，且知道什麼時候需要釋放佔有的資源，如此一來其他程序才可以運作，但這樣是非常麻煩的，因此我們需要抽象化物理的資源並提供特定服務，讓程序無法直接access硬體資源，而是透過系統提供的指令服務來操作，這樣作業系統也能管理硬碟。

User mode, kernel mode, and system calls

如果一個程式出錯，我們不希望作業系統因此而掛掉，作業系統應該清理此錯誤程式，並繼續運行，所以應用程式不應該有權限去修改系統的資料結構或指令。

為了避免一個使用者的程式修改其他使用者的程式甚至是系統核心，並且更進一步，讓作業系統可以壟斷所有的硬體資源，大部分的機器(或者 CPU)至少會有二個執行特權(privilege)：Kernel mode 與 User mode。

kernel mode
- 可以直接操縱所有的硬體
- 可以存取所有的實體記憶體位址、處理鍵盤中斷
user mode
- 所有存取記憶體的行為都會有邊界檢查

流程：

當電腦的應用程式要執行特殊指令時（read,write,exec…），是在user mode中運行處理器並不會直接運行此指令
轉換到kernal mode
kernal檢視此指令是否可以執行
執行或拒絕

Kernel organization

整合式核心 Monolithic kernel

整合式核心、單體式核心，一種作業系統核心架構，此架構的特性是整個核心程式是一個單一二進位執行檔，在核心空間以監管者模式（Supervisor Mode）來執行。

Microkernel

將OS kernel的眾多模組中，移除一些較非必要的模組，給予system library(software) or user program來製作提供，如此可得到具有較少模組數的kernel。故核心的架構相對簡單。

從下圖可知，當shell需要執行read或write指令時，它會透過kernal發訊息給file server，大部分的system service是在user mode執行，所以一旦service fail，亦不會對系統造成影響。

Process overview（行程）

process abstraction

防止一個process去存取另一個process的memory，並且向程序提供“看起來”私有的，其他行程無法讀寫的內存系統（或地址空間），以及一顆“看上去”僅執行該程序的CPU。
Xv6使用page table來為每個process提供其獨有的地址空間。

頁表將虛擬地址（x86 指令所使用的地址）映射為物理地址。

一區地址空間包含了從虛擬地址0開始的用戶內存。它的地址最低處放置process的指令，接下來則是全局變量，堆區，以及一個用戶可按需拓展的“堆”區（malloc 用）。
內核的指令和資料也會被行程映射到每個行程的地址空間中。當行程使用系統調用時，系統調用實際上會在行程地址空間中的內核區域執行。這種設計使得內核的系統調用程式可以直接指向用戶內存。為了給用戶留下足夠的內存空間，xv6 將內核映射到了地址空間的高地址處，即從 0x80100000 開始。0~0x80000000是用戶可以使用的地址

xv6 使用結構 struct proc 來維護一個行程的狀態，其中最為重要的狀態是進程的頁表，內核棧，當前運行狀態。我們接下來會用 p->xxx 來指代 proc 結構中的元素。

Thread

執行緒（英語：thread）是作業系統能夠進行運算排程的最小單位。它被包含在行程之中，是行程中的實際運作單位。一條執行緒指的是行程中一個單一順序的控制流，一個行程中可以並行多個執行緒，每條執行緒並列執行不同的任務。

每個行程都有一個運行執行緒來執行行程的指令。執行緒可以被暫時停止，稍後再恢覆運行。

系統在行程之間切換實際上就是掛起當前運行的執行緒，恢覆另一個行程的執行緒。執行緒的大多數狀態（局部變量和函數調用的返回地址）都保存在線程的stack上。

Stack

每個進程都有用戶堆和內核堆（p->kstack）。當行程運行用戶指令時，只有其用戶堆被使用，其內核堆則是空的。然而當行程（通過系統調用或中斷）進入內核時，內核代碼就在行程的內核堆中執行；
行程處於內核中時，其用戶堆仍然保存著數據，只是暫時處於不活躍狀態。進程的線程交替地使用著用戶堆和內核堆。要註意內核堆是用戶代碼無法使用的，這樣即使一個進程破壞了自己的用戶堆，內核也能保持運行。

當行程使用系統調用時，處理器轉入內核堆中，提升硬件的特權級，然後運行系統調用對應的內核代碼。
當系統調用完成時，又從內核空間回到用戶空間：降低硬件特權級，轉入用戶堆，恢覆執行系統調用指令後面的那條用戶指令。執行緒可以在內核中“阻塞”，等待 I/O, 在 I/O 結束後再恢覆運行。

p->state 指示了行程的狀態：新建、準備運行、運行、等待 I/O 或退出狀態中。
p->pgdir 保存了行程的page table。

Code: the first address space

當 PC 開機時，它會初始化然後從磁盤中載入 boot loader 到內存並運行。boot loader 把 xv6 內核從磁盤中載入並從 entry（1040）開始運行。x86 的分頁硬體在此時還沒有開始工作；所以這時的虛擬地址是直接映射到物理地址上的。



























1042 # Entering xv6 on boot processor, with paging off.
1043 .globl entry
1044 entry:
1045 # Turn on page size extension for 4Mbyte pages
1046 movl %cr4, %eax
1047 orl $(CR4_PSE), %eax
1048 movl %eax, %cr4
1049 # 設置頁表page table,將 0x80000000（稱為 KERNBASE（0207））開始的虛擬地址映射到物理地址 0x0 處。
1050 movl $(V2P_WO(entrypgdir)), %eax
將entrypgdir的物理位址載入到寄存器cr3
1051 movl %eax, %cr3
1052 # Turn on paging.
1053 movl %cr0, %eax
1054 orl $(CR0_PG|CR0_WP), %eax
1055 movl %eax, %cr0
1056
1057 # Set up the stack pointer.
1058 movl $(stack + KSTACKSIZE), %esp
1059
1060 # Jump to main(), and switch to executing at
1061 # high addresses. The indirect call is needed because
1062 # the assembler produces a PC−relative instruction
1063 # for a direct jump.
1064 mov $main, %eax
1065 jmp *%eax
1066
1067 .comm stack, KSTACKSIZE

Code: creating the first process

main初始化程式後，透過userinit建立了第一個process





















1217 main(void)
1218 {
1219 kinit1(end, P2V(4*1024*1024)); // phys page allocator
1220 kvmalloc(); // kernel page table
1221 mpinit(); // detect other processors
1222 lapicinit(); // interrupt controller
1223 seginit(); // segment descriptors
1224 picinit(); // disable pic
1225 ioapicinit(); // another interrupt controller
1226 consoleinit(); // console hardware
1227 uartinit(); // serial port
1228 pinit(); // process table
1229 tvinit(); // trap vectors
1230 binit(); // buffer cache
1231 fileinit(); // file table
1232 ideinit(); // disk
1233 startothers(); // start other processors
1234 kinit2(P2V(4*1024*1024), P2V(PHYSTOP)); // must come after startothers()
1235 userinit(); // 第一個行程
1236 mpmain(); // finish this processor’s setup
1237 }

allocproc的工作是在頁表中分配一個槽（即結構體 struct proc），並初始化行程的狀態，為其內核執行緒的運行做準備。

p = allocproc();

注意：userinit 僅僅在創建第一個行程時被調用，而 allocproc 創建每個行程時都會被調用。

allocproc 會在 proc 的表中找到一個標記為 UNUSED的槽位。當它找到這樣一個未被使用的槽位後，allocproc 將其狀態設置為 EMBRYO，使其被標記為被使用的並給這個進程一個獨有的 pid。接下來，它嘗試為行程的kernal的執行緒分配內核堆。如果分配失敗了，allocproc 會把這個槽位的狀態恢覆為 UNUSED 並返回0以標記失敗。

kernal的執行緒會從 p->context 中拷貝的內容開始運行。通過將 p->context->eip 指向 forkret 從而讓kernal的執行緒從 forkret的開頭開始運行。
這個函數會返回到那個時刻棧底的地址。context switch的程式把堆指針指向 p->context 結尾。allocproc 又將 p->context 放在棧上，並在其上方放一個指向 trapret 的指針；這樣運行完的 forkret 就會返回到 trapret 中了。 trapret 接著從堆的頂部恢覆用戶寄存器然後跳轉到 process的程式。
一旦進程初始化完畢，userinit 將 p->state 設置為 RUNNABLE，使行程能夠被調度。

Code: Running the first process

Scheduler 找到為一個 p->state 為 RUNNABLE 的行程 initproc，然後將 per-cpu 的變量 proc 為該行程，接著調用 switchuvm 通知硬體開始使用目標進程的頁表。
scheduler接著把進程的p->state設置為RUNNING，調用swtch。

swtch會保存當前的寄存器，並把目標內核線程中保存的寄存器（proc->context）載入到x86的硬件寄存器中

allocproc通過把initproc的p->context->eip設置為forkret使得ret開始執行forkret的代碼。

The first system call: exec

initcode.S觸發exec系統調用，用一個新的程序來代替當前行程的內存和寄存器，但是其文件描述符、行程id和父行程都是不變的。

initcode.S剛開始會將 $argv，$ init，$0三個值推入堆中
將%eax設置為SYS_exec
執行int T_SYSCALL
如果運行正常的話，exec不會返回：它會運行名為$init的程序
如果exec失敗並且返回了，initcode會不斷調用一個不會返回的系統調用exit

作業系統作業一 - 項目三 Chapter 5 Scheduling

Scheduling 排程

由於一個作業系統可能進行的process比電腦本身的processor多很多，所以我們必須time-share 我們的處理器。常見的方法是透過mutiplexing（多工）將單獨的一個物理處理器模擬為多個虛擬處理器。

Multiplexing 多工

Xv6在下列兩種狀況時，會switch從一個process到另一個process。

sleep and wakeup 機制轉換

當一個process等待I/O請求或等待子行程exit時，xv6使之進入睡眠狀態，然後調度執行另一個process。

週期性中斷

當一個process耗盡了它在處理器上運行的時間片（100毫秒）後，xv6使用週期性中斷強制它停止運行，這樣排程器才能調度運行其他行程。

Code : Context switching

程式流程

swtch一開始從堆中彈出參數，放入寄存器%eax和%edx中；
swtch壓入寄存器，在當前棧上建立一個新的上下文結構。
%ebp %ebx %esi %ebp %esp寄存器此時被保存。
保存了舊寄存器後，swtch準備恢復新的寄存器。它將指向新上下文的指針放入堆指針中。
新的堆結構和舊的堆相同，因為新的上下文其實是之前某次的切換中的舊上下文。
最後彈出%edi %esi %ebx %ebp然後返回

代碼解釋

3057 .globl swtch
3058 swtch:
//copying its arguments from the stack to the caller-saved registers
3059 movl 4(%esp), %eax //將%esp的4個bit放入%eax
3060 movl 8(%esp), %edx //將%esp的8個bit放入%edx
3061 //pushes the registerstate, creating a context structure on the current stack
3062 # Save old callee−save registers
3063 pushl %ebp
3064 pushl %ebx
3065 pushl %esi
3066 pushl %edi
3067//交換堆的內容
3068 # Switch stacks
3069 movl %esp, (%eax)
3070 movl %edx, %esp
3071//移出%edi %esi %ebx %ebp
3072 # Load new callee−save registers
3073 popl %edi
3074 popl %esi
3075 popl %ebx
3076 popl %ebp
3077 ret

資料結構







2326 struct context {
2327 uint edi;//定義無符號的int
2328 uint esi;
2329 uint ebx;
2330 uint ebp;
2331 uint eip;
2332 };

Code: Scheduling

程式流程

代碼解析






































 scheduler(void)
2759 {
2760 struct proc *p;
2761 struct cpu *c = mycpu();
2762 c−>proc = 0;
2763
2764 for(;;){
2765 // 開啟中斷
2766 sti();
2767
2768 // 循環去尋找可以run的process
2769 acquire(&ptable.lock);
2770 for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
2771 if(p−>state != RUNNABLE)//在process table找尋p->state==RUNNABLE的進程
2772 continue;
2773
2774 // Switch to chosen process. It is the process’s job
2775 // to release ptable.lock and then reacquire it
2776 // before jumping back to us.
//將per-cpu的當前進程變量proc設為該進程
2777 c−>proc = p;
//用switchuvm切換到該進程的頁表，標記該進程為RUNNING，
2778 switchuvm(p);
2779 p−>state = RUNNING;
2780
//調用swtch切換到該進程中運行
2781 swtch(&(c−>scheduler), p−>context);
2782 switchkvm();
2783
2784 // Process is done running for now.
2785 // It should have changed its p−>state before coming back.
2786 c−>proc = 0;
2787 }
//釋放此進程持有的其他鎖
2788 release(&ptable.lock);
2789
2790 }
2791 }

資料結構















2337 struct proc {
2338 uint sz; // process memory (bytes) 大小
2339 pde_t* pgdir; // Page table
2340 char *kstack; // Bottom of kernel stack for this process
2341 enum procstate state; // Process state
2342 int pid; // Process ID
2343 struct proc *parent; // connect with Parent process
2344 struct trapframe *tf; // Trap frame for current syscall
2345 struct context *context; // 暫存器
2346 void *chan; // 若為非零，則為sleeping
2347 int killed; // 若不為零，則為被殺掉了
2348 struct file *ofile[NOFILE]; // Open files
2349 struct inode *cwd; // Current directory
2350 char name[16]; // Process name (debugging)
2351 };

Code: mycpu and myproc

程式流程

代碼解釋
















2437 mycpu(void)
2438 {
2439 int apicid, i;
2440
2441 if(readeflags()&FL_IF)
2442 panic("mycpu called with interrupts enabled\n");
2443
2444 apicid = lapicid();//lapicid 回傳這個processor的硬體識別碼
2445 // APIC IDs are not guaranteed to be contiguous. Maybe we should have
2446 // a reverse map, or reserve a register to store &cpus[i].
2447 for (i = 0; i < ncpu; ++i) {
2448 if (cpus[i].apicid == apicid)
2449 return &cpus[i];
2450 }
2451 panic("unknown apicid\n");
2452 }

資料結構











2456 struct proc*
2457 myproc(void) {
2458 struct cpu *c;
2459 struct proc *p;
2460 pushcli();
2461 c = mycpu();//invokes mycpu to find its processor’s state
2462 p = c−>proc;//When aprocessor switches to a new process in 
// scheduler, it sets proc to that process’s struct proc.
2463 popcli();
2464 return p;
2465 }

Sleep & Wakeup

運作原理

睡眠和喚醒實際上提供了進程間通信的機制，它們可以讓一個進程暫時休眠，等待某個特定事件的發生，然後當特定事件發生時，另一個進程會喚醒該進程。
睡眠與喚醒通常被稱為順序合作（sequence coordination）或者有條件同步（conditional synchronization）機制。






















struct q {
    void *ptr;
};
//send會不斷循環，直到隊列為空（ptr == 0），然後將指針p放到隊列中。
void*
send(struct q *q, void *p)
{
    while(q->ptr != 0)
        ;
    q->ptr = p;
}
//recv會不斷循環，直到隊列非空然後取出指針。
void*
recv(struct q * q)
{
    void *p;
    while((p = q->ptr) == 0)
        ;
    q->ptr = 0;
    return p;
}

send和recv會同時修改q->ptr，不過send只在隊列空時寫入指針，而recv只在隊列非空時拿出指針，這樣他們之間是不會互相干擾的。

上面這種實現方法正確，但是代價是巨大的。如果發送者很少發送，那麼接受者就會消耗大量的時間在while循環中等待一個指針的出現。而實際上如果有一種方法使得send放入指針時，能夠通知接受者。那麼接受者所在的CPU就能在這段時間找到更有意義的事情做。

調用sleep和wakeup，其工作方式如下。


















void*
send(struct q *q, void *p)
{
    while(q->ptr != 0)
        ;
    q->ptr = p;
    wakeup(q);    /*wake recv*/
}

void*
recv(struct q *q)
{
    void *p;
    while((p = q->ptr) == 0)
        sleep(q);
    q->ptr = 0;
    return p;
}

sleep(chan)讓進程在任意的chan上休眠，稱之為等待隊列（wait channel）。sleep讓調用進程休眠，釋放所佔CPU。
wakeup(chan)則喚醒在chan上休眠的所有進程，讓他們的sleep調用返回。

現在recv能夠讓出CPU而不是空等浪費資源了。但對於圖表5-2中出現的“遺失的喚醒”問題，我們卻很難通過已有的介面下，設計出能夠避免該問題的sleep和wakeup機制。
假設在第215行recv發現q->ptr == 0，然後決定調用sleep，但是在recv調用sleep之前，send又在另一個CPU上運行了，它將q->ptr置為非零，然後調用wakeup，發現沒有進程在休眠，於是什麼也沒有做。
接著，recv從第216行繼續執行了：它調用sleep進入休眠。這就出現問題了，休眠的recv實際上在等待一個已經到達的指針。而下一個send又在睡眠中等著recv取出隊列中的指針。這種情況就被稱為死鎖（deadlock）。

想要解決問題，我們必須要改變sleep的interface。sleep必須將鎖作為一個參數，然後在進入睡眠狀態後釋放之。
這樣就能避免上面提到的“遺失的喚醒”問題。一旦進程被喚醒了，sleep在返回之前還需要重新獲得鎖。於是我們應該使用下面的代碼：





























struct q {
    struct spinlock lock;
    void *ptr;
};

void *
send(struct q *q, void *p)
{
    acquire(&q->lock);
    while(q->ptr != 0)
        ;
    q->ptr = p;
    wakeup(q);
    release(&q->lock);
}
//recv持有q->lock就能防止send在recv檢查q->ptr與調用sleep之間調用wakeup。
void*
recv(struct q *q)
{
    void *p;
    acquire(&q->lock);
    //sleep釋放q->lock並讓接收進程進入休眠狀態。
    while((p = q->ptr) == 0)
        sleep(q, &q->lock);
    q->ptr = 0;
    release(&q->lock;
    return p;
}

程式流程

代碼解釋

Sleep







































2874 sleep(void *chan, struct spinlock *lk)
2875 {
2876 struct proc *p = myproc();
2877
//必須存在當前進程
2878 if(p == 0)
2879 panic("sleep");
2880
//sleep必須持有鎖
2881 if(lk == 0)
2882 panic("sleep without lk");
2883
2884 // Must acquire ptable.lock in order to
2885 // change p−>state and then call sched.
2886 // Once we hold ptable.lock, we can be
2887 // guaranteed that we won’t miss any wakeup
2888 // (wakeup runs with ptable.lock locked),
2889 // so it’s okay to release lk.
//sleep要求持有ptable.lock
2890 if(lk != &ptable.lock){
2891 acquire(&ptable.lock);
2892 release(lk);
2893 }
2894 // Go to sleep.
2895 p−>chan = chan;
2896 p−>state = SLEEPING;
2897
2898 sched();
2899 
2900 // Tidy up.
2901 p−>chan = 0;
2902
//有了ptable.lock，那麼它現在就能安全地釋放lk了
2903 // Reacquire original lock.
2904 if(lk != &ptable.lock){
2905 release(&ptable.lock);
2906 acquire(lk);
2907 }
2908 }

Wake up






















2950 // Wake up all processes sleeping on chan.
2951 // The ptable lock must be held.
2952 static void
2953 wakeup1(void *chan)
2954 {
2955 struct proc *p;
2956
2957 for(p = ptable.proc; p < &ptable.proc[NPROC]; p++)
//當wakeup找到了對應chan中處於SLEEPING的進程時，它將進程狀態修改為RUNNABLE
2958 if(p−>state == SLEEPING && p−>chan == chan)
2959 p−>state = RUNNABLE;
2960 }
2961
2962 // Wake up all processes sleeping on chan.
2963 void
2964 wakeup(void *chan)
2965 {
//要求獲得ptable.lock並調用wakeup1
2966 acquire(&ptable.lock);
2967 wakeup1(chan);
2968 release(&ptable.lock);
2969 }

Code: Pipes

運作原理

管道的一端寫入數據字節，然後數據被拷貝到內核緩衝區中，接著就能從管道的另一端讀取數據。

每個管道由一個結構體struct pipe表示，
其中有一個鎖lock和內存緩衝區。
nread和nwrite表示從緩衝區讀出和寫入的字節數。
pipe對緩衝區做了包裝，使計數器繼續增長，但實際上在buf[PIPESIZE - 1]之後寫入的字節存放在buf[0]。這樣就讓我們可以區分一個滿的緩衝區（nwrite == nread + PIPESIZE）和一個空的緩衝區（nwrite == nread），但這也意味著我們必須使用buf[nread % PIPESIZE]而不是buf[nread]來讀出/寫入數據。

程式流程

代碼解釋（Pipewrite和piperead）

Piperead























6851 piperead(struct pipe *p, char *addr, int n)
6852 {
6853 int i;
6854
6855 acquire(&p−>lock);//請求獲得鎖
6856 while(p−>nread == p−>nwrite && p−>writeopen){
6857 if(myproc()−>killed){
6858 release(&p−>lock);
6859 return −1;
6860 }
6861 sleep(&p−>nread, &p−>lock);
6862 }
6863 for(i = 0; i < n; i++){
6864 if(p−>nread == p−>nwrite)
6865 break;
//依次寫入addr[0], addr[1], ..., addr[n-1]並添加到管道中
6866 addr[i] = p−>data[p−>nread++ % PIPESIZE];
6867 }
6868 wakeup(&p−>nwrite);
6869 release(&p−>lock);
6870 return i;
6871 }

Pipewrite





















6829 int
6830 pipewrite(struct pipe *p, char *addr, int n)
6831 {
6832 int i;
6833 //請求獲得管道的鎖
6834 acquire(&p−>lock);
6835 for(i = 0; i < n; i++){
6836 while(p−>nwrite == p−>nread + PIPESIZE){
6837 if(p−>readopen == 0 || myproc()−>killed){
6838 release(&p−>lock);
6839 return −1;
6840 }
6841 wakeup(&p−>nread);
6842 sleep(&p−>nwrite, &p−>lock);
6843 }
6844 p−>data[p−>nwrite++ % PIPESIZE] = addr[i];
6845 }
6846 wakeup(&p−>nread);
6847 release(&p−>lock);
6848 return n;
6849 }

資料結構









6762 struct pipe {
6763 struct spinlock lock;//鎖
6764 char data[PIPESIZE];//內存緩衝區
//nread&nwrite表示從緩衝區讀出和寫入的字節數。
6765 uint nread; // number of bytes read
6766 uint nwrite; // number of bytes written
6767 int readopen; // read fd is still open
6768 int writeopen; // write fd is still open
6769 };

Code: Wait, exit, and kill

代碼解析＆程式流程

Wait









































2671 wait(void)
2672 {
2673 struct proc *p;
2674 int havekids, pid;
2675 struct proc *curproc = myproc();
2676
2677 acquire(&ptable.lock);
2678 for(;;){
2679 // 查看進程表中是否有子進程
2680 havekids = 0;
2681 for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
2682 if(p−>parent != curproc)
2683 continue;
2684 havekids = 1;
2685 if(p−>state == ZOMBIE){
2686 // Found one.
2687 pid = p−>pid;
2688 kfree(p−>kstack);
2689 p−>kstack = 0;
2690 freevm(p−>pgdir);
2691 p−>pid = 0;
2692 p−>parent = 0;
2693 p−>name[0] = 0;
2694 p−>killed = 0;
2695 p−>state = UNUSED;
2696 release(&ptable.lock);
2697 return pid;
2698 }
2699 }
2700 // No point waiting if we don’t have any children.
2701 if(!havekids || curproc−>killed){
2702 release(&ptable.lock);
2703 return −1;
2704 }
2705
2706 // Wait for children to exit. (See wakeup1 call in proc_exit.)
//調用sleep等待其中一個子進程退出
//這裡sleep中釋放的鎖是ptable.lock
2707 sleep(curproc, &ptable.lock);
2708 }
2709 }

Exit

exit讓一個應用程序可以自我終結



























2627 exit(void)
2628 {
2629 struct proc *curproc = myproc();
2630 struct proc *p;
2631 int fd;
2632
2648 //獲得ptable.lock
2649 acquire(&ptable.lock);
2650 // Parent might be sleeping in wait().
//喚醒當前進程的父進程
2651 wakeup1(curproc−>parent);
2652
2653 // exit把所有子進程交給initproc
2654 for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
2655 if(p−>parent == curproc){
2656 p−>parent = initproc;
2657 if(p−>state == ZOMBIE)
2658 wakeup1(initproc);
2659 }
2660 }
2661
// exit調用sched來讓出CPU
2662 // Jump into the scheduler, never to return.
2663 curproc−>state = ZOMBIE;
2664 sched();
2665 panic("zombie exit");
2666 }

Kill

kill讓一個應用程序可以終結其他進程。
在實現kill時有兩個困難：
1）被終結的進程可能正在另一個CPU上運行，所以它必須在被終結之前把CPU讓給調度器；
2）被終結的進程可能正在sleep中，並持有內核資源。

kill很輕鬆地解決了這兩個難題：它在進程表中設置被終結的進程的p->killed，如果這個進程在睡眠中則喚醒之。如果被終結的進程正在另一個處理器上運行，它總會通過系統調用或者中斷（例如時鐘中斷）進入內核。
當它離開內核時，trap會檢查它的p->killed，如果被設置了，該進程就會調用exit，終結自己。


















2975 kill(int pid)
2976 {
2977 struct proc *p;
2978
2979 acquire(&ptable.lock);
2980 for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
2981 if(p−>pid == pid){
2982 p−>killed = 1;
2983 // Wake process from sleep if necessary.
2984 if(p−>state == SLEEPING)
2985 p−>state = RUNNABLE;
2986 release(&ptable.lock);
2987 return 0;
2988 }
2989 }
2990 release(&ptable.lock);
2991 return −1;
2992 }

作業系統作業一 - 項目一

B10402113 四電子四乙 鄭和軒

操作流程

一、開啟qemu - gdb

二、開啟另一個終端remote進去

三、設定斷點位址與執行

四、紀錄暫存器的值

作業系統作業一 - 項目二

Chapter 0

Operating system interfaces

本節重點：

Processes and memory

I/O and File descriptors

Pipes

File system

Chapter 1 Operating system organization

Abstracting physical resources

User mode, kernel mode, and system calls

Kernel organization

整合式核心 Monolithic kernel

Microkernel

Process overview（行程）

process abstraction

Thread

Stack

Code: the first address space

Code: creating the first process

Code: Running the first process

The first system call: exec

作業系統作業一 - 項目三 Chapter 5 Scheduling

Scheduling 排程

Multiplexing 多工

sleep and wakeup 機制轉換

週期性中斷

Code : Context switching

程式流程

代碼解釋

資料結構

Code: Scheduling

程式流程

代碼解析

資料結構

Code: mycpu and myproc

程式流程

代碼解釋

資料結構

Sleep & Wakeup

運作原理

程式流程

代碼解釋

Sleep

Wake up

Code: Pipes

運作原理

程式流程

代碼解釋（Pipewrite和piperead）

Piperead

Pipewrite

資料結構

Code: Wait, exit, and kill

代碼解析＆程式流程

Wait

Exit

Kill

B10402113 四電子四乙鄭和軒