死锁与饥饿

华东师范大学期中/期末试卷（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设备和内存间利用总线的数据交换。

死锁的概念什么是死锁？各进程互相等待对方手里的资源， 导致各进程都阻塞， 无法向前推进
死锁、饥饿、死循环的区别
死锁至少是两个进程一起死锁， 死锁进程处于阻塞态
饥饿可以只有一个进程饥饿， 饥饿进程可能阻塞也可能就绪
死循环可能只有一个进程发生死循环， 死循环的进程可以上处理机
死锁和饥饿时操作系统要解决的问题， 死循环是应用程序员要解决的死锁产生的必要条件
互斥条件对必须互斥使用的资源的争抢才会导致死锁
不剥夺条件进程保持的资源只能主动释放， 不可强行剥夺
请求和保持条件保持着某些资源不放的同时， 请求别的资源
循环等待条件
存在一种进程资源的循环等待链
循环等待未必死锁， 死锁一定需要循环等待
什么时候会发生死锁？对不可剥夺资源的不合理分配， 可能导致死锁
死锁的处理策略
预防死锁破坏死锁产生的四个必要条件
避免死锁避免系统进入不安全状态（银行家算法）
死锁的检测和解除允许死锁发生， 系统负责检测出死锁并解除。

死锁和饥饿的区别
1. ⾸先死锁是同步的，饥饿时异步的。

也就是说，死锁可以认为是两个线程或进程同时在请求对⽅占有的资源
2. 饥饿可以认为是⼀个线程或是进程在⽆限的等待另外两个或多个线程或进程占有的但是不会往外释放的资源。

当饥饿到⼀定程度的进程所赋予的任务即使完成也不再具有实际意义时称该进程被饿死。

介绍“死锁”的例⼦1：如果线程A锁住了记录R1并等待记录R2，⽽线程B锁住了记录R2并等待记录R1，这样两个线程A和B就发⽣了死锁现象。

介绍“死锁”的例⼦2：两个⼭⽺过⼀个独⽊桥，两只⽺同时⾛到桥中间，⼀个⼭⽺等另⼀个⼭⽺过去了然后再过桥，另⼀个⼭⽺等这⼀个⼭⽺过去，结果两只⼭⽺都堵在中间动弹不得。

介绍饥饿的例⼦：资源在其中两个或以上线程或进程相互使⽤，第三⽅线程或进程始终得不到。

想像⼀下三个⼈传球，其中两个⼈传来传去，第三个⼈始终得不到。

多线程编程中的同步和并发问题解析在多线程编程中，同步和并发是两个关键的概念，主要涉及到多个线程之间的协同工作和共享资源的管理。

了解和解决同步和并发问题是保证多线程程序正确执行的关键。

一、同步问题同步问题是指多个线程之间的协作和按照一定的顺序执行。

在多线程编程中，可能会遇到以下几种同步问题：1.竞态条件（Race Condition）：竞态条件是指多个线程竞争共享资源导致的问题。

当多个线程对同一共享资源进行读写操作时，可能会出现不可预期的结果。

例如，一个线程在读取共享资源的同时，另一个线程可能在修改这个资源，导致读取的结果不正确。

解决竞态条件的常见方法是使用互斥锁（Mutex）来保证对共享资源的排他访问，确保同一时间只有一个线程能够对共享资源进行操作。

2.死锁（Deadlock）：死锁是指多个线程互相等待对方释放资源导致的无法继续执行的情况。

当多个线程都在等待对方释放资源时，将无法继续执行下去，形成死锁。

解决死锁问题的方法可以使用资源分级策略，即按照一定的顺序请求资源，释放资源也按照相反的顺序进行。

这样能够避免多个线程同时请求相同的资源，从而降低死锁的可能性。

3.饥饿（Starvation）：饥饿是指某个线程由于资源被其他优先级高的线程占用而无法获得所需的资源，无法继续执行的情况。

解决饥饿问题的方法可以使用公平调度策略，即按照请求的先后顺序分配资源，避免某个线程长时间无法获得资源的情况。

二、并发问题并发问题是指多个线程同时执行，可能会导致不可预期的结果。

在多线程编程中，可能会遇到以下几种并发问题：1.数据竞争（Data Race）：数据竞争是指多个线程同时读写共享数据导致的问题。

当多个线程对同一数据进行读写操作时，可能会出现不一致的结果。

例如，一个线程正在写入数据，同时另一个线程正在读取这个数据，导致读取的结果不正确。

