pintos-thread

pintos-threads

中文文档

机翻文档

实验环境

系统名：Ubuntu 20.04.2 LTS操作系统环境

操作系统类型：64位

模拟器：qemu模拟器

实验过程与分析、调试过程

1、Pintos内核分析

在/threads/init.c中查找main，找到系统入口函数如下：

/* Pintos main program. */
int
main (void)
{char **argv;/* Clear BSS. */  bss_init ();/* Break command line into arguments and parse options. */argv = read_command_line ();argv = parse_options (argv);/* Initialize ourselves as a thread so we can use locks,then enable console locking. */thread_init ();console_init ();  /* Greet user. */printf ("Pintos booting with %'"PRIu32" kB RAM...\n",init_ram_pages * PGSIZE / 1024);/* Initialize memory system. */palloc_init (user_page_limit);malloc_init ();paging_init ();/* Segmentation. */
#ifdef USERPROGtss_init ();gdt_init ();
#endif/* Initialize interrupt handlers. */intr_init ();timer_init ();kbd_init ();input_init ();
#ifdef USERPROGexception_init ();syscall_init ();
#endif/* Start thread scheduler and enable interrupts. */thread_start ();serial_init_queue ();timer_calibrate ();#ifdef FILESYS/* Initialize file system. */ide_init ();locate_block_devices ();filesys_init (format_filesys);
#endifprintf ("Boot complete.\n");/* Run actions specified on kernel command line. */run_actions (argv);/* Finish up. */shutdown ();thread_exit ();
}

系统启动时，会初始化BSS，读取并分析命令行，初始化主线程、终端、内存、中断及时钟，开启线程调度，开中断，并最终运行程序后退出。

BSS段通常是指用来存放程序中未初始化的或者初始化为0的全局变量和静态变量的一块内存区域。特点是可读写的，在程序执行之前BSS段会自动清0。

可执行程序包括BSS段、数据段、代码段。

为了了解中断机制，首先在/device/timer.h中可以看到：

#define TIMER_FREQ 100

即每秒100次时钟中断，定时为0.01秒。操作系统内核通过中断来获得CPU时间。

然后在timer.c中查找timer_init函数：

/* Sets up the timer to interrupt TIMER_FREQ times per second,and registers the corresponding interrupt. */
void
timer_init (void) 
{pit_configure_channel (0, 2, TIMER_FREQ);intr_register_ext (0x20, timer_interrupt, "8254 Timer");
}

其中0x20是中断向量号；timer_interrupt是中断处理函数的入口地址，每当时钟定时时间到就调用该函数（周期性调用）；”8254
Timer”是时钟。

查找timer_interrupt函数：

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

即每次时钟到时全局变量ticks自增1。

再进入/threads，先查看interrupt.h：

enum intr_level
{INTR_OFF,INTR_ON
};

再查看thread.h中的thread结构体：

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. *//* 添加代码 */int64_t ticks_blocked;              /* 需要被阻塞线程的时间. */int base_priority;                  /* 用于记录线程未被捐赠时的优先级. */struct list locks_holding;          /* 线程持有的锁的列表. */struct lock *lock_waiting;         /* 线程正在等待的锁. */int nice;                           /* Nice value. */fixed_point_t recent_cpu;                 /* Recent CPU. *//* 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. *//* My Implementation */struct semaphore wait;              /* semaphore for process_wait */int ret_status;                     /* return status */struct list files;                  /* all opened files */struct file *self;                  /* the image file on the disk */struct thread *parent;              /* parent process *//* == My Implementation */
#endif/* Owned by thread.c. */unsigned magic;                     /* Detects stack overflow. */};

以及thread的状态类型：

/* States in a thread's life cycle. */
enum thread_status{THREAD_RUNNING,     /* Running thread. */THREAD_READY,       /* Not running but ready to run. */THREAD_BLOCKED,     /* Waiting for an event to trigger. */THREAD_DYING        /* About to be destroyed. */};

在main函数中看到，运行测试的函数是run_actions，查找：

