Operation Systems Homework-1

B10515012 四資工三 葉定豪

Part 1

Part 2

Chapter 0: Operating system interfaces

作業系統

作業系統負責提供硬體的服務與管理、程式與硬體間的溝通(記憶體管理、cpu使用及其他硬體等)
、管理多個程式的資源分配。

Kernel

作業系統的核心程式即為 Kernel，提供一系列 system calls作為與程式溝通的橋梁，這些 system calls 和稱 system interface。

System Calls

下表為 xv6 提供的 sytem calls

System call Description
fork() Create a process
exit() Terminate the current process
wait() Wait for a child process to exit
kill(pid) Terminate process pid
getpid() Return the current process’s pid
sleep(n) Sleep for n clock ticks
exec(filename, *argv) Load a file and execute it
sbrk(n) Grow process’s memory by n bytes
open(filename, flags) Open a file; the flags indicate read/write
read(fd, buf, n) Read n bytes from an open file into buf
write(fd, buf, n) Write n bytes to an open file
close(fd) Release open file fd
dup(fd) Duplicate fd
pipe( p) Create a pipe and return fd’s in p
chdir(dirname) Change the current directory
mkdir(dirname) Create a new directory
mknod(name, major, minor) Create a device file
fstat(fd) Return info about an open file
link(f1, f2) Create another name (f2) for the file f1
unlink(filename) Remove a file

Chapter 1: Operating system organization

作業系統在管理運行中的程式時須滿足以下三點

  1. Multiplexing
  2. Isolation
  3. Interaction

Physical resources

在有程式遇到Bug時，為了讓 kernel等其他程式能繼續運行，程式間需要strong isolation，會將硬體IO等全部交給 kernel來處理，並禁止其他程式Access到底層硬體。

User Mode, Kernel Mode

將程式(Process)標出state(mode)，以及對應的處理層級的system calls，硬體IO的部分是分在kernel mode的 system call裡的，假設有在 user mode的程式想執行這道指令，則會通知 kernel發生錯誤並中止程式。

Kernel organization

Monolithic kernel

monolithic kernel 是全部 System calls 都在 kernel mode上執行的架構。
全部功能都不用切分，硬體IO都隨便system call裡面寫，設計方便，不過內部實作需縝密，否則作業系統自己出bug就難看了。

Microkernel

micro kernel為最小化kernel mode system call 的數量，保持底層硬體使用單純，大部分處理都在 user mode執行。

Process overview

每個程式 isolation的單位稱作 process，process之間無法進行記憶體的access，為達到這種效果，讓每個 process被分配到自己的一塊記憶體，且有自己的虛擬address space，透過 page table 將 process自己的 address space mapping到實體記憶體上。

Thread

thread 為 process中實際運行的部分，kernel可以監控並管理每個 thread進行的狀態。

Part 3

Chapter 4: Locking

Lock的機制旨在多CPU的時候，同一塊存取位置只能有一個CPU access，確保其資料完整性。

Race condition

同一存取位置被多個CPU同時 access，造成資料可能被覆寫，失去其完整性。
為防止這種狀況，會加上 lock(下方 listlock)來註明是否正在被使用。















struct list *list = 0;
struct lock listlock;

void insert(int data)
{
    struct list *l;

    acquire(&listlock);
    l = malloc(sizeof *l);
    l->data = data;
    l->next = list;
    list = l;
    release(&listlock);
}

在 acquire() 及 release()中的區塊叫做 critical section。
進入 critical section前會需要取得 該塊存取空間的 lock使用權。










void acquire(struct spinlock *lk)
{
    for(;;) {
        if(!lk->locked) {
            lk->locked = 1;
            break;
        }
    }
}

acquire的實作中用了一個無限迴圈等待 lock的存取權( lock在可以存取時值為 0 )
可以看出使用完的 lock是必須 release掉的，不然下次要用沒辦法 acquire到，且會產生錯誤。
若多個 CPU同時執行到第4行則也會發生race condition，所以這部分需要使用 atomic step，讓判斷、賦值一氣呵成。
上述的 lock即為 spinlock的機制。
#atomic step 使用的是xchg這條 instruction

Using locks

lock的使用是為了防範 race condition發生，但是 acquire()使用到 atomic step，讓程式無法平行運算，下降處理速度，所以 lock要用在刀口上才是有智之舉。

Dead lock & ordering

要注意 lock的調用順序，例如同一段程式若在 release前使用到同一塊的 acquire則會發生 dead lock的狀況。
若擁有 lock的程式中斷了，則會造成其他程式 acquire失敗，所以不能夠在允許中斷發生時持有lock。

Sleeplock

sleeplock使用在程式需要持有lock長一點的時間時(讀寫檔案等)，sleep lock在acquire lock時會呼叫另一個 sleeplock aquire routine，讓 thread可以分別執行。

END