[关闭]
@SovietPower 2021-11-07T17:11:07.000000Z 字数 4631 阅读 1285

OS 实验4 解决忙等待

OS

https://www.zybuluo.com/SovietPower/note/1827615

背景

控制线程睡眠/等待的函数timer_sleep()位于src/devices/timer.c中，它通过忙等待并持续调用thread_yield()控制线程暂停执行，直到指定时间过去。
忙等待浪费CPU资源。该实验的目的为不使用忙等待重新实现timer_sleep()。

本次实验测试，在src/tests/threads/test.c中指向的test_alarm_multiple函数。
通过pintos -- run alarm-multiple执行该部分测试。

会修改的文件：devices/timer.c, threads/thread.c, threads/thread.h。

测试数据分析

测试数据：test_sleep (5, 7)。
会生成5个线程0,1,2,3,4，每次分别休眠duration即10,20,30,40,50ms。每个线程需共休眠7次（休眠结束后继续休眠）。
iteration记录了其当前已休眠了多少次。
当依次执行的线程，满足休眠时间已休眠次数的值非降时，测试成功，即不会因为等待一个休眠进程而不调用一个未休眠进程。

因为所有线程优先级相同，所以每次线程开始休眠后，会放到队尾；而每次一个线程休眠，会调用队首的，又线程按休眠时间从小到大依次结束休眠、进入队尾，所以每次调度，如果有线程没在休眠，就一定会调度没在休眠的进程。
所以实际上不需修改，测试一定能成功。

实验前：
> pintos -- run alarm-multiple

实验后：

  1. > make clean
  2. > make
  3. > pintos -- run alarm-multiple

前后的区别：
实验前：当product相等时，哪个线程先开始时无序的，取决于进入队列尾部的顺序，是比较随机的（取决于哪个先执行）。
实验后：当product相等时，线程开始的顺序从小到大，因为解除休眠、加入队尾是在枚举所有线程时执行，而线程枚举是按线程产生顺序枚举，所以进入队列尾部的顺序一定从小到大。

计时器相关函数及定义

TIMER_FREQ

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

  1. #define TIMER_FREQ 100

timer_elapsed()

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

  1. int64_t timer_elapsed (int64_t then)
  2. {
  3.   return timer_ticks () - then;
  4. }

timer_ticks()

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

  1. int64_t timer_ticks (void);

timer_interrupt()

计时器中断/tick的句柄。会增加ticks并调用thread_tick()。

  1. static void timer_interrupt (struct intr_frame *args UNUSED)
  2. {
  3.   ticks++;
  4.   thread_tick ();
  5. }

TIME_SLICE, thread_ticks

TIME_SLICE设定每个线程最多运行多少个计时器周期（即一个时间片大小）。为4次即40ms。
thread_ticks记录新线程获取CPU后计时器中断了多少次。

  1. /* Scheduling. */
  2. #define TIME_SLICE 4            /* # of timer ticks to give each thread. */
  3. static unsigned thread_ticks;   /* # of timer ticks since last yield. */

thread_tick()

每次计时器中断/tick时都会被调用，即每10ms调用一次。
调用时检测当前运行线程，运行时间是否到达了40ms（运行时中断次数是否到达了4次），是则将yield_on_return设为True，应该是释放当前线程对CPU的占用（没细看）。

  1. void thread_tick (void)
  2. {
  3.   struct thread *t = thread_current ();
  5.   /* Update statistics. */
  6.   if (t == idle_thread)
  7.     idle_ticks++;
  8. #ifdef USERPROG
  9.   else if (t->pagedir != NULL)
  10.     user_ticks++;
  11. #endif
  12.   else
  13.     kernel_ticks++;
  15.   /* Enforce preemption. */
  16.   if (++thread_ticks >= TIME_SLICE)
  17.     intr_yield_on_return ();
  18. }

解决忙等待

问题分析

最初的timer_sleep()，在被休眠线程获得CPU资源时，不断调用thread_yield()，直到线程结束休眠。

  1. void timer_sleep (int64_t ticks) 
  2. {
  3.   int64_t start = timer_ticks ();
  5.   ASSERT (intr_get_level () == INTR_ON);
  6.   while (timer_elapsed (start) < ticks) 
  7.     thread_yield ();
  8. }

