程序辅导案例 > Program >

代写辅导接单-CS3331

欢迎使用51辅导，51作业君孵化低价透明的学长辅导平台，服务保持优质，平均费用压低50%以上！ 51fudao.top

Programming Assignment IV

CS3331

Summer 2025

1 River Crossing

A river running east-west separates a barren wasteland in the south, and luscious fields and forests in the

north. Both sheep and wolves want to go to the north to graze and hunt (respectively). However, to do this

they must share a river crossing. A single boat is used to cross the river, but it only seats three passengers,

and must always carry a full load. To guarantee the safety of the sheep, you cannot put one sheep and two

wolves in the boat at the same time (because the wolves would gang up and eat the sheep), but all other

combinations are acceptable. An evil wizard owns the land north of the river, and does not take too kindly

to the illegal grazing of the sheep, nor the wolves’ poaching, and so he will eventually magically teleport

each sheep and wolf back to the south side of the river (where they will go to board the boat again).

2 Requirements

You will simulate this system using ThreadMentor. Wolves, sheep, and the boat will be modeled as a thread.

You are to write aHoare-type monitor to implement the boat policy.

Each wolf is a thread with the following pattern:

while( 1 ){

p r i n t ( ” Wolf i t e l e p o r t s s o u t h ” ) ;// Placeholder s t r i n g

Delay ( ) ;// Take a r e s t .

W o l f A r r i v e s ( . . . ) ;// Register to cross the r i v e r .

p r i n t ( ” Wolf i h u n t s i n t h e n o r t h ” ) ;// Placeholder s t r i n g

Delay ( ) ;

}

The following shows a similar sheep thread:

while( 1 ){

p r i n t ( ” Sheep i t e l e p o r t s s o u t h ” ) ;// Placeholder s t r i n g

Delay ( ) ;// Take a r e s t

S h e e p A r r i v e s ( . . . ) ;// Register to cross the r i v e r .

p r i n t ( ” Sheep i g r a z e s i n t h e n o r t h ” ) ;// Placeholder s t r i n g

Delay ( ) ;

}

Both wolf and sheep threads are to run an infinite loop. When a wolf arrives at the south bank, it must

sheep thread, on the other hand, will call S h e e p A r r i v e s ( ) . The caller will be blocked in the monitor until

the monitor can find a safe boat load.

The boat is also simulated by a thread and has the following pattern:

while( 1 ){

Delay ( ) ;// take a r e s t

BoatReady ( . . . ) ;// ready for the next round

Delay ( ) ;// row the boat

BoatDone ( . . . ) ;// a l l passengers are on the other side

// come back for another r i v e r crossing

}

The boat calls the monitor procedure BoatReady ( ) when it is ready (i.e., empty) for the next boat load.

It may be blocked in the monitor until a safe boat load is possible. At that time, the boat is released from

the monitor with the passenger names, and starts rowing. The thread will use Delay ( ) to simulate the

time spent crossing the river. Then, the boat calls monitor procedure BoatDone ( ) to indicate one boat

load is completed, and comes back for another boat load. The call to BoatDone ( ) may or may not block

the boat, depending on your implementation. You should, however, be aware of the fact that all passengers

must be off the boat before the boat can be used again.

Your monitor will maintain all necessary information to guarantee a safe boat load. When a safe boat load

is possible, your monitor tells the boat to send the selected three passengers (i.e., three wolves, three sheep,

or two sheep and one wolf) to cross the river. After a boat load completes, each of these three passengers

returns to their respect thread function, does something, and comes back (via the machinations of the evil

wizard) for another river crossing. Thus, all river crossings are in the same direction (south to north).

Note that if a safe crossing is possible with the current pool of waiting passengers, a crossing must be made.

The boat cannot be delayed for a specific passenger grouping if a different passenger grouping is currently

possible. For example, if the pool of waiting passengers is one sheep and three wolves, the boat cannot

wait for another sheep to arrive to form a two sheep and one wolf boat. It is almost always possible to

immediately form a boat load when you have enough passenger threads running, but be sure to test with a

smaller numbers of passenger threads.

The boat should not be biased towards any load type. It should choose randomly which of the valid boat

types it will form. For example, if 1 wolf and 3 sheep are waiting the boat will randomly form either a

1-wolf-2-sheep boat or a 3-sheep boat (but not a 3 wolf boat). The monitor should not, for example, always

choose to do a wolf-only boat if that is possible.

It is very important that no one can jump off the boat before the boat reaches the other side and request to

cross the river again, and that no one can jump on the boat before getting the permission to do so from the

monitor. Additionally, no one can cross the river without being on the boat.

Progress should be guaranteed by your solution. However, you neednotguarantee bounded waiting.

After some number of boat loads have been made, your monitor should display the following message and

exit the system:

***** nnn crosses have been made.

***** This river cross is closed indefinitely for renovation.

wherennnis a positive integer taken from the command line and passed to the monitor in the initialization

stage. Note that a boat load completes only once the passengers have been deboarded. After displaying this

message, the system terminates.

3 Other Requirements

Write a C++ program using ThreadMentor to simulate these activities. Further,you may only use a

