当前位置：文档之家 › 经典互斥算法

经典互斥算法

  • 格式：pdf
  • 大小：192.02 KB
  • 文档页数：6

下载文档原格式

  / 6

合集下载

操作系统5--信号量机制

操作系统5--信号量机制
信号量是一个被保护的变量，并且只能通过初始化和两个标准
的原子操作来访问.
1、整型信号量机制 2、记录型信号量机制 3、信号量集机制
5.1/28 2011
操作系统
1、整型信号量机制
1).整型信号量 是一个整数，表示空闲资源总数（又称为“资源信号量”） ----若为非负值表示当前的空闲资源数， ----为负值其绝对值表示当前等待临界区的进程数 ----初值应该大于零。
5.19/28
2011
操作系统
A.采用记录型信号量机制
Wmutex：互斥信号量：表示“允许写”，初值是1。 公共变量Readcount表示“正在读”的进程数，初值是0； Rmutex:互斥信号量：表示对Readcount的互斥操作，初值是1。
reader writer
Wait(Wmutex); Write; Signal(Wmutex); wait(Rmutex); if(Readcount=0) then wait(wmutex) Readcount=Readcount+1; Signal(Rmutex); //关闭写的同时允许读（无上限） read; Wait(Rmutex); Readcount:=Readcount-1; if Readcount=0 then signal(Wmutex); Signal(Rmutex); //适当的时候打开写
两个原子操作即: P,V操作。也常称为wait(s),singal(s)
（P、V分别是荷兰语的test(proberen)和increment(verhogen)） 即： P(s): Wait(s): while s<=0 do no_op s:=s-1; V(s): Singal(s): s:=s+1;

一种改进的主副本分布式锁

一种改进的主副本分布式锁

摘要 ： 分布式互斥 是分布式系统 【的 亟要问题之 一。通过对 分 布式锁 的使 ｆ ， ｝ 一种基 于涣 请求作 不 同 Ｉ ｜ ｝提 Ｉ Ｊ Ｉ 加锁处理的主副本锁。同时给 ｝ 了执行方案 ， ｆ Ｊ 对其性能进行 了分析 。最后 ， 与传统 主副本锁进 行 了比较 ， 证明其高
效性。 关 键 词 ： 副 本 锁 ； 布 式 数 据 库 ； 信 量 主 分 通
２ １ 主 要思 想 ．
传统 的主副本分布式锁选择某个节点上的副本为主副本 ， 所有的读写操作均 申请对主副本的锁 ， 每个资源都 指定 一个节 点 ， 负责 锁 的控 制 ， 此节 点称 为该 数据 的 主节 点 （ ｒ ｒ ｉ ） ｐｉ ｙｓｅ 。当 申请 资 源 的锁 时 ， 管 它 有 多少 副 ｍａ ｔ 不 本和副本位于何处均需到该资源的主节点进行申请 。由于锁申请 由主节点统一管理 ， 多副本 的锁管理机制如 同 单 副 本一样 。如 果事 务就 发生 在主 节 点 ， 则锁 的 通信 开 销 可 以免 去 。主 节 点 一 般选 在 使 用 该 资 源 最 多 的节 点 。 主副本 锁机 制可 以避 免死 锁 的产生 。 在传统的主副本锁机制中， Ｒ 锁 也需 要扩散到整个 系统中从而造成加锁过程中通信次数 的增加。在分 读（ ） 布式数据库中， 时间延迟多为加锁操作中的网络通信开销。在读操作较频繁的系统中， 这将导致整个系统的运行 速 度下 降 。
ＶＤ． ２ ＮＯ ５ １２ ． Ｏｃ ．２ ０ ｔ ０７
文章编号 ：Ｉ７Ｉ１４ ｌ（１）５１ ９ 一４ ６ ．７ ２２１７１ 一５ ８（ （ ）） １
一
种 改 进 的 主 副 本 分 布 式 锁
朱 静 ， 刘心松 ， 王 征
（ 电子科技 大 学 ８ １ 究室 ，－ 成 都 ６ ０ ５ ） ０ ０研 ｖ川 － ｑ １０ ４

读者-写者问题说明书

读者-写者问题说明书

《操作系统原理》课程设计任务书题目：读者-写者问题的实现学生姓名：李志旭学号：13740113 班级：_13级软件工程_题目类型：软件工程（R）指导教师：陈文娟、马生菊一、设计目的学生通过该题目的设计过程，掌握读者、写者问题的原理、软件开发方法并提高解决实际问题的能力。

二、设计任务编写程序实现读者优先和写者优先问题:读者-写者问题的读写操作限制（包括读者优先和写者优先）写-写互斥：不能有两个写者同时进行写操作读-写互斥：不能同时有一个线程在读，而另一个线程在写。

读-读允许：可以有一个或多个读者在读。

三、设计要求1.分析设计要求，给出解决方案（要说明设计实现所用的原理、采用的数据结构）。

2.设计合适的测试用例，对得到的运行结果要有分析。

