<0x01> 任务说明
更高效的线程睡眠
目前的timer_sleep实现是忙等待的
这并不高效
严格优先级调度
在pintos中，每个线程的优先级有0(PRI _ MIN)到63 (PRI _ MAX)
但是，当前计划程序不尊重这些优先级值
您必须修改调度程序，使高优先级线程始终在低优先级线程之前运行
注意：在优先级相同的情况下，应该以循环方式调度具有相同优先级值的线程
现有代码已经在线程运行超过分配的时间片时抢占了线程
因此您不必担心循环实现的这一部分
如果您想更仔细地了解这是如何实现的，那么可以查看thread_tick
您还必须修改3个pintos同步原语
lock、信号量、条件变量
以便这些共享资源更喜欢优先级较高的线程，而不是优先级较低的线程
此外，您必须实现优先级借用机制
当高优先级线程(A)不得不等待获取一个已经被低优先级线程(B)持有的锁时，我们暂时将B的优先级提高到A的优先级。不提供优先级的调度程序容易出现优先转置1的问题，即中等优先级的线程在运行，而高优先级的线程 (a) 在等待由低优先级线程 (b) 持有的资源。支持优先级捐赠的调度程序将允许 B 先运行，这样具有最高优先级的 A 可以被解除阻塞。执行优先捐赠必须处理以下事项： 1) 来自多个来源的捐赠；2) 解锁后撤销捐赠；3) 嵌套 / 递归捐赠。
线程可以调用thread_set_priority设置自己的优先级
也可以调用thread_get_priority获得自己的优先级。
如果一个线程不再拥有最高的“有效优先级”
它必须立即将 CPU 交给最高优先级的线程。
实际的优先级调度程序本身并不需要太多的复杂性
如果您对如何有效地实现这种调度程序感到困惑
请考虑现有的操作系统如何实现这种调度程序。
不要忘记实现thread_get_priority，这是返回当前线程优先级的函数
在考虑优先级借用机制是，应该返回线程的有效优先级
一个线程不能改变另一个线程的优先级，除非通过优先级借用
如果一个线程不再具有最高的有效优先级 (例如，因为它释放了一个锁或者它用一个较低的值调用 thread _ set _ 优先级) ，它必须立即生成 CPU。如果释放了一个锁，但是当前线程仍然具有最高的有效优先级，那么它不应该产生 CPU。
这项任务的优先捐赠部分可能需要一些思考ーー在纸上或白板上描绘一些场景，看看你提议的系统是否有效，可能会有所帮助。
您只需实现锁的优先级捐赠。不要对其他同步变量实现它们 (对信号量或监视器这样做没有任何意义，因为，例如，没有信号量唯一 “所有者” 的概念)。但是，您需要为锁、信号量和条件变量实现优先级调度。优先级调度是当释放资源或发出监视器信号时解除阻塞最高优先级线程的情况。
一个线程一次只能 (直接) 捐赠给一个线程，因为一旦它调用 lock _ access，捐赠者线程就会被阻塞。
您的实现必须处理嵌套捐赠： 考虑一个高优先级线程 H、一个中优先级线程 M 和一个低优先级线程 L。如果 H 必须等待 M，M 必须等待 L，那么我们应该将 H 的优先级赋予 L。
如果在调用 lock _ release 时，一个锁上有多个服务器，那么所有这些优先级捐赠必须应用于接收下一个锁的线程。
不需要为用户线程增加调度程序；只需让调度程序以相同的方式对待所有线程，即使它们属于同一个进程。作为一个病态的例子，如果一个用户程序 A 有 100 个线程，而一个用户程序 B 只有 1 个线程，那么大部分的 CPU 将被 A 的线程所主宰，而 B 的线程将处于饥饿状态。您不需要增加调度程序来使这个场景更加公平。
这个优先转置的具体例子并不是优先转置发生的唯一途径。优先转置就是高优先级的线程被低优先级的线程阻止运行。↩
用户级线程
pintos 是一个多线程内核 (也就是说，可以有多个线程在内核中运行)
在使用userprog时，您无疑使用了内核中的线程接口
在 thread/thread.c 中，thread_create 允许我们创建一个运行特定内核任务的新内核线程
类似地，thread_exit 函数允许线程终止自己。您应该阅读并理解内核线程模型。
另一方面，正如在userprog中一样，每个用户进程只有一个控制线程
换句话说，用户程序不可能创建一个新线程来运行另一个用户函数
用户程序没有执行 thread_create 和 thread_exit 的能力
但在真实的系统中，用户程序可以创建自己的线程。比如通过 POSIX pthread 库。
对于此任务，需要在 lib/user/pthread.h 中实现 pthread 库的简化版本
应该允许用户程序使用 pthread_create 和 pthread_exit 函数创建自己的线程
线程还可以使用 pthread_join 函数等待其他线程，这类似于等待进程的系统调用
线程应该能够通过一个新的 get_tid 系统调用学习它们的线程 ID (TID)
还需要说明使用户程序成为多线程对项目用户程序中的系统调用的影响。
在userprog中，每当一个用户程序 (只包含一个线程) 在操作系统中时，它都会在自己的专用内核线程中运行
换句话说，用户线程与内核线程之间有 1-1 的映射
对于这个任务，您将需要维护这个 1-1 映射。也就是说，具有 n 个用户线程的用户进程应该与 n 个内核线程 1-1 配对，每个用户线程在陷入操作系统时应该在其专用的内核线程中运行。您不应该实现绿色线程，绿色线程在用户线程和内核线程之间有多对一的映射。绿色线程并不理想，因为一旦一个用户线程被阻塞，例如在 IO 上，所有的用户线程都会被阻塞。
此外，还必须实现用户级同步。毕竟，如果我们不能用锁和信号量正确地同步线程，那么线程就没有多大用处。您需要为用户程序实现 lock_init、 lock_access、 lock_release、 sema_init、 sema_down 和 sema_up。
工作流建议： 这个任务最容易在小步骤中完成。首先实现一个简单的 pthread_create 和 pthread_execute，这样就可以通过 test/userprog/multithread/create-simple。然后，慢慢地添加越来越多的特性。扩充一个工作设计比修复一个坏的设计更容易。确保仔细跟踪资源。您分配的所有东西都必须被释放！
实现需求
新的系统调用
需要修改的系统调用
同步
实现提示
额外信息
pthread库
threading
用户级的同步
<0x02> 代码实现
更高效的线程睡眠
这个相对简单
原本的timer_sleep实现是这样的
void timer_sleep(int64_t ticks)
{
int64_t start = timer_ticks();
ASSERT(intr_get_level() == INTR_ON);
while (timer_elapsed(start) < ticks)
thread_yield();
}
可以看到就是跑了个死循环
线程还是在就绪和运行态中切换，我们需要让它进入阻塞态
首先先添加一个休眠线程队列（记得初始化）
// 存放睡眠队列
static struct list sleep_thread_list;
然后要给线程加上相应的休眠信息
struct thread
{
// ...
int64_t sleep_tick; // 睡眠终止时间刻
// ...
};
现在开始实现线程休眠的逻辑
首先就是要先想办法让线程休眠
这个相对简单，先更新线程的休眠终止时间，然后让线程进入阻塞态即可
// 修改原来的忙等待实现
void timer_sleep(int64_t ticks)
{
int64_t start = timer_ticks();
struct thread *cur = thread_current();
enum intr_level old_level = intr_disable();
cur->sleep_tick = start + ticks;
// 加入睡眠队列
list_push_back(&sleep_thread_list, &cur->sleep_elem);
thread_block();
intr_set_level(old_level);
}
现在线程休眠了，那么怎么醒来呢
在系统中，有一个时钟中断函数timer_interrupt
系统每过一个tick，就会执行这个函数
我们的苏醒逻辑就添加在这里
static void timer_interrupt(struct intr_frame *args UNUSED)
{
ticks++;
enum intr_level old_level = intr_disable();
struct list_elem *e = list_begin(&sleep_thread_list);
while (e != list_end(&sleep_thread_list))
{
struct thread *t = list_entry(e, struct thread, sleep_elem);
if (t->sleep_tick <= ticks)
{
t->sleep_tick = 0;
thread_unblock(t);
e = list_remove(e);
}
else
e = list_next(e);
}
intr_set_level(old_level);
thread_tick();
}
这样就可以了
严格优先级调度
首先先添加按优先级的调度
// 优先级调度的列表
static struct list prio_ready_list;
// ...
static struct thread *thread_schedule_prio(void)
{
if (!list_empty(&prio_ready_list))
{
list_sort(&prio_ready_list, thread_cmp_priority_more, NULL);
return list_entry(list_pop_front(&prio_ready_list), struct thread, elem);
}
else
{
return idle_thread;
}
}
然后处理新建线程时新线程优先级更高的情况
tid_t thread_create(const char *name, int priority, thread_func *function, void *aux)
{
// ...
// 新创建的线程优先级更高就让步
if (active_sched_policy == SCHED_PRIO && t->priority > thread_current()->priority)
{
thread_yield();
}
// ...
}
下面处理优先级借用的问题
首先先对thread的数据结构进行更改
struct thread
{
// ...
int priority; /* Priority. */
int origin_priority; // 原始优先级
struct list donation_list; // 借用队列
struct lock *blocking_lock; // 被阻塞的锁
// ...
};
struct thread_donation_node
{
struct list_elem elem;
struct lock *lock;
struct thread *donor;
int priority;
};
优先级借用队列信息保存在thread中
这个问题的处理关键是让一系列锁同步的线程都具有链条上的最高优先级
所以可以做出下面的更改
static void lock_update_blocking_priority(struct thread *t)
{
if (t->blocking_lock == NULL)
{
return;
}
struct thread *holder = t->blocking_lock->holder;
ASSERT(holder != NULL);
for (struct list_elem *e = list_begin(&holder->donation_list); e != list_end(&holder->donation_list);)
{
struct thread_donation_node *node = list_entry(e, struct thread_donation_node, elem);
e = list_next(e);
if (node->lock == t->blocking_lock)
{
node->priority = t->priority;
if (holder->priority < t->priority)
{
holder->priority = t->priority;
lock_update_blocking_priority(holder);
}
return;
}
}
}
static void lock_holder_insert_donation(struct thread *cur, struct lock *lock)
{
if (lock->holder != NULL && lock->holder->priority < cur->priority)
{
struct thread_donation_node *node = malloc(sizeof(struct thread_donation_node));
node->lock = lock;
node->donor = cur;
node->priority = cur->priority;
list_push_back(&lock->holder->donation_list, &node->elem);
lock->holder->priority = cur->priority;
lock_update_blocking_priority(lock->holder);
}
}
然后在合适的位置调用即可
其他的同步设施更改就不是很关键了，只要确保优先调用高优先级的即可
用户级线程
这个相对困难，又涉及到一些汇报和内存位置问题
首先，pthread没有load函数中那样，自动帮你把一下内存位置设置好
不过参考前面的函数，也可以写出
bool setup_thread(void **esp)
{
uint8_t *kpage;
bool success = false;
enum intr_level old_level = intr_disable();
struct thread *t = thread_current();
if (t->pcb != NULL && t->pcb->pagedir != NULL)
{
// 获取一个新的内存页，初始为0
kpage = palloc_get_page(PAL_USER | PAL_ZERO);
if (kpage != NULL)
{
void *base = PHYS_BASE;
int max_pthread_num = 1000000;
// 寻找空闲的页
for (int i = 0; i < max_pthread_num; i++)
{
base -= PGSIZE;
if (!pagedir_is_accessed(t->pcb->pagedir, (uint8_t *)base - PGSIZE))
{
break;
}
}
if (t->pcb->pagedir != NULL)
{
// 将新分配的内存页安装到页目录中，确保线程可以访问这段内存。
success = install_page(((uint8_t *)base) - PGSIZE, kpage, true);
}
if (success)
{
t->upage = ((uint8_t *)base) - PGSIZE;
*esp = base;
}
else
{
palloc_free_page(kpage);
}
}
}
intr_set_level(old_level);
return success;
}
剩下的工作跟userprog中差不多
按功能要求即可，注意资源的释放
<0x03> 测试相关
如果跟我一样是手搓的环境，并且没搓bochs环境的话
跑测试会有一些小问题
首先是threads部分的测试默认都是在bochs下面跑的
如果要用qemu跑，那么就要改makefile
# /tests/threads/Make.tests
# 90行左右
# tests/threads/%.output: SIMULATOR = --bochs
tests/threads/%.output: SIMULATOR = --qemu
然后就是qemu的运行速度会比较慢，在部分测试中会超时
但如果单独运行的话会发现结果还是正确的
(就是耗时超长)
由于测试机会读项目的makefile，所以提交时最好改回来
还有一个办法，就是改计时器频率
也就是devices/timer.h里面的TIMER_FREQ
这个值默认是100，意味着pintos每秒100个时钟周期
虽然正常情况下是不要动这个东西，但这里可以暂时改成20000
然后吧devices/timer.c的这个注释掉
#if TIMER_FREQ < 19
#error 8254 timer requires TIMER_FREQ >= 19
#endif
#if TIMER_FREQ > 1000
// #error TIMER_FREQ <= 1000 recommended
#endif
如果测试功能的话可以暂时开启，但不知道会出什么别的问题