monitor with condition variables to implement synchronization. The use of any other synchroniza-

tion primitives (such as semaphores) may result in a grade of zero or a significant point penalty. Youmay

however use a single mutex lock to protect any print statements (as an alternative to sprintf + write). This

lock may not be used to synchronize anything else.

3.1 Input

The input of your program consists of the following: The number of wolvesw, the number of sheeps, and

the number of safe boat loadsb. These should be taken as command line arguments like so:

./prog4 w s b

Thus,./prog4 15 8 10means there are 15 wolves and 8 sheep, and after 10 safe boat loads the program

terminates. All command line arguments are always non-negative integers≤30. You may assume all

supplied values are within this range, and formatted correctly.

3.2 Output

Your program should generate an output similar to the following (.....indicates other print statements

may occur here, and are not required output in your program. There are other notes in here that should

not be printed.):

Sheep 1 teleports south.

Sheep 2 teleports south.

Sheep 3 teleports south.

Sheep 4 teleports south.

Sheep 2 waits on the south bank.

Sheep 5 teleports south.

Sheep 6 teleports south.

Sheep 7 teleports south.

Wolf 1 teleports south.

Sheep 8 teleports south.

Wolf 2 teleports south.

.....

Wolf 13 waits on the south bank.

Wolf 12 teleports south.

Wolf 14 teleports south.

Wolf 8 waits on the south bank.

***** BOAT thread starts

***** The boat is ready to take new passengers.

SPEC NOTE: If a valid boat load is not immediately possible, there may be other prints between these!

***** The boat starts boarding three sheep.

Wolf 6 teleports south.

Sheep 2 boards.

Wolf 9 waits on the south bank.

Sheep 7 waits on the south bank.

Sheep 7 boards.

Sheep 4 waits on the south bank.

Sheep 4 boards.

Wolf 3 waits on the south bank.

.....

Wolf 14 waits on the south bank.

Wolf 6 waits on the south bank.

***** Boat load (1): Passenger list (s2, s7, s4) sets off.

***** Boat load (1): Arrives at the north bank, deboarding...

Sheep 2 deboards.

Sheep 2 is grazing in the north.

Sheep 7 deboards.

Sheep 7 is grazing in the north.

Sheep 4 deboards.

Sheep 4 is grazing in the north.

***** Boat load (1): All passengers unloaded, returning to south bank.

Sheep 7 teleports south.

Sheep 2 teleports south.

Sheep 4 teleports south.

***** The boat is ready to take new passengers.

***** The boat starts boarding three sheep.

Sheep 5 boards.

.....

***** Boat load (2): All passengers unloaded, returning to south bank.

Sheep 5 teleports south.

***** The boat is ready to take new passengers.

***** The boat starts boarding one wolf and two sheep.

Sheep 3 teleports south.

Sheep 1 boards.

Sheep 6 boards.

Sheep 4 waits on the south bank.

Wolf 2 boards.

***** Boat load (3): Passenger list (w2, s1, s6) sets off.

Sheep 5 waits on the south bank.

Sheep 3 waits on the south bank.

***** Boat load (3): Arrives at the north bank, deboarding...

Sheep 1 deboards.

Sheep 1 is grazing in the north.

.....

Sheep 1 waits on the south bank.

***** The boat is ready to take new passengers.

***** The boat starts boarding three wolves.

Wolf 1 boards.

Wolf 13 boards.

Wolf 8 boards.

***** Boat load (4): Passenger list (w1, w13, w8) sets off.

***** Boat load (4): Arrives at the north bank, deboarding...

Wolf 1 deboards.

Wolf 1 is hunting in the north.

Wolf 13 deboards.

Wolf 13 is hunting in the north.

Wolf 8 deboards.

Wolf 8 is hunting in the north.

Wolf 13 teleports south.

***** Boat load (4): All passengers unloaded, returning to south bank.

Wolf 13 waits on the south bank.

Wolf 1 teleports south.

Wolf 1 waits on the south bank.

***** The boat is ready to take new passengers.

Wolf 8 teleports south.

***** The boat starts boarding three sheep.

.....

Sheep 2 deboards.

Sheep 2 is grazing in the north.

***** Boat load (5): All passengers unloaded, returning to south bank.

Sheep 8 teleports south.

Sheep 8 waits on the south bank.

Sheep 2 teleports south.

Sheep 7 teleports south.

.....

Sheep 7 boards.

Wolf 10 boards.

Sheep 1 waits on the south bank.

***** Boat load (10): Passenger list (w10, s4, s7) sets off.

***** Boat load (10): Arrives at the north bank, deboarding...

Sheep 4 deboards.

Sheep 4 is grazing in the north.

Sheep 7 deboards.

Sheep 7 is grazing in the north.

Wolf 10 deboards.

Wolf 10 is hunting in the north.

Sheep 2 waits on the south bank.

***** Boat load (10): All passengers unloaded, returning to south bank.

***** 10 crosses have been made.

***** This river cross is closed indefinitely for renovation.

•In the above, the boat’s output always starts on column 1. The output lines from wolfiand sheepi

start on columni.

•All messages from the boat thread start with the string “*****”.