3.设计中遇到的问题，设计的心得体会。

4.文档：课程设计打印文档每个学生一份，并装在统一的资料袋中，资料袋前面要贴有学校统一的资料袋封面。

四、提交的成果1. 课程设计说明书内容包括(1) 封面（学院统一印制）；(2) 课程设计任务书；(3) 中文摘要150字；关键词3-5个；(4) 目录；(5) 正文；（设计思想；各模块的伪码算法；函数的调用关系图；测试结果等）(6) 设计总结；(7) 参考文献；(8) 致谢等。

注：每一部分是单独的一章，要另起一页写。

2. 排版要求(1) 所有一级标题为宋体三号加粗（即上面写的2～8部分，单独一行，居中）(2) 所有二级标题为宋体四号加粗（左对齐）(3) 所有三级标题为宋体小四加粗（左对齐）(4) 除标题外所有正文为宋体小四，行间距为固定值22磅，每个段落首行缩进2字符(5) 目录只显示3级标题，目录的最后一项是无序号的“参考文献资料”。

3. 其他要求（班长负责，务必按照以下方式建文件夹）(1) 以班级为单位刻录光盘一张，光盘以班级命名，例如：“10级计算机科学与技术1班”；(2) 光盘内每人一个文件夹，以学号姓名命名——如“10730101 陈映霞”，内容包括任务书、设计文档。

pv操作题目 软考

pv操作题目 软考

PV操作在软考中的深入探讨1. 基本概念PV操作是用于进程同步的两种基本操作。

P操作通常表示为一个进程需要一个资源，而V操作表示释放一个资源。

这两种操作通常用于实现进程间的同步和互斥。

2. PV操作原理PV操作基于信号量机制。

信号量是一个整数值，通常用于表示资源的数量。

P操作会尝试获取资源，减少信号量的值；而V操作会释放资源，增加信号量的值。

如果P操作不能立即获得资源（即信号量为0），则该进程会被阻塞或等待，直到资源可用。

3. PV操作在进程同步中的应用PV操作在进程同步中有着广泛的应用。

例如，在生产者-消费者问题中，生产者用于生成数据，消费者用于消费数据。

通过PV操作，可以确保生产者在没有数据被消费之前不会继续生产，同时确保消费者在没有数据可供消费时不会继续消费。

4. PV操作和互斥量互斥量是一种特殊的信号量，其值只能为0和1。

当一个进程获得互斥量时，其他任何进程都无法获得该互斥量，直到第一个进程释放它。

这使得互斥量可以用于保护某些临界区域，以实现互斥访问。

PV操作和互斥量通常一起使用，以实现更复杂的同步问题。

5. PV操作的编程实现在大多数编程语言中，PV操作可以通过系统调用或库函数实现。

例如，在UNIX系统中，可以使用semop函数进行PV操作。

在实现PV操作时，需要注意避免死锁和饥饿等问题。

6. PV操作的复杂度分析PV操作的复杂度取决于所使用的算法和数据结构。

在一些算法中，例如二叉堆或斐波那契堆，PV操作的平均时间复杂度可以达到O(1)。

然而，在最坏的情况下，PV操作的复杂度可能会达到O(n)，其中n是信号量的值。

7. PV操作与信号量信号量是一种同步机制，用于控制多个进程对共享资源的访问。

PV操作是信号量机制中的基本操作，通过它们可以实现对共享资源的互斥访问和同步。

信号量通常用于保护临界区、实现进程间的同步和互斥等。

8. PV操作与死锁预防死锁是操作系统中的一个重要问题，它发生在两个或多个进程无限期地等待对方释放资源的情况。

龙门同步算法

龙门同步算法

龙门同步算法龙门同步算法是一种用于多线程编程的同步机制，用于协调多个线程之间的操作顺序，以保证数据的一致性和正确性。

本文将介绍龙门同步算法的原理、应用场景以及其在实际开发中的使用方法和注意事项。

一、龙门同步算法的原理龙门同步算法是基于信号量机制实现的一种同步机制。

信号量是一种用于控制并发访问的计数器，通过对信号量的操作（比如P操作和V操作）来实现线程的同步和互斥。

而龙门同步算法则是在信号量的基础上进行了进一步的优化。

龙门同步算法的核心思想是引入了龙门和龙珠的概念。

龙门相当于一个互斥锁，用于控制临界区的访问权限，而龙珠则相当于一个信号量，用于控制线程之间的同步。

当一个线程需要进入临界区时，首先要获取龙门，如果龙门已经被其他线程持有，则该线程会被阻塞；当线程执行完临界区的操作后，需要释放龙门，以便其他线程可以获取并进入临界区。

龙门同步算法适用于多线程访问共享资源的场景，特别是当多个线程需要按照一定的顺序执行时，龙门同步算法可以保证线程之间的顺序执行，从而避免数据竞争和不一致性的问题。

例如，在生产者-消费者模型中，生产者线程负责生产数据，消费者线程负责消费数据，而且消费者线程必须在生产者线程生产完数据后才能进行消费。

