轉載請注明出處。

前言：

本實驗來自斯坦福大學cs140課程，只限于教學用途，以下是他們對于Pintos系統的介紹：

Pintos is a simple Operating system framework for the 80x86 architecture. It supports kernel threads, loading and running user programs, and a file system, but it implements all of these in a very simple way. In the Pintos projects, you and your project team will strengthen its support in all three of these areas. You will also add a virtual memory implementation.

Pintos實驗主要分成四部分，如下所示：

• 實驗一：Thread
• 實驗二：User Programs
• 實驗三：Virtual Memory
• 實驗四：File System

實驗原理：

通過 bochs 加載 pintos 操作系統， 該操作系統會根據 pintos 的實現打印運行結果，通過比較標準輸出文檔和實際輸出，來判斷 pintos 實現是否符合要求。

環境配置：

參考： http://www.stanford.edu/class/cs140/projects/pintos/pintos_12.html#SEC166

實驗實現代碼地址：

https://github.com/laiy/Pintos/tree/master/src

實驗一 THREAD：

我們試驗一的最終任務就是在threads/中跑make check的時候， 27個test全pass。

Mission1:

重新實現timer_sleep函數（2.2.2）

（注意， 博主以下用了包括代碼在內大概7000字的說明從每一個底層細節解析了這個函數的執行， 雖然很長但是讓我們對pintos這個操作系統的各種機制和實現有更深刻的理解， 如果嫌長請直接跳到函數重新實現）

timer_sleep函數在devices/timer.c。系統現在是使用busy wait實現的，即線程不停地循環，直到時間片耗盡。更改timer_sleep的實現方式。

我們先來看一下devices目錄下timer.c中的timer_sleep實現：

 1 /* Sleeps for approximately TICKS timer ticks.  Interrupts must 2    be turned on. */ 3 void 4 timer_sleep (int64_t ticks) 5 { 6   int64_t start = timer_ticks (); 7   ASSERT (intr_get_level () == INTR_ON); 8   while (timer_elapsed (start) < ticks) 9     thread_yield();10 }

讓我們一行一行解析：

第6行： 調用了timer_ticks函數， 讓我們來看看這個函數做了什么。

1 /* Returns the number of timer ticks since the OS booted. */2 int64_t3 timer_ticks (void)4 {5   enum intr_level old_level = intr_disable ();6   int64_t t = ticks;7   intr_set_level (old_level);8   return t;9 }

然后我們注意到這里有個intr_level的東西通過intr_disable返回了一個東西，沒關系，我們繼續往下找。

1 /* Interrupts on or off? */2 enum intr_level 3   {4     INTR_OFF,             /* Interrupts disabled. */5     INTR_ON               /* Interrupts enabled. */6   };

 1 /* Disables interrupts and returns the previous interrupt status. */ 2 enum intr_level 3 intr_disable (void)  4 { 5   enum intr_level old_level = intr_get_level (); 6  7   /* Disable interrupts by clearing the interrupt flag. 8      See [IA32-v2b] "CLI" and [IA32-v3a] 5.8.1 "Masking Maskable 9      Hardware Interrupts". */10   asm volatile ("cli" : : : "memory");11 12   return old_level;13 }

這里很明顯，intr_level代表能否被中斷，而intr_disable做了兩件事情：1. 調用intr_get_level() 2. 直接執行匯編代碼，調用匯編指令來保證這個線程不能被中斷。

注意： 這個asm volatile是在C語言中內嵌了匯編語言，調用了CLI指令，CLI指令不是command line interface, 而是clear interrupt, 作用是將標志寄存器的IF（interrupt flag）位置為0, IF=0時將不響應可屏蔽中斷。

好，讓我們繼續來看intr_get_level又做了什么鬼。

 1 /* Returns the current interrupt status. */ 2 enum intr_level 3 intr_get_level (void)  4 { 5   uint32_t flags; 6  7   /* Push the flags register on the processor stack, then pop the 8      value off the stack into `flags'.  See [IA32-v2b] "PUSHF" 9      and "POP" and [IA32-v3a] 5.8.1 "Masking Maskable Hardware10      Interrupts". */11   asm volatile ("pushfl; popl %0" : "=g" (flags));12 13   return flags & FLAG_IF ? INTR_ON : INTR_OFF;14 }

這里就是intr_disable函數調用的最深的地方了!

這個函數一樣是調用了匯編指令，把標志寄存器的東西放到處理器棧上，然后把值pop到flags（代表標志寄存器IF位）上，通過判斷flags來返回當前終端狀態(intr_level)。

好， 到這里。 函數嵌套了這么多層， 我們整理一下邏輯：

1. intr_get_level返回了intr_level的值

2. intr_disable獲取了當前的中斷狀態， 然后將當前中斷狀態改為不能被中斷， 然后返回執行之前的中斷狀態。

有以上結論我們可以知道： timer_ticks第五行做了這么一件事情： 禁止當前行為被中斷， 保存禁止被中斷前的中斷狀態（用old_level儲存）。

讓我們再來看timer_ticks剩下的做了什么， 剩下的就是用t獲取了一個全局變量ticks, 然后返回， 其中調用了set_level函數。

