anki

临界资源

Q: 什么是临界资源？
A: 临界资源是指一次仅允许一个进程使用的资源，例如打印机、共享变量等。
补充细节：多个进程同时访问临界资源会导致数据错误，因此需要使用同步机制来保证对临界资源的互斥访问。

临界区

Q: 什么是临界区？
A: 临界区是指进程中访问临界资源的那段代码，又称临界段。
补充细节：临界区是需要进行同步控制的关键代码段，它保证了对临界资源的互斥访问。

访问临界资源的过程可以分为哪几个部分？

Q: 访问临界资源的过程可以分为哪几个部分？分别描述每个部分的作用。
A: 访问临界资源的过程可以分为四个部分：
1) 进入区。为了进入临界区使用临界资源, 在进入区要检查可否进入临界区, 若能进入临界区, 则应设置正在访问临界区的标志, 以阻止其他进程同时进入临界区。
2) 临界区。进程中访问临界资源的那段代码, 又称临界段。
3) 退出区。将正在访问临界区的标志清除。
4) 剩余区。代码中的其余部分。

同步

Q: 什么是同步？
A: 同步是指进程之间的相互合作，例如生产者-消费者问题中，生产者进程必须在生产完数据后才能唤醒消费者进程。
补充细节：同步关系源于进程之间的相互合作，需要在某些位置上协调它们的工作次序。

互斥

Q: 什么是互斥？
A: 互斥是指进程之间的相互制约，例如多个进程访问同一个临界资源时，只能有一个进程访问，其他进程必须等待。
补充细节：互斥是实现临界区访问控制的一种基本机制，可以使用各种同步方法来实现互斥。

软件实现方法

Q: 什么是同步互斥的软件实现方法？
A: 软件实现方法是指通过设置一些标志来标明是否有进程在临界区中，若已有进程在临界区，则在进入区通过循环检查进行等待，进程离开临界区后则在退出区修改标志。
补充细节：软件实现方法的缺点是效率低下，容易出现死锁和饥饿问题。

单标志法

Q: 单标志法是如何实现的？
A: 单标志法使用一个公用整型变量 turn 来指示允许进入临界区的进程编号，当 turn = 0 时，表示允许 P0 进入临界区；当 turn = 1 时，表示允许 P1 进入临界区。
进程退出临界区时将临界区的使用权赋给另一个进程，当 Pi 退出临界区时，将 turn 置为 j (i = 0、j = 1 或 i = 1、j = 0)。
补充细节：单标志法的缺点是两个进程必须交替进入临界区，若某个进程不再进入临界区，则另一个进程也将无法进入临界区，这样很容易造成资源利用不充分。

双标志先检查法

Q: 双标志先检查法是如何实现的？
A: 双标志先检查法使用一个布尔型数组 flag[2]，用来标记各个进程想进入临界区的意愿，flag[i] = true 表示想要进入临界区 (i = 0 或 1)。
P[i] 进入临界区前，先检查对方是否想进入临界区，若想，则等待；
否则，将 flag[i] 置为 true 后，再进入临界区；
当 P[i] 退出临界区时，将 flag[i] 置为 false。
补充细节：双标志先检查法的缺点是 P0 和 P1 可能同时进入临界区，因为检查和设置操作不是一气呵成的。

双标志后检查法

Q: 双标志后检查法是如何实现的？
A: 双标志后检查法先设置自己的标志，再检查对方的标志，若对方的标志为 true，则等待；否则，进入临界区。
补充细节：双标志后检查法的缺点是两个进程都长期无法访问临界区而导致 “饥饿” 现象。

Peterson 算法

Q: Peterson 算法是如何实现的？
A: Peterson 算法结合了单标志法和双标志后检查法的思想，使用 flag[] 解决互斥访问问题，使用 turn 解决饥饿问题。
补充细节：Peterson 算法很好地遵循了 “空闲让进” “忙则等待” “有限等待” 三个准则，但依然未遵循 “让权等待” 准则。它是软件实现方法中最好的算法。

