Xv6報告

Part.1
eax 0xaa55 43605
ecx 0x0 0
edx 0x80 128
ebx 0x0 0
esp 0x6f2c 0x6f2c

Part.2-Ch0. System Interface

0. 前言

OS的工作主要是協調process與process、user與hardware之間的協調、分配資源
同時，OS也是一個做為process跟hardware之間的溝通介面
當process要求kerenl service時，便向OS介面發system call

在OS裡，kernel用CPU內的hardware protection確保每個process都只用自己的memory

OS中還有另一個部分為Shell，它也是system call的介面之一，但它不是kernel的一環，它會讀取user的command並執行之。

本次使用的作業系統為Xv6，它模擬了Unix的內部環境，而Unix整合性強，使得後來許多OS都沿用之，例如BSD、Lunix、MacOS…等

接下來將開始介紹process之間的溝通方式

1. Outline

  1. Process
  2. I/O & File Descriptor
  3. Pipes
  4. File System

2. 正文

先簡單介紹一下甚麼是process：
process指的是每一個正在執行中的program
process分成user space 與 kernel space 兩個分區，其中：

User Space Kernel Space
包含使用者的指令、
存的變數及堆疊、
分配記憶體(malloc)的heap
會在這裡		 kernel 運作的地方，
在這裡提供一些硬體相關的服務給user

每個process都有各自的kernel 這是為了防止process各自獨立，避免無意間侵犯到其他process運作

2-1. Process & Memory

在Xv6中，CPU空閒時，會往返於待執行的process檢查，
若該process未執行下，Xv6會執行該process的位於CPU中的register中的位置，直到下次他們運行，這種方式稱為time-sharing。

每個process都有各自的process identifier (以下稱為pid)，pid 是用來讓OS辨別不同process的。

Process 中有一個很重要的指令fork()，它能夠讓當下的process再產生出chile process—而產生child process的原process稱為parent process，透過parent產生child的方式，使得process成為樹狀的結構。

fork()所產生的child process會與parent process相同，
但child process傳回的pid會是0。
如果要修改child process 所執行的內容，那就要透過exec()這個system call

exec()會從透過file system從指定路徑中取出file、覆蓋原本執行中的process並執行之，跟fork()結合使用時，便可透過pid不同這個條件，讓child跟parent執行不同的process

2-2. I/O & File Descriptor

File Descriptor是一個整數變數，它負責記錄每個process寫入、讀取的檔案紀錄。

在打開檔案、輸入輸出、或處理process之間的資料傳遞時，都會需要知道檔案路徑，而file descriptor便將這個概念抽象化，把路徑改以一個整數代替，這樣就不需要知道它的細節了

kernel 中會有一個 per-process table 作為 fd 的 index。

在每次啟動process時，一定會有3個附帶的file descriptor(簡稱fd)

相關的call function 是read() 和 write()：

  1. read (fd , buf , n) 指從fd 對應的檔案中，讀取最多n個byte 存入buf中，之後跟fd相關的offset會向後移動讀取的byte量。
  2. 相對的write(fd , buf , f) 指從buf 將讀取最多n byte寫入fd，當然這時fd的offset也會後移n位。


此外也有一些相關的函式也稍微提一下：

  1. close()：會把指定的fd釋放掉，讓接下來open,pipe,dup等system call 可以使用該fd
  2. fork()：parent process會把file descriptor複製給child process好讓他能在同一個檔案底下運行。
    值得一提的是，雖然fork()會生成兩個process，但他們offset仍是共享的，也就是說，就算他們write到同一個fd，後寫的內容將會接在先寫的process的內容後面。下圖是範例：

  1. exec()：雖然exec()把原本的process替換了，但原process的pid仍會保留在table上，如此一來，shell可以藉fork再打開原本的檔案
  2. dup(fd)會把file descriptor複製到某變數，而且這情形下offset也是共用的。

2-3. Pipes

pipes是在kernel內中的buffer，有一對file descriptor，一個用來讀、一個用來寫
而process之間可以透過pipes溝通

例如將pipes的write端設為stdout、read端設為stdin
那就可以把前一個process寫至stdout的資料，透過pipes讓下一個process讀至stdin

2-4. File System

File System 顧名思義，就是提供檔案資料、以及路徑的系統。

xv6下的路徑類似樹狀結構：從根目錄(root)出發
例如：/a/b/c 中 第一個 " / " 就是根目錄
也就是打開「根目錄中的a，a中的b，b中的檔案c」