/* Executes all of the actions specified in ARGV[]up to the null pointer sentinel. */
static void
run_actions (char **argv) 
{/* An action. */struct action {char *name;                       /* Action name. */int argc;                         /* # of args, including action name. */void (*function) (char **argv);   /* Function to execute action. */};/* Table of supported actions. */static const struct action actions[] = {{"run", 2, run_task},
#ifdef FILESYS{"ls", 1, fsutil_ls},{"cat", 2, fsutil_cat},{"rm", 2, fsutil_rm},{"extract", 1, fsutil_extract},{"append", 2, fsutil_append},
#endif{NULL, 0, NULL},};while (*argv != NULL){const struct action *a;int i;/* Find action name. */for (a = actions; ; a++)if (a->name == NULL)PANIC ("unknown action `%s' (use -h for help)", *argv);else if (!strcmp (*argv, a->name))break;/* Check for required arguments. */for (i = 1; i < a->argc; i++)if (argv[i] == NULL)PANIC ("action `%s' requires %d argument(s)", *argv, a->argc - 1);/* Invoke action and advance. */a->function (argv);argv += a->argc;}}

第311行中可以看到run命令是actions结构体数组的第一个元素，而第324行的a则是指向结构体数组的指针，即第一个元素的地址。

所以，第340行a->function(argv)即以argv参数运行actions[0]的第三个参数，即run_task[argv]，其中argv[0]”run”,argv[1]”alarm-multiple”。

查找run_task函数：

/* Runs the task specified in ARGV[1]. */
static void
run_task (char **argv)
{const char *task = argv[1];printf ("Executing '%s':\n", task);
#ifdef USERPROGprocess_wait (process_execute (task));
#elserun_test (task);
#endifprintf ("Execution of '%s' complete.\n", task);
}

第290行相当于run_test(“alarm-multiple”);

在/tests/threads/test.c中查找run_test函数：

/* Runs the test named NAME. */
void
run_test (const char *name) 
{const struct test *t;for (t = tests; t < tests + sizeof tests / sizeof *tests; t++)if (!strcmp (name, t->name)){test_name = name;msg ("begin");t->function ();msg ("end");return;}PANIC ("no test named \"%s\"", name);
}

这里遍历了tests数组，tests数组的定义在同一文件中：

static const struct test tests[] = {{"alarm-single", test_alarm_single},{"alarm-multiple", test_alarm_multiple},{"alarm-simultaneous", test_alarm_simultaneous},{"alarm-priority", test_alarm_priority},{"alarm-zero", test_alarm_zero},{"alarm-negative", test_alarm_negative},{"priority-change", test_priority_change},{"priority-donate-one", test_priority_donate_one},{"priority-donate-multiple", test_priority_donate_multiple},{"priority-donate-multiple2", test_priority_donate_multiple2},{"priority-donate-nest", test_priority_donate_nest},{"priority-donate-sema", test_priority_donate_sema},{"priority-donate-lower", test_priority_donate_lower},{"priority-donate-chain", test_priority_donate_chain},{"priority-fifo", test_priority_fifo},{"priority-preempt", test_priority_preempt},{"priority-sema", test_priority_sema},{"priority-condvar", test_priority_condvar},{"mlfqs-load-1", test_mlfqs_load_1},{"mlfqs-load-60", test_mlfqs_load_60},{"mlfqs-load-avg", test_mlfqs_load_avg},{"mlfqs-recent-1", test_mlfqs_recent_1},{"mlfqs-fair-2", test_mlfqs_fair_2},{"mlfqs-fair-20", test_mlfqs_fair_20},{"mlfqs-nice-2", test_mlfqs_nice_2},{"mlfqs-nice-10", test_mlfqs_nice_10},{"mlfqs-block", test_mlfqs_block},};

于是第56行t->function()等价于test_alarm_multiple()。

同目录下查看alarm_wait.c，可以看到该函数调用了test_sleep(5,7)，查找test_sleep函数，核心代码：

static void
test_sleep (int thread_cnt, int iterations) 
{struct sleep_test test;struct sleep_thread *threads;int *output, *op;int product;int i;/* This test does not work with the MLFQS. */ASSERT (!thread_mlfqs);msg ("Creating %d threads to sleep %d times each.", thread_cnt, iterations);msg ("Thread 0 sleeps 10 ticks each time,");msg ("thread 1 sleeps 20 ticks each time, and so on.");msg ("If successful, product of iteration count and");msg ("sleep duration will appear in nondescending order.");/* Allocate memory. */threads = malloc (sizeof *threads * thread_cnt);output = malloc (sizeof *output * iterations * thread_cnt * 2);if (threads == NULL || output == NULL)PANIC ("couldn't allocate memory for test");/* Initialize test. */test.start = timer_ticks () + 100;test.iterations = iterations;lock_init (&test.output_lock);test.output_pos = output;/* Start threads. */ASSERT (output != NULL);for (i = 0; i < thread_cnt; i++){struct sleep_thread *t = threads + i;char name[16];t->test = &test;t->id = i;t->duration = (i + 1) * 10;t->iterations = 0;snprintf (name, sizeof name, "thread %d", i);thread_create (name, PRI_DEFAULT, sleeper, t);}/* Wait long enough for all the threads to finish. */timer_sleep (100 + thread_cnt * iterations * 10 + 100);/* Acquire the output lock in case some rogue thread is stillrunning. */lock_acquire (&test.output_lock);/* Print completion order. */product = 0;for (op = output; op < test.output_pos; op++) {struct sleep_thread *t;int new_prod;ASSERT (*op >= 0 && *op < thread_cnt);t = threads + *op;new_prod = ++t->iterations * t->duration;msg ("thread %d: duration=%d, iteration=%d, product=%d",t->id, t->duration, t->iterations, new_prod);if (new_prod >= product)product = new_prod;elsefail ("thread %d woke up out of order (%d > %d)!",t->id, product, new_prod);}/* Verify that we had the proper number of wakeups. */for (i = 0; i < thread_cnt; i++)if (threads[i].iterations != iterations)fail ("thread %d woke up %d times instead of %d",i, threads[i].iterations, iterations);lock_release (&test.output_lock);free (output);free (threads);
}

可以看到for循环内创建了thread_cnt个线程，第97行使每个线程调用timer_sleep共iteration次。所以test_sleep(5,7)即创建5个线程，每个线程调用sleep共7次。

回到/device/timer.c中查找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);while(timer_elapsed(start)<ticks)thread_yield;
}

