Pwn进你的心
0%

Ucore-Lab7

Posted on Edited on In 23k 21 mins.

原子操作

原子操作（Atomic Operator）是指一次不存在任何中断或失效的操作

等待队列

前面的实验中已经实现了进程运行队列（就绪队列），而等待队列和它们类似：

1
2
3
4
5
6
7
8
9
10
typedef struct {
    list_entry_t wait_head; /* 等待队列的头结点(哨兵节点) */
} wait_queue_t;

typedef struct {
    struct proc_struct *proc; /* 关联的进程 */
    uint32_t wakeup_flags; /* 唤醒标识 */
    wait_queue_t *wait_queue; /* 该节点所属的等待队列 */
    list_entry_t wait_link; /* 其等待队列的链表结构,可以看作是队列结点 */
} wait_t;

等待队列结构底层操作：

  • wait_init：初始化 wait 等待队列项，为 wait（等待队列结构体）绑定一个 proc（进程）
1
2
3
4
5
6
void
wait_init(wait_t *wait, struct proc_struct *proc) {
    wait->proc = proc; /* 设置关联的进程 */
    wait->wakeup_flags = WT_INTERRUPTED; /* 等待状态可中断(苏醒) */
    list_init(&(wait->wait_link)); /* 初始化等待队列 */
}
  • wait_queue_init：初始化等待队列
1
2
3
4
void
wait_queue_init(wait_queue_t *queue) {
    list_init(&(queue->wait_head)); /* 初始化等待队列 */
}
  • wait_queue_add：将 wait 节点项插入等待队列
1
2
3
4
5
6
void
wait_queue_add(wait_queue_t *queue, wait_t *wait) {
    assert(list_empty(&(wait->wait_link)) && wait->proc != NULL);
    wait->wait_queue = queue; /* 设置该等待队列结点所属的等待队列 */
    list_add_before(&(queue->wait_head), &(wait->wait_link)); /* 插头 */
}
  • wait_queue_del：将 wait 项从等待队列中移除
1
2
3
4
5
void
wait_queue_del(wait_queue_t *queue, wait_t *wait) {
    assert(!list_empty(&(wait->wait_link)) && wait->wait_queue == queue);
    list_del_init(&(wait->wait_link)); /* 脱链 */
}
  • wait_queue_next：获取等待队列中wait节点的下一项
1
2
3
4
5
6
7
8
9
wait_t *
wait_queue_next(wait_queue_t *queue, wait_t *wait) {
    assert(!list_empty(&(wait->wait_link)) && wait->wait_queue == queue);
    list_entry_t *le = list_next(&(wait->wait_link));
    if (le != &(queue->wait_head)) {
        return le2wait(le, wait_link); /* 根据链表信息获取wait结构体 */
    }
    return NULL;
}
  • wait_queue_prev：获取等待队列中wait节点的前一项
1
2
3
4
5
6
7
8
9
wait_t *
wait_queue_prev(wait_queue_t *queue, wait_t *wait) {
    assert(!list_empty(&(wait->wait_link)) && wait->wait_queue == queue);
    list_entry_t *le = list_prev(&(wait->wait_link));
    if (le != &(queue->wait_head)) {
        return le2wait(le, wait_link); /* 根据链表信息获取wait结构体 */
    }
    return NULL;
}
  • wait_queue_first：获取等待队列的第一项
1
2
3
4
5
6
7
8
wait_t *
wait_queue_first(wait_queue_t *queue) {
    list_entry_t *le = list_next(&(queue->wait_head));
    if (le != &(queue->wait_head)) {
        return le2wait(le, wait_link); /* 根据链表信息获取wait结构体 */
    }
    return NULL;
}
  • wait_queue_last：获取等待队列的最后一项
1
2
3
4
5
6
7
8
wait_t *
wait_queue_last(wait_queue_t *queue) {
    list_entry_t *le = list_prev(&(queue->wait_head));
    if (le != &(queue->wait_head)) {
        return le2wait(le, wait_link); /* 根据链表信息获取wait结构体 */
    }
    return NULL;
}
  • wait_queue_empty：检查等待队列是否为空
1
2
3
4
5
6
7
8
9
bool
wait_queue_empty(wait_queue_t *queue) {
    return list_empty(&(queue->wait_head));
}

static inline bool
list_empty(list_entry_t *list) {
    return list->next == list;
}
  • wait_in_queue：检查 wait 项是否在等待队列中
1
2
3
4
bool
wait_in_queue(wait_t *wait) {
    return !list_empty(&(wait->wait_link));
}

等待队列休眠/唤醒等高层操作：

  • wakeup_wait：将等待队列中的 wait 项对应的线程唤醒
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void
wakeup_wait(wait_queue_t *queue, wait_t *wait, uint32_t wakeup_flags, bool del) {
    if (del) {
        wait_queue_del(queue, wait); /* 根据del标识来决定该wait结构体是否保留 */
    }
    wait->wakeup_flags = wakeup_flags; /* 已经苏醒 */
    wakeup_proc(wait->proc); /* 唤醒该进程 */
}

