2023年山东大学计算机学院操作系统实验报告.pdf

《2023年山东大学计算机学院操作系统实验报告.pdf》由会员分享，可在线阅读，更多相关《2023年山东大学计算机学院操作系统实验报告.pdf（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、操 作 系 统 课 程 设 计 报 告 00 0 0 0 6 0000 0 0 0学 院:计 算 机 科 学 与 技 术 学 院 专 业：计 算 机 科 学 与 技 术 班 级：20*级*班 姓 名：*目 录-实 验 平 台.4二 P ro je c tl建 立 线 程 系 统.4Taskl.l 实 现 KThread.joinO.41.要 求.42.分 析.43.方 案.44.实 现 代 码.4Taskl.2利 用 中 断 提 供 原 子 性,直 接 实 现 条 件 变 量.61.要 求.62.分 析.63.方 案.74.实 现 代 码.7Taskl.3 实 现 waitUntil.91.要

2、 求.92.分 析.93.方 案.104.实 现 代 码.10Taskl.4用 条 件 变 量，不 使 用 信 号 量，实 现 同 步 发 送 接 收 消 息，speak,listen.121.要 求.122.分 析.133.方 案.134.实 现 代 码.14Taskl.5完 成 Priorityscheduler实 现 优 先 级 调 度.161.要 求.162.分 析.163.方 案.174.实 现 代 码.17L23.要 33123222三 P roject2多 道 程 序 设 计 32223333求 析 案 要 分 方 L23.41424243求 析 案 要 分 方 实 LZ3.4.

3、码 代 求 析 案 现 要 分 方 实 LZ3.45556655555求 析 案 现 要 分 方 实 LZ3.4.一 实 验 平 台 开 发 语 言：Jav a开 发 工 具:E clipse L u n a操 作 系 统：Ubuntul4.04=P r o j e c t l建 立 线 程 系 统 T a s k l.l 实 现 KTh r ead.join()1.规 定 实 现 Im plem ent KThread.join()函 数。注 意：其 它 的 线 程 不 必 调 用 join函 数，但 是 假 如 它 被 调 用 的 话,也 只 能 被 调 用 一 次。对 j。i n 函 数

