PintOS Lab1

PintOS

背景

暑假在家闲着无事，不想荒废光阴，遂到CS自救指南中浏览了一番，发现了这个UCB，PKU，Stanford都在使用的操作系统实验，简单看了一下实验内容包含线程调度，用户程序，虚拟内存，文件系统。这时回看春季学期刚做的操作系统实验，瞬间感觉到university gap，然而等我真正开始做PintOS发现原来是student gap🙍，lyk老师的实验还是不错的，就是内容少了一点，并不能说少吧，毕竟当时最后一个实验也是从1点肝到1点肝了两天，如果引入PintOS我直接崩溃了，我是飞舞。

回到正题，看了PintOS实验文档后，非常想尝试，以此提升对OS的理解。然而文档是全英文，我这英语飞舞对英文文档是非常抗拒的(在开始着手做之后发现英文文档没有想象中那么难懂，不会的单词就查呗，查不到的就TM跳过，影响不大，不走出舒适区怎么提升技术水平呢)。下面直接开始了

环境配置

参照实验文档的Enviroment Building即可

Lab1

exercise1.1

来看要求

要求是要重新实现timer_sleep()函数。将其从忙等待改成进入睡眠等待唤醒机制。

先来看timer_sleep函数

void
timer_sleep (int64_t ticks)
{int64_t start = timer_ticks ();ASSERT (intr_get_level () == INTR_ON);while (timer_elapsed (start) < ticks)thread_yield();
}

这里出现了一堆函数，第一次看见可能会不知所措，不知道这些函数什么意思。那该怎么阅读呢。可以看函数名或变量名和注释来猜测这个函数或变量的意思。如果想知道函数具体实现细节，那就看源码。

首先来看这个timer_ticks()

/** Returns the number of timer ticks since the OS booted. */
int64_t
timer_ticks (void) 
{enum intr_level old_level = intr_disable ();int64_t t = ticks;intr_set_level (old_level);return t;
}

就是返回一个ticks值。这个ticks值是什么呢。就是一个计数器，每发生一次时钟中断ticks值+1,就是用来计时的一个变量。

再回到timer_sleep中，下面一行，这个ASSERT是什么，他是一个宏，就是推断括号内的条件成立，若不成立就会报错，可以用来debug。

再看下面一行，timer_elapsed是什么。这个看源码很容易看懂。就是返回当前ticks与传入参数的差值。传入参数start是最开始的ticks值。那么这一行意思就是，只要当前ticks和start的差小于传入参数，就执行thread_yield()。这个thread_yield是当前执行线程放弃执行，重新调度。重新调度后执行的线程可能还是这个线程。

那这函数意思就是，只要时间没到，这个线程就放弃执行，等待下一次调度,这就是忙等待sleep。学过OS都了解，busy waiting浪费CPU资源，所以现在要重新实现timer_sleep()

如何避免忙等待呢。线程有5个状态，当线程sleep的时候直接进入BLOCKED状态，时间到了再唤醒线程，这样就可以避免busy waiting。

sleep进入BLOCKED状态很简单，thread.c里面实现了thread_block()函数，调用即可。但是当线程block之后，怎么唤醒他呢，以及在什么时候唤醒呢。一种思路是每次时钟中断更新并检查睡眠的线程的剩余睡眠时间，时间到了就唤醒。另一种思路是维护一个按唤醒时间排序的线程队列，在每次时钟中断检查队头是否需要唤醒。这两种思路显然第二种性能更好。我采用了第一种，简单容易实现。（呵呵，最主要原因是我在写代码的时候参考了其他人的实现是用第一种思路，写文档的时候才想到第二种性能更好的方法）我建议读者自行实现第二种思路。

要知道线程剩余睡眠时间，就要给struct thread增加一个数据域表示剩余睡眠时间

新增一个blocked_ticks表示剩余睡眠ticks

