死锁与饥饿

控制台示例代码有效控制饥饿问题的方法#include <iostream>#include <thread>#include <mutex>#include <condition_variable>// 定义全局变量int num_of_forks = 5;std::mutex mtx;std::condition_variable cv;// 哲学家线程函数void philosopher(int id) {while (true) {// 开始思考std::cout << "哲学家 " << id << " 正在思考" << std::endl;std::this_thread::sleep_for(std::chrono::seconds(2));// 尝试获取左边的叉子std::unique_lock<std::mutex> lck(mtx);while (num_of_forks == 0) {// 没有叉子可用，等待其他哲学家放下叉子cv.wait(lck);}num_of_forks--;// 尝试获取右边的叉子while (num_of_forks == 0) {// 没有叉子可用，等待其他哲学家放下叉子cv.wait(lck);}num_of_forks--;// 开始进餐std::cout << "哲学家 " << id << " 开始进餐" << std::endl; std::this_thread::sleep_for(std::chrono::seconds(2));// 放下左边的叉子num_of_forks++;cv.notify_all();// 放下右边的叉子num_of_forks++;cv.notify_all();// 完成进餐std::cout << "哲学家 " << id << " 结束进餐" << std::endl;}}int main() {// 创建5个哲学家线程std::thread philosophers[5];for (int i = 0; i < 5; i++) {philosophers[i] = std::thread(philosopher, i);}// 主线程等待哲学家线程返回for (int i = 0; i < 5; i++) {philosophers[i].join();}return 0;}该示例代码用于展示一个经典的饥饿问题，即哲学家就餐问题的解决方法。

华东师范大学期中/期末试卷（A）2009 —2010 学年第二学期课程名称：___操作系统__________学生姓名：___________________ 学号：___________________专业：___________________ 年级/班级：__________________课程性质：专业必修…………………………………………………………………………………………一、是非题：请判断以下论述正确与否（用T/F表示），并修正错误的论述（15分，每题3分）1. 在多进程多线程操作系统中，每个进程只需要维护一个栈（stack）；F, 每个线程都需要栈2. 微内核操作系统中，CPU调度和虚存管理功能必须在微内核中实现；F. 虚存管理可以不在微内核中3. 在虚存管理时，采用先进先出（FIFO）页面替换策略，必然会发生Belady 异常（即分配页框越多，缺页率反而越高）；F. 可能发生，也可能不发生4. 对于键盘这样的低速字符设备，采用DMA方式进行数据交换是不合适的；T5. 在目录文件中，必须保存文件名和文件控制块信息。

F. 文件控制块通常不在目录文件中二、单项选择题（15分，每题3分）1. 当发生抖动（或称为颠簸，thrashing）时，以下哪种现象不会出现？BA. 处于等待（waiting）状态的进程数增多B. CPU利用率增高C. 磁盘I/O增多D. 长程调度（long-term scheduling）允许更多的进程进入就绪（ready）状态2. 多CPU共享内存环境下，以下哪种实现临界区的方法无效？CA. 使用test_and_set机器指令实现“忙等”（busy waiting）B. Peterson算法C. 关中断D. 使用swap机器指令实现“忙等”3. 以下哪种情况仍然可能会发生死锁？BA. 资源都是可共享的；B. 每一种资源的数量都超过单个进程所需这类资源的最大值；C. 空闲资源能够满足任意一个进程还需要的资源需求；D. 每个进程必须一次申请、获得所需的所有资源4. 以下哪种数据结构必须存放在持久存储介质上？CA. 进程控制块B. 页表C. 文件控制块D. 打开文件列表5. 以下哪种海量存储技术对于提升存储系统的容错性没有直接帮助？AA. 无冗余（non-redundant）的条带化（striping）B. 映像（mirroring）C. 按位奇偶校验（bit-interleaved parity）D. 按块奇偶校验（block-interleaved parity）三、辨析题：请分别解释以下每组的两个名词，并列举他们的区别（25分，每题5分）1. 死锁（deadlock）与饥饿（starvation）死锁：多个进程循环等待对方，都无法继续执行饥饿：某个或某些进程由于无法得到资源长时间无法执行死锁必然发生饥饿，但是饥饿不一定发生死锁2. 程序控制输入输出（programmed I/O）与直接内存访问（DMA）PIO：CPU直接发出对于I/O的指令DMA：CPU在交换开始、结束时介入，其他时候由DMA控制器协调I/O设备和内存间利用总线的数据交换。

