Apr 23, 2016

Pintos

Pintos 实验分析 1.2

实现优先级抢占机制。

实验目的

修改 Pintos 源码，实现优先级抢占机制，即优先级最高的线程如果就绪则应该让其运行。

实验过程

实验分析

如果实现优先级抢占机制，则需要优先级最高的线程如果就绪则应该让其运行。由于在上次实验我们已经完成了 ready 队列的顺序插入，可以保证队首的线程就是优先级最高的线程，所以本次实验就不需要考虑了。

而纵观整个 Pintos 操作系统，在某线程运行时会有高优先级的线程出现，还有两个可能：

某个线程被修改了优先级，使得它优先级小于 ready 队列队首线程的优先级。
新创建的线程优先级大于当前运行的线程。

对于第一种情况，我们可以在优先级发生改变的时候进行判断。在 Pintos 中有改变线程优先级的函数 void thread_set_priority (int new_priority)，它的原始代码是这样的：

/* Sets the current thread's priority to NEW_PRIORITY. */
void
thread_set_priority (int new_priority)
{
  thread_current ()->priority = new_priority;
}

可以看到，整个函数只修改了当前线程的优先级，便退出了。在这里，我们修改完优先级之后可以判断一下这个修改的优先级是否比 ready 队列队首的线程的优先级低，如果是，则进行调度，让当前线程放弃 CPU 时间片，进入 ready 队列。

在上一次的实验报告已经详细解释了 thread_yield (); 的功能，这个进程丢回到 ready_list 中，然后进行调度，切换到下一个进程。

所以，修改后的函数是这样的：

/* Sets the current thread's priority to NEW_PRIORITY. */
void
thread_set_priority (int new_priority)
{
  thread_current ()->priority = new_priority;
  if (new_priority < list_entry(list_head (&ready_list), struct thread, elem)->priority)
    thread_yield ();
}

对于第二种情况，我们可以在线程创建完成，加入 ready 队列之后进行判断，同样地，如果是新建的线程优先级比当前运行的线程高，则进行调度，让当前线程放弃 CPU 时间片，进入 ready 队列。

接下来粗略地分析一下创建新线程的函数 tid_t thread_create (const char *name, int priority, thread_func *function, void *aux)。

tid_t
thread_create (const char *name, int priority,
               thread_func *function, void *aux)
{
  struct thread *t;
  struct kernel_thread_frame *kf;
  struct switch_entry_frame *ef;
  struct switch_threads_frame *sf;
  tid_t tid;
  enum intr_level old_level;

  ASSERT (function != NULL);

  /* Allocate thread. */
  t = palloc_get_page (PAL_ZERO);
  if (t == NULL)
    return TID_ERROR;

  /* Initialize thread. */
  init_thread (t, name, priority);
  t->ticks_blocked = 0;
  tid = t->tid = allocate_tid ();

可以看到，此函数一开始为此线程分配了内存空间，然后调用了 init_thread (struct thread *t, const char *name, int priority) 函数。我们按函数运行的顺序看看这个函数是怎样初始化的线程的。

static void
init_thread (struct thread *t, const char *name, int priority)
{
  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;
  // list_push_back (&all_list, &t->allelem);
  list_insert_ordered (&all_list, &t->allelem, cmp_by_priority, NULL);
}

首先是调用 memset (t, 0, sizeof *t); 把线程占有的整块内存区域清零，保证指针都为 NULL。
然后是 t->status = THREAD_BLOCKED; 将当前线程的状态设置为 BLOCKED，因为此时线程还未初始化完毕，如果被调度，会导致不可预料的后果。
接着是记录栈大小，优先级。
最后把线程插入到 ready 队列里面。

回到 thread_create 函数。

/* Prepare thread for first run by initializing its stack.
     Do this atomically so intermediate values for the 'stack'
     member cannot be observed. */
  old_level = intr_disable ();

  /* Stack frame for kernel_thread(). */
  kf = alloc_frame (t, sizeof *kf);
  kf->eip = NULL;
  kf->function = function;
  kf->aux = aux;

  /* Stack frame for switch_entry(). */
  ef = alloc_frame (t, sizeof *ef);
  ef->eip = (void (*) (void)) kernel_thread;

  /* Stack frame for switch_threads(). */
  sf = alloc_frame (t, sizeof *sf);
  sf->eip = switch_entry;
  sf->ebp = 0;

  intr_set_level (old_level);

  /* Add to run queue. */
  thread_unblock (t);

  return tid;
}

然后为改线程分配栈空间，设置栈指针，所有步骤完成之后，就可以将线程 unblock 让其允许调度了。

在这里可以看到，创建线程的时候，只是简单的按优先级插入 ready 队列，并没有判断新创建的线程的优先级是否比当前运行的线程高。所以要完成优先级抢占机制，需要在最后加上判断。需要注意的是这个判断必须加在 thread_unblock (t); 之后，因为必须等到线程创建完毕，可以接受操作系统调度，再进行判断，调度才是有效的。