中断屏蔽方法

Q: 中断屏蔽方法是如何实现的？
A: 中断屏蔽方法通过关闭中断来保证当前进程能够顺利执行临界区代码，当一个进程正在执行它的临界区代码时，防止其他进程进入其临界区的最简单方法是关中断。
补充细节：中断屏蔽方法的缺点是限制了 CPU 交替执行程序的能力，因此系统效率会明显降低；
对内核来说，在它执行更新变量的几条指令期间，关中断是很方便的，但将关中断的权限交给用户则很不明智；
不适用于多处理器系统，因为在一个 CPU 上关中断并不能防止进程在其他 CPU 上执行相同的临界区代码。

TestAndSet 指令

Q: TestAndSet 指令是如何实现的？
A: TestAndSet 指令是原子操作，它可以读出指定标志后将该标志设置为真。
补充细节：TestAndSet 指令相比于软件实现方法的优点是将 “加锁” 和 “检查” 操作用硬件的方式变成了一气呵成的原子操作。
相比于关中断方法的优点是由于 “锁” 是共享的，这种方法适用于多处理器系统。
TestAndSet 指令的缺点是暂时无法进入临界区的进程会占用 CPU 循环执行 TS 指令，因此不能实现 “让权等待”。

Swap 指令

Q: Swap 指令是如何实现的？
A: Swap 指令可以交换两个字的内容。
补充细节：Swap 指令相比于软件实现方法的优点是简单、容易验证其正确性；
适用于任意数目的进程，支持多处理器系统；
支持系统中有多个临界区，只需为每个临界区设立一个布尔变量。
Swap 指令的缺点是等待进入临界区的进程会占用 CPU 执行 while 循环，不能实现 “让权等待”；
从等待进程中随机选择一个进程进入临界区，有的进程可能一直选不上，从而导致 “饥饿” 现象。

互斥锁

Q: 什么是互斥锁？
A: 互斥锁是一种简单的同步工具，它使用 acquire() 函数获取锁，使用 release() 函数释放锁。
补充细节：互斥锁通常采用硬件机制来实现。互斥锁的缺点是忙等待，当有一个进程在临界区时，任何其他进程在进入临界区前必须连续循环调用 acquire()。

信号量

Q: 什么是信号量？
A: 信号量是一种功能较强的同步机制，它只能被两个标准的原语 wait() 和 signal() 访问，也称为 P 操作和 V 操作。
补充细节：信号量可以用来解决更复杂的同步问题，例如生产者-消费者问题、读者-写者问题等。

整型信号量

Q: 什么是整型信号量？
A: 整型信号量是一个用于表示资源数目的整型量。
补充细节：整型信号量机制中的 wait 操作，只要信号量 S <= 0，就会不断循环测试。因此，该机制并未遵循 “让权等待” 的准则，而是使进程处于 “忙等” 的状态。

记录型信号量

Q: 什么是记录型信号量？
A: 记录型信号量机制是一种不存在 “忙等” 现象的进程同步机制，它除了需要一个用于代表资源数目的整型变量 value 外，再增加一个进程链表 L，用于链接所有等待该资源的进程。
补充细节：记录型信号量遵循 “让权等待” 原则。

利用信号量实现进程互斥

Q: 如何利用信号量实现进程互斥？
A: 为了使多个进程能互斥地访问某个临界资源，需要为该资源设置一个互斥信号量 S，其初值为 1 （可用资源数为 1），然后将各个进程访问该资源的临界区置于 P(S) 和 V(S) 之间。
补充细节：每个要访问该资源的进程在进入临界区之前，都要先对 S 执行 P 操作，若该资源此刻未被访问，则本次 P 操作必然成功，进程便可进入自己的临界区。这时，若再有其他进程也要进入自己的临界区，由于对 S 执行 P 操作必然失败，因此主动阻塞，从而保证了该资源能被互斥访问。当访问该资源的进程退出临界区后，要对 S 执行 V 操作，以便释放该临界资源。

利用信号量实现同步

