## page fault
**複習　trap：**
1.user mode 觸發page fault時，會使用tarp跳轉到內核，將錯誤的vitual address 儲存到stval寄存器。

2.scaues 寄存器則會紀錄發生錯誤的原因。

3.trapframe地址存放在sepc寄存器，pc會存入sepc寄存器。

**sbrk() systemcall**
user 可以透過sbrk()指令來分配更多heap內存

lazy location 發生情況：如果 page fault發生虛擬地址在stack　<　vitual address　<　p->size（heap頂端）但該虛擬地址沒被映射到物理地址。

當編譯器生成二進制檔案，會填入三個區域，記憶體由下到上分別為:test儲存的是程式指令，接著是data存的是初始化後的全局變量，還有BSS儲存的是未被初始化的全局變量（０），佔的空間很少，所以沒有物理地址額外劃分空間。只要將虛擬地址為０的全局變量，全部指向數值為０的一塊物理地址即可。

在記憶體極度嚴苛的條件下，可以刪除某部分內存的映射，替換為其他部分，通常是使用LRU cache 來實現，由non dirty page(only read)會先刪除，因為只需修改va 即可，不需要儲存回硬碟之類的操作，可以通過操控access bit來實現 LRU cache的實現，操作系統通常每過一段時間會將access bit清零。

fd 可以理解成當前進程虛擬記憶體的偏移量，從va的起始地址開始計算文件要放置在哪。

**demanding pageing** 也是一種lazy allocation，當應用程式記憶體使用遠遠操出物理記憶體時，把物理記憶體內資訊進行swapped out，將用到的資料從disk取出來，linux內有一種鎖是mlock，能避免特定記憶體被置換，以防大量page fault 導致的性能下降。

## lab : lazy page allocation
**第一個實驗: 修改sbrk()**
sbrk()是一個system call，原先在遇到增加heap的函數是使用growproc()
growproc:
也就是有多少n，就分配多少空間，而沒有使用到 lazy allocaation

這裡修改systemcall中的sbrk()函數，不再使用 growproc()

使用 echo hi 時就會報錯

照順序分別是 錯誤原因 進程id 錯誤時的PC指針 錯誤時的虛擬地址。

**第二個實驗: 實現 lazy allocation**
在 trap.c 進行修改，由上面實驗結果可以發現，page fault發生在 scause 寄存器為15時，代表vitual address 寫錯誤，13則是讀錯誤，因此設置在發生為15時，分配虛擬內存。
其中r_stval紀錄page fault的虛擬地址，使用kalloc()分配空的物理地址，分配錯誤，則殺死進程，接著將page fault 的 vitual address 置到page的最低位(沒置使用walk函數找物理地址會有錯)，並使用mappages將va映射到實際的物理地址。
這裡則是uvmunmap遇到pte_v時會報錯，代表虛擬地址位映射，但實際上是lazy location，所以修改成continue。
最終完成lazy allocation 功能，再出現使用到未分配的虛擬地址時，會進到page fault ，並通過trap 添加的函數完成映射。

第三個實驗室增加lazy location 的細節
修改trap 和 sbrk 增加遇見n是負數的處理，process變小，和發生page fault 的範圍，不能超出heap範圍，和stack。
sbrk()
trap()

並修改uvmcopy 和 uvmunmap 一個是處理 fork()，父進程複製給子進程，出現沒有映射的pte就跳過，另一個是檢查pte的映射，同樣是沒映射就continue。

## interrupt
這章節介紹中斷，首先介紹驅動，是可以配置硬件，並管理中斷，且與IO交互的程式，通常須了解interface等通訊協議。

驅動通常分兩部分執行，上半部在內核的線程，下半部分在中斷執行，典型驅動架構如下圖所示，透過應用的read or write 寫寄存器，驅動對該數據進行處理，接著觸發中斷時，使用interrupt handler，對數據進行處理。


可以通過PLIC(platform level interrupt controller)控制外部硬件中斷(extern interrupt)，當有中斷發生時，plic會分發給cpu進行處理。

本章主要關注的CPU寄存器:

SIE(supervisor interrupt enable): 有E(external interrupt)，S(software)，T(time)三個bit，去控制不同中斷。

sstatus(supervisor status): 可打開或關閉中斷。

SIP: interrupt pending

enable plic 中斷:
enable 每一個CPU 可以接收的plic interrupt:
enable cpu interrupt(sstatus regisiter):

interrupt 流程:
cpu的SEI BIT 接收到 plic 的 interrupt-> 清空SIE BIT -> SEPC保存當前PC(trap流程) -> save現在的mode，pc變成stvec內 ->執行trap

中斷的concurrency:
1. 設備 和 cpu 的並行 (生產者和消費者並行 produce and consumer parailism)
2. 中斷的停止，有時中斷會在內核發生，未保持某些任務的 atomic (interrupt 的 enable 和 disable)
3. top driver + bottom driver 的並行 (鎖的使用)

生產者和消費者可以通過 wake 和 sleep 去控制，一方過快，導致buffer為空或是 過大時，可以通過一方 sleep，直到正常時在wake。


在CPU週期快速的情況下，使用interrupt需要替換寄存器和還原等工作，這時能使用polling取代interrupt，polling雖然會定時消耗cpu週期去輪詢，但在cpu週期快速的設備上消耗相對interrupt來的更少。

## locking
互斥鎖:mutual exclusion
細粒度:coarse-grained