void
wakeup_proc(struct proc_struct *proc) {
    assert(proc->state != PROC_ZOMBIE);
    bool intr_flag;
    local_intr_save(intr_flag);
    {
        if (proc->state != PROC_RUNNABLE) {
            proc->state = PROC_RUNNABLE; /* 设置"PROC_RUNNABLE" */
            proc->wait_state = 0;
            if (proc != current) {
                sched_class_enqueue(proc);
            }
        }
        else {
            warn("wakeup runnable process.\n");
        }
    }
    local_intr_restore(intr_flag);
}
  • wakeup_first：将等待队列中的第一项对应的线程唤醒
1
2
3
4
5
6
7
8
void
wakeup_first(wait_queue_t *queue, uint32_t wakeup_flags, bool del) {
    wait_t *wait;
    if ((wait = wait_queue_first(queue)) != NULL) {
        /* 调用wait_queue_first获取等待队列的第一项,然后将其唤醒 */
        wakeup_wait(queue, wait, wakeup_flags, del);
    }
}
  • wakeup_queue：将等待队列中的所有项对应的线程全部唤醒
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void
wakeup_queue(wait_queue_t *queue, uint32_t wakeup_flags, bool del) {
    wait_t *wait;
    if ((wait = wait_queue_first(queue)) != NULL) {
        if (del) { /* 根据del标识来决定该wait结构体是否保留 */
            do {
                wakeup_wait(queue, wait, wakeup_flags, 1); 
            } while ((wait = wait_queue_first(queue)) != NULL);
        }
        else {
            do {
                wakeup_wait(queue, wait, wakeup_flags, 0);
            } while ((wait = wait_queue_next(queue, wait)) != NULL);
        }
    }
}
  • wait_current_set：为当前进程绑定 wait，使其休眠并且插入等待队列
1
2
3
4
5
6
7
8
void
wait_current_set(wait_queue_t *queue, wait_t *wait, uint32_t wait_state) {
    assert(current != NULL);
    wait_init(wait, current); /* 为wait绑定进程current */
    current->state = PROC_SLEEPING; /* 设置当前进程状态为:PROC_SLEEPING(睡眠) */
    current->wait_state = wait_state; /* 设置等待原因(人工输入) */
    wait_queue_add(queue, wait); /* 将wait节点项插入等待队列 */
}
  • wait_current_del：将 wait 项（绑定有当前进程）从等待队列中删除（如果存在的话）
1
2
3
4
5
6
7
8
#define wait_current_del(queue, wait)                                       \
    do {                                                                    \
        if (wait_in_queue(wait)) {                                          \
            wait_queue_del(queue, wait);                                    \
        }                                                                   \
    } while (0)

#endif /* !__KERN_SYNC_WAIT_H__ */

临界区

每个进程中访问临界资源的那段程序称为临界区，临界资源是一次仅允许一个进程使用的共享资源，每次只准许一个进程进入临界区，进入后不允许其他进程进入

相关区域的概念：

  • 临界区（critical section）：进程中访问临界资源的一段需要互斥执行的代码
  • 进入区（entry section）：检查可否进入临界区的一段代码，如果可以进入，则设置“正在访问临界区”标志
  • 退出区（exit section）：清除标志
  • 剩余区（remainder section）：代码中的其余部分

信号量

信号量是一个有整数值的对象，可以用两个函数来操作它

Linux中的信号量是一种睡眠锁，本质上是一个计数器，用于多进程对共享数据对象的读取，它和管道有所不同，它不以传送数据为主要目的，它主要是用来保护共享资源（信号量也属于临界资源），使得资源在一个时刻只有一个进程独享

  • 信号量（Semaphore）是操作系统提供的一种协调共享资源访问的方法
    • 软件同步是平等线程间的一种同步协商机制
    • OS 是管理者，地位高于进程
    • 用信号量表示系统资源的数量
  • 信号量是一种抽象数据类型
    • 由一个整数（sem）变量和两个原子操作（PV）组成
    • 整数sem：
      • sem >= 0：代表剩余可供并发进程使用的资源实体数
      • sem < 0：代表正在使用的资源实体数
    • P操作：
      • sem —
      • 如果 sem < 0，则该进程进入阻塞队列（等待队列）
      • 如果 sem >= 0，则该进程继续执行
    • V操作：
      • sem ++
      • 如果 sem < 0，则唤醒阻塞队列中的第一个等待信号量的进程
      • 如果 sem > 0，则该进程继续执行
  • 信号量是被保护的整数变量
    • 初始化完成后，只能通过 P() 和 V() 操作修改
    • 由操作系统来保证，PV操作是原子操作

PV操作

PV操作是一种实现进程互斥与同步的有效方法，PV操作与信号量的处理相关（P表示通过的意思，V表示释放的意思）

PV操作是典型的同步机制之一，用一个信号量与一个消息联系起来

  • 当信号量的值为“0”时，表示期望的消息尚未产生
  • 当信号量的值非“0”时，表示期望的消息已经存在

用PV操作实现进程同步时，调用P操作测试消息是否到达，调用V操作发送消息

ucore 中采用以下结构体来管理信号量

1
2
3
4
typedef struct {
    int value; /* 信号量值 */
    wait_queue_t wait_queue; /* 等待队列 */
} semaphore_t;
  • value 是用于判断该信号量能否进入临界区的关键参数
  • wait_queue 记录了该信号量所属的等待队列，便于之后的 wait_current_set 和 wait_current_del 把当前进程填入或取出该等待队列

