107 NTUST OS - HW 1

Part 1

暫存器與 Stack 上的值

Part 2:

Chapter 0: 主要介紹 OS 的工作內容、Process、System call 的概念以及文件系統的設計

OS tasks:

Xv6

Process and System call:

這部分也順道介紹了殼 (Shell)

這裡介紹兩個重要的 system calls: fork() 跟 exec():

I/O and File descriptors

兩個主要的 function calls : read() and write()

// 這段程式碼從 standard input copy 資料到 standard output
// 此外，這段程式並不知道是從哪裡讀取資料的，也不知道寫入什麼文件中。
char buf[512];
int n;

for(;;){
    n = read(0, buf, sizeof buf);
    if(n == 0)
        break;
    if(n < 0){
        fprintf(2, "read error\n");
        exit();
    }
    if(write(1, buf, n) != n){
        fprintf(2, "write error\n");
        exit();
    }
}

Pipes

Chapter 1: 探討 OS 主要的特性

為何不將 system call 以 library 的形式使用？這樣的話每個 application 不就可以客製化其 function calls，甚至可以寫在 HW 裡頭來加速嗎？

User mode, kernel mode, and system calls

為了達到 isolation 的目的，OS 通常會阻止 app 能夠直接存取到較敏感的 hardware resources，如:

  1. 禁止較敏感的 system call 被執行, ex: read and write raw disk sectors
  2. 利用 exec() 來建立 memory image，而不是直接給予實際的記憶體空間
  3. File descriptors 的設計

而多數的 processors 為了讓 hardware 具有 strong isolation 的特性，會建立兩種空間: kernel mode and user mode 來執行指令

Kernel organization

Process overview

struct proc {
    uint sz;                    // Size of process memory (bytes)
    pde_t* pgdir;               // Page table
    char *kstack;               // Bottom of kernel stack for this process 
    enum procstate state;       // Process state
    int pid;                    // Process ID
    struct proc *parent;        // Parent process
    struct trapframe *tf;       // Trap frame for current syscall
    struct context *context;    // swtch() here to run process
    void *chan;                 // If non−zero, sleeping on chan
    int killed;                 // If non−zero, have been killed
    struct file *ofile[NOFILE]; // Open files
    struct inode *cwd;          // Current directory
    char name[16];              // Process name (debugging)
};

Part 3

Chapter 3: Traps, interrupts, and drivers

前言

通常程式在執行的時候，CPU 的運作會遵循一個固定的迴圈:

  1. read the instruction,
  2. advance the program counter,
  3. execute the instruction，

但有時候會出現需要從 user program 跳回 kernel 的情形，本章在探討處理這些情形時會遇到的三大狀況以及處理方式

在現代的 processors 中，通常都是使用一種硬體機制在處理所有情況，最常見的就是 interrupt (int in x86)

Interrupt and trap

在執行 interrupt 的時候，其程序大致如下:

  1. stops the normal processor loop
  2. processor saves its registers
  3. executes a new sequence called an interrupt handler
  4. finishes the execution
  5. processor returns to from the interrupt

這裡介紹了另一種停止的類型，traps，跟 interrupts 的差異主要在發出的來源不同:

X86 protection

switchuvm(struct proc *p)
{
    if(p == 0)
        panic("switchuvm: no process");
    if(p−>kstack == 0)
        panic("switchuvm: no kstack");
    if(p−>pgdir == 0)
        panic("switchuvm: no pgdir");
    
    pushcli();
    mycpu()−>gdt[SEG_TSS] = SEG16(STS_T32A, &mycpu()−>ts, sizeof(mycpu()−>ts)−1, 0);
    mycpu()−>gdt[SEG_TSS].s = 0;
    mycpu()−>ts.ss0 = SEG_KDATA << 3;
    mycpu()−>ts.esp0 = (uint)p−>kstack + KSTACKSIZE;
    // setting IOPL=0 in eflags *and* iomb beyond the tss segment limit
    // forbids I/O instructions (e.g., inb and outb) from user space 
    mycpu()−>ts.iomb = (ushort) 0xFFFF;
    ltr(SEG_TSS << 3);
    lcr3(V2P(p−>pgdir)); // switch to process’s address space
    popcli();
}