struct thread{/* Owned by thread.c. */tid_t tid;                          /**< Thread identifier. */enum thread_status status;          /**< Thread state. */char name[16];                      /**< Name (for debugging purposes). */uint8_t *stack;                     /**< Saved stack pointer. */int priority;                       /**< Priority. */struct list_elem allelem;           /**< List element for all threads list. *//* Shared between thread.c and synch.c. */struct list_elem elem;              /**< List element. */#ifdef USERPROG/* Owned by userprog/process.c. */uint32_t *pagedir;                  /**< Page directory. */
#endif/* Owned by thread.c. */unsigned magic;                     /**< Detects stack overflow. */int64_t blocked_ticks;};

注意：每给一个结构体新增一个数据域都要在对应的init函数中初始化新增数据域，所以要在init_thread()中初始化blocked_ticks,初始化为0

重新实现timer_sleep()

/** Sleeps for approximately TICKS timer ticks.  Interrupts mustbe turned on. */
void
timer_sleep(int64_t ticks){if(ticks<=0)return;ASSERT(intr_get_level()==INTR_ON);enum intr_level old_level=intr_disable();thread_current()->blocked_ticks=ticks;thread_block();intr_set_level(old_level);
}

至此完成了线程进入sleep的工作，接下来实现唤醒机制

在timer.c中找到timer_interupt()

/** Timer interrupt handler. */
static void
timer_interrupt (struct intr_frame *args UNUSED)
{ticks++;thread_foreach(thread_check_blocked,NULL); //新增内容thread_tick ();
}

这个thread_foreach是thread.c中一个函数，对每个线程执行一次函数，这个函数是thread_foreach的第一个参数，在这里是thread_check_blocked(这是自己定义的函数，实现在下面)

/** decrease blocked thread->blocked_ticks and unblock t if t->blocked_ticks<=0 */ 
void
thread_check_blocked(struct thread *t){if(t->status==THREAD_BLOCKED){if(t->blocked_ticks>0)t->blocked_ticks--;if(t->blocked_ticks==0){thread_unblock(t);}}
}

至此就实现了，接下来进行编译和测试。我是使用docker配置环境。所以运行

docker run -it --rm --name pintos --mount type=bind,source=absolute/path/to/pintos/on/your/host/machine,target=/home/PKUOS/pintos pkuflyingpig/pintos bash

之后进入pintos/src/threads 执行make

然后进入./build执行make check即可看到测试结果。

如果读者把代码复制粘贴，并且block_ticks在init_thread()时赋值为0，那么是会不通过测试的。会在thread_unblock中触发ASSERT，要unblock的线程的状态不是BLOCKED。如果报了这样的错请自行debug

debug tips：既然是在thread_unblock中报错，那就找在哪里调用了thread_unblock

这个bug是我遇到过的，他跟blocked_ticks的初值有关，请仔细思考

exercise2.1

这exercise要实现一个线程优先级调度算法

task

先来看线程如何调度的

回看timer.c中的timer_interupt()函数

/** Timer interrupt handler. */
static void
timer_interrupt (struct intr_frame *args UNUSED)
{ticks++;thread_foreach(thread_check_blocked,NULL);thread_tick ();
}

这里有个thread_tick()函数之前没有讲。来看thread_tick()的源码

/** Called by the timer interrupt handler at each timer tick.Thus, this function runs in an external interrupt context. */
void
thread_tick (void) 
{struct thread *t = thread_current ();/* Update statistics. */if (t == idle_thread)idle_ticks++;
#ifdef USERPROGelse if (t->pagedir != NULL)user_ticks++;
#endifelsekernel_ticks++;/* Enforce preemption. */if (++thread_ticks >= TIME_SLICE)intr_yield_on_return ();
}

该函数在时钟中断调用，他作用就是统计线程执行了多少个ticks,倒数第二行的thread_ticks变量就记录了当前线程执行了多少个ticks,可以看到，当thread_ticks大于等于TIME_SLICE (default:4)就执行intr_yield_on_return()。可以猜测这个intr_yield_on_return()是与进行调度相关的。来看源码，在interrupts.c中

intr_yield_on_return (void) 
{ASSERT (intr_context ());yield_on_return = true;
}

源码很简单，就是让一个全局变量yield_on_return值为true。通过搜索找到这个全局变量在相同文件下的intr_handler()中被引用

/** Interrupt handlers. *//** Handler for all interrupts, faults, and exceptions.  Thisfunction is called by the assembly language interrupt stubs inintr-stubs.S.  FRAME describes the interrupt and theinterrupted thread's registers. */
void
intr_handler (struct intr_frame *frame) 
{bool external;intr_handler_func *handler;/* External interrupts are special.We only handle one at a time (so interrupts must be off)and they need to be acknowledged on the PIC (see below).An external interrupt handler cannot sleep. */external = frame->vec_no >= 0x20 && frame->vec_no < 0x30;if (external) {ASSERT (intr_get_level () == INTR_OFF);ASSERT (!intr_context ());in_external_intr = true;yield_on_return = false;}/* Invoke the interrupt's handler. */handler = intr_handlers[frame->vec_no];if (handler != NULL)handler (frame);else if (frame->vec_no == 0x27 || frame->vec_no == 0x2f){/* There is no handler, but this interrupt can triggerspuriously due to a hardware fault or hardware racecondition.  Ignore it. */}elseunexpected_interrupt (frame);/* Complete the processing of an external interrupt. */if (external) {ASSERT (intr_get_level () == INTR_OFF);ASSERT (intr_context ());in_external_intr = false;pic_end_of_interrupt (frame->vec_no); if (yield_on_return) thread_yield (); }
}

来解读以下这个函数，这函数是所有中断的处理函数，参数struct intr_frame这是一个结构体，是在中断发生时保存现场的，它里面包含寄存器的值等数据。然后external是布尔变量,它等于frame->vec_no >= 0x20 && frame->vec_no < 0x30。这个frame->vec_no就是中断号，时钟中断的中断号就是0x20。根据名字就可以推测这个external表示当前发生的中断是不是外部中断（时钟中断就是外部中断)。接下来这个intr_handler_func *handler就是一个函数指针，指向一个中断处理函数，handler = intr_handlers[frame->vec_no];这一行通过中断号获得了对应中断处理函数的指针。然后就进行handler(frame);。也就是我们的时钟中断函数就是在这里被调用的。还记得那个全局变量yield_on_return吗。他就在这个函数的末尾