如下是修改好后的函数片段。

intr_set_level (old_level);

  /* Add to run queue. */
  thread_unblock (t);

  /* Check priority. */
  if (priority > list_entry(list_head (&ready_list), struct thread, elem)->priority)
    thread_yield ();

  return tid;
}

本次实验代码量很少，实验也很简单，一次就通过了。但是这是建立在阅读了 TA 提供的课件基础上的，如果没有 TA 课件上的提示，估计加这四行代码需要通读 thread.c 代码。

测试解释

可以看到测试均有断言 ASSERT (!thread_mlfqs);，表明以下测试不适合 MLFQS（多级反馈调度队列），因为该调度算法不单取决于优先级和线程入队的先后顺序。

priority-preempt

在下文，为了方便表述，统一将运行 void test_priority_preempt (void) 函数的线程称为测试线程，被测试线程创建的，运行 void simple_thread_func (void *aux UNUSED) 函数的称为新线程。

先看看测试函数是怎么运行的。

void
test_priority_preempt (void)
{
  /* This test does not work with the MLFQS. */
  ASSERT (!thread_mlfqs);

  /* Make sure our priority is the default. */
  ASSERT (thread_get_priority () == PRI_DEFAULT);

  thread_create ("high-priority", PRI_DEFAULT + 1, simple_thread_func, NULL);
  msg ("The high-priority thread should have already completed.");
}

断言 ASSERT (thread_get_priority () == PRI_DEFAULT); 保证了测试线程的优先级为 PRI_DEFAULT，这个作用会在下面提到。

然后创建了一个优先级为 PRI_DEFAULT + 1 的新线程，运行 simple_thread_func 函数。

我们再看看这个函数做了什么事情。

static void
simple_thread_func (void *aux UNUSED)
{
  int i;

  for (i = 0; i < 5; i++)
    {
      msg ("Thread %s iteration %d", thread_name (), i);
      thread_yield ();
    }
  msg ("Thread %s done!", thread_name ());
}

for 循环重复了五次操作，每次输出了当前线程名字和第几轮操作，然后放弃 CPU 时间片，循环结束后输出当前线程已运行完毕，退出。

接下来分析整个流程，如果优先级抢占实现正确，测试应按以下顺序执行：

在新线程被创建的时候，由于测试线程优先级比新线程低，所以会被调度回 ready 队列等待。
接着由新线程运行，输出信息，然后执行 thread_yield (); ，此时新线程会被丢回 ready 队列。但由于新线程优先级高于测试线程，它会被插入到队首，执行调度时又会进入 running 状态。由此至终，测试线程都没有被执行。
最后，新线程完成所有工作，退出。测试线程重新进入 running 状态，输出信息后，结束，测试完成。

所以理论上，这个测试的输出是这样的：

Thread high-priority iteration 0
Thread high-priority iteration 1
Thread high-priority iteration 2
Thread high-priority iteration 3
Thread high-priority iteration 4
Thread high-priority done!
The high-priority thread should have already completed.

priority-change

在下文，为了方便表述，统一将运行 void test_priority_change (void) 函数的线程称为测试线程，被测试线程创建的，运行 void changing_thread (void *aux UNUSED) 函数的称为新线程。

先看看测试函数是怎么运行的。

void
test_priority_change (void)
{
  /* This test does not work with the MLFQS. */
  ASSERT (!thread_mlfqs);

  msg ("Creating a high-priority thread 2.");
  thread_create ("thread 2", PRI_DEFAULT + 1, changing_thread, NULL);
  msg ("Thread 2 should have just lowered its priority.");
  thread_set_priority (PRI_DEFAULT - 2);
  msg ("Thread 2 should have just exited.");
}

创建了一个优先级为 PRI_DEFAULT + 1 的新线程，运行 changing_thread 函数。
将自身线程的优先级设置为 PRI_DEFAULT - 2。

下面看看这个新线程执行了什么操作。

static void
changing_thread (void *aux UNUSED)
{
  msg ("Thread 2 now lowering priority.");
  thread_set_priority (PRI_DEFAULT - 1);
  msg ("Thread 2 exiting.");
}

函数很短小，输出信息后将自身的优先级设置为 PRI_DEFAULT - 1，再次输出信息后退出。

接下来梳理整个流程，如果优先级抢占实现正确，测试应按以下顺序执行：

在新线程被创建的时候，由于测试线程优先级比新线程低，所以会被调度回 ready 队列等待。
接着由新线程运行，输出信息，然后将自身优先级降到比测试线程低，此时新线程会被丢回 ready 队列。
接着又轮到测试线程运行，测试线程再次将自身优先级降到比新线程低，所以会被调度回 ready 队列等待。
新线程开始运行，输出信息后退出，再轮到测试线程运行，输出信息，退出。