當 trap 發生，processor 會從 task segment descriptor 讀取 %esp and %ss 並和舊的 user %ss, %esp 做替換，但如果這整件事情是在 kernel mode 發生的話，則不會執行任何動作。再來，processor 也會記錄 %eglags, %cs, %eip 等資料，最後再由 Alltraps 來記錄 %ds, %es, %fs, %gs 的資料 (src exist in 3304-3310)

alltraps:
    # Build trap frame.
    pushl %ds
    pushl %es
    pushl %fs
    pushl %gs
    pushal

    # Set up data segments.
    movw $(SEG_KDATA<<3), %ax
    movw %ax, %ds
    movw %ax, %es
    
    # Call trap(tf), where tf=%esp
    pushl %esp
    call trap
    addl $4, %esp

最後會產生 struct trapframe

struct trapframe{
    // registers as pushed by pusha
    uint edi;
    uint esi;
    uint ebp;
    uint oesp;  //useless & ignored
    uint ebx;
    uint edx;
    uint ecx;
    uint eax;    // contains the system call number for the kernel to inspect later.

    // rest of trap frame
    ushort gs;
    ushort padding1;
    ushort fs;
    ushort padding2;
    ushort es;
    ushort padding3;
    ushort ds;
    ushort padding4;
    uint trapno;

    // below here defined by x86 hardware
    uint err;
    uint eip;
    ushort cs;    // user code segment selector
    ushort padding5;
    uint eflags;    // content of the %eflags register

    // below here only when crossing rings, such as from user to kernel
    uint esp;
    ushort ss;
    ushort padding6;
}

C trap handler

這裏解釋了 Trap 的 src 內容 (3401-3480)，列舉如下:

System calls

假如發生了 system call，trap 會呼叫 syscall，syscall會從 trap frame 中讀取 system call number，存到 system call tables 中，如果 number 有問題，return -1。

syscall(void)
{
    int num;
    struct proc *curproc = myproc();

    // 主要讀取的資訊 (eax)
    num = curproc−>tf−>eax;
    if(num > 0 && num < NELEM(syscalls) && syscalls[num]) {
        curproc−>tf−>eax = syscalls[num]();
    } else {
        cprintf("%d %s: unknown sys call %d\n", curproc−>pid, curproc−>name, num);
        curproc−>tf−>eax = −1;
    }
}

接下來討論一個問題：如何找到 system call 的 arguments？
→ 利用 helper functions: argint, argptr, argstr, and argfd
→ retrieve the n’th system call argument, as either an integer, pointer, a string, or a file descriptor.

Interrupts

早期是透過 Programmable interrupt controler (PIC) 來提供中斷程序，隨著 multiprocessor PC boards 的出現，需要新的方式來處理，因為每個 CPU 需要各自的 controller，這裏包括兩部分:

  1. 在 I/O systems 中的 (IOPIC, ioapic.c)
  2. 在每個 processor 中的 (LAPIC, lapic.c)

初始化過程中，每個 device 會處理自己的中斷，並指定哪個 processor 要來處理這個中斷，而儲存在 LAPIC 的代碼則是可以被所有的 processor 取用，xv6 將這個機制寫在 lapicinit 中，其中最重要的是底下這行：

lapicw(TIMER, PERIODIC | (T_IRQ0 + IRQ_TIMER));

這裏告訴 LAPIC 要週期性的在 IRQ_TIMER 產生一個 interrupt。

此外，processor 可以透過設定 %eflags register 中的 IF flag 來決定能不能接收 interrupts。可用的 functions 包含了 cli 以及 sti。

Drivers

這邊舉 Disk driver 為例，傳統上 disk hardware 將資料表示為一連串 512-byte 的區塊 (also called sectors)，但是，OS 對其 file system 所使用的 block size，可能會跟這個 sector 不同。此外，這兩個區塊所包含的內容很有可能不同步，可能是還沒完全從 disk 中取出，也可能是已更新但是還未完全寫到 disk。
Disk driver的作用就是要確保程式不會因為不同步的問題而無法運作。

xv6 會使用一個 struct buf 來呈現這個區塊

struct buf {
    int flags;    // track the relationship between memory and disk
    uint dev;    // numbering
    uint blockno;
    struct sleeplock lock; 
    uint refcnt;
    struct buf *prev; // LRU cache list 
    struct buf *next;
    struct buf *qnext; // disk queue 
    uchar data[BSIZE];    // BSIZE: identical to the IDE's sector size
};

#define B_VALID 0x2 // buffer has been read from disk
#define B_DIRTY 0x4 // buffer needs to be written to disk

Disk driver