Task one 今天来谈第一个project 的第二个问题--优先级调度问题。
一、内容介绍 现代操作系统，并发是基本特征。当有多个线程在系统中运行时，一般是通过排队的方式采用RR（时间片轮转法）策略轮流占用CPU的，其中最简单，看似最公平的调度策略是FCFS，但是这种方法不能够区分线程执行的轻重缓急，看似公平实则不公平，容易造成系统性能低下。因此，操作系统设计者通常会赋予线程优先级，并采用高优先级者先调用的策略，兼顾公平与效率。在原始的Pintos系统中关于优先级调度没有考虑优先级问题，本实现的内容是为pintos建立优先级调度机制，并确保在任何时刻在CPU上运行的都是最高优先级线程。 二、分析与设计 首先回顾一下线程的状态转换，线程的常见状态分为以下三种running,ready,block.在之前的操作系统课程中，我们已经学过基本的状态转换，如下。 CPU的调度是指从ready中选择线程占有CPU,状态转换是ready->run,原则是高优先级的线程先于低优先级的线程调度，所以当出现最高优先级的线程可以抢占CPU。这个修改核心思想分为两个方面，一是.当新优先级的线程线程出现时，要与原有的最高优先级线程进行比较，判断是否进行CPU抢占，二是进行结果的处理，对于高优先级线程，占有CPU，对于低优先级线程要有序插入ready_list中。 A.在判断抢占CPU时，于是出现两种可能的情况：  (1)有新线程生成，线程的最后状态是ready,此时系统中的最高优先级线程是正在运行的线程，因此需要新线程与runnning线程进行优先级比较。新线程的优先级的高于当前正在运行的线程，则新的线程应该迫使当前的线程让出CPU，在thread_yield()中会进行重新的线程调度，由于此时新线程优先级最高，则必定调度新线程，即出现新线程抢占CPU的现象。 (2)当前正在运行的线程优先级改变，尤其指优先级降低时，此时系统中的最高优先级线程是ready_list的队头线程，（注意ready_list此处为有序队列），若低于ready_list对列中的最高优先级，则出现新线程让出CPU的线程。     分析如下图示： B.在进行结果处理时，出现了两种可能情况。  (1)对于抢占上CPU的线程，那么自然就是在CPU上运行了，其状态是running.我们不需要进行特殊改变。  (2) 对于没有抢占上CPU的线程，自然要放在ready_list中了。上文已经提到过，我们在进行放入时要进行有序放入ready_list中，源码中采用的是list_push_back(),此函数只是简单的将线程放入队首，不能满足我们的要求。为了进行有序排放，我们可以选用list_insert_order()函数，通过比较优先级，将线程插入到ready_list中的合适位置。 实现如下图示功能： 三、详细实现 Pintos系统中函数调用关系如下： 具体实现分以下几种情况讨论： 关于所用到的各种函数调用关系 1.有新生线程生成 thread_create();           //thread.c 分析： 在thread_creat()中，创建新线程的过程是： init_thread()(设置线程的状态是THREAD_BLOCKED，设置线程的初始优先级,将此线程放入all_list队列中))--->设置线程的上下文环境---> thread_unblock()（解阻塞该线程，放入ready_list队列中） 状态转换是block->ready->running或者block->ready 属于上述中A类中（1）的新生线程（新优先级线程的第一种情况，系统创建新线程） 理论修改： 当新线程解阻塞之后放入reday_list中时，应该先比较该新线程的优先级与当前CPU正在运行的线程的优先级，是否发生CPU抢占。对于结果需要分情况处理 源码修改： ..... Thread_unblock(); /************************************************************* //add    If(priority>thread_current()->prioriity)          //if--抢占CPU Thread_yield()；   //else--thread_unblock()中已经将其先放入ready_list队中了，那么此时不做处理 //************************************************************ ........   1.当前线程自己改变优先级 thread_set_priority()        //thread.c   分析： 此函数是修改当前线程的优先级，那么当增高优先级时，自然还是最高优先级线程，不做处理，当优先级下降时，可能不是系统中的最高优先级，需要进行处理。 属于上述中A类中（2） 状态转换是running或者running->block 理论修改： 在设置完新线程的优先级之后，与ready_list队头的线程进行优先级比较，是否让出CPU，结果分情况处理。 源码修改： Thread_current()->pirority=new_priority; //*********************************************************************** //add if(list_entry(list_begin(&ready_list),struct thread,elem)->priority >=new_priority) thread_yield(); //********************************************************************** 此处对list_entry（）函数做格外说明，函数原型为宏定义，在list.h中可以找到； 我们一直提到的list队列，包括ready_list,all_list或者waiters等，直观意义上说是指的是线程队列，那么在list结构体中真的存的是线程体吗，或者说list中的元素elem（也可称为结点）是一个线程体吗？答案是否定的，在list中的元素是struct list_elem,队列成员是list_elem,那么list_elem又是什么呢？它与thread又有什么联系呢？下面我们看一下thread的结构体定义： struct thread { 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. */ struct list_elem elem;        /* List element. */ } 现在应该可以直接看出list_elem与thread的关系，每一个thread都会有一个专属于自己的elem成员，这个elem成员用于作为各种队列元素来代表自己，其实这里我想到了关于健值的含义，个人感觉elem好像是thread的健值一样。 分析了这么多，list_entry（）函数的作用到底是什么，可以看到我们通过使用list_entry（）函数得到了一个线程（list_entry(...)->priority）,再看list_entry（）的三个传入参数list_begin(&ready_list)，struct thread,elem，那么我们是不是可以大胆猜想list_entry()函数通过elem在ready_list中查找，找到了begin元素相应的thread.其实list_entry()函数的作用就是如此，不仅可以在ready_list中查找，还可以在all_list,和waiters中查找相应的实体结构。   2.关于结果处理情况 主要是在插入队列中时，应该有序插入，所有关于插入情况讨论如下： 所谓发生队列插入，可以向ready_list或者waiter中加入新的元素，由上述转换图可以看出，分为两大类情况   A.向ready_list中插入新的元素 (1)running->ready 可能发生在A-2中，当前线程的优先级被超越，因此thread_yield(),在thread_yield（）中已经将线程的状态由running->ready，因此我们不需要改变。 (2)block->ready. 自然会想到unblock，即解阻塞，将线程状态由阻塞变为reday,插入ready_list中，至于之后应该怎么调度，那就不是unblock的工作了，unblock只负责状态转换一次，其实，最早考虑到要不要在unblock的函数中加入重新调度的函数，表面上看似乎是合理的，但是仔细分析，这样做的话，其实你已经改变了源码中thread_unblock()的含义，此函数可以将线程的状态由block变为ready!这样做即使不影响现在的函数使用，但是有可能影响源码中其他关于thread_unblock的使用，你不经意改变了源码中函数的意思，必然与源码中的此函数其它使用情况产生冲突，这个道理是我想到状态转换图时突然明白的，之前试着改了，但是一直疑惑为什么没有结果。 源码修改： thread_unblock() /*list_push_back (&ready_list, &t->elem); */（原程序） list_insert_ordered(&ready_list, &t->elem, pri_more, NULL);（新的改法） 这里涉及了一个pri_more函数，这个函数是优先级比较函数 pri_more(const struct list_elem *a,const struct list_elem *b,void *aux) //作用对象：线程 { struct thread *a_thread,*b_thread; a_thread=list_entry(a,struct thread, elem); b_thread=list_entry(b,struct thread, elem); return (a_thread->priority > b_thread->priority); } 函数直观很好理解，在此不做说明。   B.向阻塞队列中插入新的元素，与信号量函数有关 （1）sema_down()     -----P操作 在申请信号量时，若信号量不够，则发生阻塞，对sema->waiter中的线程按照优先级有序插入 源码修改： //************************************************************************ //list_push_back (&sema->waiters, &thread_current ()->elem) (原程序) list_insert_ordered(&sema->waiters, &thread_current ()->elem, pri_more, NULL); (新方法) //**************************************************************************   （2）sema_up()       -----V操作 一个信号量可能会阻塞多个线程，应将优先级最高的线程从 block 态转换为ready 态。 源码修改： 加入定义： //****************************************************************** struct thread *t=NULL; 修改if (!list_empty (&sema->waiters)) 条件分支中： /* thread_unblock (list_entry (list_pop_front (&sema->waiters),struct thread, elem)); */（原程序） { t = list_entry (list_pop_front (&sema->waiters), struct thread, elem); thread_unblock (t); }   在sema->value++; 后加入： if(t != NULL && t->priority > thread_current()->priority) thread_yield(); //*******************************************************************   (3)cond_wait() 对等待条件变量的list(waiters)按照优先级有序插入 源码修改： //******************************************************************* 在 struct semaphore_elem 中加入新属性： int sema_priority;         //表示信号量的优先级 /* list_push_back (&cond->waiters, &waiter.elem); */ (原代码) waiter.sema_priority = thread_current ()->priority; list_insert_ordered (&cond->waiters, &waiter.elem, cond_priority, NULL); //******************************************************************* 在这里同样会设计一个优先级比较函数，是比较线程关于信号量的优先级，与上文不同。 Bool cond_priority (const struct list_elem *lhs, const struct list_elem *rhs, void *aux UNUSED) //功能与pri_more 类似，作用对象：semaphore_elem { struct semaphore_elem *l, *r; l = list_entry (lhs, struct semaphore_elem, elem); r = list_entry (rhs, struct semaphore_elem, elem); return (l->sema_priority > r->sema_priority); } 四、实验结果 实验结果截图如下：