1 /* Enables or disables interrupts as specified by LEVEL and2    returns the previous interrupt status. */3 enum intr_level4 intr_set_level (enum intr_level level) 5 {6   return level == INTR_ON ? intr_enable () : intr_disable ();7 }

有了之前的基礎，這個函數就很容易看了， 如果之前是允許中斷的（INTR_ON）則enable否則就disable.

而intr_enable正如你們所想，實現和之前基本一致：

 1 /* Enables interrupts and returns the previous interrupt status. */ 2 enum intr_level 3 intr_enable (void)  4 { 5   enum intr_level old_level = intr_get_level (); 6   ASSERT (!intr_context ()); 7  8   /* Enable interrupts by setting the interrupt flag. 9 10      See [IA32-v2b] "STI" and [IA32-v3a] 5.8.1 "Masking Maskable11      Hardware Interrupts". */12   asm volatile ("sti");13 14   return old_level;15 }

說明一下， sti指令就是cli指令的反面，將IF位置為1。

然后有個ASSERT斷言了intr_context函數返回結果的false。

再來看intr_context

1 /* Returns true during processing of an external interrupt2    and false at all other times. */3 bool4 intr_context (void) 5 {6   return in_external_intr;7 }

這里直接返回了是否外中斷的標志in_external_intr， 就是說ASSERT斷言這個中斷不是外中斷（IO等， 也稱為硬中斷）而是操作系統正常線程切換流程里的內中斷（也稱為軟中斷）。

好的， 至此， 我們總結一下：

這么多分析其實分析出了pintos操作系統如何利用中斷機制來確保一個原子性的操作的。

我們來看， 我們已經分析完了timer_ticks這個函數， 它其實就是獲取ticks的當前值返回而已， 而第5行和第7行做的其實只是確保這個過程是不能被中斷的而已。

那么我們來達成一個共識， 被以下兩個語句包裹的內容目的是為了保證這個過程不被中斷。

1 enum intr_level old_level = intr_disable ();2 ...3 intr_set_level (old_level);

好的， 那么ticks又是什么？ 來看ticks定義。

1 /* Number of timer ticks since OS booted. */2 static int64_t ticks;

從pintos被啟動開始， ticks就一直在計時， 代表著操作系統執行單位時間的前進計量。

好， 現在回過來看timer_sleep這個函數， start獲取了起始時間， 然后斷言必須可以被中斷， 不然會一直死循環下去， 然后就是一個循環

1 while (timer_elapsed (start) < ticks)2   thread_yield();

注意這個ticks是函數的形參不是全局變量， 然后看一下這兩個函數：

1 /* Returns the number of timer ticks elapsed since THEN, which2    should be a value once returned by timer_ticks(). */3 int64_t4 timer_elapsed (int64_t then)5 {6   return timer_ticks () - then;7 }

很明顯timer_elapsed返回了當前時間距離then的時間間隔， 那么這個循環實質就是在ticks的時間內不斷執行thread_yield。

那么我們最后來看thread_yield是什么就可以了：

 1 /* Yields the CPU.  The current thread is not put to sleep and 2    may be scheduled again immediately at the scheduler's whim. */ 3 void 4 thread_yield (void) 5 { 6   struct thread *cur = thread_current (); 7   enum intr_level old_level; 8  9   ASSERT (!intr_context ());10 11   old_level = intr_disable ();12   if (cur != idle_thread)13     list_push_back (&ready_list, &cur->elem);14   cur->status = THREAD_READY;15   schedule ();16   intr_set_level (old_level);17 }

第6行thread_current函數做的事情已經可以顧名思義了， 不過具有鉆研精神和強迫癥的你還是要確定它的具體實現：

 1 /* Returns the running thread. 2    This is running_thread() plus a couple of sanity checks. 3    See the big comment at the top of thread.h for details. */ 4 struct thread * 5 thread_current (void) 6 { 7   struct thread *t = running_thread (); 8  9   /* Make sure T is really a thread.10      If either of these assertions fire, then your thread may11      have overflowed its stack.  Each thread has less than 4 kB12      of stack, so a few big automatic arrays or moderate13      recursion can cause stack overflow. */14   ASSERT (is_thread (t));15   ASSERT (t->status == THREAD_RUNNING);16 17   return t;18 }

 1 /* Returns the running thread. */ 2 struct thread * 3 running_thread (void) 4 { 5   uint32_t *esp; 6  7   /* Copy the CPU's stack pointer into `esp', and then round that 8      down to the start of a page.  Because `struct thread' is 9      always at the beginning of a page and the stack pointer is10      somewhere in the middle, this locates the curent thread. */11   asm ("mov %%esp, %0" : "=g" (esp));12   return pg_round_down (esp);13 }

1 /* Returns true if T appears to point to a valid thread. */2 static bool3 is_thread (struct thread *t)4 {5   return t != NULL && t->magic == THREAD_MAGIC;6 }

先來看thread_current調用的running_thread, 把CPU棧的指針復制到esp中， 然后調用pg_round_down