timer_sleep通过不断轮询检查经过时间是否达到参数ticks，若还没达到则调用thread_yield函数，达到了ticks就会结束休眠。
在/threads/thread.c中查找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); cur->status = THREAD_READY;schedule ();intr_set_level (old_level);
}

thread_yield中调用了schedule函数重新调度线程。
继续查找schedule函数：

/* Schedules a new process.  At entry, interrupts must be off andthe running process's state must have been changed fromrunning to some other state.  This function finds anotherthread to run and switches to it.It's not safe to call printf() until thread_schedule_tail()has completed. */
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);
}

schedule函数执行了以后会把当前线程放进队列里并调度下一个线程。

因此，timer_sleep轮询时，thread_yield会通过schedule函数把当前线程放进ready队列，并调度下一个线程，线程调度时要保证中断关闭。
综上所述，得到pintos中断控制流程如下图：

2、Threads忙等问题分析及实践过程

分析timer_sleep函数，首先查找它调用的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;
}

查找intr_disable，试图找出其返回值：

/* Disables interrupts and returns the previous interrupt status. */
enum intr_level
intr_disable (void) 
{enum intr_level old_level = intr_get_level ();/* Disable interrupts by clearing the interrupt flag.See [IA32-v2b] "CLI" and [IA32-v3a] 5.8.1 "Masking MaskableHardware Interrupts". */asm volatile ("cli" : : : "memory");return old_level;
}