解决数据竞争问题的常见方法是使用原子操作（Atomic Operation）或者互斥锁来保证对共享数据的原子性操作，确保多个线程对数据的访问不会出现冲突。

并发执行的名词解释在计算机科学中，随着计算机的发展和进步，为了提高计算机系统的性能和效率，同时处理多个任务的需求也越来越强烈。

并发执行就是指在同一时间段内同时执行多个独立的任务或子任务，通过分时片段，使得这些任务在感觉上同时执行，从而提高系统的吞吐量和响应速度。

一、并发执行的原理并发执行的原理基于计算机系统中的一个重要概念，即进程。

进程是指在计算机中运行的一个程序实例，每个进程都具有各自的地址空间、执行状态和调度优先级。

并发执行通过同时运行多个进程，使得它们像同时执行一样，并在时间上互相切换。

这样的切换往往在短时间内完成，给用户一种同时执行多个任务的错觉。

二、并发执行的特点1. 提高系统资源利用率：通过并发执行，可以充分利用计算机的CPU、内存等资源，使系统的资源利用率提高，从而提高整个系统的效能。

2. 响应时间更短：通过并发执行，可以同时处理多个任务，使得系统的响应时间大幅度缩短。

无论是在操作系统还是在应用程序中，通过并发执行都能够提高用户的体验。

3. 提高系统的稳定性：通过并发执行，即使某个任务出现错误或异常，也不会影响其他任务的正常执行。

每个任务都具有一定的独立性，因此可以有效地隔离错误，提高系统的稳定性。

4. 支持多用户环境：并发执行是支持多用户环境的基础。

通过并发执行，可以同时为多个用户提供服务，满足用户的多样化需求。

5. 提高系统的扩展性：在现代计算机系统中，通过并发执行可以实现系统的扩展性。

无论是增加CPU核心数还是增加服务器节点，都可以通过并发执行来充分发挥系统的潜力。

三、并发执行的应用并发执行在各个领域都有广泛的应用。

以下是一些典型的应用场景：1. 操作系统：操作系统是最典型的并发执行应用之一。

操作系统能够同时管理多个进程，为用户提供良好的交互体验，并保证系统的稳定性和效率。

2. 数据库系统：数据库系统中的并发执行可以允许多个用户同时对数据库进行操作，实现数据并发访问和事务处理，提高数据库的访问效率和并发性。

c++线程间通信的几种方法C++是一种广泛使用的编程语言，而线程的使用在C++程序中也是很常见的。

由于多线程程序中存在多个线程同时运行的问题，线程间的通信也就变得至关重要。

本文将介绍C++中线程间通信的几种方法。

1.共享变量共享变量是最简单的线程间通信方式之一。

其原理是多个线程访问同一个变量，如果一个线程修改了该变量，则其他线程也能读到该变量的修改值。

需要注意的是，由于共享变量的修改是非线程安全的，因此在使用共享变量时需要使用线程同步机制来保证线程安全。

2.信号量信号量是另一种常用的线程间通信方式。

其原理是一个线程在执行完一定任务后，发送一个信号量通知其他线程可以执行了。

一个生产者线程向一个缓冲队列发送一个信号量表示队列已经有了数据，消费者线程则根据这个信号量来消耗队列中的数据。

需要注意的是，使用信号量需要保证其线程同步。

在生产者线程中设置信号量的值之后，需要将其置0，防止其他线程持续访问。

3.消息队列消息队列是一种线程间通信方式，可以在不同线程之间传递数据。

其原理是用于发送消息的线程将消息添加到队列中，接受消息的线程从队列中读取消息。

需要注意的是，消息队列需要使用互斥锁或信号量来保证线程同步。

4.管道管道是一种线程间通信方式，适用于有父子进程或兄弟进程的情况。

其原理是在两个进程之间创建一个单向的管道，一个进程写入数据到管道中，另一个进程从管道中读取数据。

管道可以通过系统调用pipe()来创建。

需要注意的是，管道只能在亲缘关系进程之间使用，而且只能进行单向通信。

5.套接字套接字是一种通用的线程间通信方式，适用于不同计算机之间的通信。

其原理是将数据通过TCP/IP协议传输到网络中的另一个套接字，然后将此套接字中的数据传递到目标线程中。

需要注意的是，套接字通信需要使用互斥锁或信号量来保证线程同步。

6.事件事件机制是一种线程间通信方式，其原理是一个线程产生一个事件，其他线程在等待该事件完成后才能继续执行。