if (external) {ASSERT (intr_get_level () == INTR_OFF);ASSERT (intr_context ());in_external_intr = false;pic_end_of_interrupt (frame->vec_no); if (yield_on_return) //这个全局变量thread_yield (); }

timer_interrupt函数中调用了thread_ticks,而thread_ticks中调用了intr_yield_on_return()将这个全局变量变为true。然后timer_interrupt返回后就会继续执行到这里，这时候这个全局变量是true的，那么就会执行thread_yield()也就是重新调度。

OK，至此就分析出了线程是如何调度的，除了sleep外，操作系统也会在时钟中断检查线程运行时间是否超过TIME_SLICE,超时就调度。可以猜测，当前系统的线程调度算法是Round—Robin。接下来将其改成优先级调度算法

看thread_yield()函数

/** Yields the CPU.  The current thread is not put to sleep andmay be scheduled again immediately at the scheduler's whim. */
void
thread_yield (void) 
{struct thread *cur = thread_current ();enum intr_level old_level;ASSERT (!intr_context ());old_level = intr_disable ();if (cur != idle_thread) list_push_back (&ready_list, &cur->elem);   //将当前线程插入就绪队列ready_lsitcur->status = THREAD_READY;schedule ();intr_set_level (old_level);
}

倒数第二行的schedule()就是跟调度直接相关的函数了，阅读一下

static void
schedule (void) 
{struct thread *cur = running_thread ();struct thread *next = next_thread_to_run ();struct thread *prev = NULL;ASSERT (intr_get_level () == INTR_OFF);ASSERT (cur->status != THREAD_RUNNING);ASSERT (is_thread (next));if (cur != next)prev = switch_threads (cur, next);thread_schedule_tail (prev);
}

现在最主要关心的是什么，就是调度算法，而调度算法就需要知道下一个执行线程是哪个,在本函数中，switch_thread()是上下文切换的，thread_schedule_tail()给DYING_THREAD处理后事的，不需要过多关注，而next_thread_to_run()才是我们要关注的。

阅读next_thread_to_run()

static struct thread *
next_thread_to_run (void) 
{if (list_empty (&ready_list))return idle_thread;elsereturn list_entry (list_pop_front (&ready_list), struct thread, elem);
}

如果ready_list非空，就返回ready_list的第一个节点线程。现在要实现优先级调度，是不是只需要让这个next_thread_to_run返回优先级最大的线程，并将其从ready_list删掉即可。这样就有两种思路，一种是让ready_list变成一个优先级队列，在插入的时候维护优先级顺序。第二种就是在返回next_thread_to_run的时候直接遍历找到最大值并pop调。第一种插入复杂度O(n),求max复杂度O(1),第二种反过来。但由于插入次数一定不大于删除次数，所以第二种性能可能更好一些。（虽然二叉堆性能比这两种更好但em，读者想使用二叉堆请自行实现内核二叉堆数据结构）。我在这里选择第一种，为何，因为list.c中实现了list_insert_order按序插入，所以只需要实现比较函数即可。

实现比较函数

/** Return true if a > b*/
bool thread_pri_bge(const struct list_elem *a,const struct list_elem *b,void *aux){struct thread* t_a=list_entry(a,struct thread,elem);struct thread* t_b=list_entry(b,struct thread,elem);if(t_a->priority>t_b->priority)return true;else return false;
}

关于内核中的list与平常所使用的数据结构形式不一样，读者可自行阅读源码，或查看
内核链表解读

接下来把所有thread.c中所有list_push_back替换成list_insert_order

void
thread_unblock (struct thread *t) 
{enum intr_level old_level;ASSERT (is_thread (t));old_level = intr_disable ();ASSERT (t->status == THREAD_BLOCKED);// list_push_back (&ready_list, &t->elem);list_insert_ordered(&ready_list,&t->elem,thread_pri_bge,NULL);t->status = THREAD_READY;intr_set_level (old_level);
}void
thread_yield (void) 
{struct thread *cur = thread_current ();enum intr_level old_level;ASSERT (!intr_context ());old_level = intr_disable ();if (cur != idle_thread) // list_push_back (&ready_list, &cur->elem);list_insert_ordered(&ready_list,&cur->elem,thread_pri_bge,NULL);cur->status = THREAD_READY;schedule ();intr_set_level (old_level);
}static void
init_thread (struct thread *t, const char *name, int priority)
{enum intr_level old_level;ASSERT (t != NULL);ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);ASSERT (name != NULL);memset (t, 0, sizeof *t);t->status = THREAD_BLOCKED;strlcpy (t->name, name, sizeof t->name);t->stack = (uint8_t *) t + PGSIZE;t->priority = priority;t->magic = THREAD_MAGIC;t->blocked_ticks=0;old_level = intr_disable ();// list_push_back (&all_list, &t->allelem);list_insert_ordered(&all_list,&t->allelem,thread_pri_bge,NULL);intr_set_level (old_level);
}