/* Interrupts on or off? */
enum intr_level {INTR_OFF,             /* Interrupts disabled. */INTR_ON               /* Interrupts enabled. */};

函数通过汇编关闭终端，并返回关中断前的中断状态。

也就是说，enum intr_level old_level =intr_disable();关闭中断并保存之前的状态，intr_set_level(old_level);恢复之前的中断状态。这两条语句中间是原子操作。

根据之前对timer_sleep的分析，知道了：thread_yield中，如果当前线程不是空闲线程，就将它插入队列尾部，状态变为THREAD_READY。因此，线程将不断在就绪队列和运行队列中切换，不断占用CPU资源，造成了忙等问题。

于是考虑将线程阻塞，记录该线程剩余被阻塞的时间ticks_blocked，并利用时钟中断检测所有线程的状态，每次使对应的ticks_blocked自减1，如果为0则唤醒对应线程。

在thread.h中添加成员：

在thread.c的thread_create中加入初始化语句：

为了在时钟中断时能遍历所有线程，我们使用thread_foreach函数：

/* Invoke function 'func' on all threads, passing along 'aux'.This function must be called with interrupts off. */
void
thread_foreach (thread_action_func *func, void *aux)
{struct list_elem *e;ASSERT (intr_get_level () == INTR_OFF);for (e = list_begin (&all_list); e != list_end (&all_list);e = list_next (e)){struct thread *t = list_entry (e, struct thread, allelem);func (t, aux);}
}

在timer.c中的timer_interrupt函数里使用该函数：

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

在thread.h中声明checkInvoke函数，在thread.c中实现：

/* Solution Code */
void
checkInvoke(struct thread *t, void *aux UNUSED)
{if (t->status == THREAD_BLOCKED && t->ticks_blocked > 0){--t->ticks_blocked;if (t->ticks_blocked == 0)thread_unblock(t);}
}

最后修改timer_sleep函数：

/* Sleeps for approximately TICKS timer ticks.  Interrupts mustbe turned on. */
void
timer_sleep (int64_t ticks) 
{/*int64_t start = timer_ticks();ASSERT (intr_get_level () == INTR_ON);while (timer_elapsed(start) < ticks)thread_yield();*//* 添加代码 *//* alarm-negative && alarm-zero */if (ticks <= 0) return;ASSERT (intr_get_level () == INTR_ON);enum intr_level old_level = intr_disable();/* 阻塞当前线程的ticks */thread_current()->ticks_blocked = ticks;thread_block();intr_set_level(old_level);
}

即阻塞当前线程ticks时长，这一操作是原子的。

Make Check通过。

3、Threads优先级调度问题分析及实践过程

首先thread.h中可以看到thread结构体中有priority成员，且有：

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

为了通过alarm-priority，只需要维护就绪队列为一个优先队列即可，按优先级从高到低排序。也就是说，只需要保证线程插入就绪队列时插入到了合适的位置。

经过对pintos源码的分析，知道了只有三个函数会插入线程到就绪队列：init_thread,
thread_unblock, thread_yield。

以thread_yield为例：

old_level = intr_disable ();if (cur != idle_thread)list_push_back (&ready_list, &cur->elem); 

这里直接插入到队列尾部，因此我们不能直接使用list_push_back函数。

阅读链表实现源码，在/lib/kernel/list.h中。我们发现了list_insert_ordered看起来能实现插入时维持顺序

/* Inserts ELEM in the proper position in LIST, which must besorted according to LESS given auxiliary data AUX.Runs in O(n) average case in the number of elements in LIST. */
void
list_insert_ordered (struct list *list, struct list_elem *elem,list_less_func *less, void *aux)
{struct list_elem *e;ASSERT (list != NULL);ASSERT (elem != NULL);ASSERT (less != NULL);for (e = list_begin (list); e != list_end (list); e = list_next (e))if (less (elem, e, aux))break;return list_insert (e, elem);
}

只需实现一个比较函数（先在thread.h中声明了）：