这时就可以使用龙门同步算法来保证生产者线程和消费者线程的顺序执行，从而避免数据的丢失或重复消费。

三、龙门同步算法的使用方法和注意事项使用龙门同步算法进行多线程编程时，需要注意以下几点：1. 确定临界区：首先需要确定哪些代码块是临界区，即多个线程需要同步执行的部分。

2. 创建龙门和龙珠：根据需要同步的线程数量，创建对应数量的龙门和龙珠。

3. 获取龙门和释放龙门：在线程需要进入临界区时，调用龙门的获取方法，如果龙门已经被其他线程持有，则当前线程会被阻塞；在线程执行完临界区操作后，需要释放龙门，以便其他线程可以获取。

4. 处理异常情况：在使用龙门同步算法时，需要考虑异常情况的处理，比如防止死锁和饥饿等问题。

mifare classic 认证算法

mifare classic 认证算法

mifare classic 认证算法Mifare Classic是一种使用不对称密钥进行认证的智能卡技术，广泛应用于门禁系统、电子钱包、交通票务系统等领域。

它采用了基于DES算法的认证算法，以确保卡片与读写器之间的通信安全性。

本文将详细介绍Mifare Classic的认证算法，并逐步解释其实现过程。

第一步：密钥管理在Mifare Classic认证算法中，密钥管理是非常重要的一步。

每个Mifare Classic卡片都存储有若干个扇区（Sector），每个扇区有一个密钥用于验证卡片的合法性。

通常情况下，每个扇区都使用两个密钥，分别被称为A 密钥和B密钥。

其中，A密钥用于进行读操作，而B密钥则用于写入和读取操作。

第二步：互斥操作在Mifare Classic卡片中，对于每个扇区来说，同一时间只能有一个密钥与之关联。

这就要求在进行认证操作之前，必须先获取扇区独占访问权限。

这一过程称为互斥操作，其目的是确保每次只有一个密钥能够与目标扇区进行通信。

第三步：认证过程认证过程是Mifare Classic算法的核心部分。

在这一步中，读写器会发送一个特殊的命令给Mifare Classic卡片，要求其使用指定的密钥对目标扇区进行认证。

具体的认证过程如下：1. 读写器向卡片发送认证命令，其中包含了要认证的扇区号及相应的密钥类型（A密钥或B密钥）；2. 卡片接收到命令后，首先检查是否存在互斥操作。

如果有其他密钥正在与目标扇区通信，卡片会进行等待，直到获得访问权限；3. 卡片读取目标扇区的密钥，并使用该密钥对一个随机数进行加密；4. 卡片将加密后的结果发送给读写器，并同时记录所使用的密钥类型；5. 读写器使用相同的密钥对收到的加密结果进行解密，得到卡片发送的随机数；6. 读写器将自己生成的另一个随机数，以及解密后的卡片随机数，通过一个哈希函数进行运算，得到一个消息认证码（MAC）；7. 读写器将生成的MAC发送给卡片；8. 卡片用相同的哈希函数对自己生成的随机数进行运算，并与收到的MAC进行比较。

第二部分 考前第5天 概率与统计、推理证明、算法

第二部分 考前第5天 概率与统计、推理证明、算法