题目：1、某系统中有4个并发进程，都需要同类资源6个，试问该系统不会发生死锁的最少资源数是多少？为什么？2、一台计算机有８台磁带机，它们由N个进程竞争使用，每个进程最多需要３台，请问N 为多少时，系统没有死锁危险，并说明原因。

3、如何解决死锁问题。

4、饥饿、饿死、死锁的异同点是什么？5、产生死锁的原因是什么？6、死锁的预防与死锁的避免，其区别是什么？答案：1、记某类资源共有M个实例，使用这种资源的进程共有N个，则发生死锁的条件是所有进程所需要的资源总量>=M+N。

由题设知，N=4，所需要的资源总量是6*4=24，所以使上述不等式不成立的M的最小值为21，即该系统不会发生死锁的最少资源数是21.2、与上一题同理，其中M=8，N为使用这种资源的进程个数，要使系统没有死锁危险，则不等式3*N<8+N成立。

解不等式得N<4，即N<4时系统没有死锁危险。

3、解决死锁的方法可以简述为三种：(1)静态预防死锁，其中死锁预防有两种策略，分别为预先分配策略和有序分配策略预先分配策略是进程在运行前一次性地向系统申请它所需要的全部资源，如果系统当前不能满足进程的全部资源请求，则不分配资源该进程暂时不投入运行；如果系统当前能够满足进程的全部请求资源，则一次性地将所所申请的全部资源分配给申请进程。

有序分配策略是事先将所有资源类完全排序，即对每一个资源类赋予唯一的整数，并且进程必须按照编号由小到大的次序申请资源。

(2)动态避免死锁死锁避免就是对进程发出的每一个系统能够满足的资源申请命令实施检查，根据检查结果决定是否实施资源分配。

(3)动态检测死锁及动态恢复死锁动态检测死锁及动态恢复死锁就是按照一定的死所能检测策略对系统进行死锁检测，当检测到发生死锁时，按照一定的策略将其消除以使系统从死锁状态中恢复过来。

其中死锁检测策略有进程等待时检测、定时检测、资源利用率低时检测；死锁恢复策略有系统重启、终止进程、剥夺资源、进程回退。

linux一个读写锁的使用异常导致的故障在Linux系统中，读写锁（Reader-Writer Lock）是用于优化读多写少场景下的同步机制。

它允许多个读操作同时进行，但只允许一个写操作进行。

然而，如果读写锁的使用出现异常，可能会导致各种故障，例如死锁、数据不一致等。

1.死锁：读写锁的一个常见问题是死锁，即两个或多个线程互相等待对方释放锁而无法继续执行。

这种情况可能会发生在以下情况下：-写者优先：若一个写操作一直等待读锁时，而其他线程又持有了读锁，那么这个写者将永远无法获取写锁，导致死锁。

-写锁饥饿：当读者一直等待写锁，但写锁不断被其他写者占用，那么读者可能会一直等待下去，导致死锁。

为避免死锁，应该在使用读写锁时遵循一些规则，比如避免持有写锁时再去申请读锁，或者将写锁请求转化为读锁请求等。

2.数据不一致：读写锁的使用异常也可能导致数据不一致问题。

读写锁允许并发读取，但在写操作期间，需要独占锁，以确保数据的一致性。

然而，如果在读者访问共享数据的同时，写者修改了数据，可能会导致数据的不一致性问题。

例如，一个线程正在读取一篇文章的一些段落，而另一个线程正在修改这个段落，那么读者可能会读到一个更新之前的数据，导致数据不一致。

为了避免这个问题，需要在对共享数据进行读写操作时加锁，以确保数据的一致性。

3.性能降低：读写锁的不当使用也可能导致性能降低的问题。

读写锁适合于读多写少的场景，但如果过多地使用写锁，或者持有写锁的时间过长，那么可能会导致其他线程长时间等待，降低整体的并发性能。

为了提高性能，可以尽量减少写锁的持有时间，或者使用粒度更小的锁来代替读写锁。

综上所述，如果读写锁的使用出现异常，可能会引发死锁、数据不一致和性能下降等问题。

为了避免这些问题，需要注意遵循以下原则：-避免持有写锁时再去申请读锁，以防止死锁；-避免读锁饥饿，即尽量减少写锁的占用时间；-在对共享数据进行读写操作时加锁，以确保数据的一致性；-合理使用读写锁，避免滥用写锁，提高性能。