以下是File system相關的指令:

  1. chdir:更改當前路徑
  2. mkdir:make directory，做新路徑
  3. mknod:建立裝置文件(這與驅動裝置有關)
  4. open:打開檔案，其中又有分方式:
  1. fstat()：取得file descriptor對應的檔案的資訊。包含：







struct stat {
short type; // Type of file
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 number，對於兩個不同名稱的file，若其底層的inode number相同，那就是相同的file。
我們可以透過link(檔案名,檔案名)來達到這件事，例如





open("a", O_CREATE|O_WRONLY);
link("a", "b");
fstat("a")
fstat("b") // 會發現a和b的inode數相同

這時候修改a便是在修改b，而該inode number對應檔案的link數也會變成2

  1. ulink()：把該名字移除，但只要inode number對應檔案的link數不是0，內容就會一直保存

Part.2-Ch1. System Organization

前言

作為一個好的OS，應該要

  1. 可以同時多工；這點透過fork及CPU的time-sharing 達成了
  2. 非相關的process互相獨立：避免在process出現bug甚至是failed時，會使非相關的process一起failed，造成系統崩潰
  3. process之間要能夠溝通：顧及isolation之餘，還是要讓相關process能互相溝通

正文

Abstrating Physical Resource

每個Application用自己定義的library及本機的library來執行system call，進而跟硬體資源溝通。
但是每個application都要搶processor，且都想要獨立運作，就像搶健身器材一樣，想要能自己一個人用，且獨佔時間越長越好。

所以OS就設計「禁止application直接access 硬體」
例如：Application要從硬體拿檔案，就要對kernel下open、read、write、close等system call，file system再對硬體進行操作。
這還有一個好處就是，讓操作application者只要輸入指令及檔案路徑即可，而不需要去了解其中取用的流程，讓OS去決定便可。

許多互動也透過file descriptor去達成，因為fd把路徑位置抽象化，讓互動方式更加簡化。

User Mode,Kernel Mode & System Call

為了加強獨立性，Application必須OS分清界線，才不會在application failed時牽連到OS，此時OS也必須把failed application清空接著執行其它application。

Processor分成2種方式來執行命令：

Processor 在切換成 kernel mode時，會從kernel定義的entry point進入kernel，同時kernel會開始檢查system call的參數是否合法並決定是否執行之，以此防止惡意程式執行。

Kernel Organization

這邊說的主要是OS的那些程式應該在kernel mode 下運行?
以下提及2種OS設計