并发编程实践：充分利用多核处理器和多线程并发编程是指在编写程序时充分利用多核处理器和多线程，实现多个任务的并行执行，以提高程序的性能和响应能力。

在现代计算机系统中，多核处理器已经成为主流，而多线程则是充分利用多核处理器的一种方式。

下面将介绍几个并发编程的实践技巧。

首先，要充分利用多核处理器，可以使用多线程来并行执行多个任务。

在编写程序时，可以将程序划分为若干个独立的任务，并使用多个线程并行执行这些任务。

例如，可以将一个大型图像处理任务分解成多个小任务，然后使用多个线程同时处理这些小任务。

这样可以充分利用多核处理器的并行计算能力，加速任务的执行。

其次，要注意线程之间的同步和互斥。

在多线程编程中，多个线程可能会同时访问共享的资源，如果没有合适的同步和互斥机制，就会导致数据竞争和一致性问题。

为了解决这个问题，可以使用锁、信号量等同步机制，确保多个线程对共享资源的访问是互斥的。

此外，还可以使用条件变量、读写锁等更高级的同步机制，以提高并发性能和资源利用率。

另外，要避免线程间的死锁和饥饿问题。

死锁是指多个线程因相互等待对方释放资源而无法继续执行的情况，而饥饿则是指某个线程因无法获得所需的资源而无法正常执行。

为了避免死锁和饥饿，可以使用避免策略，如按照确定的顺序获取锁资源，避免循环等待，以及使用超时机制等。

另外，要合理使用线程池。

线程池是一种管理线程的机制，它可以维护一定数量的线程，并根据需要分配任务给这些线程执行。

使用线程池可以避免频繁创建和销毁线程的开销，提高程序的性能和资源利用率。

同时，线程池还可以控制线程的数量，避免创建过多线程导致系统资源的浪费。

此外，要合理设置线程的优先级。

线程的优先级决定了线程在竞争CPU时间时的优先级，高优先级的线程会更容易获得CPU时间片。

所以，可以根据任务的紧急程度和重要性，合理设置线程的优先级，以提高任务的响应能力。

最后，要注意并发编程中的异常处理。

由于多个线程并发执行，可能会出现各种异常情况，如线程的中断、异常退出等。

SystemVerilog信号量信号量是一种在多线程环境下常用的同步工具，它可以有效地控制多线程对共享资源的访问，保证线程间的互斥和同步。

在SystemVerilog中，信号量提供了一种方便的方式来实现多线程间的同步和互斥。

本文将介绍SystemVerilog中信号量的基本概念、语法和用法，并结合实际例子进行详细说明。

1. 信号量的概念在多线程编程中，当多个线程需要共享一个资源时，为了避免竞争条件和并发访问带来的问题，需要对这个资源进行同步和互斥控制。

信号量是一种经典的同步工具，它可以用来保护共享资源，防止多个线程同时访问，从而确保线程间的正确协调和合作。

2. SystemVerilog中的信号量在SystemVerilog中，信号量可以通过`semaphore`关键字来声明，它可以是计数信号量（counting semaphore）或二元信号量（binary semaphore）。

计数信号量允许指定多个线程同时访问共享资源，而二元信号量只允许一个线程访问。

信号量的声明语法如下所示：```systemverilogsemaphore sem = new(1);```其中，`sem`是信号量的实例名，`new(1)`表示创建一个初始值为1的二元信号量。

对于计数信号量，可以指定初始值大于1。

3. 信号量的使用在SystemVerilog中，可以使用`w本人t()`和`post()`方法来对信号量进行操作。

`w本人t()`用于申请信号量资源，如果信号量的值大于0，则减1并立即返回；否则，线程阻塞等待。

`post()`用于释放信号量资源，如果有线程在等待，则唤醒一个等待线程；否则，增加信号量的值。

下面是一个简单的信号量使用示例：```systemverilogsemaphore sem = new(1);task producer();w本人t(sem);// 生产者线程访问共享资源post(sem);endtasktask consumer();w本人t(sem);// 用户线程访问共享资源post(sem);endtask```在上面的示例中，生产者和用户任务分别通过`w本人t()`和`post()`来申请和释放信号量资源，确保了对共享资源的互斥访问。

进程同步机制应遵循的原则进程同步是指在多个进程之间共享和访问共享资源时，保证数据的一致性和正确性的一种机制。