进入临界区时，uCore会执行 down 函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void
down(semaphore_t *sem) {
    uint32_t flags = __down(sem, WT_KSEM); /* 等待原因:内核信号量WT_KSEM */
    assert(flags == 0);
}

static __noinline uint32_t __down(semaphore_t *sem, uint32_t wait_state) {
    bool intr_flag;
    local_intr_save(intr_flag);
    if (sem->value > 0) {
        /* 当信号量的value值大于'0'时,说明还能容纳当前线程进入临界区 */
        sem->value --; /* value值递减(扣减信号量) */
        local_intr_restore(intr_flag);
        return 0;
    }
    /* 当信号量的value值等于'0'时,说明已经无法容纳更多的线程了 */
    wait_t __wait, *wait = &__wait;
    wait_current_set(&(sem->wait_queue), wait, wait_state); /* 使当前进程休眠 */
    local_intr_restore(intr_flag);

    schedule(); /* 重新执行调度程序(当前进程放弃CPU资源) */

    local_intr_save(intr_flag);
    wait_current_del(&(sem->wait_queue), wait); /* 将wait项从等待队列中删除 */
    local_intr_restore(intr_flag);

    if (wait->wakeup_flags != wait_state) {
        return wait->wakeup_flags;
    }
    return 0;
}
  • 当信号量的value值大于“0”时，说明还能容纳当前线程进入临界区
  • 当信号量的value值等于“0”时。说明已经无法容纳更多的线程了，此时需要将当前线程阻塞在信号量的等待队列上，等待信号量的 up 操作将其唤醒
  • 按照程序的逻辑，value值不可能小于“0”

退出临界区时，uCore会执行 up 函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void
up(semaphore_t *sem) {
    __up(sem, WT_KSEM);
}

static __noinline void __up(semaphore_t *sem, uint32_t wait_state) {
    bool intr_flag;
    local_intr_save(intr_flag);
    {
        wait_t *wait;
        if ((wait = wait_queue_first(&(sem->wait_queue))) == NULL) {
            /* 尝试获取等待队列的第一项,如果有就唤醒,没有就增加信号量 */
            sem->value ++; /* value值递增(增加信号量) */
        }
        else {
            assert(wait->proc->wait_state == wait_state);
            wakeup_wait(&(sem->wait_queue), wait, wait_state, 1); /* 将等待队列中的wait项对应的线程唤醒 */
        }
    }
    local_intr_restore(intr_flag);
}
  • 等待队列为NULL，代表了资源实体充足，也就是说没有进程因为“互斥资源实体不足”而进入等待队列，自然没有必要唤醒
  • 信号量增加，代表了剩余可供并发进程使用的资源实体数增加

PS：可以发现，ucore 对临界区的处理和 PV 操作有点不同，并没有刻意让 value 值为负，而是直接将当前进程添加入等待队列，退出临界区时，又从等待队列中唤醒该进程

与信号量有关的函数

  • sem_init：初始化信息量（各个条目需要手动输入）
1
2
3
4
5
void
sem_init(semaphore_t *sem, int value) {
    sem->value = value;
    wait_queue_init(&(sem->wait_queue));
}
  • 未进行初始化的信号量根本就没有对应的等待队列，所以需要调用 wait_queue_init 来初始化一个等待队列
  • 因为信号量是分配到栈上的，所以不需要格外的“create”或者“destroy”操作

管程

管程（Monitor）是一种用于多线程互斥访问共享资源的程序结构（其实就是封装了一下PV操作），它为进程提供了一种“抽象”，使进程可以通过访问管程来间接访问共享资源

  • 采用面向对象方法，简化了线程间的同步控制
  • 任一时刻最多只有一个线程执行管程代码
  • 正在管程中的线程可临时放弃管程的互斥访问，等待事件出现时恢复

管程的组成

  • 一个锁：控制管程代码的互斥访问
  • 0-n 个条件变量：用于管理共享数据的并发访问

引入管程机制的目的：

  • 把分散在各进程中的临界区集中起来进行管理
  • 防止进程有意或无意的违法同步操作（防止死锁）
  • 便于用高级语言来书写程序，也便于程序正确性验证

在 ucore 中有如下结构体来管理管程：

1
2
3
4
5
6
7
8
typedef struct monitor monitor_t;

typedef struct monitor{
    semaphore_t mutex;      // 管程锁,每次只能有一个进程执行管程代码(该值初始化为'1')
    semaphore_t next;       // 用于条件同步(进程同步操作的信号量),发出signal操作的进程等条件为真之前进入睡眠
    int next_count;         // 休眠的信令进程数
    condvar_t *cv;          // 当前管程中存放所有条件变量的数组
} monitor_t;
  • mutex：
    • 管程中的成员变量 mutex 是一个二值信号量，是实现每次只允许一个进程进入管程的关键元素，确保了互斥访问性质
  • cv：
    • 管程中的条件变量 cv 通过执行 wait_cv，会使得等待某个条件 C 为真的进程能够离开管程并睡眠，且让其他进程进入管程继续执行
    • 而进入管程的某进程设置条件 C 为真并执行 signal_cv 时，能够让等待某个条件 C 为真的睡眠进程被唤醒，从而继续进入管程中执行
  • next，next_count：
    • 管程中的成员变量信号量 next 和整形变量 next_count 是配合进程对条件变量 cv 的操作而设置的
    • 这是由于发出signal_cv 的进程 A 会唤醒睡眠进程 B，进程 B 执行会导致进程 A 睡眠，直到进程 B 离开管程，进程 A 才能继续执行，这个同步过程是通过信号量 next 完成的

