Pintos-斯坦福大学操作系统Project详解-Project1

转载请注明出处。

前言：

本实验来自斯坦福大学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   };

很常见的队列数据结构， 继续研究