# Project 1: Threads
## Preliminaries
Yicheng Kang 10225101538@stu.ecnu.edu.cn
### References
- https://blog.csdn.net/qq_33994373/article/details/122752551
- https://hackmd.io/@MRJWNssqTvOYWcAs8iDbSg/B1VzJbyrL
## Alarm Clock
#### DATA STRUCTURES
>A1: Copy here the declaration of each new or changed struct or struct member, global or static variable, typedef, or enumeration. Identify the purpose of each in 25 words or less.
- 改写了线程结构体，在其中增加了变量`ticks_blocked`用来记录该线程要阻塞的时间。
#### ALGORITHMS
>A2: Briefly describe what happens in a call to timer_sleep(),
>including the effects of the timer interrupt handler.
- 原版`timer_sleep()`的逻辑
timer_sleep的代码如下：
```C
void timer_sleep(int64_t ticks)
{
int64_t start = timer_ticks();
ASSERT(intr_get_level() == INTR_ON);
while (timer_elapsed(start) < ticks)
thread_yield();
}
```
我们可以看到在第三行它调用了`timer_ticks()`函数获取了线程休眠的开始时间，`timer_ticks()`函数在获取时间的过程中采用了关中断保存程序状态字，而后开中断恢复程序状态字的办法以防止在执行过程中发生中断。
第五行确保现在中断是`INTR_ON`也就是打开的状态。
第六行调用了`timer_elaspsed()`函数，这个函数结构如下：
```c
int64_t
timer_elapsed(int64_t then)
{
return timer_ticks() - then;
}
```
它计算当前线程已经休眠的时间，它将结果返回至`timer_sleep()`函数。
`timer_sleep()`的while循环会判断休眠时间是否已经达到目标时间ticks，如果没有达到就一直执行`thread_yield`。
`thread_yield`的代码如下：
```c
void thread_yield(void)
{
struct thread *cur = thread_current();
enum intr_level old_level;
ASSERT(!intr_context());
old_level = intr_disable();
if (cur != idle_thread)
list_push_back(&ready_list, &cur->elem);
cur->status = THREAD_READY;
schedule();
intr_set_level(old_level);
}
```
首先定义了一个线程结构体指针cur，调用`thread_current()`来获取指向页面初始位置的指针。第八行和第十三行实现了关中断和开中断。
总的来说，`thread_yield()`函数的作用便是将当前线程放入就绪队列，并调度下一线程。而`timer_sleep()`函数便是在限定的时间内，使运行的程序不停的放入就绪队列，从而达到休眠的目的。
- 改写后的`timer_sleep()`
```c
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);
}
```
>A3: What steps are taken to minimize the amount of time spent in
>the timer interrupt handler?
- `timer_interrupt()`的逻辑
`timer_interrupt()`的代码如下：
```C
static void
timer_interrupt (struct intr_frame *args UNUSED)
{
ticks++;
thread_tick ();
}
```
在每次定时器中断期间，我们会循环遍历 sleep_list 中的所有线程，直到找到第一个 sleep_timer 尚未过期的线程。
如果该线程的 sleep_timer 等于或小于当前的 tick，我们就会从 sleep_list 中移除该线程并解除阻塞，让它回到就绪队列中。
我们会停在第一个未过期的线程上。由于列表是排序的，所以后面的线程也不会过期。
- 改写后的`timer_interrupt()`
```c
static void
timer_interrupt (struct intr_frame *args UNUSED)
{
ticks++;
thread_tick ();
thread_foreach (blocked_thread_check, NULL);
}
```
加入`thread_foreach (blocked_thread_check, NULL);`以对所有被阻塞线程进行阻塞时间的计算。
`thread_foreach()`代码如下：
```c
void thread_foreach(thread_action_func *func, void *aux)
{
struct list_elem *e;
ASSERT(intr_get_level() == INTR_OFF);
for (e = list_begin(&all_list); e != list_end(&all_list);e = list_next(e))
{
struct thread *t = list_entry(e, struct thread, allelem);
func(t, aux);
}
}
```
第七到十一行实现了对整个sleep_lis的遍历。
`blocked_thread_check()`函数实现如下：
```c
void blocked_thread_check (struct thread *t, void *aux UNUSED)
{
if (t->status == THREAD_BLOCKED && t->ticks_blocked > 0)
{
t->ticks_blocked--;
if (t->ticks_blocked == 0)
{
thread_unblock(t);
}
}
}
```
逻辑为如果这个线程处于阻塞态且阻塞时间还未结束，则减小其阻塞时间并判断当其不用再被阻塞，便调用Pintos函数`thread_unblock()`将线程放入就绪队列并更改为就绪态。
#### SYNCHRONIZATION
>A4: How are race conditions avoided when multiple threads call
>timer_sleep() simultaneously?
在 timer_sleep() 中获取当前的要阻塞的线程，为其设置阻塞时间，并调用Pintos的线程阻塞函数，我们会关中断，即` enum intr_level old_level = intr_disable ();`。执行完成后再开中断，即` intr_set_level (old_level);`。这样就可以避免操作被中断。这样做是为了避免多个线程同时调用 sleep 时出现竞争条件。另外，调用 thread_block 时必须关闭中断。
>A5: How are race conditions avoided when a timer interrupt occurs
>during a call to timer_sleep()?
由于 CPU 外部设备（如定时器）产生的外部中断是在中断关闭的情况下运行的，因此它们不会嵌套，也不会被抢占，所以我们在调用timer_interrupt时无需手动关闭中断或锁定。
#### RATIONALE
>A6: Why did you choose this design? In what ways is it superior to
>another design you considered?
我通过重写原本的`timer_sleep()`函数避免了忙等待提高了资源利用率。想到通过调用自带的`thread_block()`来避免忙等待的功能，因此我需要增加一个变量`ticks_blocked`来记录等待时间。
在重写`timer_interrupt()`函数时利用自带的`thread_foreach()`函数实现对每个进阻塞线程的检查，而不是新开一个`sleep_list`变量来记录，节省了空间。时间复杂度为O(n)，比较低。
## Priority Scheduling
#### DATA STRUCTURES
>B1: Copy here the declaration of each new or changed struct or struct member, global or static variable, typedef, or enumeration. Identify the purpose of each in 25 words or less.
>B2: Explain the data structure used to track priority donation.
>Use ASCII art to diagram a nested donation. (Alternately, submit a
>.png file.)
- 在线程结构体中加入`base_priority`来记录基本优先级
- 在线程结构体中加入`locks`来记录哪个线程持有锁
- 在线程结构体中加入`lock_waiting`来记录线程在等待的锁的列表
- 在lock结构体中加入了`elem`来记录优先级捐赠
- 在lock结构体中加入了`max_priority`来记录最大优先级
#### ALGORITHMS
>B3: How do you ensure that the highest priority thread waiting for
>a lock, semaphore, or condition variable wakes up first?
首先要实现一个比较函数`thread_cmp_priority()`来比较优先级：
```c
bool thread_cmp_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;
}
```
然后在只要在每次插入新进程到list中时都保证按优先级插入到何时到位置即可，这样一直都是最高优先级的线程先被唤醒。调用Pintos预置函数`list_insert_ordered()`替换`thread_unblock()`、`init_thread()`、`thread_yield()`中的`list_push_back()`函数：
`thread_unblock()`：
```c
void thread_unblock (struct thread *t)
{
enum intr_level old_level;
ASSERT (is_thread (t));
old_level = intr_disable ();
ASSERT (t->status == THREAD_BLOCKED);
list_insert_ordered (&ready_list, &t->elem, (list_less_func *) &thread_cmp_priority, NULL);
t->status = THREAD_READY;
intr_set_level (old_level);
}
```
`init_thread()`：
```C
static void
init_thread (struct thread *t, const char *name, int priority)
{
enum intr_level old_level;
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;
old_level = intr_disable ();
list_insert_ordered (&all_list, &t->allelem, (list_less_func *) &thread_cmp_priority, NULL);
intr_set_level (old_level);
}
```
`thread_yield()`：
```c
void thread_yield (void)
{
struct thread *cur = thread_current ();
enum intr_level old_level;
ASSERT (!intr_context ());
old_level = intr_disable ();
if (cur != idle_thread)
list_insert_ordered (&ready_list, &cur->elem, (list_less_func *) &thread_cmp_priority, NULL);
cur->status = THREAD_READY;
schedule ();
intr_set_level (old_level);
}
```
而为了维持list始终保持优先级从高到低的顺序，我们需要在优先级被修改时重排序。若创建的线程优先级高于正在运行的进程的优先级，就要把正在运行的线程加入就绪队列，让新创建的线程上处理机。因此我们要在`thread_set_priority`函数中加入`thread_yield`，其代码如下：
```c
void thread_set_priority (int new_priority)
{
thread_current ()->priority = new_priority;
thread_yield ();
}
```
同时修改`thread_create`判断当前要创建的进程优先级与正在运行的进程的优先级：
```c
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;
ASSERT (function != NULL);
/* Allocate thread. */
t = palloc_get_page (PAL_ZERO);
if (t == NULL)
return TID_ERROR;
/* Initialize thread. */
init_thread (t, name, priority);
tid = t->tid = allocate_tid ();
t->ticks_blocked = 0;
/* 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;
/* Add to run queue. */
thread_unblock (t);
//新加入的语句
if (thread_current ()->priority < priority)
{
thread_yield ();
}
return tid;
}
```
>B4: Describe the sequence of events when a call to lock_acquire()
>causes a priority donation. How is nested donation handled?
如前所述，每个锁都会记录当前线程的所有者。当一个线程试图获取一个锁时，它首先会检查锁的所有者；如果锁是无所有者的，那么它必然是解锁的，因此可以被直接地获取，所有者被设置为获取锁的线程。
如果锁不是无主的，即当前由现有线程拥有，新线程将：
1. 禁用中断；
2. 将新线程添加到位于锁的底层 semaphore 中的等待者列表中；
3. 如果锁的最大优先级`l->max_priority`小于`current_thread->priority`，则将锁中的`max_priority`值更新为新线程的有效优先级。
4. 如果我们在上一步中更改了`max_priority`，则应用如下迭代算法，将优先级捐赠向下传递到该锁被阻塞的任何线程。
```c
while (l && current_thread->priority > l->max_priority)
{
l->max_priority = current_thread->priority;
thread_donate_priority (l->holder);
l = l->holder->lock_waiting;
}
```
5. 启用中断
6. 调用`sema_down`
其修改后代码如下：
```c
void sema_down (struct semaphore *sema)
{
enum intr_level old_level;
ASSERT (sema != NULL);
ASSERT (!intr_context ());
old_level = intr_disable ();
while (sema->value == 0)
{
list_insert_ordered (&sema->waiters, &thread_current ()->elem, thread_cmp_priority, NULL);
thread_block ();
}
sema->value--;
intr_set_level (old_level);
}
```
`acquire_lock()`完整代码如下：
```c
void lock_acquire(struct lock *lock)
{
struct thread *current_thread = thread_current();
struct lock *l;
enum intr_level old_level;
ASSERT(lock != NULL);
ASSERT(!intr_context());
ASSERT(!lock_held_by_current_thread(lock));
if (lock->holder != NULL && !thread_mlfqs)
{
current_thread->lock_waiting = lock;
l = lock;
while (l && current_thread->priority > l->max_priority)
{
l->max_priority = current_thread->priority;
thread_donate_priority(l->holder);
l = l->holder->lock_waiting;
}
}
}
```
>B5: Describe the sequence of events when lock_release() is called
>on a lock that a higher-priority thread is waiting for.
当线程释放锁时，我们将依次
1. 禁用中断
2. 取消设置锁所有者变量
3. 从线程的 lock列表中移除锁；
4. 在当前线程上更新优先级`thread_update_priority(thread_current ())`
5. 启用中断；
6. 调用` sema_up()`
完整代码如下：
```c
void lock_release (struct lock *lock)
{
ASSERT (lock != NULL);
ASSERT (lock_held_by_current_thread (lock));
//new code
if (!thread_mlfqs)
thread_remove_lock (lock);
lock->holder = NULL;
sema_up (&lock->semaphore);
}
void thread_remove_lock (struct lock *lock)
{
enum intr_level old_level = intr_disable ();
list_remove (&lock->elem);
thread_update_priority (thread_current ());
intr_set_level (old_level);
}
```
修改后的`sema_up()`如下：
```c
void sema_up (struct semaphore *sema)
{
enum intr_level old_level;
ASSERT (sema != NULL);
old_level = intr_disable ();
if (!list_empty (&sema->waiters))
{
list_sort (&sema->waiters, thread_cmp_priority, NULL);
thread_unblock (list_entry (list_pop_front (&sema->waiters), struct thread, elem));
}
sema->value++;
thread_yield ();
intr_set_level (old_level);
}
```
#### SYNCHRONIZATION
>B6: Describe a potential race in thread_set_priority() and explain
>how your implementation avoids it. Can you use a lock to avoid
>this race?
整个优先级调度程序是在`next_thread_too_run()`中实现的，它在调度程序本身中运行，因此在运行时总是禁用中断。因此不会出现竞争条件。
#### RATIONALE
>B7: Why did you choose this design? In what ways is it superior to
>another design you considered?
选择使用迭代函数而不是递归，是因为递归函数在堆栈分配和代码复杂度方面的开销得不偿失，因为 C 语言对尾部递归函数没有任何特殊处理。
由于 Pintos 中的所有同步原语在某种程度上都是使用信号实现的，因此我们选择在信号对象中实现优先级功能；这样，条件变量和锁也会自动遵循相同的功能。
在每个锁中包含`max_priority`，可以提升效率，因为在`lock_release()`时只需要调用一次`thread_update_priority()`，而不是每次调用`lock_release()`时调用 n 次`thread_update_priority()`，其中 n 是线程持有锁的数量。
## Advanced Scheduler
#### DATA STRUCTURES
>C1: Copy here the declaration of each new or changed struct or struct member, global or static variable, typedef, or enumeration. Identify the purpose of each in 25 words or less.
- 在`thread`结构体中添加变量`nice`来记录Niceness
- 在`thread`结构体中添加变量`recent_cpu`
- 声明全局变量`load_avg`
#### ALGORITHMS
>C2: How is the way you divided the cost of scheduling between code inside and outside interrupt context likely to affect performance?
对 `recent_cpu` 和优先级的大部分计算都是在定时器中断中完成的，每隔一定数量的 ticks 一次。通过每 4 个刻度只更新当前运行线程的优先级，以及每 1 秒更新所有线程的优先级，thread_tick () 中的冗余计算得以减少。
#### RATIONALE
>C3: Briefly critique your design, pointing out advantages and disadvantages in your design choices. If you were to have extra time to work on this part of the project, how might you choose to refine or improve your design?
利用pintos自带的函数实现功能，可以减小代码体积，例如调用`thread_foreach()`函数来实现对list中所有的项的遍历。
至于缺点，链表的使用极大地影响了性能，因为代码中经常使用以 O(n) 复杂度运行的有序插入和修改，一项建议包括使用优先级队列或者堆进行优化，该队列支持在 O(log n) 时间内插入和修改，并通过一些变通方法来确保稳定性，而且无需完全排序。最后，完善设计的考虑因素可能包括检测定点操作中的溢出。
>C4: The assignment explains arithmetic for fixed-point math in detail, but it leaves it open to you to implement it. Why did you decide to implement it the way you did? If you created an abstraction layer for fixed-point math, that is, an abstract data type and/or a set of functions or macros to manipulate fixed-point numbers, why did you do so? If not, why not?
`fixed-point.h `完全通过使用支持`fixed-point`算术运算的宏来实现。它们通常更快，因为它们不需要函数调用或激活记录，还允许编译器优化方程。在调度程序的整个执行过程中，例如在 `recent_cpu `和` load_avg `中使用的实数，都是使用`fixed-point`表示法而不是浮点表示法来 "模拟 "的。
完整的宏定义如下：
```c
#ifndef __THREAD_FIXED_POINT_H
#define __THREAD_FIXED_POINT_H
/* Basic definitions of fixed point. */
typedef int fixed_t;
/* 16 LSB used for fractional part. */
#define FP_SHIFT_AMOUNT 16
/* Convert a value to a fixed-point value. */
#define FP_CONST(A) ((fixed_t)(A << FP_SHIFT_AMOUNT))
/* Add two fixed-point value. */
#define FP_ADD(A,B) (A + B)
/* Add a fixed-point value A and an int value B. */
#define FP_ADD_MIX(A,B) (A + (B << FP_SHIFT_AMOUNT))
/* Subtract two fixed-point value. */
#define FP_SUB(A,B) (A - B)
/* Subtract an int value B from a fixed-point value A. */
#define FP_SUB_MIX(A,B) (A - (B << FP_SHIFT_AMOUNT))
/* Multiply a fixed-point value A by an int value B. */
#define FP_MULT_MIX(A,B) (A * B)
/* Divide a fixed-point value A by an int value B. */
#define FP_DIV_MIX(A,B) (A / B)
/* Multiply two fixed-point value. */
#define FP_MULT(A,B) ((fixed_t)(((int64_t) A) * B >> FP_SHIFT_AMOUNT))
/* Divide two fixed-point value. */
#define FP_DIV(A,B) ((fixed_t)((((int64_t) A) << FP_SHIFT_AMOUNT) / B))
/* Get the integer part of a fixed-point value. */
#define FP_INT_PART(A) (A >> FP_SHIFT_AMOUNT)
/* Get the rounded integer of a fixed-point value. */
#define FP_ROUND(A) (A >= 0 ? ((A + (1 << (FP_SHIFT_AMOUNT - 1))) >> FP_SHIFT_AMOUNT) \
: ((A - (1 << (FP_SHIFT_AMOUNT - 1))) >> FP_SHIFT_AMOUNT))
#endif /* threads/fixed-point.h */
```
Sign in with Wallet
Connect another wallet