下面是与条件变量有关的结构体：

1
2
3
4
5
typedef struct condvar{
    semaphore_t sem;        // 条件变量所对应的信号量
    int count;              // 等待当前条件变量的等待进程总数
    monitor_t * owner;      // 当前条件变量的父管程
} condvar_t;
  • sem：信号量 sem 用于让发出 wait_cv 操作的
  • count：表示等在这个条件变量上的睡眠进程的个数
  • owner：表示此条件变量的宿主是哪个管程

与管程有关的函数：

  • monitor_init：初始化一个管程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void     
monitor_init (monitor_t * mtp, size_t num_cv) {
    int i;
    assert(num_cv>0);
    mtp->next_count = 0;
    mtp->cv = NULL;
    sem_init(&(mtp->mutex), 1); /* 初始化信号量mutex(管程锁)为'1' */
    sem_init(&(mtp->next), 0); /* 初始化信号量next为'0' */
    mtp->cv =(condvar_t *) kmalloc(sizeof(condvar_t)*num_cv); /* 分配条件变量 */
    assert(mtp->cv!=NULL);
    for(i=0; i<num_cv; i++){ /* 初始化各个条件变量的值 */
        mtp->cv[i].count=0;
        sem_init(&(mtp->cv[i].sem),0);
        mtp->cv[i].owner=mtp;
    }
}
  • cond_signal：当某个线程准备离开临界区，准备释放对应的条件变量时，执行该函数（需要实现）
  • cond_wait：当某个线程需要等待锁时，执行该函数（需要实现）

进程的交互关系

相互感知的程度 交互关系 进程间的影响
相互不感知（完全不了解其他进程的存在） 独立 一个进程的操作对其他进程的结果无影响
间接感知（双方都与第三方交互，例如数据共享） 通过共享进行协作 一个进程的结果依赖于共享资源的状态
直接感知（双方直接交互，例如通信） 通过通信进行协作 一个进程的结果依赖于从其他进程获得的信息

进程之间可能出现三种关系：

  • 互斥（mutual exclusion）：一个进程占用资源，其他进程不能使用
  • 死锁（deadlock）：多个进程占用部分资源，形成循环等待
  • 饥饿（starvation）：其他进程可能轮流占用资源，一个进程一直得不到资源

CAS与锁

CAS

CPU拥有多个物理核心，利用超线程技术可以把这些物理核心分为更多的逻辑核心

这就产生了一些问题：

左边是我们预想的执行顺序，右边是可以产生的情况（从不同的寄存器中读取了“0”）

如果把 “i++” 设置为原子操作，那么 “i+2”，“i+3”，“i*3” …… 这些都要设置为原子操作，大大影响了效率，于是 CPU 就提供了一个抽象的底层指令 cas（Compare and Set）

1
cas(&i,0,1);
  • 更新内存地址“i”的时候，需要告诉CPU过去的值“0”，和想要更新的值“1”，CPU会先对比过去的值，然后再更新需要的值“1”，如果对比不通过，CPU就不作出相应
  • 通过这种方式，CPU可以给更多指令添加原子操作

假设有两个线程：（“i”初始化为“0”）

1
2
A: i++;
B: i++;

线程A可以通过“cas(&i,0,1)”，然后“i”变为“1”，线程B就不能通过了，然后线程B就会采取如下操作：

1
while(!cas(&i,i,i++));

锁

锁是一个抽象的数据结构：

  • 使用一个二进制变量，用于表示锁定/解锁
  • Lock::Acquire()：锁被释放前一直等待，直到得到锁
  • Lock::Release()：释放锁，唤醒任何等待的进程

使用锁可以解决一些 cas 无法解决的问题

定时器

定时器（timer）可以帮助操作系统在 经过一段特定时间 后执行一些特殊操作（例如：唤醒执行线程），可以说，正是有了定时器，操作系统才有了时间这个概念

timer_t 结构体中存储了一个定时器所需要的相关数据，包括 倒计时时间 以及 所绑定的进程

1
2
3
4
5
typedef struct {
    unsigned int expires;			// 定时器的过期时间(指定定时器到期的时间)
    struct proc_struct *proc;		// 在计时器中等待的进程(如果过期时间已结束,该进程将被重新安排)
    list_entry_t timer_link;		// 计时器链表(用于管理计时器)
} timer_t;

以下便是 ucore 中和定时器有关的函数：

  • timer_init：用于初始化并返回某个 timer（各个参数都需要手动设置）
1
2
3
4
5
6
7
static inline timer_t *
timer_init(timer_t *timer, struct proc_struct *proc, int expires) {
    timer->expires = expires; 
    timer->proc = proc;
    list_init(&(timer->timer_link));
    return timer;
}
  • add_timer：用于将某个 timer 按照 expires 的大小添加进 timer链表 中 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