Q: 如何利用信号量实现同步？
A: 为了实现同步关系，需要设置一个同步信号量 S，其初值为 0。
补充细节：在提供资源的行为之后执行 V 操作，在使用资源的行为之前执行 P 操作。

利用信号量实现前驱关系

Q: 如何利用信号量实现前驱关系？
A: 为保证 S1 → S2, S1 → S3, S2 → S4, S2 → S5, S3 → S6, S4 → S6, S5 → S6 的前驱关系，需分别设置同步信号量 a12, a13, a24, a25, a36, a46, a56。
补充细节：在 “前驱操作” 之后，对相应的同步信号量执行 V 操作，在 “后继操作” 之前，对相应的同步信号量执行 P 操作。

分析进程同步和互斥问题的方法步骤

Q: 分析进程同步和互斥问题的方法步骤是什么？
A: 分析进程同步和互斥问题的方法步骤包括：关系分析、整理思路、设置信号量。
补充细节：关系分析的步骤是找出问题中的进程数，分析它们之间的同步和互斥关系。整理思路的步骤是找出解决问题的关键点，根据做过的题目找出求解的思路。设置信号量的步骤是根据前两步，设置需要的信号量，确定初值，完善整理。

经典同步问题

生产者-消费者问题

Q: 生产者-消费者问题描述了什么？
A: 生产者-消费者问题描述了一组生产者进程和一组消费者进程共享一个缓冲区，生产者进程向缓冲区中添加数据，消费者进程从缓冲区中取出数据，该问题需要解决互斥访问和同步问题。
补充细节：

• 生产者-消费者问题中需要设置三个信号量：mutex、empty、full
  • mutex 信号量用于控制互斥访问缓冲池，互斥信号量初值为 1
  • empty 信号量用于记录当前缓冲池中的 “空” 缓冲区数，初值为 n
  • full 信号量用于记录当前缓冲池中的 “满” 缓冲区数，初值为 0
• 生产者进程在将数据放入缓冲区之前，先执行 P(empty) 操作，获取一个空缓冲区单元
  • 然后执行 P(mutex) 操作，进入临界区
  • 将数据放入缓冲区后，执行 V(mutex) 操作，离开临界区
  • 最后执行 V(full) 操作，满缓冲区数加 1
• 消费者进程在从缓冲区中取出数据之前，先执行 P(full) 操作，获取一个满缓冲区单元
  • 然后执行 P(mutex) 操作，进入临界区
  • 从缓冲区中取出数据后，执行 V(mutex) 操作，离开临界区
  • 最后执行 V(empty) 操作，空缓冲区数加 1
• 生产者-消费者问题中需要注意的是对缓冲区大小为 n 的处理
  • 当缓冲区中有空时，便可对 empty 变量执行 P 操作
  • 一旦取走一个产品便要执行 V 操作以释放空闲区
• 对 empty 和 full 变量的 P 操作必须放在对 mutex 的 P 操作之前

读者-写者问题

Q: 读者-写者问题描述了什么？
A: 读者-写者问题描述了读者和写者两组并发进程共享一个文件，允许多个读者同时读，但只允许一个写者写，该问题需要解决读者和写者互斥和读者之间的同步问题。
补充细节：

• 读者-写者问题中需要设置三个信号量：mutex、rw、count
• mutex 信号量用于保护更新 count 变量时的互斥
• rw 信号量用于保证读者和写者互斥地访问文件
• count 信号量用于记录当前读者的数量，初值为 0
• 写者进程在进入临界区之前，先执行 P(rw) 操作，互斥访问共享文件
  • 写入完成后，执行 V(rw) 操作，释放共享文件
• 读者进程在进入临界区之前，先执行 P(mutex) 操作，互斥访问 count 变量
  • 若 count == 0，则执行 P(rw) 操作，阻止写进程写
  • 然后执行 count++ 操作，读者计数器加 1
  • 最后执行 V(mutex) 操作，释放互斥变量 count