1 /* Round down to nearest page boundary. */2 static inline void *pg_round_down (const void *va) {3   return (void *) ((uintptr_t) va & ~PGMASK);4 }

好，這里又涉及到這個操作系統是怎么設計頁面的了：

1 /* Page offset (bits 0:12). */2 #define PGSHIFT 0                          /* Index of first offset bit. */3 #define PGBITS  12                         /* Number of offset bits. */4 #define PGSIZE  (1 << PGBITS)              /* Bytes in a page. */5 #define PGMASK  BITMASK(PGSHIFT, PGBITS)   /* Page offset bits (0:12). */

1 /* Functions and macros for working with virtual addresses.2 3    See pte.h for functions and macros specifically for x864    hardware page tables. */5 6 #define BITMASK(SHIFT, CNT) (((1ul << (CNT)) - 1) << (SHIFT))

一個頁面12位， PGMASK調用BITMASK其實就是一個頁面全部位都是1的這么個MASK， 注意1ul的意思是unsigned long的1。

然后來看pg_round_down， 對PGMASK取反的結果就是一個頁面大小全部為0的這么個數， 然后和傳過來的指針做與操作的結果就是清0指針的靠右12位。

這里有什么效果呢？ 我們知道一個頁面12位， 而struct thread是在一個頁面的最開始的， 所以對任何一個頁面的指針做pg_round_down的結果就是返回到這個頁面最開始線程結構體的位置。

好， 我們現在分析出了pg_round_down其實就是返回了這個頁面線程的最開始指針， 那么running_thread的結果返回當前線程起始指針。

再來看thread_current里最后的兩個斷言， 一個斷言t指針是一個線程， 一個斷言這個線程處于THREAD_RUNNING狀態。

然后is_thread用的t->magic其實是用于檢測時候有棧溢出的這么個元素。

1 /* Owned by thread.c. */2 unsigned magic;                     /* Detects stack overflow. */

好， 現在thread_current分析完了， 這個就是返回當前線程起始指針位置。

我們繼續看thread_yield， 然后剩下的很多東西其實我們已經分析過了， 在分析的過程其實是對這個操作系統工作過程的剖析， 很多地方都是相通的。

第9斷言這是個軟中斷， 第11和16包裹起來的就是我們之前分析的線程機制保證的一個原子性操作。

然后我們來看12-15做了什么：

1 if (cur != idle_thread)2   list_push_back (&ready_list, &cur->elem);3 cur->status = THREAD_READY;4 schedule ();

如何當前線程不是空閑的線程就調用list_push_back把當前線程的元素扔到就緒隊列里面， 并把線程改成THREAD_READY狀態。

關于隊列list的相關操作mission2會涉及到， 這里先不作解釋， 顧名思義即可。

然后再調用schedule:

 1 /* Schedules a new process.  At entry, interrupts must be off and 2    the running process's state must have been changed from 3    running to some other state.  This function finds another 4    thread to run and switches to it. 5  6    It's not safe to call printf() until thread_schedule_tail() 7    has completed. */ 8 static void 9 schedule (void)10 {11   struct thread *cur = running_thread ();12   struct thread *next = next_thread_to_run ();13   struct thread *prev = NULL;14 15   ASSERT (intr_get_level () == INTR_OFF);16   ASSERT (cur->status != THREAD_RUNNING);17   ASSERT (is_thread (next));18 19   if (cur != next)20     prev = switch_threads (cur, next);21   thread_schedule_tail (prev);22 }

首先獲取當前線程cur和調用next_thread_to_run獲取下一個要run的線程：

 1 /* Chooses and returns the next thread to be scheduled.  Should 2    return a thread from the run queue, unless the run queue is 3    empty.  (If the running thread can continue running, then it 4    will be in the run queue.)  If the run queue is empty, return 5    idle_thread. */ 6 static struct thread * 7 next_thread_to_run (void) 8 { 9   if (list_empty (&ready_list))10     return idle_thread;11   else12     return list_entry (list_pop_front (&ready_list), struct thread, elem);13 }

如果就緒隊列空閑直接返回一個空閑線程指針， 否則拿就緒隊列第一個線程出來返回。

然后3個斷言之前講過就不多說了， 確保不能被中斷， 當前線程是RUNNING_THREAD等。

如果當前線程和下一個要跑的線程不是同一個的話調用switch_threads返回給prev。

1 /* Switches from CUR, which must be the running thread, to NEXT,2    which must also be running switch_threads(), returning CUR in3    NEXT's context. */4 struct thread *switch_threads (struct thread *cur, struct thread *next);

