一道关于P、V操作的操作系统经典题目的正确算法.pdf

一道关于P V 操作的 操作系统经典题目的正确算法 徐健张雷朱向彩 捅E l 本文氽绍了操锋系统中P V 撩锋的有关凝念 分辑了瘟J I lP V 操锋的一遭经典题璃并给出了燕确的解法 关键词 操作系统P V 操作算法 l 操作系统巾的P V 操作简介 凌我攥终系绞基本上部是多送程豹攥馋系统 系鲮串蠢多令遂莛势发 执行 这些并发执行的进程之阐存在着不同的相互制约荚累 为了谤谰进 程之间的这种相藏制约关系 需要实现进程的同步与互斥 在操作系统中存在着各种资源供进程使用 如果某个资源一次只能供 一令送程爱惩 羯猕其荛瘘赛瀣漾 谤篝穰审许多物瑾浚萋翔努窜投 织 描仪等都属于临界资源 除物壤设备外 许多变量 数据等都可以被若平进 程热享 但不允许多个进程同时进行修改操作 它们也可视为临界资源 在每个进程中 访问临界资源的那段程序祢为临界区 在操作系统中 当一令送程送入骥器区菠蔫壤器资源露 男一令迸程必矮等待 墨占爱滚 界资源的进程邋出临界区后 荔一进程才允许去访问此临界资源 这种进 程间的相互制约关系称为互斥 一般说来 在操作系统中 一个进程相对于另一进程的运行速度楚不 骥霆豹 篷是援薹念佟懿死令滋翟需要在慕魏确定点上貉灞它朝筠王俸 所谓进程同步是攒多个相互台体的进程 在一些关键点上可能需要相曩等 待或相互交换信息 这种相互制约关系称为进程同步 在操作系统中艇决进程同步和互斥问题的一种重要方法是信号擞枧 弱髑P V 爨 睾 臻号量是一令辘定戆二元缀 S Q 英孛S 是一令吴套藩 负期值的整形变薰 Q 是一个韧始状态为空的队列 整形变曩s 表示系统 中巢类资源的数目 当其值大予0 时 表示系统中当前可用资源的数目 强 其馕小于0 时 其绝对值表示系统中因其请求该类资源而被阻塞的进程数 萋 羧售号量懿耪德癸 售号薰豹篷援髭垂p 擐俸窝V 攮终改变 P V 操作在1 9 6 5 年由荷兰计算机大师D i j k s t r a 引入 他用荷兰语中的 单词p a s s e r e n 通过 v r i j g e v e n 释放 的首字姆来为这两种操作命名 P V 操作由P 操作原语和V 操作原语组成 原语是不W 中断的过程 霹傣号蠢送行撩 叁 其薅定义魏下 P s 将信号量s 的值藏l 即S S l 如果 3 0 则该进程继续执行 否则该避 程置为等待状态 排入等待 队列 V f s 将德号曩s 弱篷翱l 帮S S l 如果s O 则该进程继续执行 否则释放队列中第一个等待信鸯曩 的进程 利用信号董襁P V 操作可以有效的解决进程的同步襁妪斥问题 2 一遂考察 撩薅戆经獒搔痒系统试遴 P V 揉作是操作系统课程中的重点内容 其考察形式并不仅限于计算 机中进程的互斥和同步 而更多的将现实中的某些事务纳入 要求使用P V 操作来处理这魃事务 许多操作系统教材中都有诸如餐学家进餐闻题 理发l 露淘蘧 生产密一瀵菱考藕邀等经葵剿爨 靛是这褥繁凌豹舔瑗 本 文所要讲述的这邋题目也是这种类型的 天津大学 痊搿大学 篱1 小路示意圈 在南开大学和天津大学之间有一条弯曲的小路 其中从S 到T 段路 每坎只允许一辆自行车通过 但其中有一个小的安全岛M 同时允许两辆 自缀霉痒鏊 丐供薄囊自每车瓣默嚣蕊送人小路壤凌下镶车凌雳 妇黧1 1 1 60 9 2 0 0 8 所示 试设计一个算法使来往的囱行车均可顺利通过 泼鬏霉是毒齐大攀1 9 9 7 年磷究生入学考试熬攥臻系绫糖嚣豹一逢试 题 在缎多操作系统的参考书和习题集中都有收激 其解法一般如下 分析及相关知识 在本题中 需嚣控制路段T 到L 路段S 别K 及安全 岛M 的使用 路段T 到L 及路段s 到K 同时只允许一辆自行车通过 而 安全鑫轰 允诲嚣辆彝抒辜篌爱 因貌霉泼写三今信号重来鏊瑗宅稻 另一 方面 黼一方向上的囱行车最多只能有一辆通过这段路 两个方向上有硝 辆 因此还应该用两个信号量来控制 禳 在本题中 成设置5 令信号黛s r T s K L M 信号量s T 表示是誉 竞谗鸯巍挛簸毒秀大学去天津大擎 蓑初篷惫 信号量稿袭示是歪竞译 自行车从天津大学去南开大学 其初值为1 信号擐砭表示是誉允许自行车 通过路段S 到K 其初值为1 信号黛L 表示是番允许自行车通过路段T 到 L 其初德为1 信号量M 表示安全端上还可停放囱行车的数鼹 其初值必 2 羹较裁莲程 蓥遗魏下 s e m a p h o r eS T 1 s e m a p h o r eT S 1 s e m a p h o r e K 1 s e m a p h o r eL 1 s e l n a p h o r eM 2 t o t i a n j i n 从南开大学去天津大学 l P S T P K 从S 走到K P M 蘧 入安全鑫 v K P L 从L 走到T v f 鲢 v L v S TJ t o n a n k a i 4 簸嚣津大学去裔开大学 P T S P f L 簸零走裂L P M 进入安全岛 ve L P K 从K 走到S v M v K v I S 以上是一般参考粥中给出的解法 后来笔者又在网上找到了安徽理 工大学撵作系统课程嘲站上给出的另 种解法 如下所示 垂于小夔孛滔懿安全离麓凌灸洚嚣囊鑫孬霉傍鏊 本应该掺荧褒彝资 万方数据 源而设置信号量 但仔细分析可以发现 在任何时刻进入小路的自行车最 多不会超过两辆 南开和天大方向各一辆 因此 无需为安全岛M 设置信 号量 在路口S 处 南开出发的若干自行车应进行进入小路权的争夺 以 决定谁能够进入小路s K 段 为此 设置信号量s 初值为1 来控制南开路 口资源的争夺 同理 设置信号量T 初值为1 来控制天大路口资源的争 夺 此外 小路s K 段仅允许一辆自行车通过 所以设置信号最s K 初值为 1 来进行控制 而对于L T 段则设置信号量L T 初值为1 进行控制 控制 过程描述略 3 该题目正确的算法 下面我们抛弃掉这个错误的前提 看一下真实情况下的小路 能够容 许什么样的交通 当对面没有来车的情况下 小路应该允许多辆自行车单 向行驶 若一个方向有多辆自行车进入 另一方向仅有一辆自行车 则可以 在安全岛错车 单独的自行车要在安全岛里等待对面自行车全部通过安全 岛后方可进入第二路段 若两个方向都有超过一辆的自行车进入 则双方 都无法通过 出现死锁 另外 两个路段中都只允许单个方向的自行车进 入 不能有两个方向的自行车同时存在 两个路段可以分别有不同方向的 自行车 由P V 操作的定义可知 这种方法是对资源进行封锁 当下一个进程 进行P 操作时会因为没有可用的资源而被阻塞 因此 现在问题转化为在 什么情况下应该对后来的自行车进行阻塞的问题 为方便说明 引入两个变量j j i 表示本方向已进入小路的自行车数 量 j 表示对面方向进入小路的自行车数量 分情况讨论 当i 0 j 0 时 本方可以任意进入 对方可以进一辆车 无需封锁 当i 1 j l 时本方或 对方都可以进一辆车 双方在安全岛错车 因此也无需封锁 当i 1 j 1 时 本方可以进车 而对方不能进入 因此要封锁对方后续自行车进入 i 0 j O 时 本方可以进一辆车 对方也可以进入 无需封锁 i l j 1 时 本 方不能再进 对方可以进入 因此需要封锁己方后续进入 i 1 j 1 这种 情况不可能出现 如果出现意味着算法失败 再考虑解锁 由于在封锁时可以封锁对方 也可以封锁本方 因此 解 锁时也要考虑 解锁的时机应该放在本方向最后一辆自行车离开小路时 是否解锁要根据是否封锁来确定 由于信号量只能由P V 操作访问 因此 应该设置一个共享变量来表示当前加锁情况 以上是对于整个路径的封锁情况 由于每个路段都只能单向行驶 因 此 当一辆自行车进入后 应当阻塞对面方向的自行车进入该路段 本方向 的自行车可以依次进入 在最后一辆自行车离开时 进行解锁 安全岛可以容纳两辆自行车 因此资源M 2 但是在i l j 1 的情 况下 有可能出现 本向两辆自行车进入安全岛 等待进入第二路段 而对 方自行车却在第二路段中等待进入安全岛的情况 这样就发生了死锁 由 于安全岛的作用就是错车 这里我们不考虑同方向自行车利用安全岛超车 的可能J 因此 同时进入安全岛的自行车一个方向只能有一辆 我们可以 把临界资源M 分成M 和M 两部分 数量都为1 来表示 T 和T s 两个 方向的安全岛资源 通过这种方法 可以避免前述的死锁问题 设置信号量如下 w a i t 控制两个方向的自行车只能依次进入小路 不能有两辆自行车同 时由小路两端进入 s e n t r y t e n t r y 表示是否允许两个方向的自行车进入小路 s k I t t l k s 表示是否允许自行车按方向进入该路段 比如s k l 表示 允许自行车由s 端进入s k 路段 v a r i e t y 用来封锁共享变量 避免两个进程同时访问共享变量 为避免 复杂性 程序中只提供一个这样的信号量 它对所有共享变量提供保护 设置共享变量e o u n t S K c o u n t l s e o u n t T L c o u n t L T 表示路段内某方向的 自行车数量 b l o c k 记录当前对s e n t r y 和t e n t r y 的封锁情况 b l o c k 0 表 示两个方向都没有封锁 b l o c k 1 表示封锁S T 方向 b l o c k 2 表示封锁 T s 方向 算法描述如下 s e m a p h o r ew a i t 1 s e m a p h o r eS e n t r y2 1 s e m a p h o r et e n t r y 2 l s e n L a p h o r es k 1 s e m a p h o r eh l s e m a p h o r et l 1 s e m a p h o r ek s 1 s e m a p h o r eM 8 1 s e m a p h o r eM t l s e m a p h o r ev i e t y21 i n tc o u n t S k 0 i n tc o u n t l S 0 i n tc o u n t T L 0 i n tc o u n t L T 0 i n tc o u n t N s 0 i n te o u n t M t 0 i n tb l o c k 0 l a i n e o b e g i n S t o T T t o S e 0 I e n d S t o T 从南开大学去天津大学 P w a i t P 8 一e n t r y P s k p v a r i e t y i f c o u n t S K O P k s c o u n t S K i f fe o u n t T L e o u n t M t 1 b l o c k l i f c o u n t S K e o u n t M s 1 P 1 一e n t r y b l o c k 2 V v a r i e t y V s k V w a i t 从S 走到K P M s 进入安全岛 P v a r i e t y e o u n t M s 1 c o u n t S K 一一 i f c o u n t S K O V k s V v a r i e t y P I t V M s P v a r i e t y C o u n t M s 0 I f e o u n t L T O P t 1 C o u n t L T 4 V v a r i e t y 从L 走至0T P v a r i e t y e o u n t L T 一一 i f e o u m L T O V t 1 i f c o u n t S K c o u n t M s e o u n t L T 0a n db l o c k 2 I V t e n t r y b l o c k O V v a r i e t y T t o S 从天津大学去南开大学 P w a i t P t e n t r y 下转第9 8 页 0 9 2 0 0 81 1 7 万方数据 让数学课堂 生活化 徐秀英 关键词 数学课堂生活化兴趣 学以致用 成为新课程对数学教学的一个基本要求 教学大纲 巾 明确糖出 在数学教学孛 要坚楚理论联系实际 增强擎廷羯数学豹戆 识8 数学知识来源于实践 又臌务于实践 它与实际生活鹊联系十分密 切 因此 教师要充分利用学生融有的生活缀验 从生活实际中引出数学 问题 让学生体会到数学就在身边 感受到数学的趣味和价饿 体验到数学 豹熬力 获焉壤券学生鹣数学庭溺薤走 基予淡上豹谈识 霞教学实践牵 我们艇以下几个方面努力 让 娥活 真正的耄进数学课堂 一 导课方式 生活化 罨入新课时 用创设生活情境的方法 W 以激发学习的兴趣 营造良 磐的学习羲国 使学垒缒搽辍主动逢投入学习 理学疆究表鹈 学习内 容和学生熟悉的生活情境越贴诞 学生自觉接纳知识的程度就越高 所 以 教师要善于挖掘数学内容中的生活情境 让数学贴近生活 要尽量地去 刨设一些生活情境 从中引出数学问题 并以貔诖学生惑援剿数学问题的 存在 g 超强烈豹学习需求 激发学生探索蔽德豹兴趣 献群使学生能税缀 主动地投入到学习 探索中去 墨 教学内容 生活化 一切科学知谖赣绦自生活 受囊添的寤逵 在教学露 教耀要注重联系攀 生实际 借助毽们头脑中已经积累鹳生活经验 让举生去学会憨考数学问题 从 而强化学生的数学意识 培养学生的数学能力 怎样使教学内密 生活化 q 鼹 重要的是我们要拓宽教材中的生活资源空间 即教师要在教学中联系生活实 际 趿浚莠霉 遂与聪实生活 黻等密凌援关懿爨蠢簿裁缝 逢隽牲豹数学售惫 资辩采重组教材囟释 使教学内容贴近生活 站谶学生 这样 既有助于学习必 趣的掇高 又有助予培养学生解决襄际问题的能力 熙 设置问题 嫩活化 憋数学与生渗 学习 活动鸯祝结含起来 镬学生感受裂数学漂手黛 活 从而激发学生学习数学的兴趣襁欲望 引导学生把所学知识运用于生 活实际 霹潋毽送学生鹣探索意识籁毯羲意识豹辫藏 壤姜学生初步豹实 践能力 每教一个知谈点 可以编一蓬实际应用的题目让学生练习 培养 学生运用所学知识解决实际问题的能力 如学习三角形的稳慰性后可让 学生解释一下 木工师傅帮同学修理课桌为何要在察脚对角处钳上一根斜 条 又鞠学习了孚厅霸迭形鳆蒋磐爨 请学生瓷硝 楚转么拉撩门要擞袋 平行四i 毅形的网格状而不做成三角形 通过解释一些生活现象 使学生更 深地感受数学与现实嫩活的密切联系 让学生经常去尝试解决生活中的 一些问熬 凸显数学在怼实生活中的疵用价值 西 教擎手羧 生灞纯 从教学方法看 要烧持启发式教学方式 刨设一些与实际生活有关的 问题情景 激发学生思维的积极性 引导他们自融发现和掌握有关规律 教师要楱心设计与实踩生活援联系的教学过程 以艨来激发学娥妁学习兴 趣 强纯学生的学习欲麓 教拜所携懑的实际淘趱应紧密结含教学内容 并编拟成科学的探究程序 使学生能形成一条清晰的思路 从教学手段 看 在引罨学生解决实际问题时 要黛视观察和实验教学 努力掇离学生的 理察能力 实验能力j f 鞋溯手臻圣荤能力 筏学生露验裂数学霰识与羁豢生活 豹密切联系 从而培养学生喜爱数学 学好数学的情感 总之 数学教学的鼹终目标是提高学生在生活实践中自主地 创新地 解决问题的能力 教师在教学过程中 采用与学生生活密切相关的数学活 动 激发攀生豹学习热壤 使学生遂滋镩会弱数学豹徐篷蓑袁予宅与人类 社会活动的密切联系 感到应用数学知识创造性土墩解决生活实际问题的无 穷乐趣 掇高实践活动中自主解决问题的能力和勇干探索 勇予实践 勇于 创新的科学精神 穆者擎餐 溪稳聚妥牵学 上接第1 1 7 页 p f t l P v a r i e t y i f c o u n t T L 0 P I t c o u n t T L 最 c o u n t S K c o u n t M s 1O rc o u n t T L c o u n t M t la n dc o u n t S K C O l l n t M s l V t e n t r y e l s ei f c o u n t T L c o u n t M t 1a n de o u n t S K c o u n t M s 1 b l o c k 2 藩 e o u n t T L c o u n t M t l P s e n t r y b l o c k l V v a r i e t y V t 1 V w a i t l 苁霉走弱L P M t 进入安全岛 P v a r i e t y c o t m t M t I c o u n t T L 一一 i f c