进程同步机制应遵循以下原则：1.互斥原则：同一时刻只允许一个进程访问共享资源。

互斥可以通过各种技术实现，如信号量、互斥锁等。

通过互斥机制，保证每个进程在执行临界区代码时不会被其他进程干扰，从而保证共享资源的正确性。

2.有限等待原则：进程请求临界资源时，如果该资源被其他进程占用，请求进程应该在合理的时间内得到满足，而不是无限等待。

有限等待原则的目的是避免进程饥饿，确保资源能够公平地被进程使用。

3.活锁避免原则：进程同步机制应该尽量避免活锁的发生。

活锁是指进程在等待资源时不断重试，从而导致系统资源浪费，进程无法继续执行的情况。

为避免活锁，可以引入随机因素或者优先级机制，使得等待资源的进程能够有一定的机会得到资源。

4.顺序访问原则：对共享资源的访问应该按照一定的顺序进行，以避免产生竞争条件。

顺序访问原则可以通过引入排序标记、优先级调度等机制来实现。

5.无饥饿原则：每个进程在请求共享资源时应该能够得到满足，而不是一直被其他进程抢先。

为避免进程饥饿，可以采用公平调度策略，如循环等待。

6.死锁避免原则：进程同步机制应该尽量避免死锁的发生。

死锁是指多个进程因为互相等待对方释放资源而无法继续执行的情况。

为避免死锁，可以采用资源预分配或者资源有序性原则来保证进程不会陷入死锁状态。

7.公平性原则：进程同步机制应该尽量保证每个进程具有公平的获取共享资源的机会。

公平性原则可以通过轮询、随机分配等方法来实现，确保每个进程在请求资源时都有一定的机会得到满足。

以上是进程同步机制应遵循的基本原则，通过遵循这些原则，可以确保多进程之间共享资源时，数据的一致性和正确性，避免竞争条件、死锁、饥饿等问题的发生，保证系统的稳定和可靠性。

线程饥饿问题是指在多线程环境中，某些线程由于得不到足够的资源而无法执行的情况。

下面是一个简单的例子：
假设有一个程序，包含两个线程A和B。

线程A负责处理计算任务，而线程B 负责处理I/O操作。

由于处理计算任务的线程A执行速度较快，它可能会在处理I/O操作的线程B之前完成。

如果线程A一直处于活跃状态，而线程B长时间处于等待状态，那么就出现了线程饥饿问题。

在这种情况下，线程B会因为得不到CPU资源而无法执行，导致程序的运行效率降低。

为了避免线程饥饿问题，可以采用以下措施：
1. 调整线程优先级：根据实际情况，为不同线程设置不同的优先级，以确保它们能够公平地获取CPU资源。

2. 使用线程池：通过使用线程池来管理线程，可以避免线程的频繁创建和销毁，提高程序的性能和响应速度。

3. 增加资源竞争：在多个线程之间增加资源竞争，以使得每个线程都有机会获取到所需的资源，避免某些线程一直处于饥饿状态。

4. 引入同步机制：使用同步机制来协调不同线程之间的操作，以确保它们能够按照一定的顺序执行，避免出现竞争条件和死锁等问题。

总之，解决线程饥饿问题需要综合考虑多方面因素，包括线程优先级、资源竞争、同步机制等。

通过合理地设计和优化程序，可以有效地避免线程饥饿问题的发生。

什么是死锁？如何避免死锁的算法所谓死锁：是指两个或两个以上的进程在执⾏过程中，因争夺资源⽽造成的⼀种互相等待的现象，若⽆外⼒作⽤，它们都将⽆法推进下去。

此时称系统处于死锁状态或系统产⽣了死锁，这些永远在互相等待的进程称为死锁进程。

由于资源占⽤是互斥的，当某个进程提出申请资源后，使得有关进程在⽆外⼒协助下，永远分配不到必需的资源⽽⽆法继续运⾏，这就产⽣了⼀种特殊现象死锁。

虽然进程在运⾏过程中，可能发⽣死锁，但死锁的发⽣也必须具备⼀定的条件，死锁的发⽣必须具备以下四个必要条件。

1）互斥条件：指进程对所分配到的资源进⾏排它性使⽤，即在⼀段时间内某资源只由⼀个进程占⽤。

如果此时还有其它进程请求资源，则请求者只能等待，直⾄占有资源的进程⽤毕释放。

2）请求和保持条件：指进程已经保持⾄少⼀个资源，但⼜提出了新的资源请求，⽽该资源已被其它进程占有，此时请求进程阻塞，但⼜对⾃⼰已获得的其它资源保持不放。