thread_yield()功能：使当前线程释放对CPU的占用（回到就绪队列），并切换一个新线程开始运行。

  1. void
  2. thread_yield (void)
  3. {
  4.   struct thread *cur = thread_current ();
  5.   enum intr_level old_level;
  7.   ASSERT (!intr_context ());
  9.   old_level = intr_disable ();
  10.   if (cur != idle_thread)
  11.     // list_push_back (&ready_list, &cur->elem);
  12.     list_insert_ordered (&ready_list, &cur->elem, (list_less_func *) &cmp_thread_priority, NULL);
  13.   cur->status = THREAD_READY;
  14.   schedule ();[
  15.   intr_set_level (old_level);
  16. }

将要运行的新线程由schedule()指定，因为之前实现了优先级调度，所以会选择就绪队列中优先级最高的线程执行。
由于当前执行的线程一定是优先级最高的（且未被休眠），所以在当前线程被休眠后，会回到就绪队列的队首，并取出优先级次高的线程。若也被休眠，则schedule()调用，而此时在休眠，所以又通过thread_yield()调用... 直到有一个线程结束休眠前，CPU始终在间切换，且未执行任何有效命令。
所以此处的忙等待不仅低效，还会使CPU长时间做无用功。

解决方式

1. 为了使已休眠线程不被调度，可以将其阻塞，并指定阻塞时间。
调用thread_block()，会同时调用schedule()，所以只需thread_block()当前线程即可同时完成线程切换。

2. 在每次计时器中断/tick时，需要检查当前已阻塞的线程，判断休眠时间是否结束。
thread.c中实现了thread_foreach()函数，会枚举所有线程并对其执行函数func(aux)。

  1. void thread_foreach (thread_action_func *func, void *aux);

所以在每次tick时，枚举所有进程，判断其是否处于休眠及是否休眠结束，若结束则调用thread_unblock()（转为就绪状态，并将其加入到就绪队列）。
两个阻塞和解除阻塞的函数在前面实验中提过了。

3. 所以每个线程可维护一个剩余阻塞时间，在每次tick时自减，在减为0时结束休眠。

代码实现

1. 为每个线程结构体thread添加变量int64_t block_ticks（并在thread_create()或init_thread()时初始化）。

  1. struct thread
  2. {
  3.     ...
  4.     /* Owned by thread.c. */
  5.     unsigned magic;                     /* Detects stack overflow. */
  7.     /* My code. */
  8.     int64_t block_ticks;
  9. };
  1. static void
  2. init_thread (struct thread *t, const char *name, int priority)
  3. {
  4.   ...
  5.   t->priority = priority;
  6.   t->magic = THREAD_MAGIC;
  8.   /* My code. */
  9.   t->block_ticks = 0;
  11.   old_level = intr_disable ();
  12.   ...
  13. }

2. 用thread_block()重新实现timer_sleep()。
注意thread_block()要求must be called with interrupts turned off，所以在阻塞线程前需关闭中断，即之前说的实现原子操作：

  1. enum intr_level old_level = intr_disable ();
  2. // do something without being interrupted
  3. intr_set_level (old_level);

而timer_sleep()也要求Interrupts must be turned on，也需ASSERT判断。
所以可得：

  1. void timer_sleep (int64_t ticks)
  2. {
  3.     if (ticks<=0) return;
  4.     ASSERT (intr_get_level () == INTR_ON);
  6.     enum intr_level old_level = intr_disable ();
  7.     thread_current()->block_ticks = ticks;
  8.     thread_block();
  9.     intr_set_level (old_level);
  10. }

3. 在计时器中断的句柄timer_interrupt()中，加入thread_foreach()。
首先要实现一个函数thread_check_block()，判断一个线程t是否处于阻塞状态，处于则使其t->block_ticks自减，当减为0时thread_unblock(t)。
（以及在thread.h中添加void thread_check_block(struct thread *t, void *aux);）

  1. void thread_check_block(struct thread *t, void *aux UNUSED)
  2. {
  3.     if (t->status==THREAD_BLOCKED && t->block_ticks>0 && --t->block_ticks==0)
  4.         thread_unblock(t);
  5. }

然后在timer_interrupt()中，调用thread_foreach(thread_check_block, NULL)。

  1. static void
  2. timer_interrupt (struct intr_frame *args UNUSED)
  3. {
  4.     // My code.
  5.     thread_foreach(thread_check_block, NULL);
  7.     ticks++;
  8.     thread_tick ();
  9. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注