static list_entry_t timer_list; /* 记录有timer链表的链表头 */

void
add_timer(timer_t *timer) {
    bool intr_flag;
    local_intr_save(intr_flag); /* local_intr_save:屏蔽中断 */
    {
        assert(timer->expires > 0 && timer->proc != NULL);
        assert(list_empty(&(timer->timer_link)));
        list_entry_t *le = list_next(&timer_list); /* 获取链表头 */
        while (le != &timer_list) { /* 遍历整个链表,按照expires大小插链(从小到大) */
            timer_t *next = le2timer(le, timer_link); 
            if (timer->expires < next->expires) { 
                next->expires -= timer->expires; /* 使目标结点next的expires减去timer->expires */
                break;
            }
            timer->expires -= next->expires; /* 每遍历一次,timer->expires不断减小(保证了expires是从小到大排序的) */
            le = list_next(le);
        }
        list_add_before(le, &(timer->timer_link)); /* 插入结点前(从小到大) */
    }
    local_intr_restore(intr_flag); /* local_intr_restore:打开中断 */
}
  • del_timer：用于将某个 timer 从 timer链表 中删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void del_timer(timer_t *timer) {
    bool intr_flag;
    local_intr_save(intr_flag); /* local_intr_save:屏蔽中断 */
    {
        if (!list_empty(&(timer->timer_link))) {
            if (timer->expires != 0) {
                list_entry_t *le = list_next(&(timer->timer_link));
                if (le != &timer_list) {
                    timer_t *next = le2timer(le, timer_link);
                    next->expires += timer->expires; /* 设使目标结点next的expires加上timer->expires(平衡add_timer的影响) */
                }
            }
            list_del_init(&(timer->timer_link)); /* 将当前timer从链表中移除 */
        }
    }
    local_intr_restore(intr_flag); /* local_intr_restore:打开中断 */
}
  • run_timer_list：用于更新定时器的时间，并更新当前进程的运行时间片，如果当前定时器的剩余时间结束，则唤醒某个处于 WT_INTERRUPTED 等待状态的进程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#define WT_INTERRUPTED               0x80000000 /* 等待状态可以被中断(可以苏醒) */

void
run_timer_list(void) {
    bool intr_flag;
    local_intr_save(intr_flag); /* local_intr_save:屏蔽中断 */
    {
        list_entry_t *le = list_next(&timer_list); /* 获取timer链表头 */
        if (le != &timer_list) {
            timer_t *timer = le2timer(le, timer_link); /* 获取第一个timer结构体 */
            assert(timer->expires != 0); 
            timer->expires --; /* 间接使所有timer的expires都减一的目的 */
            while (timer->expires == 0) { /* 遍历timer链表,找出所有连续的expires为0的timer,将其唤醒后再把timer删除 */
                le = list_next(le);
                struct proc_struct *proc = timer->proc; /* 获取对应的进程 */
                if (proc->wait_state != 0) {
                    assert(proc->wait_state & WT_INTERRUPTED); /* 断言正在等待的目标进程的wait_state是WT_INTERRUPTED */
                }
                else {
                    warn("process %d's wait_state == 0.\n", proc->pid);
                }
                wakeup_proc(proc); /* 设置新的子进程可执行(唤醒该进程) */
                del_timer(timer); /* 用于将某个timer从timer链表中删除 */
                if (le == &timer_list) {
                    break;
                }
                timer = le2timer(le, timer_link);
            }
        }
        sched_class_proc_tick(current); /* 处理时钟中断的函数,令调度框架更新对应的调度参数(lab6中用此函数处理时钟中断,lab7中被run_timer_list替代) */
    }
    local_intr_restore(intr_flag); /* local_intr_restore:打开中断 */
}

定时器的检查机制：

内核会每隔一段时间会检查一次定时器（如果定时器的 expires 为“0”，内存就会执行某个进程），但是检查的频率可能不相同，对于 expires 越小的定时器，内核检查的频率越高（例如：如果 expires 为“一年”，可能内核就一个月检查一次，如果 expires 小于一个月，内核就每天检查一次）

  • 处于性能考虑，每个新添加的 timer 都会按照其 expires 属性的大小排列，同时减去上一个 timer 的 expires 属性
    • 在 run_timer_list 中，程序会遍历 timer 链表，找出所有连续的expires为“0”的 timer，所以按大小排序后，一次执行 run_timer_list 后可能会找到多个目标，提高了效率
    • 按照 timer 的机制：在更新 timer_list 中的所有 timer 的 expires 时，只需递减链首的第一个 timer 的 expire，即可间接达到所有 timer 的 expires 减一的目的
1
2
3
4
5
6
7
8
9
timer1->expires = 20;
timer2->expires = 38;
timer3->expires = 24;
timer4->expires = 10;
----------------------------
timer1插入 >> timer1:20 
timer2插入 >> timer1:20 <=> timer2:18(38)
timer3插入 >> timer1:20 <=> timer3:4(24) <=> timer2:14(38)
timer4插入 >> timer4:10 <=> timer1:10(20) <=> timer3:4(24) <=> timer2:14(38)
  • 在目标 timer 遍历的时候会不断减去 “结点timer->expires” ，这样保证了 timer 链表中，原来的 timer->expires（没有进行过加减操作，是真正的 timer）是按从小到大排序的
  • 这样也避免了 “结点timer->expires” 或者 “目标timer->expires” 被减到“0”的情况发生