3）不剥夺条件：指进程已获得的资源，在未使⽤完之前，不能被剥夺，只能在使⽤完时由⾃⼰释放。

4）环路等待条件：指在发⽣死锁时，必然存在⼀个进程——资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0正在等待⼀个P1占⽤的资源；P1正在等待P2占⽤的资源，……，Pn正在等待已被P0占⽤的资源。

1) 预防死锁。

这是⼀种较简单和直观的事先预防的⽅法。

⽅法是通过设置某些限制条件，去破坏产⽣死锁的四个必要条件中的⼀个或者⼏个，来预防发⽣死锁。

预防死锁是⼀种较易实现的⽅法，已被⼴泛使⽤。

但是由于所施加的限制条件往往太严格，可能会导致系统资源利⽤率和系统吞吐量降低。

a 破坏互斥条件 如果允许系统资源都能共享使⽤，则系统不会进⼊死锁状态。

但有些资源根本不能同时访问，如打印机等临界资源只能互斥使⽤。

所以，破坏互斥条件⽽预防死锁的⽅法不太可⾏，⽽且在有的场合应该保护这种互斥性。

b 破坏不剥夺条件 当⼀个已保持了某些不可剥夺资源的进程，请求新的资源⽽得不到满⾜时，它必须释放已经保持的所有资源，待以后需要时再重新申请。

哲学家进餐问题-3中解决⽅案问题描述⼀张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆⼀根筷⼦，桌⼦的中间是⼀碗⽶饭，如图2-10所⽰。

哲学家们倾注毕⽣精⼒⽤于思考和进餐，哲学家在思考时，并不影响他⼈。

只有当哲学家饥饿的时候，才试图拿起左、右两根筷⼦（⼀根⼀根地拿起）。

如果筷⼦已在他⼈⼿上，则需等待。

饥饿的哲学家只有同时拿到了两根筷⼦才可以开始进餐，当进餐完毕后，放下筷⼦继续思考。

问题分析1) 关系分析。

5名哲学家与左右邻居对其中间筷⼦的访问是互斥关系。

2) 整理思路。

显然这⾥有五个进程。

本题的关键是如何让⼀个哲学家拿到左右两个筷⼦⽽不造成死锁或者饥饿现象。

那么解决⽅法有两个，⼀个是让他们同时拿两个筷⼦；⼆是对每个哲学家的动作制定规则，避免饥饿或者死锁现象的发⽣。

⼀共５个哲学家，编号0 ~4, ５⽀筷⼦编号也是0 ~4, 0号哲学家右⼿的筷⼦编号是0号,逆时针增加,哲学家的编号也是逆时针增加所以:0号哲学家对应的是: 4号和1号筷⼦.1号哲学家对应的是: 0号和2号筷⼦.2号哲学家对应的是: 1号和3号筷⼦.3号哲学家对应的是: 2号和4号筷⼦.4号哲学家对应的是: 3号和0号筷⼦.所以有宏定义:#define left(phi_id) (phi_id+N-1)%N#define right(phi_id) (phi_id+1)%NN = 55⽀筷⼦对应５个互斥锁,所以:pthread_mutex_t forks[N]={PTHREAD_MUTEX_INITIALIZER};哲学家线程需要执⾏的动作是：void take_forks(int id){//获取左右两边的筷⼦printf("Pil[%d], left[%d], right[%d]\n", id, left(id), right(id));pthread_mutex_lock(&forks[left(id)]);pthread_mutex_lock(&forks[right(id)]);//printf("philosopher[%d] take_forks...\n", id);}void put_down_forks(int id){printf("philosopher[%d] is put_down_forks...\n", id);pthread_mutex_unlock(&forks[left(id)]);pthread_mutex_unlock(&forks[right(id)]);}void* philosopher_work(void *arg){int id = *(int*)arg;printf("philosopher init [%d] \n", id);while(1){thinking(id);take_forks(id);eating(id);put_down_forks(id);}}该算法存在以下问题：当五个哲学家都想要进餐，分别拿起他们左边筷⼦的时候（都恰好执⾏完pthread_mutex_unlock(&forks[left(id)]);）筷⼦已经被拿光了，等到他们再想拿右边的筷⼦的时候（执⾏pthread_mutex_unlock(&forks[right(id)]);)就全被阻塞了，这就出现了死锁。