练习#

课后练习#

编程题#

在Linux环境中，基于pthread线程，有一系列的系统调用实现对应用程序的线程间同步互斥的支持。

信号量是一种特殊的变量，可用于线程同步。它只取自然数值，并且只支持两种操作：P(SV): 如果信号量SV大于0，将它减一；如果SV值为0，则挂起该线程。V(SV)： 如果有其他进程因为等待SV而挂起，则唤醒，然后将SV+1；否则直接将SV+1。其系统调用为：

  • sem_wait(sem_t *sem)：以原子操作的方式将信号量减1，如果信号量值为0，则sem_wait将被阻塞，直到这个信号量具有非0值。

  • sem_post(sem_t *sem)：以原子操作将信号量值+1。当信号量大于0时，其他正在调用sem_wait等待信号量的线程将被唤醒。

互斥量：互斥量又称互斥锁，主要用于线程互斥，不能保证按序访问，可以和条件锁一起实现同步。当进入临界区 时，需要获得互斥锁并且加锁；当离开临界区时，需要对互斥锁解锁，以唤醒其他等待该互斥锁的线程。其主要的系统调用如下：

  • pthread_mutex_init: 初始化互斥锁

  • pthread_mutex_destroy： 销毁互斥锁

  • pthread_mutex_lock： 以原子操作的方式给一个互斥锁加锁，如果目标互斥锁已经被上锁，pthread_mutex_lock调用将阻塞，直到该互斥锁的占有者将其解锁。

  • pthread_mutex_unlock: 以一个原子操作的方式给一个互斥锁解锁。

条件变量:条件变量，又称条件锁，用于在线程之间同步共享数据的值。条件变量提供一种线程间通信机制：当某个共享数据达到某个值时，唤醒等待这个共享数据的一个/多个线程。即，当某个共享变量等于某个值时，调用 signal/broadcast。此时操作共享变量时需要加锁。其主要的系统调用如下：

  • pthread_cond_init: 初始化条件变量

  • pthread_cond_destroy： 销毁条件变量

  • pthread_cond_signal： 唤醒一个等待目标条件变量的线程。哪个线程被唤醒取决于调度策略和优先级。

  • pthread_cond_wait： 等待目标条件变量。需要一个加锁的互斥锁确保操作的原子性。该函数中在进入wait状态前首先进行解锁，然后接收到信号后会再加锁，保证该线程对共享资源正确访问。

  1. ** 在Linux环境下，请用信号量实现哲学家就餐的多线程应用程序。

  2. ** 在Linux环境下，请用互斥锁和条件变量实现哲学家就餐的多线程应用程序。

  3. ** 在Linux环境下，请建立一个多线程的模拟资源分配管理库，可通过银行家算法来避免死锁。

  4. ** 扩展内核功能，实现读者优先的读写信号量。

  5. ** 扩展内核功能，实现写者优先的读写信号量。

  6. *** 扩展内核功能，在内核中支持内核线程。

  7. *** 进一步扩展内核功能，在内核线程中支持同步互斥机制，实现内核线程用的mutex, semaphore, cond-var。

  8. *** 扩展内核功能，实现多核支持下的同步互斥机制。

  9. *** 解决优先级反转问题：实现RM实时调度算法，设计优先级反转的实例，实现优先级天花板和优先级继承方法。

问答题#

  1. * 什么是并行？什么是并发？

  2. * 为了创造临界区，单核处理器上可以【关中断】，多核处理器上需要使用【自旋锁】。请回答下列问题：

    • 多核上可不可以只用【关中断】？

    • 单核上可不可以只用【自旋锁】？

    • 多核上的【自旋锁】是否需要同时【关中断】？

    • [进阶] 假如某个锁不会在中断处理函数中被访问，是否还需要【关中断】？

  3. ** Linux的多线程应用程序使用的锁（例如 pthread_mutex_t）不是自旋锁，当上锁失败时会切换到其它进程执行。分析它和自旋锁的优劣，并说明为什么它不用自旋锁？

  4. *** 程序在运行时具有两种性质：safety: something bad will never happen；liveness: something good will eventually occur. 分析并证明 Peterson 算法的 safety 和 liveness 性质。

  5. * 信号量结构中的整数分别为+n、0、-n 的时候，各自代表什么状态或含义？

  6. ** 考虑如下信号量实现代码：

class Semaphore {
  int sem;
  WaitQueue q;
}
Semaphore::P() {
  sem --;
  if(sem < 0) {
    Add this thread to q.
    block.
  }
}
Semaphore::V() {
  sem ++;
  if(sem <= 0) {
    t = Remove a thread from q;
    wakeup(t);
  }
}

假如 P操作或V操作不是原子操作，会出现什么问题？举一个例子说明。上述代码能否运行在用户态？上面代码的原子性是如何保证的？

  1. ** 条件变量的 Wait 操作为什么必须关联一个锁？

  2. ** 下面是条件变量的wait操作实现伪代码：