exercise2.2.1

该练习涉及优先级调度的优先级反转问题

priority为H,M,L的三个线程，当H等待L持有的锁时，同时M在等待队列，则系统不会将CPU立刻给L而是给M。这样H就需要等待M结束（这并不合理）

解决方案:采用优先级继承方式，当高优先级thread等待低优先级资源时，强制提升低优先级线程优先级。当然，这只是一个大致方向，实际实现需要考虑很多细节

先来考虑一个问题，一个线程t，其持有若干个锁，每个锁都有若干个线程等待该锁释放。那么这个线程t的实际优先级priority就应该是max(线程t本身的优先级，max(所有等待t拥有的锁的线程的实际优先级))。按这种方式就能解决上面H，M，L三线程优先级反转问题，还能解决后续更加复杂的情况。

那么该如何设计这种结构呢？可以先定义锁的优先级：锁的优先级定义为所有等待该锁的线程中最大实际优先级。注意区分线程实际优先级和基本优先级，基本优先级在创建线程定义，调用thread_set_priority改变，其他时候不会变。而实际优先级取决于基本优先级和持有锁的优先级。

暂时先写到这里，写文档真是非常耗时，先摆一会，等中秋节过了再继续更新

内核链表解读

Pintos本身实现了一些数据结构,在src/lib/kernel/ 下可以找到。其中就包含了最基本的数据结构链表list.c。在这里将带读者阅读list.c，理解内核数据结构是如何实现的。