/* 线程优先级比较函数. */
bool
thread_cmp_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED)
{return list_entry(a, struct thread, elem)->priority > list_entry(b, struct thread, elem)->priority;
}

随后修改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_insert_ordered(&ready_list, &cur->elem, (list_less_func *)&thread_cmp_priority, NULL);//list_push_back (&ready_list, &cur->elem);cur->status = THREAD_READY;schedule ();intr_set_level (old_level);
}

最后，对init_thread和thread_unblock中的list_push_back函数替换为list_insert_ordered即可。

接下来实现优先级变化和抢占调度，即priority-change和priority-preempt。
只能在线程优先级发生变化时将其插入就绪队列，这样才能对所有线程重新排序。
同理，在创建线程时，如果优先级高于当前线程，当前线程也会被插入就绪队列。

因此修改thread.c中的thread_set_priority，并且，在thread_create的最后，根据新线程优先级判断是否要将当前线程插入就绪队列：

/* Sets the current thread's priority to NEW_PRIORITY. */
void
thread_set_priority (int new_priority) 
{/*thread_current ()->priority = new_priority;thread_yield();*//* 添加代码 */if (thread_mlfqs)return;enum intr_level old_level = intr_disable();struct thread *cur = thread_current();int old_priority = cur->priority;cur->base_priority = new_priority;if (list_empty(&cur->locks_holding) || new_priority > old_priority){cur->priority = new_priority;thread_yield();}intr_set_level(old_level);
}

make check，通过这两个测试。

为了防止优先级反转，需要实现优先级捐赠

donate-one中出现了新的函数lock_acquire,lock_release，含义分别是锁的获取与释放。这个测试说明，线程A获取锁时如果发现拥有锁的线程B优先级比自己低，则提升线程B的优先级；在线程B释放锁后，还要恢复线程B原来的优先级。

donate-multiple与donate-multiple2中出现了两个锁，要求在恢复优先级时，考虑其它线程对该线程的优先级捐赠。这就需要记录给线程捐赠了优先级的所有线程。

donate-nest中有优先级分别为高中低的三个线程H,M,L。当M在等待L的锁时，L的优先级会被提升为M。而当H来获取M的锁时，M和L的优先级都会提升为H。这等于要求优先级的捐赠是递归捐赠的。因此还需要记录线程正在等待哪个线程释放锁。

donate-sema中出现了sema_up和sema_down，对应着V操作和P操作。加入了信号量的调整，但其实没有使问题更复杂，因为锁的本质也是信号量的变化。

donate-lower则修改了一个优先级被捐赠的线程的优先级。在修改时线程优先级依然是被捐赠的优先级，但释放锁后线程的优先级变成了修改后的优先级。

sema和condvar两个测试要求信号量的等待队列和condition的waiters队列都是优先队列。

donate-chain则要求实现链式优先级捐赠，释放锁后如果线程没有被捐赠，则需要立即恢复原来的优先级。

在thread.h中加入如下成员并在thread.c的init_thread中初始化：

随后在synch.h中的lock结构体中加入成员：

修改synch.c中的lock_acquire函数：

void
lock_acquire (struct lock *lock)
{ASSERT (lock != NULL);ASSERT (!intr_context ());ASSERT (!lock_held_by_current_thread (lock));/*sema_down (&lock->semaphore);lock->holder = thread_current ();*//* 添加代码  */struct thread *cur = thread_current();struct lock *tmp;/* 锁由当前的一些线程持有 */if (!thread_mlfqs && lock->holder != NULL){cur->lock_waiting = lock;tmp = lock;/* 循环实现了递归捐赠，并通过修改锁的max_priority成员，再通过thread_update_priority函数更新优先级来实现优先级捐赠 */while (tmp != NULL && tmp->max_priority < cur->priority){/* 更新最大优先级 */tmp->max_priority = cur->priority;/* 将优先级赋予其持有者的线程 */thread_donate_priority(tmp->holder);/* 继续捐赠给持有者正在等待的线程 */tmp = tmp->holder->lock_waiting;}}sema_down(&lock->semaphore);enum intr_level old_level = intr_disable();cur = thread_current();if (!thread_mlfqs){/* 有锁了不等别的锁了. */cur->lock_waiting = NULL;/* 另外，这个锁的最大优先级必须是我的优先级. */lock->max_priority = cur->priority;thread_hold_lock(lock);}lock->holder = cur;intr_set_level(old_level);
}

