操作系统课程设计实验报告proj1

和孩子创建一个线程，这个线程就相当于一个人，他们能自己判断（思考），什么时候可以过河，而不是通过调度程序的调度。在解决问题的过程中不能出现忙等待，而且问题最终一定要解决。不符合逻辑的事情不能发生，比如在这个岛的人能知道对面岛的情况。

2.6.2题目分析与实现方案

需要记录的信息有：

1. O岛上大人/小孩的人数和M岛上大人/小孩的人数

1)船的位置(在O岛还是M岛) 和状态(空/半满/全满) (半满指只有一

个 小孩, 全满指有两个小孩或一个大人)

2. 是否最后一次运输

3. 孩子、大人信息的条件变量，并且需要一个锁

运送过程大体如下：

1：所以我们可以尽可能多的先从O岛把孩子运过来（M岛到O岛需要一个child驾驶员，要避免出现当大人到M岛上而没有孩子在M岛上出现这种情况）

2：然后开始运输大人，并且让孩子把船开回O岛 3：重复1，2

4：最后将两个孩子运到M岛

对于大人，若满足以下条件则独自乘船过河(每个大人过且仅过一次河, 线程即告结束), 否则(在O岛)等待:

2)O岛上只有一个小孩或没有小孩

3)2)船在O岛

17

4)3)船为空

对于小孩, 满足以下情况则乘船过河：

1)初始条件，小孩全在O岛, 船在O岛，且M岛没有小孩。 2)某小孩在O岛, 船在O岛, 船为空, O岛上的小孩数大于等于2，则该小孩上船等另外一个小孩上船后,两人一起划船过河到M。

3)某小孩在O岛, 船在O岛, 船为空, O岛上没有大人: 该小孩上船过河

4)当所有的大人运完了之后，O岛出现了两个孩子，这个时候这两个孩子划船过河。

方案：使用一个锁变量保证互斥,四个条件变量保证同步。结构如下：程序首先创建大人线程和孩子线程——获取锁——唤醒一个孩子进程——释放锁。

ChildItinerary()思路： 先获得锁

conditionLock.acquire()并处于等待状态

childOnOahu.sleep()；

判断是否为最后一次运输若是最后一次，直接进行运输并结束。 若不是，则判断是否在Oahu。若在，O岛孩子数减一。判断是否有驾驶员，若有，直接进行运输ChildRideToMolokai()；若没有驾驶员，他将成为驾驶员并唤醒一个孩子线程。

若孩子在M岛，则将船开回O岛，O岛孩子数量改变。如果O岛孩子数为1则唤醒大人线程，准备运送大人，否则唤醒孩子线程，继续运送孩子。

18

AdultItinerary()思路：与ChildItinerary思想类似，但少了返回O岛这一步。大体为获得锁 conditionLock.acquire()并进入等待状态adultOnOahu.sleep()，直接去M岛然后唤醒M岛一个孩子。

2.6.3关键点与难点

难点在渡河过程分析。只有小孩可以有返程路线，大人返程没有意义；要避免出现当大人到M岛上而没有孩子在M岛上出现这种情况。开始之前让所有人sleep, 然后begin()叫醒一个child, 然后每次一个人干完了活叫醒另一个然后自己睡，所有人都是被动的，相比所有人都主动竞争当驾驶员或乘客，这样可以避免冲突。

2.6.4实现代码

public class Boat {

public static void selfTest(int i, int j) {

}

bg = b;

lock1 = new Lock();

childrenWaitOnOahu = new Condition(lock1); lock2 = new Lock();

adultWaitOnOahu = new Condition(lock2); lock3 = new Lock();

childrenReadyOnMolokai = new Condition(lock3); for (int i = 0; i < adults; i++) { }

for (int i = 0; i < children - 1; i++) {

19

BoatGrader b = new BoatGrader(); childrenOnOahuBG = j; childrenOnMolokaiBG = 0; adultOnOahuBG = i; adultOnMolokaiBG = 0;

System.out.println(j + \ + i + \); begin(i, j, b);

public static void begin(int adults, int children, BoatGrader b) {

new KThread(new Adult(childrenWaitOnOahu, adultWaitOnOahu,

childrenReadyOnMolokai)).setName(\).fork();

} }

}

new KThread(new Child(childrenWaitOnOahu, adultWaitOnOahu,

childrenReadyOnMolokai)).setName(\).fork();

KThread t = new KThread(new Child(childrenWaitOnOahu,

childrenReadyOnMolokai));

adultWaitOnOahu,

t.setName(\); t.fork();

KThread.currentThread().yield(); lock1.acquire();

childrenWaitOnOahu.wake(); lock1.release(); t.join();

static void AdultItinerary() {

bg.initializeAdult(); adultOnOahu++; lock2.acquire();

adultWaitOnOahu.sleep(); bg.AdultRowToMolokai(); adultOnOahu--; adultOnMolokai++; lock2.release(); lock3.acquire();

childrenReadyOnMolokai.wake(); lock3.release();

static void ChildItinerary() {

// 创建一个划船的孩子 bg.initializeChild(); childrenOnOahu++; lock1.acquire();

childrenWaitOnOahu.sleep(); lock1.release(); while (true) {

if (pilot != 1) {

if (childrenOnOahu > 1) // 有孩子 {

lock1.acquire();

childrenWaitOnOahu.wake(); pilot = 1;// 运孩子

bg.ChildRowToMolokai(); childrenOnOahu--;

20