Condvar::wait(lock) {
  Add this thread to q.
  lock.unlock();
  schedule();
  lock.lock();
}

如果改成下面这样：

Condvar::wait() {
  Add this thread to q.
  schedule();
}
lock.unlock();
condvar.wait();
lock.lock();

会出现什么问题？举一个例子说明。

  1. * 死锁的必要条件是什么？

  2. * 什么是死锁预防，举例并分析。

  3. ** 描述银行家算法如何判断安全性。

实验练习#

实验练习包括实践作业和问答作业两部分。

编程作业#

银行家算法——分数更新#

注解

本实验为用户态实验，请在 Linux 环境下完成。

背景：在智能体大赛平台 Saiblo 网站上每打完一场双人天梯比赛后需要用 ELO 算法更新双方比分。由于 Saiblo 的评测机并发性很高，且 ELO 算法中的分值变动与双方变动前的分数有关，因此更新比分前时必须先为两位选手加锁。

作业：请模拟一下上述分数更新过程，简便起见我们简化为有 p 位选手参赛（编号 [0, p) 或 [1, p] ），初始分值为 1000 分，有 m 个评测机线程（生产者）给出随机的评测结果（两位不同选手的编号以及胜负结果，结果可能为平局），有 n 个 worker 线程（消费者）获取结果队列并更新数据库（全局变量等共享数据）记录的分数。m 个评测机各自模拟 k 场对局结果后结束线程，全部对局比分更新完成后主线程打印每位选手最终成绩以及所有选手分数之和。

上述参数 p、m、n、k 均为可配置参数（命令行传参或程序启动时从stdin输入）。

简便起见不使用 ELO 算法，简化更新规则为：若不为平局，当 胜者分数 >= 败者分数 时胜者 +20，败者 -20，否则胜者 +30，败者 -30；若为平局，分高者 -10，分低者+10（若本就同分保持则不变）。

消费者核心部分可参考如下伪码：

获取选手A的锁 获取选手B的锁 更新A、B分数 睡眠 1ms（模拟数据库更新延时） 释放选手B的锁 释放选手A的锁

tips:

  • 由于 ELO 以及本题中给出的简化更新算法均为零和算法，因此出现冲突后可以从所有选手分数之和明显看出来，正确处理时它应该永远为 1000p

  • 将一个 worker 线程看作哲学家，将 worker 正在处理的一场对局的两位选手看作两根筷子，则得到了经典的哲学家就餐问题

实现 eventfd#

在 Linux 中有一种用于事件通知的文件描述符，称为 eventfd 。其核心是一个 64 位无符号整数的计数器，在非信号量模式下，若计数器值不为零，则 read 函数会从中读出计数值并将其清零，否则读取失败； write 函数将缓冲区中的数值加入到计数器中。在信号量模式下，若计数器值非零，则 read 操作将计数值减一，并返回 1 ； write 将计数值加一。我们将实现一个新的系统调用： sys_eventfd2 。

eventfd：

  • syscall ID: 290

  • 功能：创建一个 eventfd， eventfd 标准接口 。

  • C 接口： int eventfd(unsigned int initval, int flags)

  • Rust 接口： fn eventfd(initval: u32, flags: i32) -> i32

  • 参数：

    • initval: 计数器的初值。

    • flags: 可以设置为 0 或以下两个 flag 的任意组合（按位或）：

      • EFD_SEMAPHORE (1) ：设置该 flag 时，将以信号量模式创建 eventfd 。

      • EFD_NONBLOCK (2048) ：若设置该 flag ，对 eventfd 读写失败时会返回 -2 ，否则将阻塞等待直至读或写操作可执行为止。

  • 说明：

    • 通过 write 写入 eventfd 时，缓冲区大小必须为 8 字节。

    • 进程 fork 时，子进程会继承父进程创建的 eventfd ，且指向同一个计数器。

  • 返回值：如果出现了错误则返回 -1，否则返回创建成功的 eventfd 编号。

  • 可能的错误

    • flag 不合法。

    • 创建的文件描述符数量超过进程限制

注解

还有一个 sys_eventfd 系统调用（调用号 284），与 sys_eventfd2 的区别在于前者不支持传入 flags 。

Linux 中的原生异步 IO 接口 libaio 就使用了 eventfd 作为内核完成 IO 操作之后通知应用程序的机制。

实验要求#

  • 完成分支: ch8-lab

  • 实验目录要求不变。

  • 通过所有测例。

问答作业#

无

实验练习的提交报告要求#

  • 简单总结本次实验与上个实验相比你增加的东西。（控制在5行以内，不要贴代码）

  • 完成问答问题

  • (optional) 你对本次实验设计及难度的看法。