在thread.h中声明如下函数：

实现thread_donate_priority和thread_hold_lock：

/* 将当前线程的优先级赋予线程t. */
void
thread_donate_priority(struct thread *t)
{enum intr_level old_level = intr_disable();thread_update_priority(t);/* 移除旧的t并按顺序插入新的t */if (t->status == THREAD_READY){list_remove(&t->elem);list_insert_ordered(&ready_list, &t->elem, thread_cmp_priority, NULL);}intr_set_level(old_level);
}/* 让线程持有锁. */
void
thread_hold_lock(struct lock *lock)
{enum intr_level old_level = intr_disable();struct thread *cur = thread_current();list_insert_ordered(&cur->locks_holding, &lock->elem, lock_cmp_priority, NULL);/* 捐赠锁的优先级 */if (cur->priority < lock->max_priority){cur->priority = lock->max_priority;thread_yield();}intr_set_level(old_level);
}/* 移除线程的锁. */
void
thread_remove_lock(struct lock *lock)
{enum intr_level old_level = intr_disable();list_remove(&lock->elem);thread_update_priority(thread_current());intr_set_level(old_level);
}/* 最大优先级的锁的比较功能. */
bool
lock_cmp_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED)
{return list_entry(a, struct lock, elem)->max_priority > list_entry(b, struct lock, elem)->max_priority;
}/* 更新锁的优先级. */
void
thread_update_priority(struct thread *t)
{enum intr_level old_level = intr_disable();int max_pri = t->base_priority;int lock_pri;/* 如果线程持有锁，则选择具有最高优先级的线程.* 如果这个优先级大于原本的优先级,* 将更新实际（捐赠）的优先级.*/if (!list_empty(&t->locks_holding)){list_sort(&t->locks_holding, lock_cmp_priority, NULL);lock_pri = list_entry(list_front(&t->locks_holding), struct lock, elem)->max_priority;if (max_pri < lock_pri)max_pri = lock_pri;}t->priority = max_pri;intr_set_level(old_level);
}

修改synch.c中的lock_release函数：

/* Releases LOCK, which must be owned by the current thread.An interrupt handler cannot acquire a lock, so it does notmake sense to try to release a lock within an interrupthandler. */
void
lock_release (struct lock *lock) 
{ASSERT (lock != NULL);ASSERT (lock_held_by_current_thread (lock));/* 添加代码 */if (!thread_mlfqs)thread_remove_lock(lock);lock->holder = NULL;sema_up (&lock->semaphore);
}

该函数处理了释放锁时优先级的变化：如果当前线程还有锁，则获取其拥有锁的max_priority。如果它大于base_priority则更新被捐赠的优先级。

最后，修改thread_set_priority函数：

/* Sets the current thread's priority to NEW_PRIORITY. */
void
thread_set_priority (int new_priority) 
{/*thread_current ()->priority = new_priority;thread_yield();*//* 添加代码 */if (thread_mlfqs)return;enum intr_level old_level = intr_disable();struct thread *cur = thread_current();int old_priority = cur->priority;cur->base_priority = new_priority;if (list_empty(&cur->locks_holding) || new_priority > old_priority){cur->priority = new_priority;thread_yield();}intr_set_level(old_level);
}

接下来实现sema和condvar的两个优先队列。

首先修改synch.c中的cond_signal函数：

void
cond_signal (struct condition *cond, struct lock *lock UNUSED) 
{ASSERT (cond != NULL);ASSERT (lock != NULL);ASSERT (!intr_context ());ASSERT (lock_held_by_current_thread (lock));if (!list_empty (&cond->waiters)) {/* 添加代码 */list_sort(&cond->waiters, cond_cmp_priority, NULL);sema_up (&list_entry (list_pop_front (&cond->waiters), struct semaphore_elem, elem)->semaphore);}
}