4、 第 二 次 调 用 的 执 行 结 果 是 不 被 定 义 的(即 使 第 二 次 调 用 的 线 程 与 第 一 次 调 用 的 线 程 不 同 I2.分 析 J o in函 数 的 作 用 即 为 等 待 某 线 程 运 营 完 毕.当 前 线 程(唯 一 一 个 正 在 运 营 的 线 程)A调 用 另 一 个 线 程(处 在 就 绪 状 态)B的 j o i n 函 数 时(A 和 B在 N ach o s中 均 为 K T h re a d类 型 对 象)，A 被 挂 起，直 到 B 运 营 结 束 后，j o i n 函 数 返 回，A 才 干 继 续 运 营。3.方 案 原 K

5、Thre a d 的 join()中 的 L ib.a ssertTrue(th i s!=c u rr e ntT h read)已 经 实 现 线 程 只 能 调 用 一 次 j oin()方 法，根 据 规 定，在 调 用 j。in()方 法 时,让 当 前 运 营 线 程 休 眠，并 将 当 前 运 营 的 线 程 加 入 到 一 个 阻 塞 队 列 中。在 线 程 结 束 时，finish。函 数 循 环 唤 醒 所 有 被 阻 塞 的 线 程。4.实 现 代 码public void jo in()Lib.debug(dbgTh read,Joi n ing to th re a

6、d:+t o S tringO);L i b.a sser t Tr u e(t his!=current T h r ead);bo ole a n in t S t a t u s=Mach i ne.i nterr u p t().disa b 1 e();if(s t a t u s!=statusFinished)(wait F orJo i n.waitForA c c e s s(cu r rentThread);ooKThread.sleep();)public static v o i d fin i sh()(oLib.d e bug(d bgTh read,F inish

7、ing threa d:+cu r r entTh read.toString();Machine.i n terrupt().di s able();Ma c h in e.a u toGrader().finishingC u rre ntTh r ea d();Lib.assertTrue(to B e Dest r o y e d=n u II);toBeDe s t r oyed=currentTh rea d;o c u r rent T h r e ad.st atus=s tatusFin i s hed;KThread wa i tThr e ad;whi 1 e(wa i

8、tThread=c u r re n t Thr e a d.w a i tForJ o i n.nextThr e a d()!=nu 1 1)(w a i tThread.r ead y();0)s 1 e e p();)T a s k l.2 运 用 中 断 提 供 原 子 性，直 接 实 现 条 件 变 量 1.规 定 通 过 运 用 中 断 有 效 和 无 效 所 提 供 的 原 子 性 实 现 条 件 变 量。我 们 已 经 提 供 类 似 的 例 子 用 例 实 现 信 号 量。你 要 按 此 提 供 类 似 的 条 件 变 量 的 实 现，不 能 直 接 运 用 信 号 量 来

9、 实 现(你 可 以 使 用 Io c k,虽 然 它 间 接 地 调 用 了 信 号 量)。在 你 完 毕 时 要 提 供 条 件 变 量 的 两 种 实 现 方 法。你 的 第 二 种 条 件 变 量 实 现 要 放 在 n ach o s.th r e ads.Conditio n 2 中。2.分 析 t hread s.L o c k类 提 供 了 锁 以 保 证 互 斥.在 临 界 代 码 区 的 两 端 执 行 Loc k.ac q u i r e()和 L。c k.relea s e()即 可 保 证 同 时 只 有 一 个 线 程 访 问 临 界 代 码 区.条 件 变 量 建

10、 立 在 锁 之 上，由 th re a d s.C o n d i t io n实 现，它 是 用 来 保 证 同 步 的 工 具.每 一 个 条 件 变 量 拥 有 一 个 锁 变 量(该 锁 变 量 亦 可 被 执 行 a cq u ire和 r e le a s e 操 作，多 个 条 件 变 量 可 共 享 同 一 个 锁 变 量）.当 处 在 临 界 区 内 的 拥 有 某 锁 L的 当 前 线 程 对 与 锁 L联 系 的 条 件 变 量 执 行 sleep操 作 时，该 线 程 失 去 锁 L 并 被 挂 起.下 一 个 等 待 锁 L 的 线 程 获 得 锁 L（这 个 过

11、程 由 调 度 程 序 完 毕）并 进 入 临 界 区.当 拥 有 锁 L 的 临 界 区 内 的 当 前 线 程 对 与 锁 L联 系 的 条 件 变 量 执 行 w a k e 操 作 时（通 常 调 用 w ake之 后 紧 接 着 就 是 Loc k.r e 1 e a s e）,等 待 在 该 条 件 变 量 上 的 之 多 一 个 被 挂 起 的 线 程（由 调 用 s le e p引 起）被 重 新 唤 醒 并 设 立 为 就 绪 状 态.若 执 行 w a k e a ll操 作，则 等 待 在 该 条 件 变 量 上 的 所 有 被 挂 起 的 线 程 都 被 唤 醒.3.方

12、 案 cond i tion.sle e p 采 用 waiter.P（）实 现 休 眠（wai t or 是 一 个 信 号 量）并 将 w aitor放 入 信 号 量 队 列，在 我 们 的 实 现 中 改 成 用 KTh read.sle ep（）实 现 休 眠 并 将 当 前 线 程 放 入 线 程 队 列，并 在 slee p函 数 开 始/结 尾 处 屏 蔽/允 许 中 断 以 保 证 原 子 性。cond i t i o n.w a k e 中 从 等 待 信 号 量 队 列 中 取 出 信 号 量 并 对 其 进 行 V 操 作 实 现 唤 醒,在 我 们 的 实 现 中 改

13、 成 从 线 程 队 列 中 取 出 线 程 用 KThread.r eady（）实 现 唤 醒（同 样 要 在 w a k e函 数 开 始/结 尾 处 屏 蔽;允 许 中 断）。w akeall函 数 的 实 现 依 赖 于 w a k e（）.只 需 不 断 地 w a k e直 到 队 列 为 空 为 止.4.实 现 代 码 p rivate T h readQueu e wai t Queue=Thre a dedK e mel.s c he d u 1 e r.newTh r e a d Queu e（false）;p r ivat e bool ean hasW a i te r

14、=fal s e;pub 1 ic v oid slee p()Lib.assertT r u e(cond i t i on Lock.isHeld B y C u r ren t Thread();boolean i nt Status=M a c hine.in t e r ru p t().dis a ble();w a itQu e u e.wa i tForAc c ess(KThrea d.c u rre n t T h re a d();hasWa i t e r=tru e;c ond i t i o n L o c k.rele a se()；K T h re a d.s

15、ie e p();c onditi o nLock.a c quire();Machin e.interrup t().r es t ore(intStat u s);)pu blic v o i d wa k e()(L i b.a s s e r tT ru e(co n d itionLock.isHeldByCurrentThread();0boole a n intSt a tu s=Machin e.i nter r u pt().disableQ;KTh read thread waitQu e u e.nextThrea d();i f(thread!=n u II)threa

16、d,r ea d y();e 1 seh a sWaite r=fal s e;0Ma c hine.i nterru p t().resto r e(i n t Stat u s);)publ i c void wa k e A II()(L i b.assertT rue(condition L ock.isHe 1 dByC u rrentThre a d();wh i 1 e(h asWaiter)w ake();)T askl.3 实 现 wai t Until1.规 定 通 过 实 现 wa i t U n t i l(i n t x)方 法 来 完 毕 Ala r m 类。2.分

17、 析 一 个 线 程 通 过 调 用 wai t U n til函 数 来 挂 起 它 自 己 直 到 n ow+x 后 才 被 唤 醒。在 实 时 操 作 中，对 线 程 是 非 常 有 用 的，例 如 实 现 光 标 每 秒 的 闪 烁。这 里 并 不规 定 线 程 被 唤 醒 后 立 即 执 行 它,只 是 在 它 等 待 了 指 定 期 间 后 将 它。放 入 等 待 队 列 中。不 要 通 过 产 生 任 何 附 加 的 线 程 来 实 现 wai t U n ti 1 函 数,你 仅 需 要 修 改 w aitU ntil函 数 和 时 间 中 断 解 决 程 序。w a it U

18、 n til函 数 并 不 仅 限 于 一 个 线 程 使 用 在 任 意 时 间，任 意 多 的 线 程 可 以 调 用 它 来 阻 塞 自 己。3.方 案 于 Al a r m 类 有 关 的 是 machi n e.Tim e r 类.它 在 大 约 每 500个 时 钟 滴 答 使 调 用 回 调 函 数(由 T i m e r.s e tl nterruptHand 1 e r 函 数 设 立).因 此 A 1 arm类 的 构 造 函 数 中 一 方 面 要 设 立 该 回 调 函 数 Ala r m.timerl n t errup t().为 了 实 现 w a i tUnti

19、 1,需 要 在 Al a r m类 中 实 现 一 个 内 部 类 W a ite r,保 存 等 待 的 线 程 及 其 唤 醒 时 间.在 调 用 w a itU n til(x)函 数 时，一 方 面 得 到 关 于 该 线 程 的 信 息：(线 程：当 前 线 程，唤 醒 时 间：当 前 时 间+x),然 后 构 造 新 的 Waite r 对 象，并 调 用 s le e p操 作 使 当 前 线 程 挂 起.在 时 钟 回 调 函 数 中(大 约 每 5 0 0 个 时 钟 间 隔 调 用 一 次)则 依 次 检 查 队 列 中 的 每 个 对 象。假 如 唤 醒 时 间 大 于

20、 当 前 时 间，则 将 该 对 象 移 出 队 列 并 执 行 wa k e操 作 将 相 应 线 程 唤 醒。4.实 现 代 码 class Wa i ter(Wai t er(1 ong wa k eTime,KThrea d threa d)(0 t h i s.wak e Tim e=wa k eT i me;0 t h i s.t hread=thread;)p r i v a te 1 ong wa k eTime;private KTh r ea d th r ead;)pub 1 i c void waitUntil(long x)(boole a n intSta t us

21、=Mach i ne.i n ter r u p t().d i sable();A o ng wake T i me=Ma c h i ne.time r().g etTime()+x;Waiter w a it e r=new W aite r(wake T ime,KThr e ad.c u r r e n t Thread();ow a itli s t.a dd(w a it e r);System.out.p r in 11 n(KTh r ead.cu r re n t Th read().g e tN a m e()。+线 程 休 眠,时 间 为 厂+Machine.timer

22、O.ge t Time()+，应 当 在。+wakeT i me+醒 来.)；oKThread.s 1 ee p();M a chine.inte r r u p t().r e sto r e(in t Sta tus);)p u b li c vo i d t imerlnterru p t()Wa i ter wai t e r;fo r(in t i=0;iwaitlist.size();i+)wa i ter=wai 11 i s t.remov e();if(wa i t e r.wakeTime=Ma c hi n e.timer().g e t Tim e()(System.o

23、ut.pri n tln(唤 醒 线 程:+w a iter.th r e a d.g etN am e()+,时 间 为:+M a c h i ne.timer().g etTimeO);。w a ite r.t h r ead.r ead y();/线 程 进 入 就 绪 状 态)e Isewai t lis t.ad d(waiter);)KThread.c u rrentTh r ead().y i eld();)p ri v ate Li n k edList waitl i st;Ta s k l.4 用 条 件 变 量，不 使 用 信 号 量，实 现 同 步 发 送 接 受 消

24、息，s pea k,I i sten1.规 定使 用 条 件 变 量 来 实 现 一 个 字 长 信 息 的 发 送 和 接 受 同 步。使 用 v。i d s p e ak(i nt word)和 i nt liste n()函 数 来 实 现 通 讯(Commun i c a to r)类 的 通 讯 操 作。speak函 数 具 有 原 子 性，在 相 同 地 C ommunica t or类 中 档 待 listen函 数 被 调 用，然 后 将 此 字 发 生 给 listen函 数。一 旦 传 送 完 毕，两 个 函 数 都 返 回(1isten函 数 返 回 此 字“2.分 析

25、对 一 个 Commun i ca t o r类 的 对 象 c,线 程 A 先 调 用 c.spea ker(x)发 送 一 个 字 后 被 挂 起，直 到 另 一 线 程 B调 用 c.listen()收 到 这 个 字 x后，A和 B同 时 返 回.类 似 地，线 程 B先 调 用 c.1 i st e n(x)后 被 挂 起，直 到 另 一 线 程 B调 用 c.s p e a k e r(x)发 送 一 个 字 后，A 和 B同 时 返 回.同 时 需 要 注 旨 在 一 个 C。mm u nica t o r上 有 多 个 s pak e r和 lis t ener的 情 形.此

26、时 的 spea ke r和 1 is t ene r只 能 是 一 对 一 的，即 一 个 sp eaker只 能 将 数 据 发 送 到 一 个 Ii s t ene r,一 个 listen e r 也 只 能 接 受 来 自 一 个 s pekaer的 数 据，其 余 的 speakers和 liste n e r s都 需 要 等 待.3.方 案 每 个 C o m m u n icato r有 一 个 锁(保 证 操 作 的 原 子 性)和 与 该 锁 联 系 的 两 个 条 件 变 量 用 于 保 证 spea k e r和 I i s t en e r 间 的 同 步.在 sp

27、e a k 函 数 中,一 方 面 检 查 若 已 有 一 个 s pea k er在 等 待(s peaknum 0)或 无 lis ten e r等 待，则 挂 起.否 则 设 立 变 量，准 备 数 据 并 唤 醒 一 个 listener.在 listen函 数 中,增 长 一 个 listen e r后，一 方 面 唤 醒 s p eak e r,然 后 将 自 己 挂 起 以 等 待 s peake r 准 备 好 数 据 再 将 自 己 唤 醒.这 个 问 题 其 实 是 一 个 缓 冲 区 长 度 为 0 的 生 产 者/消 费 者 问 题.4.实 现 代 码 p u b li

28、e Comm u n i cator()loc k=n e w Lock();co n=new Condition(lo c k);)publi c v o i d spea k(int word)(l o c k.acquire();if(spe a k n u m 0 1|1 isten num=0)(spea k num+;con.s leep();)if(1 iste nnum 0)(o c on.wakeAl 1();i sten nu m=0;)this.w ord=w o r d;Sys t em.o u t.pri n 1 1 n(KT h read.curren t T h

29、r ead().g e tN a16()+编 呈 说+1:%5.。r d);1 o c k.re 1 ease();)p u b 1 i c i n t li s ten()(lock.acquireO;while(listennum0|sp eaknum=0)(Jis t en n um+;ocon.sleep();l i s t e n num-;)if(speaknum 0)(o c o n.wake();spea k n u m-;KTh r ead.c urrentTh r ea d().y i e ld();Sy s tem.o ut.pri ntln(KTh r ea d.cu

30、r rentTh r ead().g etN am e()+线 程 听 到+th is.w。r d);1 i s t e nnum=0;1 ock.re 1 e ase()；retu r n this.word;)p rivat e Lock loc k;private Cond it i o n con;private int word;pr i vat e static int speaknum;p r i vate s tati c int I i sten n um;T a s k l.5完 毕 P r io r i t y Scheduler实 现 优 先 级 调 度 1.规 定 通

31、 过 完 毕 P r io r itySche d u 1 e r类 在 Nacho s 中 实 现 优 先 级 调 度(pr i ori ty sched u ling)o优 先 级 调 度 是 实 时 系 统 中 的 关 键 构 建 模 块。2.分 析 在 N a c h o s中，所 有 的 调 度 程 序 都 继 承 抽 象 类 S c heduler.系 统 已 经 提 供 了 一 个 简 朴 的 轮 转 调 度 器 Round R o b in S c h e d u le r,它 对 所 有 线 程 不 区 分 优 先 级 而 采 用 简 朴 的 F IF O 队 列 进 行 调

32、 度.我 们 实 现 的 优 先 级 调 度 类 PrioritySched u 1 e r也 继 承 自 S c heduler.优 先 级 调 度 的 传 统 算 法 如 下：每 个 线 程 拥 有 一 个 优 先 级(在 Nach。s 中，优 先 级 是 一 个 0 到 7 之 间 的 整 数，默 认 为 1).在 线 程 调 度 时，调 度 程 序 选 择 一 个 拥 有 最 高 优 先 级 的 处 在 就 绪 状 态 的 线 程 运 营.这 种 算 法 的 问 题 是 也 许 出 现 饥 饿 现 象：设 想 有 一 个 低 优 先 级 的 线 程 处 在 临 界 区 中 运 营 而

33、高 优 先 级 的 线 程 在 临 界 区 外 等 待.由 于 前 者 优 先 级 较 低，它 也 许 不 会 被 调 度 器 选 中 从 而 高 优 先 级 的 线 程 也 不 得 不 浪 费 时 间 等 待.为 解 决 上 述 优 先 级 反 转 问 题，需 要 实 现 一 种 让 出 优 先 级 的 机 制(Priority D o n a t io n):提 高 拥 有 锁 的 低 优 先 级 线 程 的 优 先 级 以 使 它 迅 速 完 毕 临 界 区，不 使 其 它 较 高 优 先 级 的 线 程 等 待 太 久.提 高 后 的 优 先 级 称 为 有 效 优 先 级，它 可 以

34、 不 断 变 化.实 际 调 度 时 就 是 以 有 效 优 先 级 为 评 判 标 准 的.3.方 案 在 Thr e a d S tate类 中 增 长 两 个 表 即 Li n kedLi s t类，存 放 的 对 象 是 Pr i orityQu e ue,即 优 先 级 队 列 对 象。一 个 表 用 来 记 录 该 线 程 所 占 用 资 源 的 优 先 队 列 r eso u r cesIHave,另 一 个 表 用 来 记 录 该 线 程 所 想 占 有 的 资 源 的 优 先 队 列 resou r ceIWanto resour c e s I H a v e 作 为 发

35、生 优 先 级 反 转 时，捐 献 优 先 级 计 算 有 效 优 先 级 的 来 源 依 据,res。u r c e lW a n t用 来 为 线 程 声 明 得 到 资 源 做 准 备。wai t ForAccess()将 需 要 等 待 获 得 资 源 的 线 程 加 入 一 个 等 待 队 列 等 待 调 度。g e tEffectiveP r iority()计 算 有 效 优 先 级 时，遍 历 等 待 队 列 中 所 用 线 程 的 有 效 优 先 级，找 出 最 大 的 优 先 级 即 可。4.实 现 代 码 p u bli c v oid w a i t ForA c ce

36、 s s(Pri o ri t yQueu e w a i tQueue)wa i tQue u e.waitQue u e.ad d(thi s.threa d);if(iwaitQueu e.t r ansf e r P riority)waitQ u e u e.l o ckHol d er.e f f ectiveP r io r i ty=e xpiredEff ect i vePrio r i ty;)publi c v o i d acq u i r e(Prio r i tyQueu e waitQ ueu e)(waitQueue.waitQue u e.r emov e(t

37、 his.t h read);wai t Queu e.Io c kH o 1 der=th is;w a i t Queue.loc k H o ld e r.effec t ivePriority=exp i re d E ff ectiveP r iori t y;w a i tQu eu e.1 oc k Holder.wa iters=wa i t Queu e;)pu b 1 ic in t g et E f f e ct i vePr i o r i t y()(if(ef f ecti v ePri o r ity!=expiredEffectivePriority)。retu

38、rn effe c tivePrio r i t y;00e f feet i v e P ri o r ity=p riority;if(wa i te r s=null)r e t u r n eff e c tivePrio r ity;fo r(It e rato r i=waiters.wa i tQ u eue.ite r a t o r();i.h as N ext();)(Threa d S t ate ts=g e tThre a dState(KT h re a d)i.next();i f(ts.pr i o r i t y e f f e c t i v e Prior

39、 i t y)(effec t i veP r ior i t y=t s.pr i ority;)return ef f ect i v e Prio r ity;)protec t e d i n t e f f e c t i vePriority=e xpir ed E f f ect i veP r io r i ty；p r otecte d st a tic f i na 1 int e x piredE f f ec t iv e P rior i t y=-protected P riori t yQ u eue wait e r s=null;publ i c KThre

40、a d n extT h re a d()L i b.a s sertT ru e(Ma c hine.in t er r upt().disabled();o i f(pi c kNextTh r ea d()=n u II)。return n u l l;KThread t h r e a d=p i ckNextTh r ead().th re a d;getThreads t ate(thre a d).acqui r e(this);re t urn t hread;)pro t ec t ed Threads t ate pickNextThrea d()(i f(wai t Qu

41、eue.i s Empt y()return n ull;0T h r ead Sta t e to P ick=g etThread S t a t e(KTh re a d)wai t Queue.getF i rst();fo r(I te r ato r i=wa i tQueue.iter a to r()；i-hasN e xt();)Th read S ta t e t s=g etTh read State(K T h re a d)i.next()；if(ts.g e t Eff e cti v e P ri o ri t y()to P ick.ge t E f fecti

42、vePr i orityO)toP i ck=ts;)r etu r n t oPic k;L inke d L i s t wa i t Q u e u e=new LinkedL i st();Threadstate lockHo 1 de r=null;T as k l.61.规 定 用 以 上 实 现 的 线 程 互 斥/同 步 机 制 解 决 一 个 过 河 问 题。成 人 和 小 孩 都 试 图 从。a h u 出 发 到 moloka i。一 只 船 只 可 以 携 带 最 多 两 个 小 孩 或 一 个 成 人（但 不 能 是 一 个 小 孩 和 一 个 成 人）。船 上 可

43、划 回 瓦 胡 岛，但 这 么 做 需 要 一 个 引 航 员。安 排 一 个 能 让 所 有 人 到 m。1 o ka i岛 的 解 决 方 案2.分 析 需 要 记 录 的 信 息：1）。岛 上 大 人/小 孩 的 人 数 2）M岛 上 大 人/小 孩 的 人 数 3）船 的 位 置（在 0 岛 还 是 M岛）4）船 的 状 态（空/半 满/全 满）（半 满 指 只 有 一 个 小 孩，全 满 指 有 两 个 小 孩 或 一 个 大 人）初 始 状 态：1）大 人 和 小 孩 都 在。岛 上 2）船 在。岛 3）船 为 空 对 于 大 人 比 较 简 朴.若 满 足 以 下 条 件 则 独

44、 自 乘 船 过 河（每 个 大 人 过 且 仅 过 一 次 河，线 程 即 告 结 束），否 则（在。岛）等 待：1）。岛 上 只 有 一 个 小 孩 或 没 有 小 孩 2）船 在。岛 3）船 为 空 对 于 小 孩，分 以 下 5种 情 况 讨 论 1）某 小 孩 在 0 岛，船 在。岛，船 为 空，0 岛 上 的 小 孩 数 大 于 等 于 2:该 小 孩 上 船 等 此 外 一 个 小 孩 上 船 后，两 人 一 起 划 船 过 河 到 M2）某 小 孩 在。岛，船 在 0 岛，船 为 空，0 岛 上 没 有 大 人：该 小 孩 上 船 过 河 3）某 小 孩 在。岛，且 不 属 于

45、 以 上 三 种 情 况：等 待4）某 小 孩 在 M岛，船 在。岛：等 待 5）当 所 有 的 大 人 运 完 了 之 后 开 始 运 大 人，当 运 过 去 两 个 大 人 后，。岛 出 现 了 两 个 孩 子，这 个 时 候 这 两 个 孩 子 划 船 过 河，即 使 此 时 大 人 还 没 有 完 全 被 运 送 完 全。返 程:只 有 小 孩 可 以 有 返 程 路 线，大 人 返 程 没 故 意 义。3.方 案 使 用 三 个 锁 变 量 保 证 互 斥，三 个 条 件 变 量 保 证 同 步。4.实 现 代 码 pa c ka ge n a chos.t hreads;impo

46、r t nach o s.ag.BoatG r ader;pu b 1 ic class Boat（s t ati c BoatGrade r bg;s t atic i nt ch i IdrenOnOa h u=0;s t a t ic i nt c hild r enOnM olokai=0;st a tic in ta d u l tO n O a h u=0;s t atic i nt a dul t OnM oIoka i=0;s ta t ic i nt p i 1 ot=0;static boolean over;stati c Lock 1 oc k 1;s t a tic

47、Cond i t io n childre nWaitOnOahu;static Loc k I o c k2;s ta t i c Con d i t i on a dul t Wa i tOn Oa h u;static Lock lo c k 3;st a tic Conditi o n childrenReadyOnMolok a i;public s t a tic void begin(in t a d ults,int chi 1 d r en,BoatGrader b)(0bg=b;Joe k 1=new L o c k();。c h ild r e n Wa i tOnO a

48、 hu=new Condition(loc k 1);lock 2=new Lock();o a d u 1 tWa i tOnO a hu=new C o n d it io n(1 ock2);Jo c k3=n e w Lo c k();children ReadyOn Molo k a i=new Condition(lock3);。f o r(i nt i=0;iadult s;i+)(onew KTh r ead(n e wAdult(childrenWaitOnOa hu,adu 1 tWaitOnO a h u,children Rea dyOnMolo k a i).se t

49、 Nam e(ad u It).for k();oo4or(i nt i=0;i c h ild re n-l;i+)new KThread(new Child(c hil d renWaitOnOa h u,adultW a i t OnOahu,c hildrenRead y OnMolok a i).se tName(child).fo r k();)KThre a d t=new KThread(new Ch i Id(ch i Id renWa itOnOaadultWai t OnO a h u,chi 1 dre n Rea d yOnMolokai);t.s etName(c

50、hi 1 d);吐.f o r k();KTh read.currentT hread().y i eld();lock 1.acq u i r e();chi 1 drenW aitOnOa hu.wake();lo c k l.re lea s e();t-j o i n();)s t ati c void Ad u 1 tit i neraryOb g.i n i tial i zeAd ult();adul t OnOahu+;Jock2.acq u ire()；o a d ultWaitO n O a hu.sle e p();“b g.Ad u ItR ow To M olokai