•The “w” and “s” in the passenger list represent wolves and sheep, respectively, followed by their number.

•Due to the dynamic behavior of multithreaded programs, you will not be able to generate an output

that is identical to the above.

The wolves/sheep print the following messages:

•Sheep i teleports south.

Wolf i teleports south.

This is printed by the thread when it is teleported by the evil wizard to the horrible south bank. This

can happen when a thread starts.

•Sheep i waits on the south bank.

Wolf i waits on the south bank.

This is printed by the thread when it is ready to head to the north bank and has begun to wait to be

boarded by the boat.

•Sheep i boards.

Wolf i boards.

This is printed by the thread when the monitor has decided to let a passenger board and cross the

river.

•Sheep i deboards.

Wolf i deboards.

This is printed by the thread when the boat has reached the north shore and the thread leaves the

boat.

•Sheep i is grazing in the north.

Wolf i is hunting in the north.

This is printed by the thread when they’re enjoying their time in the north.

The boat will print the following messages

•***** BOAT thread starts

This is printed by the boat at the start of the program.

•***** The boat is ready to take new passengers.

This is printed by the boat when it arrives at the south shore.

•***** The boat starts boarding three sheep.

***** The boat starts boarding three wolves.

***** The boat starts boarding one wolf and two sheep.

This is printed by the boat when it has found a valid boat load it would like to start boarding.

•***** Boat load (n): Passenger list (ti, ti, ti) sets off.

This is printed when all three passengers have boarded and the boat leaves the south for the north.

tshould be replaced with eitherwors(depending on the thread of the passenger), and similarlyi

should be replaced with the associated thread’s id.nshould be replaced with the number load this is.

•***** Boat load (n): Arrives at the north bank, deboarding...

This, of course, is printed when the boat reaches the north bank and can unload its passengers.n

should be replaced with the number load this is.

•***** Boat load (n): All passengers unloaded, returning to south bank.

This is printed when all the passengers have disembarked on the north bank.nshould be replaced

with the number load this is.

•***** n crosses have been made.

***** This river cross is closed indefinitely for renovation.

These lines should be printed after the passengers on the final boat load have deboarded.nshould be

replaced with the number of the final load. The system should exit after this message has been printed

(but it doesn’t need to be the final message of the system).

4 Specification

Your submission must satisfy the following formal requirements:

1. The boat will never contain an unsafe boat load (i.e., 2 wolves + 1 sheep).

2. The boat will only every depart the south bank with exactly 3 passengers.

3. Passengers are only able to board while they are at the south bank.

4. Passengers are only able to board the boat while it is docked.

5. Passengers cannot leave the boat until it has reached the north bank.

6. The boat cannot leave the north bank until all passengers have deboarded.

7. Passengers cannot wait on the south bank while they are in the north.

8. The boat cannot pick up new passengers without dropping off the previous ones.

9. If a valid boat load is possible, the boat should start to form a valid boat load.

10. The boat does not bias towards one type of boat load.

11. The boat only completesbtrips.

5 Submission Guidelines

The following sections elaborate submission requirements not directly related to the semantics of the program

itself.

5.1 General Rules

1. The program must be written in C++, programs written in other languages will receive a 0.

2. The program must use ThreadMentor, programs that make use of non-ThreadMentor concurrency/syn-

chronization libraries will receive a 0.

3. Your work must be submitted as a.zipfile via canvas. This.zipwill contain your source code, your

Makefile, and yourREADME.

4. YourMakefileshould produce an executable file namedprog4, and should compile with the non-visual

ThreadMentor library when passed the noVisual target.

5. We will use the following approach to compile and test your programs:

make clean

make noVisual # make your program

./prog4 w s b # test your program

wherew,s, andbare placeholder values. This procedure may be repeated a number of times with

different input to see whether your program works correctly.

6. As always, you should test your program’s output when performingstdoutredirection as well.

7. Your program is only allocated 5 seconds to execute. If your program takes longer than this to complete,

it is assumed to be in a deadlocked / non-terminating state, thus you will lose points.

8. Your implementation should fulfill the program specification as stated. Major deviations from the

specification may cause you to receive zero points.

5.2 Program Style and Documentation

•At the top of each.cppfile, the first comment should be a program header to identify yourself like so:

// -----------------------------------------------------------

// NAME : John Smith User ID: xxxxxxxx

// DUE DATE : mm/dd/yyyy

// PROGRAM ASSIGNMENT #n

// FILE NAME : xxxx.yyy

// PROGRAM PURPOSE :

// A couple of lines describing your program briefly

// -----------------------------------------------------------

Here, User ID is the one you use to log in to MTU systems.

•Your programs must contain a reasonable amount of concise and to-the-point comments. Do not write

a novel.

•Your program should have reasonable indentation.

5.3 TheREADMEFile

A plaintext file namedREADME(or a pdf namedREADME.pdf) is required to answer the following questions:

How does your program satisfy the specifications listed in section??? Give an explanation/argument as to

how your implementation satisfies each. While it is not expected that you give a formal proof, an argument

like “This situation will not occur because I use a condition variable.” will not be considered convincing.