解决程序框图问题时， ❻ 解决程序框图问题时，一定要仔细分析程序框图的 实际意义是什么，也就是这个程序框图要计算的是什么， 实际意义是什么，也就是这个程序框图要计算的是什么， 这个计算是从什么时候开始、中间按照什么规律进行、 这个计算是从什么时候开始、中间按照什么规律进行、最 后计算到什么位置．这是分析程序框图的一个基本思路． 后计算到什么位置．这是分析程序框图的一个基本思路．
[尝试 尝试3] 若将一枚质地均匀的骰子 一种各面上分别标 若将一枚质地均匀的骰子(一种各面上分别标 尝试 个点的正方体玩具)先后抛掷 有1,2,3,4,5,6个点的正方体玩具 先后抛掷 次，则出现向 个点的正方体玩具 先后抛掷2次 上的点数之和为4的概率为 上的点数之和为 的概率为____________． 的概率为 ．
[尝试 7] 尝试 ＋b＝ ＝ A．1 ． B．0 ． C．－ ．－1 ．－ D. 3 2 1＋2i ＋ (2011·辽宁协作体 辽宁协作体) 辽宁协作体 ＝2－i，a∈R，b∈R，则 a －， ∈ ， ∈ ， a＋bi ＋ ( )
[答案 A 答案] 答案
❽类比推理用一类事物的性质去推测另一类事物的性 猜想)， 质，得出一个明确的命题(猜想 ，类比的结论不一定正 得出一个明确的命题 猜想 确． 归纳推理是由部分推知整体的一种合情推理， 归纳推理是由部分推知整体的一种合情推理，和 类比推理一样， 合乎情理 是其主要特征， 合乎情理”是其主要特征 类比推理一样，“合乎情理 是其主要特征，即我们作 出的归纳首先要适合“部分 ． 出的归纳首先要适合 部分”． 部分
应用互斥事件的概率加法公式， ❶ 应用互斥事件的概率加法公式，一定要注意首先确 定各事件是否彼此互斥， 定各事件是否彼此互斥，然后求出各事件分别发生的 概率，再求和． 概率，再求和．

操作系统20

操作系统20

一、选择题（每题1分，共30分）1. 在Hoare管程中，signal操作的语义是______。

A. signal and leaveB. signal and urgent waitC. signal and continueD. signal and entry wait2. 忙式等待的进程处于______状态。

A. 等待状态B. 运行状态C. 就绪状态或运行状态D. 就绪状态3. 经典UNIX系统采用的互斥方法是______。

A. 开关中断B. 软件互斥算法C. ＰＶ操作D. 自旋锁4. 在段页式存储管理中，逻辑地址为（s,p,d），其中______可能越界。

A. s和dB. p和dC. s和pD. s、p、d都5. UNIX操作系统的进程调度算法是______。

A. 可抢占CPU的HPF算法B. RR算法C. FB算法D. HRN算法6. CPU执行______时所花的时间不属于系统开销。

A. 用户程序B. 死锁检测程序C. 处理机调度程序D. 缺页中断处理程序7. 在下列调度算法中，______可用于实时调度且属于剥夺式（可抢占式）调度算法。

A. RMS算法B. EDF算法C. FB算法D. HRN算法8. 适合分布环境的同步机制是______。

A. 信号灯与PV操作B. 管程C. 会合D. 条件临界区9．作业调度是从输入井中处于______ 状态的作业中选取作业调入主存运行。

A. 运行B. 完成C. 提交D. 后备10.Hash文件采用的寻址方法主要是以______ 为主。

A. 计算B. 比较C. 索引D. 顺序11. 可能发生Belady异常的页面置换算法是______。

A. FIFO算法B. NUR算法C. LRU算法D. LFU算法12．在Solaris系统中，用户和系统均可见的成分是______。

A. 用户级线程B. 核心级线程C. 轻进程D. 系统线程13．某计算机系统中有8台打印机，由K个进程竞争使用，每个进程最多需要3台打印机。

图论中的二分图匹配问题及其算法设计思路

图论中的二分图匹配问题及其算法设计思路

图论中的二分图匹配问题及其算法设计思路二分图匹配问题是图论中的重要问题之一。

二分图是指一个图的顶点可以分为两个互斥的集合，并且图的边只能连接两个集合之间的顶点。

二分图匹配的目标是找到一个匹配，即找到一种对应关系，使得图中的所有顶点都能够与另一个集合中的顶点相连。

在实际应用中，二分图匹配有着广泛的应用。

比如在招聘网站中，求职者和企业可以被看作是一个二分图，通过匹配求职者和企业，可以使得求职者找到合适的工作岗位，企业找到合适的人才。

在网络流量调度中，可以将网络中的节点和链路看作一个二分图，通过匹配可以实现有效的数据传输。

那么如何解决二分图匹配问题呢？目前比较常用的算法有匈牙利算法和增广路径算法。

匈牙利算法，也称为增广路径算法，是解决二分图最大匹配问题的一种经典算法。

该算法从某一个未匹配的顶点开始，尝试去匹配其他的顶点。

如果当前顶点没有匹配的边，那么匈牙利算法会尝试寻找一个增广路径，即一条能够增加匹配数的路径。

当不存在增广路径时，匈牙利算法会返回当前匹配的结果。

增广路径算法是一个递归的过程。

首先，我们从一个未匹配的顶点开始，将其标记为已访问。

然后遍历与该顶点相连的所有边，如果边的另一个顶点没有被访问过，那么我们尝试去匹配这个顶点。

如果匹配成功，那么整个算法就结束了，返回当前的匹配结果。

如果匹配失败，我们需要尝试寻找另一个增广路径，这时我们会递归地调用增广路径算法，从当前的匹配边的另一个顶点开始。

增广路径算法的时间复杂度为O(V*E)，其中V是顶点数，E是边数。

在实际应用中，匈牙利算法已经被广泛应用，因为其算法简单易懂，同时具有较好的计算效率。

除了匈牙利算法，还有其他一些解决二分图匹配问题的算法，比如多项式时间的Hopcroft-Karp算法和Edmonds的算法。

这些算法在不同的应用场景中，可能有着更好的性能表现。

总结来说，二分图匹配问题在图论中具有重要的地位，它可以通过匈牙利算法等多种算法来解决。

在实际应用中，二分图匹配问题可以用于求职招聘、网络流量调度等领域。

经典密钥加密算法和量子密码通信对比验证

经典密钥加密算法和量子密码通信对比验证

经典密钥加密算法和量子密码通信对比验证密钥加密算法和量子密码通信是当今主要的数据通信保密方法。

两种方法在不同方面具有优势和劣势，本文将对经典密钥加密算法和量子密码通信进行对比验证。

经典密钥加密算法作为一种常见的加密方式，使用公钥和私钥来进行加密和解密。

常见的经典算法包括DES、AES和RSA等。

这些算法在过去几十年中得到了广泛应用并取得了良好的效果。

然而，随着计算机技术的发展，传统密钥加密算法面临着一些挑战。

首先，经典密钥加密算法在安全性方面存在一定的风险。

由于计算机计算能力的不断增强，传统算法的加密强度逐渐减弱。

特别是RSA算法，它的安全性依赖于大数因子分解的困难性，但是随着量子计算机的发展，这个问题可能会被迅速解决，导致传统密钥加密算法容易受到攻击。

其次，经典密钥加密算法需要传送密钥，而密钥的传输本身也面临着一定的安全风险。

在传统网络通信中，密钥的传递需要使用非对称加密算法，这就意味着在传输过程中需要使用大量的计算资源和时间来完成。

此外，由于密钥的传输是在非安全信道中进行的，攻击者有可能截获密钥并进行解密。

与传统密钥加密算法相比，量子密码通信是一种具有创新意义的通信方式。

量子密码通信采用了量子力学原理来保护数据的安全性。

量子密码通信基于两个基本原则：不可克隆性和不可破译性。

量子密钥分发（QKD）是最常见的量子密码通信方法之一。

在QKD中，当传输密钥的量子比特与外部环境发生相互作用时，传输过程会被监测到，并立即检测到攻击行为。

值得注意的是，量子密码通信并不是一个完美的解决方案。

尽管量子密码通信可以防止密钥被窃取，但它并不能阻止中间人攻击等其他类型的攻击。

此外，量子密码通信的实现依赖于专门的量子技术，这使得其成本相对较高，限制了其在实际应用中的推广和普及。

特别值得一提的是，经典密钥加密算法和量子密码通信并非完全互斥。

事实上，在实际应用中，常常将两种方法结合起来使用，以充分发挥各自的优势。

例如，在现代通信中，经典密钥加密算法常用于保护传输的对称密钥，而量子密码通信用于分发和验证对称密钥的安全性。

读者学者问题

读者学者问题

矿产资源开发利用方案编写内容要求及审查大纲
矿产资源开发利用方案编写内容要求及《矿产资源开发利用方案》审查大纲一、概述
㈠矿区位置、隶属关系和企业性质。

如为改扩建矿山, 应说明矿山现状、
特点及存在的主要问题。

㈡编制依据
(1简述项目前期工作进展情况及与有关方面对项目的意向性协议情况。

(2 列出开发利用方案编制所依据的主要基础性资料的名称。

如经储量管理部门认定的矿区地质勘探报告、选矿试验报告、加工利用试验报告、工程地质初评资料、矿区水文资料和供水资料等。

对改、扩建矿山应有生产实际资料, 如矿山总平面现状图、矿床开拓系统图、采场现状图和主要采选设备清单等。

二、矿产品需求现状和预测
㈠该矿产在国内需求情况和市场供应情况
1、矿产品现状及加工利用趋向。

2、国内近、远期的需求量及主要销向预测。

㈡产品价格分析
1、国内矿产品价格现状。

2、矿产品价格稳定性及变化趋势。

三、矿产资源概况
㈠矿区总体概况
1、矿区总体规划情况。

2、矿区矿产资源概况。

3、该设计与矿区总体开发的关系。

㈡该设计项目的资源概况
1、矿床地质及构造特征。

2、矿床开采技术条件及水文地质条件。

浅析生产者和消费者问题算法

浅析生产者和消费者问题算法
的同步互斥 关 系。
一
ｎ １２ Ａｌｓ＇ｒａ Ｓ ｍ ｐ ｏｅ （ Ｓ ｍａｈ ｒＡｔｉｕ ｓ ｅ ＇ ｉ ‘ ｅｔ ｅ ａ ｈ ｒ’１ ｅ ｐ ｏｅ ｔｂ ｔ ３’ ａ Ｃ ｅ ＇ ｐ ｒ ｅ
Ａｓ Ｓ ＥＣＵＲＩ ＴＹ ＡＴＦ ＢＵＴＥＳ， Ｖａ ｌ ｉｉｌ ＲＩ Ｂｙ ｌｌｎｔａＣｏｕ ｔＡｓ ｎ
、
信 号量机 制
安全特性 的数据 结构 。
２ ． 参数ｌ ｉ ｌｏ ｎ ｌｔ Ｃｕｔ ｎｉ ａ ￣置信号量的初始值。
信号量 、操作和Ｖ Ｐ 操作统称为信号量机制 ， 它是
解 决进 程互斥 ｎ Ｍａｉ ｍＣ ｕ ｔ ｍ ￣置信号量的最大值（ 可
ｖ０ ． Ｎ ｏ３ １ ２２ ．
Ｊｎ ｕｅ
２ ０８ ０
浅析生产者和消费者问 题算法
口 王 哲
长春 １０ １ ） ３ ０２ （ 吉林省 经济 管理 干部 学 院 ，吉林 睛
要】 操作 系统 中生产者 和 消 费者 的进 程 同步 问题 是 计 算机 中一个 经 典 的抽 象模 型 。 利 用信 号
量机制以及 Ｗｉｄ ｗ Ｐ 函数解决生产者和消费者 问题 的算法，可以解决生产者和消费者之间的同步 ｎｏ ｓ Ｉ Ａ
互斥 关 系。
【 关
键
词】 信号量； 同步； 互斥 ； 缓冲区
【 中图分类号】 Ｐ ０ ． Ｔ ３ １ ６
【 文献标识码】 Ａ
【 文章编号］０９０ ５（ ０ ８０．０ ８０ １０．６ ７２ ０ ）３０７ ．４
品 ： 费者不断 地从数 据缓 冲区取 出产品并 消费 。 消
“ｅｎ ｌ２ Ａｌ ｓ “ ｉ ｏ Ｓｎ ｌＯｂｅ ｔ ｒ ｙ ａ ｋ ｒ ｅ３ ” ｉ ａ Ｗａｔ ｒ ｉｇｅ ｊ ｃ” Ｂ Ｖ ｌ Ｆ

操作系统实验报告经典生产者—消费者问题范文大全[修改版]

操作系统实验报告经典生产者—消费者问题范文大全[修改版]

第一篇：操作系统实验报告经典生产者—消费者问题实验二经典的生产者—消费者问题一、目的实现对经典的生产者—消费者问题的模拟，以便更好的理解经典进程同步问题。

二、实验内容及要求编制生产者—消费者算法，模拟一个生产者、一个消费者，共享一个缓冲池的情形。

1、实现对经典的生产者—消费者问题的模拟，以便更好的理解此经典进程同步问题。

生产者－消费者问题是典型的PV 操作问题，假设系统中有一个比较大的缓冲池，生产者的任务是只要缓冲池未满就可以将生产出的产品放入其中，而消费者的任务是只要缓冲池未空就可以从缓冲池中拿走产品。

缓冲池被占用时，任何进程都不能访问。

2、每一个生产者都要把自己生产的产品放入缓冲池，每个消费者从缓冲池中取走产品消费。

在这种情况下，生产者消费者进程同步，因为只有通过互通消息才知道是否能存入产品或者取走产品。

他们之间也存在互斥，即生产者消费者必须互斥访问缓冲池，即不能有两个以上的进程同时进行。

三、生产者和消费者原理分析在同一个进程地址空间内执行两个线程。

生产者线程生产物品，然后将物品放置在一个空缓冲区中供消费者线程消费。

消费者线程从缓冲区中获得物品，然后释放缓冲区。

当生产者线程生产物品时，如果没有空缓冲区可用，那么生产者线程必须等待消费者线程释放一个空缓冲区。

当消费者线程消费物品时，如果没有满的缓冲区，那么消费者线程将被阻挡，直到新的物品被生产出来。

四、生产者与消费者功能描述：生产者功能描述：在同一个进程地址空间内执行两个线程。

生产者线程生产物品，然后将物品放置在一个空缓冲区中供消费者线程消费。

当生产者线程生产物品时，如果没有空缓冲区可用，那么生产者线程必须等待消费者线程释放出一个空缓冲区。

消费者功能描述：消费者线程从缓冲区获得物品，然后释放缓冲区，当消费者线程消费物品时，如果没有满的缓冲区，那么消费者线程将被阻塞，直到新的物品被生产出来。

五、实验环境操作系统环境：Windows 系统。

编程语言：C#。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

2 经典互斥算法 每一个线程都有一个私有变量 i 表示自己的 id，由于有两 个线程，所以 i 的取值为 1 或者 2，因此 other = 3 − i 取值 表示下一轮应该轮到谁进入临界区了。 算法 1 Dekker 算法 1: status[i] = competing;
2: 3: 4: 5: 6: 7: 8: 9: 10: 11:
Dijkstra 算法，因为 Dijkstra 算法通常指的
是求图中最短路径的算法。
2 经典互斥算法
3
后来都反对 [Dij68b] 的 go to 语句。所以这里列出的算法 N 个线程的情况，结构同样很简单。我们先看 2 线程的 对原文的算法结构进行了一些调整，使其更适合当代的 Peterson 算法，如算法 3 所示。算法中 q 是一个二元组， 阅读习惯。从算法的结构可以看出，在临界区之前的 lock q[1] 由线程 1 操作，q[2] 由线程 2 操作，两个值的初始值 部分包含一个循环，循环内部是一个 if 判断语句，根据 条件将循环体分割为两部分。假设 N 个线程都在竞争临 界区，根据第 3 行的条件，只有一个线程能进入 else 部 分，即第 7–8 行，这个线程也就是 k 表示的那个线程。这 个线程判断是否除了自己的 c[i] 之外其他所有线程的 c[i] 都为 true，如果满足的话则退出循环进入临界区。这个 条件显然最后是可以满足的，因为所有其他的线程都在 循环执行 if 条件满足的那一部分，因此一定会将自己的 c[i] 设置为 true。当 k 表示的这个线程完成了临界区之后， 会将 c[i] 和 b[i] 都设置为 true。这时，除了线程 k 之外的 所有其他的线程的第 5 行的 if 条件都会满足，因此执行 k = i，试图将 k 设置为自己。最终 k 总会表示某一个正 在竞争的线程，这个线程进入 else 部分循环，而且此时 b[k] == false，所以其他失败的线程依然在第 4–5 行循环 执行，并且还会争相将自己的 c[i] 设置为 true，让抢到了 k 的线程能够尽快进入临界区。所以可以看出， Dijkstra 提出的算法解决了 N 个线程之间的互斥问题。 都为 false。 turn 是两个线程共享的一个整型变量，初始 值可以是 1 或 2。 算法 3 Peterson 算法（2 线程） 1: q[i] = true;
接在总线上访问或通过互联网络访问或通过多核处理器 互斥问题最早是 Edsger W. Dijkstra1 在 1965 年的 ACM 内部的互联网络访问。为了统一术语，本文使用最常用的 通讯中正式提出的 [Dij65]。文中的问题描述如下：有 N 多线程编程使用的术语。 台计算机都在重复执行某项任务，这项任务中有一段称 为 “临界区”，要求同一时刻这 N 台计算机中只能有一台 在临界区中。计算机之间可以通过共享的存储空间协调 访问临界区。写入和读取临界区的操作是不可分割的。解 决方法必须满足以下特点： 1. N 台计算机是对称的，没有指定的优先级；
1
互斥问题的定义
互斥（mutual exclusive）是我们现在进行多线程编程
每一次只能发出一次读写请求，按照现在的话说，就是在 的一个基本工具。本文探寻分布式计算历史上的几个非 缺少 read-modify-write 这类原子操作的情况下要实现互 常有名非常经典的互斥算法，尽管这些算法几乎是所有 斥是很难的。 操作系统、分布式系统或多线程编程课本中必介绍的算 法，可是由于这些算法由于性能问题已经被现代的算法 或机制替代了，实际中不会有人使用这些算法。尽管如 此，了解这些算法可以帮助我们理解同步领域的基本原 理。此外，了解这些算法的正确性证明可还可以训练并发 算法正确性推导的思维。 在那个没有多核处理器或多处理器计算机的年代， 一台 “计算机” 同时只能执行一个线程，所以原文中的 “计 算机” 用现在的话来说就是一个处理器或多核处理器中的 一个核心或一个硬件线程， “共享的存储空间” 可以是线 程或进程间的共享内存，访问共享内存的方式可以是直
* zhengsyao@，/zhengsyao/ 1 Edsger
2
2.1
经典互斥算法
Dekker 算法
Dekker 算法是第一个正确地通过软件方法解决两
W. Dijkstra 是计算机发展历史上的重要人物，除了耳熟能详
线程互斥问题的算法，该算法最早由 Dijkstra 在 [Dij68a] 中 描 述， 算 法 1 就 是 Dekker 算 法。 算 法 中 的 status[1] 和 status[2] 分 别 表 示 两 个 线 程 的 状 态， 状 态 可 以 取 值 competing 和 out。如果状态取值 competing，表示当前线 程处于正在竞争进入临界区的状态；如果状态取值为 out， 则表示这个线程放弃尝试进入临界区或已经退出临界区。 1
2 本文不把这个算法称为
算法 2 Dijkstra 提出的算法 1: b[i] = false;
2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12:
loop if k ≠ i then c[i] = true; if b[k] == true then k = i; else c[i] = false; if ∀j ≠ i, c[j] == true then break; end if end loop 临界区; c[i] = true; b[i] = true;
经典互斥算法
郑思遥* 2013 年 1 月 4 日
摘要
本文用较为轻松的方式介绍了几个经典的互斥算法： Dekker 算法、 Dijkstra 提出的算法、 Peterson 算法和面包 店算法，并简单地给出了每一个算法的正确性证明和相 关的讨论。
2. 对 N 台计算机的速度不做任何假设，甚至同一台计 算机的速度也不一定是固定不变的； 3. 如果某台计算机在临界区之外停机了，那么不允许 导致其他计算机阻塞； 4. 不允许发生 “Aer you”–“Aer you” 阻塞，也就是说， 如果所有计算机都没有在临界区中，那么必须允许 一个——只允许一个——计算机进入临界区。 这个问题看上去挺简单，其实不容易，因为每一台计算机
的计算最短路径的 Dijkstra 算法，他也是分布式计算领域的开创者，重 要成果包括信号量和哲学家就餐问题。 Dijkstra 卒于 2002 年，同年其 1974 年的论文 “Self-stabilizing systems in spite of distributed control” 被授 予 ACM PODC（Symposium on Principles of Distributed Computing）最有 影响力论文奖。为了纪念这位科学家，PODC 最有影响力论文奖在 2003 年更名为 Dijkstra 奖。
为 2 或者 1，表示另一个线程的 id。turn 是一个共享变量， 次变化只能由线程 2 来完成，所以线程 2 最终总能发现
while status[other] == competing do if turn == other then status[i] = out; wait until turn == i; status[i] = competing; end if end while 临界区; turn = other; status[i] = out;
2: 3: 4: 5:
turn = i; wait until not q[3 − i] or not turn == i; 临界区; q[i] = false; 在 lock 操作中，线程首先将自己的 q[i] 设置为 true，
并且试图将 turn 设置为自己。第 3 行的等待循环判断两 个条件，如果有一个为真就进入临界区。两个线程不可能 同时通过第 3 行的判断条件，因为如果两个线程都到达这 一行了，那么 q[1] 和 q[2] 都为 true，所以只能同时满足 判断的后一个条件，而 turn 不可能同时为两个值，所以 两个线程只能先后通过这个条件。假设线程 1 通过了这个 条件判断，进入了临界区。那么此时必满足 q[2] == false

这个算法中的采用的变量名初看上去不好理解， 实际 和 turn == 2 中至少一个条件。如果满足前者，说明线程 上对照算法 1 中使用的变量名，数组 b[1 ∶ N] 和 c[1 ∶ N] 2 已经退出临界区或还没有开始竞争临界区，如果线程 2 共同表示了线程的状态，整数 k 实际上等同于 turn。 开始竞争进入临界区，那么必然无法通过第 3 行的判断条 Dijkstra 提出的算法有一个问题就是不能防止线程饿 死。如果有一个线程获得了 k，而且这个线程反复试图访 问临界区，假设这个线程很快进入 lock 部分的代码，将 b[k] 设置为 false，那么其他线程有可能永远都在循环中 等待。这个问题很快被 Knuth 发现了 [Knu66]（对，就是 件。如果满足后者，说明线程 2 已经执行完成了第 2 行， 此时由于线程 1 仍然在临界区，所以 q[1] 为 true，因此线 程 2 仍然无法通过第 3 行的判断条件。因此，这个算法可 以保证两个线程互斥访问临界区。另外也可以看出，这两 个线程都不会饿死。假设线程 1 在第 3 行的循环等待，线
2.2
Dijkstra 提出的算法
Dijkstra 在 [Dij65] 文中正式提出了并发编程中的互
斥问题并给出了一个解决方法。和 Dekker 算法不同的地 方在于，Dijkstra 提出的算法支持 N 个线程同时竞争临界 区，算法如算法2所示2 。这个算法使用了 2 个共享的数组
以第 9 行表示的临界区为界，之前的操作是试图进 b[1 ∶ N] 和 c[1 ∶ N]， N 表示最大的线程数。这两个数组 入临界区之前要执行的操作，相当于互斥锁中的 lock 操 的 b[i] 和 c[i] 只能由线程 i 写入，但是可以由所有线程读 作，之后的操作是执行完临界区之后要执行的操作，相 取。还有一个共享整数变量 k，满足 1 ≤ k ≤ N，所有线程 当于 unlock 操作。线程在试图进入临界区的时候，首先 都可以原子地读写这个变量。i 是线程的私有变量，表示 将自己的状态标记为正在竞争进入临界区。然后通过第 自己的 id。 b[1 ∶ N] 和 c[1 ∶ N] 的初始值都为 true， k 的 2–8 行的 while 循环反复检查对方是否放弃或结束执行临 初始值可以是 [1 ∶ N] 之间的任意值，具体值无所谓。 界区。如果对方没有竞争，则直接进入临界区。如果对方 正在竞争，而且下一轮还轮到对方的话，那么自己首先放 弃，然后在第 5 行等待对方将 turn 让与自己，然后自己 再宣布进入竞争状态。如果下一轮即将轮到自己，那么回 到 while 循环等待对方完成临界区操作。 首先理解这个算法为什么能实现两个线程的互斥。 对于一个试图进入临界区的线程来说，如果另一个线程 没有这个企图，那么很简单直接进入临界区即可。如果 两个线程同时在竞争进入临界区，那么根据第 3 行的条件 判断，只有一个线程能够进入这个 if 语句，进入的这个 线程将自己的状态设置为放弃，所以给另一个线程进入 临界区的机会。另一个线程进入了临界区之后，会将 turn 设置为对方，所以放弃竞争临界区的线程又可以重新竞 争临界区。从这个描述可以看出这个算法可以保证两个 线程的互斥。 要理解这个算法要从这个算法的整体结构入手。原 再来看这个算法是否会导致一个线程 饿死。假设线 文 [Dij65] 中列出的算法代码使用的是 ALGOL 60 语言编 程 1 和线程 2 同时进入临界区， 并且不失一般性假设 写的，结构和缩进都比较混乱，还使用了 Dijkstra 他自己 turn = 1，那么两个线程进入 while 循环，其中线程 2 进入 if 语句。线程 2 将 status[2] 设置为 out，然后等待 turn 变