• 读者进程在离开临界区之前，先执行 P(mutex) 操作，互斥访问 count 变量
  • 然后执行 count-- 操作，读者计数器减 1
  • 若 count == 0，则执行 V(rw) 操作，允许写进程写
  • 最后执行 V(mutex) 操作，释放互斥变量 count
• 读者-写者问题中需要注意的是，在上面的算法中，读进程是优先的，即当存在读进程时，写操作将被延迟，且只要有一个读进程活跃，随后而来的读进程都将被允许访问文件

哲学家进餐问题

Q: 哲学家进餐问题描述了什么？
A: 哲学家进餐问题描述了 5 名哲学家围坐在一张圆桌边，每两名哲学家之间有一根筷子，哲学家需要同时拿到两根筷子才能进餐，该问题需要解决死锁问题。
补充细节：哲学家进餐问题中需要设置 5 个信号量，分别对应 5 根筷子。
哲学家进餐问题可以通过制定一些规则来防止死锁，例如：

• 至多允许 4 名哲学家同时进餐。
• 仅当一名哲学家左右两边的筷子都可用时，才允许他抓起筷子。
• 对哲学家顺序编号，要求奇数号哲学家先拿左边的筷子，然后拿右边的筷子，而偶数号哲学家刚好相反。

吸烟者问题

Q: 吸烟者问题描述了什么？
A: 吸烟者问题描述了三个抽烟者进程和一个供应者进程，每个抽烟者需要三种材料才能卷烟，供应者每次提供两种材料，该问题需要解决同步和互斥问题。
补充细节：

• 吸烟者问题中需要设置四个信号量：offer1、offer2、offer3、finish
  • offer1 信号量表示烟草和纸组合的资源
  • offer2 信号量表示烟草和胶水组合的资源
  • offer3 信号量表示纸和胶水组合的资源
  • finish 信号量用于互斥进行抽烟动作
• 供应者进程在提供两种材料后，执行 V(offer1)、V(offer2) 或 V(offer3) 操作，通知对应的抽烟者可以卷烟
• 抽烟者进程在卷完烟后，执行 V(finish) 操作，通知供应者可以提供新的材料

死锁

Q: 什么是死锁？
A: 死锁是指两个或多个进程因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。
补充细节：死锁是进程同步中常见的问题，需要使用一些方法来防止或解除死锁。

读者-写者问题

写者优先

Q: 写者优先的解决方法是什么？
A: 写者优先是指当有写进程请求访问文件时，应禁止后续读进程的请求，等到已在共享文件的读进程执行完毕，立即让写进程执行，只有在无写进程执行的情况下才允许读进程再次运行。
补充细节：写者优先的解决方法可以保证写进程能够尽快地获得对文件的访问权。

管程

管程的定义

Q: 什么是管程？
A: 管程是一种新的进程同步工具，它将对共享资源的操作封装起来，保证了进程互斥，并提供了条件变量来实现进程同步。
补充细节：管程可以简化进程同步的实现，降低死锁的风险。

管程的实现方式

Q: 管程的实现方式有哪些？
A: 管程可以通过软件或硬件来实现，软件实现方式通常使用互斥锁和条件变量来实现，硬件实现方式通常使用特殊的硬件指令来实现。
补充细节：管程的实现方式取决于具体的系统环境。

条件变量

Q: 什么是条件变量？
A: 条件变量是一种同步机制，用于在进程之间进行条件同步。
补充细节：条件变量通常与互斥锁一起使用，用于实现更复杂的同步操作。

条件变量的 wait 操作

Q: 条件变量的 wait 操作有什么作用？
A: 当进程发现条件不满足时，调用条件变量的 wait 操作将自己阻塞，直到条件满足。
补充细节：wait 操作会释放互斥锁，允许其他进程进入临界区。

条件变量的 signal 操作

Q: 条件变量的 signal 操作有什么作用？
A: 当进程发现条件满足时，调用条件变量的 signal 操作唤醒一个等待该条件的进程。
补充细节：signal 操作不会立即释放互斥锁，因此调用 signal 操作的进程需要继续持有互斥锁。