案例：do_sleep（将当前进程状态设置为睡眠）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int
do_sleep(unsigned int time) {
    if (time == 0) {
        return 0;
    }
    bool intr_flag;
    local_intr_save(intr_flag); /* 关闭中断 */
    timer_t __timer, *timer = timer_init(&__timer, current, time); 
    /*
    __timer:未初始化的timer
    current:为该timer绑定进程(current当前进程)
    time:设置剩余时间
    *timer:初始化完毕的timer(__timer只是临时数据,最终会把数据返回给*timer)
    */
    current->state = PROC_SLEEPING; /* 设置进程状态为:PROC_SLEEPING(睡眠) */
    current->wait_state = WT_TIMER; /* 设置等待原因为:等待定时器 */
    add_timer(timer); /* 添加该定时器 */
    local_intr_restore(intr_flag); /* 重新打开中断 */

    schedule(); /* 执行调度程序(当前进程放弃CPU资源) */

    del_timer(timer); /* 删除定时器 */
    return 0;
}

这里我会结合前面实验中有关进程的调度的部分内容，详细描述一下这个过程：

  • 内核的第一个进程 idleproc（空闲进程）会执行 cpu_idle 函数，在这个函数中循环执行 schedule 用于空闲进程的调度，这个函数是永远不会停止的
  • 其他的进程都会因为schedule 而被调度，又会因为各种原因被中断，然后再次调度
  • 当 “PROC_SLEEPING” 被设置时：schedule 就已经不会再调度该进程了，如果再次执行schedule ，CPU就会放弃当前进程，转而去遍历整个进程链表，直到找出处于就绪状态的进程，并将其调度
  • 当 “add_timer(timer)” 执行时：绑定有当前进程的 timer 被链入 timer 链表，然后CPU会周期性调用 run_timer_list 检查 timer->expires 是否为“0”
  • 如果时间结束，就会调用 wakeup_proc 重新设置该进程为 “PROC_RUNNABLE” ，这样schedule 就可以再次调度该进程了

练习0-把 lab6 的内容复制粘贴到 lab7

trap_dispatch 中有关时钟中断的部分需要更新：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
static void
trap_dispatch(struct trapframe *tf) {
    char c;

    int ret=0;

    switch (tf->tf_trapno) {
    case T_PGFLT: /* 页错误异常(page fault) */
        if ((ret = pgfault_handler(tf)) != 0) {
            print_trapframe(tf);
            /* lab5新增:与进程相关的if判断语句 */
            if (current == NULL) {
                panic("handle pgfault failed. ret=%d\n", ret);
            }
            else {
                if (trap_in_kernel(tf)) {
                    panic("handle pgfault failed in kernel mode. ret=%d\n", ret);
                }
                cprintf("killed by kernel.\n");
                panic("handle user mode pgfault failed. ret=%d\n", ret); 
                do_exit(-E_KILLED);
            }
        }
        break;
    case T_SYSCALL: /* 系统调用(syscall) */
        syscall();
        break;
            
            /*  <---- start ---->  */
    case IRQ_OFFSET + IRQ_TIMER:
        ticks ++;
        assert(current != NULL);
        run_timer_list(); /* lab7新添:更新定时器的时间,并更新当前进程的运行时间片 */
        break;
            /*  <---- end ---->  */
            
    case IRQ_OFFSET + IRQ_COM1: /* 中断请求-串口中断 */
        c = cons_getc();
        cprintf("serial [%03d] %c\n", c, c);
        break;
    case IRQ_OFFSET + IRQ_KBD: /* 中断请求-键盘中断 */
        c = cons_getc();
        cprintf("kbd [%03d] %c\n", c, c);
        break;
    case T_SWITCH_TOU: /* 中断请求-内核到用户空间触发的中断 */
    case T_SWITCH_TOK: /* 中断请求-用户空间到内核触发的中断 */
        panic("T_SWITCH_** ??\n");
        break;
    case IRQ_OFFSET + IRQ_IDE1: /* 中断请求-IDE通道1中断 */
    case IRQ_OFFSET + IRQ_IDE2: /* 中断请求-IDE通道2中断 */
            /* 本实验不涉及这一部分 */
        break;
    default:
            /* lab5改动:完善了报错处理 */
        print_trapframe(tf); /* 打印trapframe结构体(中断帧,用于存储执行中断的信息) */
        if (current != NULL) {
            cprintf("unhandled trap.\n");
            do_exit(-E_KILLED);
        }
        panic("unexpected trap in kernel.\n");
    }
}

练习1-理解内核级信号量的实现和基于内核级信号量的哲学家就餐问题

哲学家就餐问题：

  • 五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五只筷子，他们的生活方式是交替的进行思考和进餐，平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐，进餐完毕，放下筷子继续思考

ucore 中的案例：

  • 相关宏定义与结构体：