注意， 這個函數實現是用匯編語言實現的在threads/switch.S里：

 1 #### struct thread *switch_threads (struct thread *cur, struct thread *next); 2 #### 3 #### Switches from CUR, which must be the running thread, to NEXT, 4 #### which must also be running switch_threads(), returning CUR in 5 #### NEXT's context. 6 #### 7 #### This function works by assuming that the thread we're switching 8 #### into is also running switch_threads().  Thus, all it has to do is 9 #### preserve a few registers on the stack, then switch stacks and10 #### restore the registers.  As part of switching stacks we record the11 #### current stack pointer in CUR's thread structure.12 13 .globl switch_threads14 .func switch_threads15 switch_threads:16     # Save caller's register state.17     #18     # Note that the SVR4 ABI allows us to destroy %eax, %ecx, %edx,19     # but requires us to preserve %ebx, %ebp, %esi, %edi.  See20     # [SysV-ABI-386] pages 3-11 and 3-12 for details.21     #22     # This stack frame must match the one set up by thread_create()23     # in size.24     pushl %ebx25     pushl %ebp26     pushl %esi27     pushl %edi28 29     # Get offsetof (struct thread, stack).30 .globl thread_stack_ofs31     mov thread_stack_ofs, %edx32 33     # Save current stack pointer to old thread's stack, if any.34     movl SWITCH_CUR(%esp), %eax35     movl %esp, (%eax,%edx,1)36 37     # Restore stack pointer from new thread's stack.38     movl SWITCH_NEXT(%esp), %ecx39     movl (%ecx,%edx,1), %esp40 41     # Restore caller's register state.42     popl %edi43     popl %esi44     popl %ebp45     popl %ebx46         ret47 .endfunc

分析一下這個匯編代碼： 先4個寄存器壓棧保存寄存器狀態（保護作用）， 這4個寄存器是switch_threads_frame的成員：

 1 /* switch_thread()'s stack frame. */ 2 struct switch_threads_frame  3   { 4     uint32_t edi;               /*  0: Saved %edi. */ 5     uint32_t esi;               /*  4: Saved %esi. */ 6     uint32_t ebp;               /*  8: Saved %ebp. */ 7     uint32_t ebx;               /* 12: Saved %ebx. */ 8     void (*eip) (void);         /* 16: Return address. */ 9     struct thread *cur;         /* 20: switch_threads()'s CUR argument. */10     struct thread *next;        /* 24: switch_threads()'s NEXT argument. */11   };

然后全局變量thread_stack_ofs記錄線程和棧之間的間隙， 我們都知道線程切換有個保存現場的過程，

來看34,35行， 先把當前的線程指針放到eax中， 并把線程指針保存在相對基地址偏移量為edx的地址中。

38,39： 切換到下一個線程的線程棧指針， 保存在ecx中， 再把這個線程相對基地址偏移量edx地址（上一次保存現場的時候存放的）放到esp當中繼續執行。

這里ecx, eax起容器的作用， edx指向當前現場保存的地址偏移量。

簡單來說就是保存當前線程狀態， 恢復新線程之前保存的線程狀態。

然后再把4個寄存器拿出來， 這個是硬件設計要求的， 必須保護switch_threads_frame里面的寄存器才可以destroy掉eax, edx, ecx。

然后注意到現在eax(函數返回值是eax)就是被切換的線程棧指針。

我們由此得到一個結論， schedule先把當前線程丟到就緒隊列，然后把線程切換如果下一個線程和當前線程不一樣的話。