所以理论上，这个测试的输出是这样的：

Creating a high-priority thread 2.
Thread 2 now lowering priority.
Thread 2 should have just lowered its priority.
Thread 2 exiting.
Thread 2 should have just exited.

整个测试短小精悍，但是也需要正确实现了创建线程和修改优先级的优先级抢占才能通过。

回答问题

如果不考虑 `thread_create` 的情况，test 能通过吗？如果不能，会出现什么结果(请截图)，并解释为什么会出现这个结果？

测试不能通过。

先分析 priority-preempt 这个测试。新线程被创建之后，即使优先级比当前运行的测试线程高，但由于 thread_create 函数没有进行重新调度，新线程仍然在 ready 队列等待，直到测试线程运行结束，新线程都没有被运行。但由于测试线程结束，系统认为测试结束，所以新线程的输出并没有显示。

接下来分析 priority-change 这个测试，如果没有考虑到 thread_create 的情况，整个测试应该是这样运行的。

测试线程以 PRI_DEFAULT 的优先级运行，创建了优先级为 PRI_DEFAULT + 1 的新线程，新线程被添加到 ready 队列中。
测试线程将自身优先级设置为 PRI_DEFAULT - 2，此时优先级比队首的新线程优先级低，进行调度，新线程开始运行。
新线程将自身优先级设置为 PRI_DEFAULT - 1，但此时仍然是所有线程中优先级最高的，它将继续运行，完成后退出。
新线程结束后，轮到测试线程运行，然后退出。

所以根据上面的分析，运行测试的输出理论上是：

Creating a high-priority thread 2.
Thread 2 should have just lowered its priority.
Thread 2 now lowering priority.
Thread 2 exiting.
Thread 2 should have just exited.

可以看到，实际测试结果符合推论。

什么是信号量？什么是 PV 操作？

信号量是操作系统设计给进程之间通信的工具，它主要的目的是保护多个线程访问的共享资源（临界区域）而不发生冲突。

共享资源冲突是怎么来的？

现代计算机为了运行运行更高效，被设计成了多任务并行运算，很多资源都是可复用的，这样会提高运行效率。但是正如流水线设计的 CPU 比单周期的 CPU 更高效，也会有 hazard 一样，多任务并行运算提高了运行效率之外，也引起了同时读写冲突，或者请求使用某些资源却发现该资源被占用。

举最简单的例子，例如两个进程同时对一个变量自增，而自增这个操作至少涉及三条汇编指令，在开启中断的时候，这个操作并不是原子的。假如此时进行了调度，就很有可能只有一次自增成功。

后来，就有计算机科学家发明了信号量这个东西。简单的来说，信号量用来限制一个资源被同时占有的个数。在一般的情况下，这个限制都是 1，也就是我们常说的锁。要进入临界区的时候，线程先要根据信号量判断现在资源是否可用，从而达到避免冲突的作用。

P 操作

P 操作用于线程进入临界区，通常情况下会将信号量减一。并且此时判断是否有空闲的资源，如果有，则占有资源继续进行操作，否则将会被阻塞。

V 操作

V 操作用于线程退出临界区，通常情况下会将信号量加一。此时已经释放了之前占有的资源，并且唤醒其他在等待这个资源的线程。

PV 操作均是原子操作，需要关闭中断，保证修改信号量不会发生冲突。

实验感想

这次的实验要求比较简单，测试也简单易分析，但是完成这个实验还是需要把 thread 文件夹相关的代码读了一次，分析清楚每个函数的作用和调用关系，才知道要在哪里加代码。

Terry Chan

Laziness, impatience, and hubris.

Except where otherwise noted, content on this page is copyrighted.

Pintos 实验分析 1.2

实现优先级抢占机制。

实验目的

实验过程

实验分析

测试解释

priority-preempt

priority-change

回答问题

如果不考虑 `thread_create` 的情况，test 能通过吗？如果不能，会出现什么结果(请截图)，并解释为什么会出现这个结果？

什么是信号量？什么是 PV 操作？

共享资源冲突是怎么来的？

P 操作

V 操作

实验感想

Read This

Pintos 实验分析 1.1

Pintos 实验分析 1.2

实现优先级抢占机制。

实验目的

实验过程

实验分析

测试解释

priority-preempt

priority-change

回答问题

如果不考虑 thread_create 的情况，test 能通过吗？如果不能，会出现什么结果(请截图)，并解释为什么会出现这个结果？

什么是信号量？什么是 PV 操作？

共享资源冲突是怎么来的？

P 操作

V 操作

实验感想

Subscribe

Read This

Pintos 实验分析 1.1

如果不考虑 `thread_create` 的情况，test 能通过吗？如果不能，会出现什么结果(请截图)，并解释为什么会出现这个结果？