1
2
3
4
5
6
7
8
#define N 5 /* 哲学家数目 */
#define LEFT (i-1+N)%N /* i的左邻号码 */
#define RIGHT (i+1)%N /* i的右邻号码 */
#define THINKING 0 /* 哲学家正在思考 */
#define HUNGRY 1 /* 哲学家想取得叉子 */
#define EATING 2 /* 哲学家正在吃面 */
#define TIMES  4 /* 吃4次饭 */
#define SLEEP_TIME 10
  • philosopher_using_semaphore：实现主体
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int state_sema[N]; /* 记录每个人状态的数组 */
semaphore_t mutex; /* 临界区互斥 */
semaphore_t s[N]; /* 每个哲学家一个信号量 */

struct proc_struct *philosopher_proc_sema[N];

int philosopher_using_semaphore(void * arg) /* i：哲学家号码，从0到N-1 */
{
    int i, iter=0;
    i=(int)arg;
    cprintf("I am No.%d philosopher_sema\n",i);
    while(iter++<TIMES)
    { /* 无限循环 */
        cprintf("Iter %d, No.%d philosopher_sema is thinking\n",iter,i); /* 哲学家正在思考 */
        do_sleep(SLEEP_TIME);
        phi_take_forks_sema(i); /* 需要两只叉子,或者阻塞 */
        cprintf("Iter %d, No.%d philosopher_sema is eating\n",iter,i); /* 进餐 */
        do_sleep(SLEEP_TIME);
        phi_put_forks_sema(i); /* 把两把叉子同时放回桌子 */
    }
    cprintf("No.%d philosopher_sema quit\n",i);
    return 0;    
}
  • phi_take_forks_sema：需要两只叉子,或者阻塞 
1
2
3
4
5
6
7
8
void phi_take_forks_sema(int i) /* i：哲学家号码从0到N-1 */
{
        down(&mutex); /* 进入临界区 */
        state_sema[i]=HUNGRY; /* 记录下哲学家i饥饿的事实 */
        phi_test_sema(i); /* 哲学家尝试得到两只叉子,并且进餐 */
        up(&mutex); /* 离开临界区 */
        down(&s[i]); /* 如果得不到叉子就阻塞 */
}
  • phi_put_forks_sema：把两把叉子同时放回桌子 
1
2
3
4
5
6
7
8
void phi_put_forks_sema(int i) /* i：哲学家号码从0到N-1 */
{
        down(&mutex); /* 进入临界区 */
        state_sema[i]=THINKING; /* 哲学家进餐结束 */
        phi_test_sema(LEFT); /* 看一下左邻居现在是否能进餐 */
        phi_test_sema(RIGHT); /* 看一下右邻居现在是否能进餐 */
        up(&mutex); /* 离开临界区 */
}
  • phi_test_sema：哲学家尝试得到两只叉子，并且进餐
1
2
3
4
5
6
7
8
void phi_test_sema(i) /* i：哲学家号码从0到N-1 */
{ 
    if(state_sema[i]==HUNGRY && state_sema[LEFT]!=EATING && state_sema[RIGHT]!=EATING) /* 哲学家自己是饥饿状态,左右两边的哲学家都不是进食状态 */
    {
        state_sema[i]=EATING; /* 设置为进食状态 */
        up(&s[i]);
    }
}

完整过程：

  • 哲学家会循环进行两件事情：
    • phi_take_forks_sema：拿起两把叉子准备进食
    • phi_put_forks_sema：放回两把叉子
  • 本程序没有对叉子进行标记，而是通过检查相邻哲学家的进食状态，来判断自己是否可以进食
  • 在哲学家执行 phi_put_forks_sema 时，会检查相邻的哲学家是否可以进食（因为自己进食以后会归还叉子，给相邻哲学家创造了进食机会）

练习2-完成内核级条件变量和基于内核级条件变量的哲学家就餐问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef struct monitor{ /* 管程 */
    semaphore_t mutex;      // 管程锁,每次只能有一个进程执行管程代码(该值初始化为'1')
    semaphore_t next;       // 用于条件同步(进程同步操作的信号量),发出signal操作的进程等条件为真之前进入睡眠
    int next_count;         // 休眠的信令进程数
    condvar_t *cv;          // 当前管程中存放所有条件变量的数组
} monitor_t;

typedef struct condvar{ /* 条件变量 */
    semaphore_t sem;        // 条件变量所对应的信号量
    int count;              // 等待当前条件变量的等待进程总数
    monitor_t * owner;      // 当前条件变量的父管程
} condvar_t;

typedef struct { /* 信号量 */
    int value;					   // 信号量值 
    wait_queue_t wait_queue;		// 等待队列
} semaphore_t;

monitor_init 函数会初始管程，而对信号量进行的 P()，V() 操作（up，down）将会被封装为控制管程的两个函数 - cond_signal 和 cond_wait：

  • cond_signal：当某个线程准备离开临界区，准备释放对应的条件变量时，执行该函数
