操作系统课程设计之Pintos_fail tests/threads/alarm-priority

资源下载地址：https://download.csdn.net/download/sheziqiong/86784890
资源下载地址：https://download.csdn.net/download/sheziqiong/86784890

Pintos 的安装和配置

1. 安装 qemu
   sudo apt-get install qemu
2. 从 Git 公共库获得最新 Pintos
   git clone git://pintos-os.org/pintos-anon
3. /utils/pintos-gdb 用 VIM 打开，编辑 GDBMACROS 变量，将 Pintos 完整路径赋给该变量。
4. 用 VIM 打开 Makefile 并将 LOADLIBES 变量名编辑为 LDLIBS
5. 在/src/utils 中输入 make 来编译 utils
6. 编辑/src/threads/Make.vars（第 7 行）：更改 bochs 为 qemu
7. 在/src/threads 并运行来编译线程目录 make
8. 编辑/utils/pintos（第 103 行）：替换 bochs 为 qemu
   编辑/utils/pintos（257 行）：替换 kernel.bin 为完整路径的 kernel.bin
   编辑/utils/pintos（621 行）：替换 qemu 为 qemu-system-x86_64
   编辑/utils/Pintos.pm（362 行）：替换 loader.bin 为完整路径的 loader.bin
9. 打开~/.bashrc 并添加 export PATH=/home/…/pintos/src/utils:$PATH 到最后一行。
10. 重新打开终端输入 source ~/.bashrc 并运行
11. 在 Pintos 下打开终端输入 pintos run alarm-multiple

Threads

Mission1

该部分内容主要是需要我们修改 timer_sleep 函数
首先查看原本 timer_sleep 代码

/* Sleeps for approximately TICKS timer ticks.  Interrupts must
   be 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();
}
1
2
3
4
5
6
7
8
9
10

通过查看相关教程及分析，可知 start 获取了起始时间， 然后断言必须可以被中断， 不然会一直死循环下去。

while (timer_elapsed (start) < ticks)
   thread_yield();
1
2

追踪 thread_yield()函数及 schedule()函数，schedule 负责切换下一个线程进行 run，thread_yield 负责把当前线程放到就绪队列里，然后重新 schedule（当 ready 队列为空时线程会继续在 CPU 执行）。 而 timer_sleep 则是在 ticks 时间内，如果线程出于 running 状态就不断把线程放到就绪队列不让他执行。由此可以发现它存在的问题：
线程不断在 CPU 就绪队列和 running 队列之间来回，占用了 CPU 资源。因此我们决定添加唤醒机制。

函数实现

修改 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. */

    /* 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 ticks_blocked;              /* Time for blocked. */
  };
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

添加了一个变量 ticks_blocked 用于记录剩余阻塞时间。在 timer_sleep 函数中，将该线程阻塞并设置阻塞时间。这一过程需要解除中断。
修改 timer_sleep 函数

void
timer_sleep (int64_t ticks)
{
  if(ticks <= 0) return;
  ASSERT (intr_get_level () == INTR_ON);
  enum intr_level old_level = intr_disable ();
  struct thread *current_thread = thread_current ();
  current_thread->ticks_blocked = ticks;
  thread_block ();
  intr_set_level (old_level);
}
```www.biyezuopin.vip

thread_block()的底层是将当前线程设置为 THREAD_BLOCKED 后重新调度，状态为 THREAD_BLOCKED 的线程将从就绪队列中移除。
然后在适当时间唤醒线程，在每个 tick 内遍历所有线程，并将 ticks_blocked 值减一，如果该值小于等于 0，则将其从阻塞队列中移除并重新调度。每次时间片轮转都会调度 timer_interrupt 函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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

定义 check_blocked_time 函数：将 ticks_blocked 减一，若 ticks_blocked 小于 0，则将其唤醒。

```void check_blocked_time(struct thread *t, void *aux){
  if (t->status == THREAD_BLOCKED && t->ticks_blocked > 0){
    t->ticks_blocked--;
    if (t->ticks_blocked == 0)
      thread_unblock(t);
  }
}

1
2
3
4
5
6
7
8
9
10
11

在头文件也要添加关于 check_blocked_time 的声明

void check_blocked_time(struct thread *t, void *aux);
1

此时 Mission1 通过部分

pass tests/threads/alarm-single
pass tests/threads/alarm-multiple
pass tests/threads/alarm-simultaneous
FAIL tests/threads/alarm-priority
pass tests/threads/alarm-zero
pass tests/threads/alarm-negative
1
2
3
4
5
6

然后完成线程优先级的问题。通过发现 thread.c 中的 next_thread_to_run()函数，发现其中存在一个 ready_list。

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);
}
1
2
3
4
5
6
7
8

查找 list.c 文件，发现了 list_max 函数，可用于根据比较函数查找 ready_list 中优先级最高的线程。构造比较函数，利用 list_max 和 list_entry 将优先级最高的线程移除并返回。

bool thread_compare_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;
}
static struct thread *
next_thread_to_run (void)
{
  if (list_empty (&ready_list))
    return idle_thread;
  else{
    struct list_elem *max_priority = list_max (&ready_list,thread_compare_priority,NULL);
    list_remove (max_priority);
    return list_entry (max_priority,struct thread,elem);
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

此时，Mission1 部分全部通过。

pass tests/threads/alarm-single
pass tests/threads/alarm-multiple
pass tests/threads/alarm-simultaneous
pass tests/threads/alarm-priority
pass tests/threads/alarm-zero
pass tests/threads/alarm-negative
1
2
3
4
5
6

Mission2

从 priority-fifo 测试看起，改测试创建了一个一个优先级 PRI_DEFAULT+2 的主线程，并用这个线程创建了 16 个优先级 PRI_DEFAULT+1 的子线程，然后把主线程的优先级设置为优先级 PRI_DEFAULT。
测试需要把 16 个线程跑完后结束主线程，但操作系统中线程是并行执行的，有可能最开始的一个线程在设置完优先级之后立刻结束了，而此时其他线程并未结束。因此在线程设置完优先级之后应该立刻重新调度，需要在 thread_set_priority()函数里添加 thread_yield()函数。

结语

斯坦福操作系统课程设计的难度很大，无论是从环境的配置和搭建，文档的查询和翻译，相关资料的搜集和理解，都需要花费很多的功夫。通过 pintos 的自学，我能够更清晰地理解操作系统中的线程到底是怎么一回事，需要考虑哪些因素：优先级的循环更新，嵌套调度，时间片的考量，关于线程锁的概念，以及更复杂的队列调度算法。受限于时间原因，这里只完成到 thread 部分。

资源下载地址：https://download.csdn.net/download/sheziqiong/86784890
资源下载地址：https://download.csdn.net/download/sheziqiong/86784890