先读头文件，打开list.h。

/** List element. */
struct list_elem {struct list_elem *prev;     /**< Previous list element. */struct list_elem *next;     /**< Next list element. */};/** List. */
struct list {struct list_elem head;      /**< List head. */struct list_elem tail;      /**< List tail. */};

首先就是这两个结构体，很明显list_elem就是链表的节点,包含prev和next指针。这和平常写的或用的链表不太一样，它除了这两指针外没有其他数据。我们在学数据结构时一般写的链表里面都是包含其他数据的，像C++STL中的list<typename T>也是带有T类型数据的。而这里的链表节点就是单纯的一个节点，那是如何让其携带数据的呢。来看一个例子。

struct thread{/* Owned by thread.c. */tid_t tid;                          /**< Thread identifier. */enum thread_status status;          /**< Thread state. */char name[16];                      /**< Name (for debugging purposes). */uint8_t *stack;                     /**< Saved stack pointer. */int base_prioriy;int priority;                       /**< Priority. */struct list_elem allelem;           /**< List element for all threads list. *//* Shared between thread.c and synch.c. */struct list_elem elem;              /**< List element. */}

这是thread结构体中的成员。最后一个是struct list_elem类型。也就是说，他并不是让链表节点携带某类数据，而是让某类结构体携带链表节点。那是如何通过list_elem来访问携带该list_elem的结构体呢，也就是如何通过链表节点访问其背后的数据呢。来看后面一段代码

/** Converts pointer to list element LIST_ELEM into a pointer tothe structure that LIST_ELEM is embedded inside.  Supply thename of the outer structure STRUCT and the member name MEMBERof the list element.  See the big comment at the top of thefile for an example. */
#define list_entry(LIST_ELEM, STRUCT, MEMBER)           \((STRUCT *) ((uint8_t *) &(LIST_ELEM)->next     \- offsetof (STRUCT, MEMBER.next)))

这个宏实现了从链表节点获得包含该链表节点的结构体指针。如何使用，来看个例子

struct thread* t;
t=list_entry (list_pop_front (&ready_list), struct thread, elem);

list_entry第一个参数输入某个链表节点的指针，第二个参数输入包含该节点的结构体类型，第三个参数是该结构体类型定义中链表节点对应的成员名称,宏返回一个第二个参数的指针。

读到这里，读者可能会有一个疑惑，struct thread中有两个struct list_elem的成员，为什么list_entry中第三个参数是elem而不是allelem。这和这两个成员的含义有关，elem是作为ready_list的节点的，而allelem是作为所有线程链表all_list的节点的。list_entry中第一个参数是ready_list的头节点，固然第三个参数就是elem。这个list_entry就是通过第三个参数的成员在struct thread中的偏移字节数和elem的地址计算出struct thread的地址。

然后剩下的就是list相关的函数了，和平常接触的list区别不大，读者都应该能自行阅读并理解.