OS 实验3 实现优先级调度

OS

https://zybuluo.com/SovietPower/note/1827212

背景

第一个项目在src/threads中。pintos的各项目之间是独立的，不会互相影响。
该实验中需做到Project 1中优先级调度的基本实现，即（只需）将原本的FIFS调度改为优先级调度。

测试方法：
在thread文件夹中使用make，可生成build目录；使用make clean，可清空之前编译生成的结果，以进行新的测试；使用命令make check可生成build并测试当前的threads是否能通过所有测试（非常非常慢，可能是qemu的问题）。
make完后，使用命令pintos -- run alarm-priority可运行alarm-priority的单个测试，其它测试同理。

make check是pintos自带的测试对比工具，会将当前threads中代码的运行结果与预期结果进行比对，以测试当前代码正确性。
在修改threads前，不能通过20/27个测试点。Project 1的目标为通过所有测试点。

make check的测试方式在src/tests/threads/Make.tests中定义，可增加或减少测试参数，自定义或简化测试（修改文件开始tests/threads_TESTS中的内容）。

若不使用make check，即使用pintos -- run <test>自己测试，需自行将输出结果与预期结果进行比对。
每个test的预期结果保存在对应的.ck中。如：alarm-priority.ck中保存了test_alarm_priority的预期结果。

注意，要修改的是配置pintos时指定的路径那里的pintos文件。使用pintos命令时，会运行那个路径下对应的目录里的build，而不是当前目前下的build。所以make和文件修改都应在那个目录下进行。
每次修改完代码后，要重新make（可能还要先make clean），再pintos -- run才能看到更新后的结果。

在src/threads/init.c中定义了所有pintos测试的入口。
运行pintos测试会执行run_actions(argv)，然后调用run_test(argv[1])执行argv[1]指定的task：run_test(task)会调用与task对应的测试函数，具体可见src/tests/threads/tests.c。
本实验中则使用测试函数test_alarm_priority()，位于src/threads/alarm-priority.c。

pintos部分代码

src/lib/debug.h中有若干宏定义：

/* GCC lets us add "attributes" to functions, function
   parameters, etc. to indicate their properties.
   See the GCC manual for details. */
#define UNUSED __attribute__ ((unused))
#define NO_RETURN __attribute__ ((noreturn))
#define NO_INLINE __attribute__ ((noinline))
#define PRINTF_FORMAT(FMT, FIRST) __attribute__ ((format (printf, FMT, FIRST)))

使用这些宏，可实现代码注释，以显著表现一个函数或参数的特性。
如在任意位置加入UNUSED，表明该位置的函数或参数未被使用。

线程优先级调度实现

测试函数test_alarm_priority()及相关定义

PRI_MIN, PRI_MAX, PRI_DEFAULT

优先级的最小值、最大值、默认值。为$0,\ 63,\ 31$。

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

semaphore

信号量。信号量为非负整数，当为正时表示资源可用，为0时表示资源不可用。
除初始化外，信号量只能由两个原子操作控制：
sema_down或P：等待信号量变为正，然后减少信号量，即等待一个被分配资源。
sema_up或V：增加信号量，即增加一个可用资源（若有等待线程则唤醒一个）。

sema_init()

将信号量初始化为给定非负整数。

void sema_init (struct semaphore *sema, unsigned value);

test_alarm_priority()

创建10个线程，优先级分别为$21\sim 30$。
这10个线程会在5秒后同时执行、同时竞争CPU。每个线程执行完毕后会输出它的名称。
该函数会等待所有线程执行完毕。

void test_alarm_priority (void)

thread_create()

创建一个内核线程，其名称为name，优先级为priority，需要执行函数function，需要的参数为aux。
如果创建成功，返回其tid；否则返回TID_ERROR。

tid_t thread_create (const char *name, int priority, thread_func *function, void *aux)

thread_mlfqs

bool变量。若为true，表示使用多级反馈队列调度（multi-level feedback queue scheduler）；否则使用轮询调度（round-robin scheduler）。
通过加入命令行参数-o mlfqs启用。

TIMER_FREQ

计时器每秒的中断次数（计时次数）。为$100$，即每10ms次中断/tick一次。

#define TIMER_FREQ 100

timer_elapsed()

返回给定时刻距现在经过了多少次计时(tick)。

int64_t timer_elapsed (int64_t then)
{
  return timer_ticks () - then;
}

timer_ticks()

返回自系统启动以来计时器计时(tick)了多少次。

int64_t timer_ticks (void);

调度函数及相关定义

调度函数为schedule()，位于thread.c。

list_entry()

将指向列表元素的指针转为给定结构体指针（比如struct thread）。

#define list_entry(LIST_ELEM, STRUCT, MEMBER)           \
        ((STRUCT *) ((uint8_t *) &(LIST_ELEM)->next     \
                     - offsetof (STRUCT, MEMBER.next)))

next_thread_to_run()

从就绪队列中选择并返回下一个要调度运行的线程。若就绪队列为空，返回idle_thread。

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

running_thread()

返回当前正在运行的线程。
类似的函数是thread_current()，为running_thread()加上线程合法性检查。

struct thread *running_thread (void);
struct thread *thread_current (void);

schedule()

寻找一个新的可切换进程，并切换。
中断必须关闭。
在该函数运行完成前（即thread_schedule_tail()运行完成前），不应调用printf()。

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_threads()

进程切换函数。switch.c中无该函数的源码，在switch.S中有。
将当前进程从cur切换到next：保存next的上下文，切换到cur的上下文。
cur必须是当前正在运行的线程，next必须正在运行该函数。

struct thread *switch_threads (struct thread *cur, struct thread *next);

thread_schedule_tail()

激活新线程的页表，以完成新线程切换。若之前的进程处于THREAD_DYING状态，释放它的页表结构。
在该函数运行完毕后，表示schedule()运行完毕，此时新线程已经开始运行，中断依旧处于关闭状态。

void thread_schedule_tail (struct thread *prev);

FIFS调度

在函数next_thread_to_run()中，可以看到pintos如何调度：

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

即在就绪队列非空时，选择就绪队列ready_list的队首。

在thread.c中，需要加入线程到就绪队列的函数有：thread_unblock(), init_thread(), thread_yield()。
而所有使用的操作是list_push_back (&ready_list, &cur->elem)，即直接加入到队列尾。
所以先产生、先进入队列的线程，最先被调度（通过list_pop_front），即pintos使用的FIFS。

优先级调度

list.c中包含了：在列表指定位置插入元素的list_insert()；根据指定优先级比较函数less，在列表的合适位置（按less排序）插入指定元素的list_insert_ordered()。
所以，若要将FIFS调度改为优先级调度，只需实现以下操作，以保证优先级更高的线程位于就绪队列的更前面。
因为目前线程优先级不会改变，所以只需实现加入线程到队列时，优先级更高的线程位于就绪队列的更前面。

1. 声明一个优先级比较函数compare_by_priority()，根据priority进行比较，使less (elem, e, aux)在elem优先级高于e时为真。
该函数的比较元素为struct list_elem *，若需作为线程使用，需使用list_entry(x, struct thread, elem)转为struct thread *。

bool cmp_thread_priority(const struct list_elem *x, const struct list_elem *y, void *aux)
{
    return list_entry(x, struct thread, elem)->priority > list_entry(y, struct thread, elem);
}

2. 将加入线程到就绪队列的所有操作，从list_push_back (&list, elem)改为list_insert_ordered (&list, elem, (list_less_func *) &cmp_thread_priority, NULL)。
共需修改三个函数thread_unblock(), init_thread(), thread_yield()。

测试结果：