**加鎖的時機:**
當兩個process或thread訪問同一塊共享內存，且其中一個會進行寫操作之類的導致內存內容被修改時，就需要加鎖，避免發生race condition。
不過有時候像是printf("")的任務，避免輸出的內容重疊，也會加鎖。

結論就是想加就加。

**鎖會降低併發性，可能變成串行的任務，需要斟酌。**

cpu在確認鎖是空的，並且解鎖時，此時訪問鎖並加鎖的過程必須對於CPU是atomic的，避免有兩個CPU同時解鎖之情形發生。

**死鎖**:假設有兩個code有AB兩個鎖，其中一個CPU執行第一個程式(先A在B)，獲得A鎖，另一個CPU執行第二個程式(先B在A)獲得B鎖，這時這兩個程式就會陷入死鎖。

要避免死鎖要規定好鎖的全局排序，都要遵循先A後B，避免陷入死鎖。

不過會破壞code的模塊化，因為func A調用func B需要知道func B的鎖，避免陷入死鎖，但func A和B的隔離性就被破壞。

有時候中斷也會導致死鎖，因為中斷前鎖已被其他系統調用獲得，如果這時進中斷，而中斷又需要鎖，將會導致死鎖。

**鎖的類型:**
鎖有兩種，分別是spinlock 和 sleeplock，分別是自旋鎖和睡眠鎖，自旋鎖就像輪尋，睡眠鎖像是阻塞。
1.自旋鎖:因為會消耗CPU，適合短時間任務，執行自旋鎖的CPU不能進中斷。

2.睡眠鎖:睡眠時，會釋放鎖，並讓出CPU，可以進中斷，等IO結束後再重新鎖上。

可以睡眠鎖內包含自旋鎖，但反過來不行。

**鎖跟原子操作差別:**
原子操作適合簡單任務，鎖適合比較複雜的任務，不過鎖住的時候跟原子操作概念相同，且功能較原子操作來的多，能根據情形選擇睡眠鎖或自旋鎖，code也更加簡單易懂。

硬件原子操作的方式:通常是透過鎖住寄存器地址，並將資料寫入和讀出並返回讀出數據。

## 實驗:copy-on-write
這次實驗類似page fault，當fork()發生時，子進程不是直接分配一塊新的內存，而是將子進程的pte跟父進程的pte共用同一塊物理內存，兩者pte_w設置為0，當遇到寫的情況時，觸發page fault，重新分配物理內存，並將寫保護撤銷。

**hint:**

1.修改uvmcopy()将父进程的物理页映射到子进程，而不是分配新页。在子进程和父进程的PTE中清除PTE_W标志。

2.修改usertrap()以识别页面错误。当COW页面出现页面错误时，使用kalloc()分配一个新页面，并将旧页面复制到新页面，然后将新页面添加到PTE中并设置PTE_W。

3.确保每个物理页在最后一个PTE对它的引用撤销时被释放——而不是在此之前。这样做的一个好方法是为每个物理页保留引用该页面的用户页表数的“引用计数”。当kalloc()分配页时，将页的引用计数设置为1。当fork导致子进程共享页面时，增加页的引用计数；每当任何进程从其页表中删除页面时，减少页的引用计数。kfree()只应在引用计数为零时将页面放回空闲列表。可以将这些计数保存在一个固定大小的整型数组中。你必须制定一个如何索引数组以及如何选择数组大小的方案。例如，您可以用页的物理地址除以4096对数组进行索引，并为数组提供等同于kalloc.c中kinit()在空闲列表中放置的所有页面的最高物理地址的元素数。

4.修改copyout()在遇到COW页面时使用与页面错误相同的方案。

hint1 就是實現cow的功能，讓fork()時子進程和父進程使用同一塊物理內存，但內存須改為不可寫。

hint2 就是觸發page fault 能處理cow時的情況，分配一塊新的內存，並使其可寫。

hint3 因為物理內存是多對1，必須確定物理內存沒人映射時，再將其釋放。

hint4 觸發syscall時，內核會用copyout對user的內存進行寫入，如果是cow的頁表，需進行處理，而copyin則是讀的操作，因此不須進行cow的處理。

首先修改kalloc的內容，多設置一個結構體，將每個物理頁表設置成一個矩陣，來儲存一個物理頁表映射多少個虛擬內存，並加鎖。


設置相關interface，共有四個，分別是複製uvmcopy()時對應映射+1，以及獲取當前映射(trap)，和映射減1(kfree)，並且為0時進行刪除，以及初始化應設為1(kalloc())。


**接著修改uvmcopy()**

複製時不再分配內存，而是將新的process指向 mappages 原先的物理內存，並且寫保護至零，並使用rsw位，才知道是cow


**rsw位由軟件使用**
**設置rsw位**

接著修改usertrap，利用cow_walkaddr找到最後的pte，並判斷當前pte映射的物理內存，有多少虛擬內存的映射，如果只剩一個，就直接給予寫保護，然後取消PTE_RSW，如果有多個映射，則分配一塊新的物理內存，並複製物理內存內容和改變原先虛擬內存的映射，到新的物理內存。


其中 cow_walkaddr 是根據 walkaddr設計而來，多判斷一個 PTE_w位，利用 va 和 pagetable 映射到最後的pte。


接著是修改kfree和 kalloc 和cow作搭配，kfree改成物理內存映射量-1，當歸零時，釋放內存，kfree則需初始化映射為1。

最後是copyout跟trap差不多，如果是cow，直接分配一塊新映射的物理內存，給原來的虛擬內存，之後一樣。


鎖要記得初始化