  1. Monolithic Kernel:整個OS都在kernel，
    這樣一來，所有system call都在kernel mode 下運行。
    這樣的好處是，user 不須去分辨哪個部份需要特權、kernel 中的資源也可以兼用、OS 中每個部份也容易合作。
    缺點就是分界不明顯，只要OS 裡有任一部分掛掉，整個OS 都會掛掉。
  2. Micro kernel:盡量把kernel mode的code減少、簡化—只剩下啟動程式、傳送訊息、操作hardware等基本功能，把大多功能設在user mode 上，每個OS的成員要其他成員的服務時，就透過傳送message 給micro kernel，由kernel 去協調。

Process

xv6中每個獨立運作的單元皆稱為process。

OS中 把process 抽象化可以避免process妨礙或駭入其他非相關的process。
此外process抽象化也可以讓program認為它自己在屬於自己的機器上工作，有屬於自己的memory space 及 CPU 來執行program的指令。

xv6用page table把physical address(process實際操作的位置)轉換成virtual address(program認為它可操作的位置)

如上圖，連kernel也會一同map到virtual address，這樣的好處是執行system call時，可以直接參照process在user 端存的變數。

process通常都有兩個stack：user stack及kernel stack

Process中有thread來執行process 的instruction。
例如一個email程式，送信與收信都是不同的thread。
thread可隨時暫停，並切換至其它thread執行，在被暫停時，會把當前資料(如local variable、return address)存入thread stack。

開機之後

在電腦開機之後，boot loader會從disk把kernel存入實體記憶體0x100000，之所以不像上面process那樣存在0x80000000(kernel通常定義的entry point)是因為考量到裝置的記憶體大小可能沒那麼大。
不是從0開始存入是因為0xa0000~0x100000存的是I/O

開機的同時，硬體便會設置好page table作為virtual address及physical address間的轉換。

kernel的轉換便是將0:0x40000map至0x80000000:0x80000000+0x40000

再來entry便會轉移至kernel的C code部分，開始建立kernel stack及stack pointer %esp等指標

創造process

xv6的amin function會在初始化之後，call userinit()function製作第一個process，userinit()會call allocproc尋找process table上有無空間：

若有：則將該空間從UNUSED改成EMBRYO，並給process自己的pid
接著allocproc會把kernel stack 分配至 process的kernel thread，如果失敗了，會再將空間改回UNUSED

kernel stack 建完後，allocproc也寫入process中方便往後的fork()

Part3- File System

xv6的file system時做成一共有7個layer的結構，

接下來會從底層一一開始介紹：

1. Disk:

這層會讀寫IDE硬碟上的blocks

2. buffer cache layer：負責兩個工作：


2-1. 同步化對disk的access block確保一次只有一個block複製到memory且只有一個kernel thread使用之。
2-2. 常用的block會存在cache，才不用每次都到disk拿導致浪費時間。

buffer cache的資料結構是一個雙向的linked list，以一個buf型態的bcache的head串聯一個固定大小的陣列buf[NBUF]，所有access便只會透過bcache的head而非裡面的buf陣列。












struct buf {
 int flags;
 uint dev;
 uint blockno;
 struct sleeplock lock;
 uint refcnt;
 struct buf *prev; // linked list
 struct buf *next;
 struct buf *qnext; // disk queue
 uchar data[BSIZE];
 };

每個buffer都有兩種狀態：
1. B_VALID:代表它從硬碟中讀取出來，未經過修改
2. B_DIRTY:代表它修改過了，需要被寫入硬碟中

每個buffer都有一個sleeping lock對應之，確保只有1個thread 使用之

以下是buffer cache的一些code：
bread()會先由bget()去檢查buffer是否有指定的block number了，若沒有將會用iderw()去讀寫指定的block。
bget()會在device下去找是否有紀錄指定的blockno.的buf，若是找到了，bget會索要該buffer的sleeping lock之後回傳buffer值；若沒有找到，就會找沒有使用且狀態不是B_DIRTY的buffer取代之，若這樣還是沒有找到，那就會傳錯誤訊息了
write()會將buffer調為B_DIRTY告知iderw這時應該是寫入IDE中
當buffer已使用完畢時，便會使用brelse()釋放之，它會把sleeping lock也釋放掉，並把該buffer移動到linked list的最前面(代表它是多久之前被released的) ，這樣一來bget()在從disk取資料時，也會從最前面的buffer存入

3.Logging Layer

要解決的是crash recovery的問題，避免寫disk到一半crash掉導致資料在不穩定的狀態。
原先的解決方法是在crash就留下一個inode或一個分配好的block，但是在重建時，可能會導致kerenl將其分配至另一個file，如此一來，會有兩個file指向同一個block，造成更動不同文件卻導致讀寫相同的block。

xv6透過logging解決這問題，它在disk安排一個log把想要對硬碟執行的敘述都記錄下來，等記完之後，在用commit 這個指令來執行內容，修改硬碟的資料，然後清除disk。

如此一來，只要在reboot時看log是否完整，若是便執行，反之則清除之。
因為log的關係，就算在更新期間遇到crash，要嘛是完全更新，要麼是完全不更新。

為了讓多個process同時執行file system，logging system會把多個process的system call包成一個transaction。而且一次只會發一個transaction，transaction之間不會有system call進行避免有遺漏。

常見的code如下:









begin_op(); // 占用使用權，如果正在寫入log就wait，寫完就會把使用權釋出，

...
bp = bread(...);
bp->data[...] = ...;
log_write(bp);
...
end_op();

其它的code:

log_write()：類似bwrite()
commit_trans():
remove_from_logs():

Inode Layer

Inode可以指在disk上的資料結構—包含檔案大小及block numbers
也可以指記憶體中，對disk裡inode的複本，再加上一些kernel信息

disk 上的inode由struct dinode定義









 struct dinode {
 short type; // File type
 short major; // Major device number (T_DEV only)
 short minor; // Minor device number (T_DEV only)
 short nlink; // Number of links to inode in file system
 uint size; // Size of file (bytes)
 uint addrs[NDIRECT+1]; // Data block addresses
 };

Directory Layer&path

Directory 也類似於file—只是它的inode型態是T_DIR，而其資料是一連串的路徑

File Descriptor

回到file system

file system 一定要先把整個block的分配先決定好：

其中0不會用(因為那是boot)、
block 1稱為superblock，是用來存file system的資料、
block 2開始用來存log，接著是inodes、bit map、然後是data