然后声明并实现比较函数cond_cmp_priority：

/* condvar waiters 优先级比较函数. */
bool
cond_cmp_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED)
{struct semaphore_elem *sa = list_entry(a, struct semaphore_elem, elem);struct semaphore_elem *sb = list_entry(b, struct semaphore_elem, elem);return list_entry(list_front(&sa->semaphore.waiters), struct thread, elem)->priority > \ list_entry(list_front(&sb->semaphore.waiters), struct thread, elem)->priority;
}

这样就实现了将条件变量等待队列变为优先队列，类似地，分别修改sema_up和sema_down

Make Check，通过。

4、Threads高级调度程序设计及实践过程。

在thread结构体中加入成员并在init_thread中初始化：

然后在thread.c中声明全局变量load_avg：

thread_start中初始化load_avg：

先修改timer_interrupt函数。每次时钟中断，运行线程的recent_cpu都会加1，并且每TIMER_FREQ个ticks更新系统load_avg和所有线程的recent_cpu，每4个ticks更新线程优先级。因此加入代码：

接下来，在thread.c中实现recent_cpu自增函数（并在thread.h中声明）：

/* Recent CPU++; */
void
mlfqs_inc_recent_cpu()
{ASSERT(thread_mlfqs);ASSERT(intr_context());struct thread *cur = thread_current();if (cur == idle_thread)return;cur->recent_cpu = fix_add(cur->recent_cpu, fix_int(1));
}

实现更新系统load_avg和所有线程recent_cpu的函数：

/* 更新所有线程的 load_avg and recent_cpu of every TIMER_FREQ ticks. */
void
mlfqs_update_load_avg_and_recent_cpu()
{ASSERT(thread_mlfqs);ASSERT(intr_context());size_t ready_cnt = list_size(&ready_list);if (thread_current() != idle_thread)++ready_cnt;load_avg = fix_add(fix_unscale(fix_scale(load_avg, 59), 60), fix_unscale(fix_int(ready_cnt), 60));struct thread *t;struct list_elem *e;for (e = list_begin(&all_list); e != list_end(&all_list); e = list_next(e)){t = list_entry(e, struct thread, allelem);if (t != idle_thread){t->recent_cpu = fix_add(fix_mul(fix_div(fix_scale(load_avg, 2), fix_add(fix_scale(load_avg, 2), fix_int(1))), t->recent_cpu), fix_int(t->nice));mlfqs_update_priority(t);}}
}

实现更新优先级的函数：

/* 更新线程的优先级. */
void
mlfqs_update_priority(struct thread *t)
{ASSERT(thread_mlfqs);if (t == idle_thread)return;t->priority = fix_trunc(fix_sub(fix_sub(fix_int(PRI_MAX), fix_unscale(t->recent_cpu, 4)), fix_int(2 * t->nice)));t->priority = t->priority < PRI_MIN ? PRI_MIN : t->priority;t->priority = t->priority > PRI_MAX ? PRI_MAX : t->priority;
}

实现四个本来没有完成的函数：

/* Sets the current thread's nice value to NICE. */
void
thread_set_nice (int nice UNUSED) 
{/* 添加代码 */thread_current()->nice = nice;mlfqs_update_priority(thread_current());thread_yield();
}/* Returns the current thread's nice value. */
int
thread_get_nice (void) 
{/* 添加代码 */return thread_current()->nice;
}/* Returns 100 times the system load average. */
int
thread_get_load_avg (void) 
{/* 添加代码 */return fix_round(fix_scale(load_avg, 100));
}/* Returns 100 times the current thread's recent_cpu value. */
int
thread_get_recent_cpu (void) 
{/* 添加代码 */return fix_round(fix_scale(thread_current()->recent_cpu, 100));
}

Make Check通过27个测试点