然后再看shedule最后一行的函數thread_schedule_tail做了什么鬼， 這里參數prev是NULL或者在下一個線程的上下文中的當前線程指針。

 1 /* Completes a thread switch by activating the new thread's page 2    tables, and, if the previous thread is dying, destroying it. 3  4    At this function's invocation, we just switched from thread 5    PREV, the new thread is already running, and interrupts are 6    still disabled.  This function is normally invoked by 7    thread_schedule() as its final action before returning, but 8    the first time a thread is scheduled it is called by 9    switch_entry() (see switch.S).10 11    It's not safe to call printf() until the thread switch is12    complete.  In practice that means that printf()s should be13    added at the end of the function.14 15    After this function and its caller returns, the thread switch16    is complete. */17 void18 thread_schedule_tail (struct thread *prev)19 {20   struct thread *cur = running_thread ();21 22   ASSERT (intr_get_level () == INTR_OFF);23 24   /* Mark us as running. */25   cur->status = THREAD_RUNNING;26 27   /* Start new time slice. */28   thread_ticks = 0;29 30 #ifdef USERPROG31   /* Activate the new address space. */32   process_activate ();33 #endif34 35   /* If the thread we switched from is dying, destroy its struct36      thread.  This must happen late so that thread_exit() doesn't37      pull out the rug under itself.  (We don't free38      initial_thread because its memory was not obtained via39      palloc().) */40   if (prev != NULL && prev->status == THREAD_DYING && prev != initial_thread)41     {42       ASSERT (prev != cur);43       palloc_free_page (prev);44     }45 }

先是獲得當前線程cur, 注意此時是已經切換過的線程了（或者還是之前run的線程， 因為ready隊列為空）。

然后把線程狀態改成THREAD_RUNNING， 然后thread_ticks清零開始新的線程切換時間片。

然后調用process_activate觸發新的地址空間。

 1 /* Sets up the CPU for running user code in the current 2    thread. 3    This function is called on every context switch. */ 4 void 5 process_activate (void) 6 { 7   struct thread *t = thread_current (); 8  9   /* Activate thread's page tables. */10   pagedir_activate (t->pagedir);11 12   /* Set thread's kernel stack for use in processing13      interrupts. */14   tss_update ();15 }

這里先是拿到當前線程， 調用pagedir_activate:

 1 /* Loads page directory PD into the CPU's page directory base 2    register. */ 3 void 4 pagedir_activate (uint32_t *pd)  5 { 6   if (pd == NULL) 7     pd = init_page_dir; 8  9   /* Store the physical address of the page directory into CR310      aka PDBR (page directory base register).  This activates our11      new page tables immediately.  See [IA32-v2a] "MOV--Move12      to/from Control Registers" and [IA32-v3a] 3.7.5 "Base13      Address of the Page Directory". */14   asm volatile ("movl %0, %%cr3" : : "r" (vtop (pd)) : "memory");15 }

這個匯編指令將當前線程的頁目錄指針存儲到CR3（頁目錄表物理內存基地址寄存器）中，也就是說這個函數更新了現在的頁目錄表。

最后來看tss_update：

1 /* Sets the ring 0 stack pointer in the TSS to point to the end2    of the thread stack. */3 void4 tss_update (void) 5 {6   ASSERT (tss != NULL);7   tss->esp0 = (uint8_t *) thread_current () + PGSIZE;8 }

首先要弄清楚tss是什么， tss是task state segment， 叫任務狀態段，任務（進程）切換時的任務現場信息。

這里其實是把TSS的一個棧指針指向了當前線程棧的尾部， 也就是更新了任務現場的信息和狀態。

好， 到現在process_activate分析完了， 總結一下： 其實就是做了2件事情： 1.更新頁目錄表 2.更新任務現場信息（TSS）

我們現在繼續來看thread_schedule_tail， 最后是這4行：

 1   /* If the thread we switched from is dying, destroy its struct 2      thread.  This must happen late so that thread_exit() doesn't 3      pull out the rug under itself.  (We don't free 4      initial_thread because its memory was not obtained via 5      palloc().) */ 6   if (prev != NULL && prev->status == THREAD_DYING && prev != initial_thread) 7     { 8       ASSERT (prev != cur); 9       palloc_free_page (prev);10     }

這里是如果我們切換的線程狀態是THREAD_DYING（代表欲要銷毀的線程）的話， 調用palloc_free_page：

1 /* Frees the page at PAGE. */2 void3 palloc_free_page (void *page) 4 {5   palloc_free_multiple (page, 1);6 }

 1 /* Frees the PAGE_CNT pages starting at PAGES. */ 2 void 3 palloc_free_multiple (void *pages, size_t page_cnt)  4 { 5   struct pool *pool; 6   size_t page_idx; 7  8   ASSERT (pg_ofs (pages) == 0); 9   if (pages == NULL || page_cnt == 0)10     return;11 12   if (page_from_pool (&kernel_pool, pages))13     pool = &kernel_pool;14   else if (page_from_pool (&user_pool, pages))15     pool = &user_pool;16   else17     NOT_REACHED ();18 19   page_idx = pg_no (pages) - pg_no (pool->base);20 21 #ifndef NDEBUG22   memset (pages, 0xcc, PGSIZE * page_cnt);23 #endif24 25   ASSERT (bitmap_all (pool->used_map, page_idx, page_cnt));26   bitmap_set_multiple (pool->used_map, page_idx, page_cnt, false);27 }

這里創建了一個pool的結構體：

1 /* A memory pool. */2 struct pool3   {4     struct lock lock;                   /* Mutual exclusion. */5     struct bitmap *used_map;            /* Bitmap of free pages. */6     uint8_t *base;                      /* Base of pool. */7   };

首先palloc實現的是一個頁分配器， 這里pool的角色就是記憶分配的內容。 這里結構體用位圖記錄空的頁， 關鍵是這里又有一個操作系統很重要的知識概念出現了，就是lock：

1 /* Lock. */2 struct lock 3   {4     struct thread *holder;      /* Thread holding lock (for debugging). */5     struct semaphore semaphore; /* Binary semaphore controlling access. */6   };

然后鎖其實是由二值信號量實現的：

1 /* A counting semaphore. */2 struct semaphore 3   {4     unsigned value;             /* Current value. */5     struct list waiters;        /* List of waiting threads. */6   };

具體信號量方法實現在threads/synch.c中， 這里不作更多講解了， 畢竟函數分析還沒涉及到這里。

繼續看palloc_free_multiple， 第8行其實就是截取后12位， 即獲得當前頁偏差量， 斷言為0就是說頁指針應該指向線程結構體

1 /* Offset within a page. */2 static inline unsigned pg_ofs (const void *va) {3   return (uintptr_t) va & PGMASK;4 }

然后分析12-17行， 這里要弄清楚一點是系統memory分成2個池， 一個是kernel pool, 一個是user pool，user pool是提供給用戶頁的， 別的都是kernel pool。

然后看下這里調用的page_from_pool函數：

 1 /* Returns true if PAGE was allocated from POOL, 2    false otherwise. */ 3 static bool 4 page_from_pool (const struct pool *pool, void *page)  5 { 6   size_t page_no = pg_no (page); 7   size_t start_page = pg_no (pool->base); 8   size_t end_page = start_page + bitmap_size (pool->used_map); 9 10   return page_no >= start_page && page_no < end_page;11 }

pg_no是獲取虛擬頁數的， 方法其實就是直接指針右移12位就行了：

1 /* Virtual page number. */2 static inline uintptr_t pg_no (const void *va) {3   return (uintptr_t) va >> PGBITS;4 }

然后這里獲取當前池中的的起始頁和結束頁位置， 然后判斷頁面時候在這個池的Number范圍之類來判斷時候屬于某個池。

再看NOT_REACHED函數,這個函數博主找了半天， 最后用全文件搜索才找著在哪，在lib/debug.h中：

 1 /* This is outside the header guard so that debug.h may be 2    included multiple times with different settings of NDEBUG. */ 3 #undef ASSERT 4 #undef NOT_REACHED 5  6 #ifndef NDEBUG 7 #define ASSERT(CONDITION)                                       / 8         if (CONDITION) { } else {                               / 9                 PANIC ("assertion `%s' failed.", #CONDITION);   /10         }11 #define NOT_REACHED() PANIC ("executed an unreachable statement");12 #else13 #define ASSERT(CONDITION) ((void) 0)14 #define NOT_REACHED() for (;;)15 #endif /* lib/debug.h */

 1 /* GCC lets us add "attributes" to functions, function 2    parameters, etc. to indicate their properties. 3    See the GCC manual for details. */ 4 #define UNUSED __attribute__ ((unused)) 5 #define NO_RETURN __attribute__ ((noreturn)) 6 #define NO_INLINE __attribute__ ((noinline)) 7 #define PRINTF_FORMAT(FMT, FIRST) __attribute__ ((format (printf, FMT, FIRST))) 8  9 /* Halts the OS, printing the source file name, line number, and10    function name, plus a user-specific message. */11 #define PANIC(...) debug_panic (__FILE__, __LINE__, __func__, __VA_ARGS__)12 13 void debug_panic (const char *file, int line, const char *function,14                   const char *message, ...) PRINTF_FORMAT (4, 5) NO_RETURN;

這里根據NDEBUG狀態分兩種define， 一個是ASSERT空函數， NOT_REACHED執行死循環， 一個是如果ASSERT參數CONDITION為false的話就調用PANIC輸出文件，行數，函數名和用戶信息， NOT_REACHED也會輸出信息。

有些童鞋在跑測試的時候會出現卡在一個地方不動的狀態， 其實不是因為你電腦的問題， 而是當一些錯誤觸發NOT_REACHED之類的問題的時候， 因為非debug環境就一直執行死循環了， 反映出來的行為就是命令行卡住不動沒有輸出。

注意這里的語法類似__attribute__和((format(printf, m , n)))是面向gcc編譯器處理的寫法， 這里做的事情其實是參數聲明和調用匹配性檢查。

好， 繼續來看palloc_free_multiple， 用page_idx保存了計算出來了頁id， 清空了頁指針， 然后還剩下最后兩行：

1   ASSERT (bitmap_all (pool->used_map, page_idx, page_cnt));2   bitmap_set_multiple (pool->used_map, page_idx, page_cnt, false);

第一個斷言：

1 /* Returns true if every bit in B between START and START + CNT,2    exclusive, is set to true, and false otherwise. */3 bool4 bitmap_all (const struct bitmap *b, size_t start, size_t cnt) 5 {6   return !bitmap_contains (b, start, cnt, false);7 }

 1 /* Returns true if any bits in B between START and START + CNT, 2    exclusive, are set to VALUE, and false otherwise. */ 3 bool 4 bitmap_contains (const struct bitmap *b, size_t start, size_t cnt, bool value)  5 { 6   size_t i; 7    8   ASSERT (b != NULL); 9   ASSERT (start <= b->bit_cnt);10   ASSERT (start + cnt <= b->bit_cnt);11 12   for (i = 0; i < cnt; i++)13     if (bitmap_test (b, start + i) == value)14       return true;15   return false;16 }

bitmap_contains首先做斷言對參數正確性確認， 然后如果所有位處于start到start+cnt都是value的話， 別的都是~value的話， 返回true， 從我們的函數調用來看就是斷言位圖全是0。

1 /* Returns the value of the bit numbered IDX in B. */2 bool3 bitmap_test (const struct bitmap *b, size_t idx) 4 {5   ASSERT (b != NULL);6   ASSERT (idx < b->bit_cnt);7   return (b->bits[elem_idx (idx)] & bit_mask (idx)) != 0;8 }9 

 1 /* Returns the index of the element that contains the bit 2    numbered BIT_IDX. */ 3 static inline size_t 4 elem_idx (size_t bit_idx)  5 { 6   return bit_idx / ELEM_BITS; 7 } 8  9 /* Returns an elem_type where only the bit corresponding to10    BIT_IDX is turned on. */11 static inline elem_type12 bit_mask (size_t bit_idx) 13 {14   return (elem_type) 1 << (bit_idx % ELEM_BITS);15 }

來看bit_test的實現， 這里直接返回某一位的具體值。

這里直接用elem_idx獲取idx對應的index取出位， 然后和bit_mask做與操作， bit_mask就是返回了一個只有idx位是1其他都是0的一個數， 也就是說idx必須為1才返回true對bit_test來說， 否則false。

好， 至此， 對palloc_free_multiple只剩一行了：

1   bitmap_set_multiple (pool->used_map, page_idx, page_cnt, false);

/* Sets the CNT bits starting at START in B to VALUE. */voidbitmap_set_multiple (struct bitmap *b, size_t start, size_t cnt, bool value) {  size_t i;    ASSERT (b != NULL);  ASSERT (start <= b->bit_cnt);  ASSERT (start + cnt <= b->bit_cnt);  for (i = 0; i < cnt; i++)    bitmap_set (b, start + i, value);}

這里對位圖所有位都做了bitmap_set設置：

 1 /* Atomically sets the bit numbered IDX in B to VALUE. */ 2 void 3 bitmap_set (struct bitmap *b, size_t idx, bool value)  4 { 5   ASSERT (b != NULL); 6   ASSERT (idx < b->bit_cnt); 7   if (value) 8     bitmap_mark (b, idx); 9   else10     bitmap_reset (b, idx);11 }

很明顯這里mark就是設為1, reset就是置為0。

來看一下實現：

 1 /* Atomically sets the bit numbered BIT_IDX in B to true. */ 2 void 3 bitmap_mark (struct bitmap *b, size_t bit_idx)  4 { 5   size_t idx = elem_idx (bit_idx); 6   elem_type mask = bit_mask (bit_idx); 7  8   /* This is equivalent to `b->bits[idx] |= mask' except that it 9      is guaranteed to be atomic on a uniprocessor machine.  See10      the description of the OR instruction in [IA32-v2b]. */11   asm ("orl %1, %0" : "=m" (b->bits[idx]) : "r" (mask) : "cc");12 }13 14 /* Atomically sets the bit numbered BIT_IDX in B to false. */15 void16 bitmap_reset (struct bitmap *b, size_t bit_idx) 17 {18   size_t idx = elem_idx (bit_idx);19   elem_type mask = bit_mask (bit_idx);20 21   /* This is equivalent to `b->bits[idx] &= ~mask' except that it22      is guaranteed to be atomic on a uniprocessor machine.  See23      the description of the AND instruction in [IA32-v2a]. */24   asm ("andl %1, %0" : "=m" (b->bits[idx]) : "r" (~mask) : "cc");25 }

一樣， 最底層的實現依然是用匯編語言實現的， 兩個匯編語言實現的就是兩個邏輯： 1. b->bits[idx] |= mask 2. b->bits[idx] &= ~mask， 這里mask都是只有idx位為1, 其他為0的mask。

好， 到現在位置palloc_free_multiple已經分析完了， 整理一下邏輯：

其實就是把頁的位圖全部清0了， 清0代表這這個頁表的所有頁都是free的， 等于清空了頁目錄表中的所有頁面。

邏輯繼續向上回溯：

thread_schedule_tail其實就是獲取當前線程， 分配恢復之前執行的狀態和現場， 如果當前線程死了就清空資源。

schedule其實就是拿下一個線程切換過來繼續run。

thread_yield其實就是把當前線程扔到就緒隊列里， 然后重新schedule， 注意這里如果ready隊列為空的話當前線程會繼續在cpu執行。

最后回溯到我們最頂層的函數邏輯： timer_sleep就是在ticks時間內， 如果線程處于running狀態就不斷把他扔到就緒隊列不讓他執行。

好的， 至此我們對原來的timer_sleep的實現方式有了十分清楚的理解了， 我們也很清楚的看到了它的缺點：

線程依然不斷在cpu就緒隊列和running隊列之間來回， 占用了cpu資源， 這并不是我們想要的， 我們希望用一種喚醒機制來實現這個函數。

函數重新實現：

實現思路： 調用timer_sleep的時候直接把線程阻塞掉，然后給線程結構體加一個成員ticks_blocked來記錄這個線程被sleep了多少時間， 然后利用操作系統自身的時鐘中斷（每個tick會執行一次）加入對線程狀態的檢測， 每次檢測將ticks_blocked減1, 如果減到0就喚醒這個線程。

具體代碼：

 1 /* Sleeps for approximately TICKS timer ticks.  Interrupts must 2    be turned on. */ 3 void 4 timer_sleep (int64_t ticks) 5 { 6   if (ticks <= 0) 7   { 8     return; 9   }10   ASSERT (intr_get_level () == INTR_ON);11   enum intr_level old_level = intr_disable ();12   struct thread *current_thread = thread_current ();13   current_thread->ticks_blocked = ticks;14   thread_block ();15   intr_set_level (old_level);16 }

注意這里調用的thread_block：

 1 /* Puts the current thread to sleep.  It will not be scheduled 2    again until awoken by thread_unblock(). 3  4    This function must be called with interrupts turned off.  It 5    is usually a better idea to use one of the synchronization 6    primitives in synch.h. */ 7 void 8 thread_block (void) 9 {10   ASSERT (!intr_context ());11   ASSERT (intr_get_level () == INTR_OFF);12 13   thread_current ()->status = THREAD_BLOCKED;14   schedule ();15 }

線程的各種原理之前分析都已經剖析過了， 不作過多解釋。

給線程的結構體加上我們的ticks_blocked成員：

1     /* Record the time the thread has been blocked. */2     int64_t ticks_blocked;

然后在線程被創建的時候初始化ticks_blocked為0， 加在thread_create函數內：

1   t->ticks_blocked = 0;

然后修改時鐘中斷處理函數， 加入線程sleep時間的檢測， 加在timer_interrupt內：

1   thread_foreach (blocked_thread_check, NULL);

這里的thread_foreach就是對每個線程都執行blocked_thread_check這個函數：

 1 /* Invoke function 'func' on all threads, passing along 'aux'. 2    This function must be called with interrupts off. */ 3 void 4 thread_foreach (thread_action_func *func, void *aux) 5 { 6   struct list_elem *e; 7  8   ASSERT (intr_get_level () == INTR_OFF); 9 10   for (e = list_begin (&all_list); e != list_end (&all_list);11        e = list_next (e))12     {13       struct thread *t = list_entry (e, struct thread, allelem);14       func (t, aux);15     }16 }

aux就是傳給這個函數的參數。

然后， 給thread添加一個方法blocked_thread_check即可：

thread.h中聲明：

1 void blocked_thread_check (struct thread *t, void *aux UNUSED);

thread.c：

 1 /* Check the blocked thread */ 2 void 3 blocked_thread_check (struct thread *t, void *aux UNUSED) 4 { 5   if (t->status == THREAD_BLOCKED && t->ticks_blocked > 0) 6   { 7       t->ticks_blocked--; 8       if (t->ticks_blocked == 0) 9       {10           thread_unblock(t);11       }12   }13 }

thread_unblock就是把線程丟到就緒隊列里繼續跑：

 1 /* Transitions a blocked thread T to the ready-to-run state. 2    This is an error if T is not blocked.  (Use thread_yield() to 3    make the running thread ready.) 4  5    This function does not preempt the running thread.  This can 6    be important: if the caller had disabled interrupts itself, 7    it may expect that it can atomically unblock a thread and 8    update other data. */ 9 void10 thread_unblock (struct thread *t)11 {12   enum intr_level old_level;13 14   ASSERT (is_thread (t));15 16   old_level = intr_disable ();17   ASSERT (t->status == THREAD_BLOCKED);18   list_push_back (&ready_list, &t->elem);19   t->status = THREAD_READY;20   intr_set_level (old_level);21 }

好的， 這樣timer_sleep函數喚醒機制就實現了。

然后跑測試結果會是這樣的：

好， 我們還需要pass掉alarm_priority我們這個實驗一就算完成了，繼續搞~

Mission2:

實現優先級調度（2.2.3）

先來分析一下線程， 線程成員本身就有一個priority。

 1 struct thread 2   { 3     /* Owned by thread.c. */ 4     tid_t tid;                          /* Thread identifier. */ 5     enum thread_status status;          /* Thread state. */ 6     char name[16];                      /* Name (for debugging purposes). */ 7     uint8_t *stack;                     /* Saved stack pointer. */ 8     int priority;                       /* Priority. */ 9     struct list_elem allelem;           /* List element for all threads list. */10 11     /* Shared between thread.c and synch.c. */12     struct list_elem elem;              /* List element. */13 14 #ifdef USERPROG15     /* Owned by userprog/process.c. */16     uint32_t *pagedir;                  /* Page directory. */17 #endif18 19     /* Owned by thread.c. */20     unsigned magic;                     /* Detects stack overflow. */21 22     /* Record the time the thread has been blocked. */23     int64_t ticks_blocked;24   };

然后priority的約束：

1 /* Thread priorities. */2 #define PRI_MIN 0                       /* Lowest priority. */3 #define PRI_DEFAULT 31                  /* Default priority. */4 #define PRI_MAX 63                      /* Highest priority. */

我們之前分析timer_sleep的時候其實已經對線程的調度有了非常深刻的剖析了，這里實現優先級調度的核心思想就是： 維持就緒隊列為一個優先級隊列。

換一種說法： 我們在插入線程到就緒隊列的時候保證這個隊列是一個優先級隊列即可。

那么我們在什么時候會把一個線程丟到就緒隊列中呢？

1. thread_unblock

2. init_thread

3. thread_yield

那么我們只要在扔的時候維持這個就緒隊列是優先級隊列即可。

我們來看： thread_unblock現在丟進隊列里是這么干的：

1   list_push_back (&ready_list, &t->elem);

這個是直接扔到隊列尾部了， 我們并不希望這么做， 于是我們只要改一下這個扔的動作就可以了，因為調度的時候下一個thread是直接取隊頭的。

那么我們先來研究一下pintos的隊列是如何搞的，在/lib/kernel/：

 1 /* List element. */ 2 struct list_elem  3   { 4     struct list_elem *prev;     /* Previous list element. */ 5     struct list_elem *next;     /* Next list element. */ 6   }; 7  8 /* List. */ 9 struct list 10   {11     struct list_elem head;      /* List head. */12     struct list_elem tail;      /* List tail. */13   };

很常見的隊列數據結構， 繼續研究