1
2
3
4
5
6
7
8
9
10
11
void 
cond_signal (condvar_t *cvp) {
   cprintf("cond_signal begin: cvp %x, cvp->count %d, cvp->owner->next_count %d\n", cvp, cvp->count, cvp->owner->next_count);  
    if(cvp->count>0) {
        cvp->owner->next_count ++;
        up(&(cvp->sem)); /* 尝试唤醒条件变量cvp对应的信号量中的等待队列中的第一项 */
        down(&(cvp->owner->next));
        cvp->owner->next_count --;
    }
    cprintf("cond_signal end: cvp %x, cvp->count %d, cvp->owner->next_count %d\n", cvp, cvp->count, cvp->owner->next_count);
}
  • cond_wait：当某个线程需要等待锁时，执行该函数
1
2
3
4
5
6
7
8
9
10
11
12
void
cond_wait (condvar_t *cvp) {
    cprintf("cond_wait begin:  cvp %x, cvp->count %d, cvp->owner->next_count %d\n", cvp, cvp->count, cvp->owner->next_count);
    cvp->count++;
    if(cvp->owner->next_count > 0)
        up(&(cvp->owner->next));
    else
        up(&(cvp->owner->mutex));
    down(&(cvp->sem));
    cvp->count --;
    cprintf("cond_wait end:  cvp %x, cvp->count %d, cvp->owner->next_count %d\n", cvp, cvp->count, cvp->owner->next_count);
}

下面是对哲学家就餐问题的改进：（基于管程）

  • philosopher_using_condvar：程序主体
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct proc_struct *philosopher_proc_condvar[N]; // N个哲学家
int state_condvar[N];                            // 哲学家的状态
monitor_t mt, *mtp=&mt;                          // 管程

int philosopher_using_condvar(void * arg) { 
    int i, iter=0;
    i=(int)arg;
    cprintf("I am No.%d philosopher_condvar\n",i);
    while(iter++<TIMES)
    { 
        cprintf("Iter %d, No.%d philosopher_condvar is thinking\n",iter,i); 
        do_sleep(SLEEP_TIME);
        phi_take_forks_condvar(i); /* 需要两只叉子,或者阻塞 */

        cprintf("Iter %d, No.%d philosopher_condvar is eating\n",iter,i);
        do_sleep(SLEEP_TIME);
        phi_put_forks_condvar(i); /* 把两把叉子同时放回桌子 */
    }
    cprintf("No.%d philosopher_condvar quit\n",i);
    return 0;    
}
  • phi_take_forks_condvar：需要两只叉子，或者阻塞
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void phi_take_forks_condvar(int i) {
    down(&(mtp->mutex));
//--------into routine in monitor--------------
    state_condvar[i]=HUNGRY; /* 记录下哲学家i饥饿的事实 */
    phi_test_condvar(i); /* 哲学家尝试得到两只叉子,并且进餐 */
    if (state_condvar[i] != EATING) {
        cprintf("phi_take_forks_condvar: %d didn't get fork and will wait\n",i);
        cond_wait(&mtp->cv[i]);
    }
//--------leave routine in monitor--------------
    if(mtp->next_count>0)
        up(&(mtp->next));
    else
        up(&(mtp->mutex));
}
  • phi_put_forks_condvar：把两把叉子同时放回桌子
1
2
3
4
5
6
7
8
9
10
11
12
void phi_put_forks_condvar(int i) {
    down(&(mtp->mutex));
//--------into routine in monitor--------------
    state_condvar[i]=THINKING;
    phi_test_condvar(LEFT); /* 看一下左邻居现在是否能进餐 */
    phi_test_condvar(RIGHT); /* 看一下右邻居现在是否能进餐 */
//--------leave routine in monitor--------------
    if(mtp->next_count>0)
        up(&(mtp->next));
    else
        up(&(mtp->mutex));
}
  • phi_test_condvar：哲学家尝试得到两只叉子,并且进餐
1
2
3
4
5
6
7
8
9
void phi_test_condvar (i) { 
    if(state_condvar[i]==HUNGRY&&state_condvar[LEFT]!=EATING
            &&state_condvar[RIGHT]!=EATING) {
        cprintf("phi_test_condvar: state_condvar[%d] will eating\n",i);
        state_condvar[i] = EATING ;
        cprintf("phi_test_condvar: signal self_cv[%d] \n",i);
        cond_signal(&mtp->cv[i]) ;
    }
}
  • PS：为了让整个管程正常运行，还需在管程中的每个函数的入口和出口增加相关操作
1
2
3
4
5
6
7
8
9
10
void monitorFunc() {
      down(&(mtp->mutex));
//--------into routine in monitor--------------
      /* ... */
//--------leave routine in monitor--------------
      if(mtp->next_count>0)
         up(&(mtp->next));
      else
         up(&(mtp->mutex));
}

这样做的好处有两个

  • 只有一个进程在执行管程中的函数
  • 避免由于执行了 cond_signal 函数而睡眠的进程无法被唤醒

针对 “避免由于执行了 cond_signal 函数而睡眠的进程无法被唤醒” 这个优点简单说一下：

  • 管程中 wait 和 signal 函数的调用存在时间顺序
    • 例如：当线程1先调用 signal 唤醒线程2并将自身线程挂起后，线程2在开始执行时将无法唤醒原先的在 signal 中挂起的线程1
  • 也就是说，只要存在线程在管程中执行了 signal，那么至少存在一个线程在管程中被挂起
  • 此时，就只能在临界区外唤醒挂起的线程1，而这一步在代码中也得到了实现