Managing Events and Processes in Jurassic Park
undefined
P
r
o
j
e
c
t
3
–
J
u
r
a
s
s
i
c
P
a
r
k
CS 345
Lab 3 – Jurassic Park
D
e
l
t
a
C
l
o
c
k
Problem: How to efficiently monitor timed
events?
Examples of timed events:
scheduling
real-time sequencing
timers
timeouts
Lists require each event to be examined to
determined if time has expired.
2
CS 345
Lab 3 – Jurassic Park
D
C
I
m
p
l
e
m
e
n
t
a
t
i
o
n
Suppose:
Event1 occurs in 20 tics
Event2 occurs in 5 tics
Event3 occurs in 35 tics
Event4 occurs in 27 tics
Event 5 occurs in 27 tics
Event 6 occurs in 22 tics
Notice that Event1
occurs 15 tics
after Event2
And that Event6
occurs 2 tics after
Event1
What if Event7 occurs in 17 tics?
Event8 in 31 tics?
3
CS 345
Lab 3 – Jurassic Park
P
r
o
j
e
c
t
3
–
J
u
r
a
s
s
i
c
P
a
r
k
Contemporary operating systems are built around the
concept of processes or tasks. These tasks usually need
to share resources in a protected, prioritized, and
equitable manner.
Jurassic Park is a inter-process communication and
synchronization problem between multiple tasks.
Visitors, drivers, and cars are represented by concurrent
tasks while additional tasks display the park status and
check for any lost visitors.
A poorly implemented solution could lead to the inter-
process communication problems of starvation and
deadlock.
4
CS 345
Lab 3 – Jurassic Park
Visitors try to enter the Jurassic Park at random times. (Only
a set number of visitors may be in the park at any one time –
OSHA requirements!)
J
u
r
a
s
s
i
c
P
a
r
k
Upon being allowed in the
park, a visitor must get in
line to purchase a ticket.
A
f
t
e
r
s
u
c
c
e
s
s
f
u
l
l
y
o
b
t
a
i
n
i
n
g
a
t
i
c
k
e
t
f
r
o
m
a
d
r
i
v
e
r
,
t
h
e
v
i
s
i
t
o
r
g
e
t
s
i
n
t
h
e
m
u
s
e
u
m
l
i
n
e
a
n
d
v
i
s
i
t
s
t
h
e
m
u
s
e
u
m
.
(
A
l
i
m
i
t
e
d
n
u
m
b
e
r
o
f
v
i
s
i
t
o
r
s
a
r
e
a
l
l
o
w
e
d
i
n
t
h
e
m
u
s
e
u
m
a
s
w
e
l
l
a
s
t
h
e
g
i
f
t
s
h
o
p
.
)
After visiting the
museum, the visitor gets
in the tour car line to
wait until permitted to
board a tour car. (As a
visitor boards a tour car,
he returns his ticket.)
When the touring car is filled with visitors and a driver is
obtained, the car enters Jurassic Park and runs a
guided tour through the park.
When the tour car pulls
into the unloading station,
the visitors exit the tour
car. and the driver goes to
sleep awaiting new duties.
The tour car pulls forward
to be loaded again.
After visiting the gift shop,
the visitors exit the park.
After the visitors exit a tour car,
they get into the gift shop line until
they can visit the gift shop.
5
CS 345
Lab 3 – Jurassic Park
P
r
o
j
e
c
t
3
–
G
u
i
d
e
l
i
n
e
s
…
You may use the arguments to the project3 command to
optionally specify the number of park visitors, in multiples
of 3. (The default is 45 visitors.)
Add a delta clock to your operating system. The delta
clock ticks in tenth-of-a-second increments.
C
r
e
a
t
e
a
t
a
s
k
f
o
r
e
a
c
h
p
a
r
k
v
i
s
i
t
o
r
(
N
U
M
_
V
I
S
I
T
O
R
S
)
,
d
r
i
v
e
r
(
N
U
M
_
D
R
I
V
E
R
S
)
,
a
n
d
t
o
u
r
c
a
r
(
N
U
M
_
C
A
R
S
)
.
T
h
e
s
e
t
a
s
k
s
s
h
o
u
l
d
a
l
l
r
u
n
a
t
t
h
e
s
a
m
e
p
r
i
o
r
i
t
y
l
e
v
e
l
.
U
p
d
a
t
e
t
h
e
p
a
r
k
d
a
t
a
s
t
r
u
c
t
u
r
e
v
a
r
i
a
b
l
e
s
a
p
p
r
o
p
r
i
a
t
e
l
y
a
s
v
i
s
i
t
o
r
,
d
r
i
v
e
r
,
a
n
d
c
a
r
s
t
a
t
e
s
c
h
a
n
g
e
.
T
h
e
p
a
r
k
i
s
d
i
s
p
l
a
y
e
d
u
s
i
n
g
t
h
e
p
a
r
k
d
a
t
a
s
t
r
u
c
t
e
v
e
r
y
s
e
c
o
n
d
b
y
t
h
e
j
u
r
a
s
s
i
c
T
a
s
k
t
a
s
k
.
6
CS 345
Lab 3 – Jurassic Park
P
r
o
j
e
c
t
3
–
G
u
i
d
e
l
i
n
e
s
…
E
a
c
h
t
a
s
k
(
v
i
s
i
t
o
r
,
d
r
i
v
e
r
,
a
n
d
c
a
r
)
s
h
o
u
l
d
c
r
e
a
t
e
i
t
s
o
w
n
t
i
m
i
n
g
s
e
m
a
p
h
o
r
e
,
w
h
i
c
h
i
s
u
s
e
d
f
o
r
t
i
m
i
n
g
f
u
n
c
t
i
o
n
s
(
i
e
,
a
r
r
i
v
a
l
d
e
l
a
y
,
s
t
a
n
d
i
n
g
i
n
l
i
n
e
s
,
t
i
m
e
i
n
g
i
f
t
s
h
o
p
o
r
m
u
s
e
u
m
.
)
T
h
e
d
e
l
t
a
c
l
o
c
k
s
h
o
u
l
d
b
e
u
s
e
d
t
o
S
E
M
_
S
I
G
N
A
L
t
h
e
s
e
s
e
m
a
p
h
o
r
e
s
.
Park visitors should randomly arrive at the park over a
10 second period. In addition, visitors should stand in
lines for a random time before requesting a ticket or
entrance to the museum or gift shop (3 seconds
maximum).
7
CS 345
Lab 3 – Jurassic Park
P
r
o
j
e
c
t
3
–
G
u
i
d
e
l
i
n
e
s
…
Use resource semaphores (counting) to control access
to the park, the number of tickets available, and the
number of people allowed in the gift shop and museum.
Use mutex semaphores (binary) to protect any critical
sections of code within your implementation, such as
when updating the delta clock, acquiring a driver to buy
a ticket or drive a tour car, accessing global data, or
sampling the state of a semaphore.
Use semaphores (binary) to synchronize and
communicate events between tasks, such as to awaken
a driver, signal data is valid, signal a mode change, etc.
8
CS 345
Lab 3 – Jurassic Park
P
r
o
j
e
c
t
3
–
G
u
i
d
e
l
i
n
e
s
…
U
s
e
a
t
l
e
a
s
t
o
n
e
S
E
M
_
T
R
Y
L
O
C
K
f
u
n
c
t
i
o
n
i
n
y
o
u
r
s
i
m
u
l
a
t
i
o
n
.
T
h
e
“
S
W
A
P
”
d
i
r
e
c
t
i
v
e
s
h
o
u
l
d
b
e
i
n
s
e
r
t
e
d
b
e
t
w
e
e
n
e
v
e
r
y
l
i
n
e
o
f
c
o
d
e
i
n
y
o
u
r
J
u
r
a
s
s
i
c
P
a
r
k
s
i
m
u
l
a
t
i
o
n
.
P
a
r
k
c
r
i
t
i
c
a
l
c
o
d
e
m
u
s
t
b
e
p
r
o
t
e
c
t
e
d
b
y
t
h
e
p
a
r
k
M
u
t
e
x
m
u
t
e
x
.
T
h
e
p
a
r
k
s
i
m
u
l
a
t
i
o
n
c
r
e
a
t
e
s
a
“
l
o
s
t
V
i
s
i
t
o
r
”
t
a
s
k
w
h
i
c
h
s
u
m
s
c
r
i
t
i
c
a
l
v
a
r
i
a
b
l
e
s
i
n
t
h
e
p
a
r
k
t
o
d
e
t
e
c
t
a
n
y
l
o
s
t
v
i
s
i
t
o
r
s
.
B
e
w
a
r
e
!
You are to implement a fair algorithm that prevents
deadlock and starvation rather than detect them
9
CS 345
Lab 3 – Jurassic Park
J
u
r
a
s
s
i
c
P
a
r
k
s
t
r
u
c
t
Driver Status
p
a
r
k
.
d
r
i
v
e
r
s
[
]
# of Passengers
p
a
r
k
.
c
a
r
s
[
]
.
p
a
s
s
e
n
g
e
r
s
# Exited Park
n
u
m
E
x
i
t
e
d
P
a
r
k
# Waiting to Enter Park
n
u
m
O
u
t
s
i
d
e
P
a
r
k
# Tickets Available
n
u
m
T
i
c
k
e
t
s
A
v
a
i
l
a
b
l
e
# in Park
n
u
m
I
n
P
a
r
k
# Rides Taken
n
u
m
R
i
d
e
s
T
a
k
e
n
Ticket Line
n
u
m
I
n
T
i
c
k
e
t
L
i
n
e
# in Gift Shop
n
u
m
I
n
G
i
f
t
S
h
o
p
# in Museum
n
u
m
I
n
M
u
s
e
u
m
Tour Car Line
n
u
m
I
n
C
a
r
L
i
n
e
Gift Shop Line
n
u
m
I
n
G
i
f
t
L
i
n
e
Museum Line
n
u
m
I
n
M
u
s
e
u
m
L
i
n
e
10
CS 345
Lab 3 – Jurassic Park
S
e
m
a
p
h
o
r
e
s
U
s
e
r
e
s
o
u
r
c
e
s
e
m
a
p
h
o
r
e
s
(
c
o
u
n
t
i
n
g
)
t
o
c
o
n
t
r
o
l
a
c
c
e
s
s
t
o
t
h
e
p
a
r
k
,
t
h
e
n
u
m
b
e
r
o
f
t
i
c
k
e
t
s
a
v
a
i
l
a
b
l
e
,
a
n
d
t
h
e
n
u
m
b
e
r
o
f
p
e
o
p
l
e
a
l
l
o
w
e
d
i
n
t
h
e
g
i
f
t
s
h
o
p
a
n
d
m
u
s
e
u
m
.
/
/
c
r
e
a
t
e
M
A
X
_
T
I
C
K
E
T
S
t
i
c
k
e
t
s
u
s
i
n
g
c
o
u
n
t
i
n
g
s
e
m
a
p
h
o
r
e
t
i
c
k
e
t
s
=
c
r
e
a
t
e
S
e
m
a
p
h
o
r
e
(
"
t
i
c
k
e
t
s
"
,
C
O
U
N
T
I
N
G
,
M
A
X
_
T
I
C
K
E
T
S
)
;
S
W
A
P
;
/
/
b
u
y
a
t
i
c
k
e
t
(
c
o
n
s
u
m
e
)
S
E
M
_
W
A
I
T
(
t
i
c
k
e
t
s
)
;
S
W
A
P
;
/
/
r
e
s
e
l
l
t
i
c
k
e
t
(
p
r
o
d
u
c
e
)
S
E
M
_
S
I
G
N
A
L
(
t
i
c
k
e
t
s
)
;
S
W
A
P
;
11
CS 345
Lab 3 – Jurassic Park
S
e
m
a
p
h
o
r
e
s
U
s
e
m
u
t
e
x
s
e
m
a
p
h
o
r
e
s
(
b
i
n
a
r
y
)
t
o
p
r
o
t
e
c
t
a
n
y
c
r
i
t
i
c
a
l
s
e
c
t
i
o
n
s
o
f
c
o
d
e
,
s
u
c
h
a
s
w
h
e
n
u
p
d
a
t
i
n
g
t
h
e
d
e
l
t
a
c
l
o
c
k
,
a
c
q
u
i
r
i
n
g
a
d
r
i
v
e
r
t
o
b
u
y
a
t
i
c
k
e
t
o
r
d
r
i
v
e
a
t
o
u
r
c
a
r
,
a
c
c
e
s
s
i
n
g
g
l
o
b
a
l
d
a
t
a
,
o
r
s
a
m
p
l
i
n
g
t
h
e
s
t
a
t
e
o
f
a
s
e
m
a
p
h
o
r
e
.
/
/
n
e
e
d
t
i
c
k
e
t
,
w
a
i
t
f
o
r
d
r
i
v
e
r
(
m
u
t
e
x
)
S
E
M
_
W
A
I
T
(
n
e
e
d
D
r
i
v
e
r
M
u
t
e
x
)
;
S
W
A
P
;
{/
/
s
i
g
n
a
l
n
e
e
d
t
i
c
k
e
t
(
s
i
g
n
a
l
,
p
u
t
h
a
n
d
u
p
)
…
}
/
/
r
e
l
e
a
s
e
d
r
i
v
e
r
(
m
u
t
e
x
)
S
E
M
_
S
I
G
N
A
L
(
n
e
e
d
D
r
i
v
e
r
M
u
t
e
x
)
;
S
W
A
P
;
12
CS 345
Lab 3 – Jurassic Park
S
e
m
a
p
h
o
r
e
s
U
s
e
s
i
g
n
a
l
s
e
m
a
p
h
o
r
e
s
(
b
i
n
a
r
y
)
t
o
s
y
n
c
h
r
o
n
i
z
e
a
n
d
c
o
m
m
u
n
i
c
a
t
e
e
v
e
n
t
s
b
e
t
w
e
e
n
t
a
s
k
s
,
s
u
c
h
a
s
t
o
a
w
a
k
e
n
a
d
r
i
v
e
r
,
s
i
g
n
a
l
d
a
t
a
i
s
v
a
l
i
d
,
e
t
c
.
/
/
s
i
g
n
a
l
n
e
e
d
t
i
c
k
e
t
(
s
i
g
n
a
l
,
p
u
t
h
a
n
d
u
p
)
S
E
M
_
S
I
G
N
A
L
(
n
e
e
d
T
i
c
k
e
t
)
;
S
W
A
P
;
{/
/
w
a
k
e
u
p
d
r
i
v
e
r
(
s
i
g
n
a
l
)
S
E
M
_
S
I
G
N
A
L
(
w
a
k
e
u
p
D
r
i
v
e
r
)
;
S
W
A
P
;
/
/
w
a
i
t
t
i
c
k
e
t
a
v
a
i
l
a
b
l
e
(
s
i
g
n
a
l
)
S
E
M
_
W
A
I
T
(
t
i
c
k
e
t
R
e
a
d
y
)
;
S
W
A
P
;
/
/
b
u
y
t
i
c
k
e
t
(
s
i
g
n
a
l
)
S
E
M
_
S
I
G
N
A
L
(
b
u
y
T
i
c
k
e
t
)
;
S
W
A
P
;
}
/
/
p
u
t
h
a
n
d
d
o
w
n
(
s
i
g
n
a
l
)
S
E
M
_
W
A
I
T
(
n
e
e
d
T
i
c
k
e
t
)
;
S
W
A
P
;
13
CS 345
Lab 3 – Jurassic Park
S
h
a
r
e
d
M
e
m
o
r
y
Shared memory can be implemented using C global
memory when protected with mutex semaphores.
/
/
p
r
o
t
e
c
t
s
h
a
r
e
d
m
e
m
o
r
y
a
c
c
e
s
s
S
E
M
_
W
A
I
T
(
p
a
r
k
M
u
t
e
x
)
;
;
S
W
A
P
/
/
a
c
c
e
s
s
i
n
s
i
d
e
p
a
r
k
v
a
r
i
a
b
l
e
s
m
y
P
a
r
k
.
n
u
m
O
u
t
s
i
d
e
P
a
r
k
-
-
;
;
S
W
A
P
m
y
P
a
r
k
.
n
u
m
I
n
P
a
r
k
+
+
;
;
S
W
A
P
/
/
r
e
l
e
a
s
e
p
r
o
t
e
c
t
s
h
a
r
e
d
m
e
m
o
r
y
a
c
c
e
s
s
S
E
M
_
S
I
G
N
A
L
(
p
a
r
k
M
u
t
e
x
)
;
;
S
W
A
P
14
CS 345
Lab 3 – Jurassic Park
P
r
o
j
e
c
t
3
–
J
u
r
a
s
s
i
c
P
a
r
k
3
p
o
i
n
t
s
–
I
m
p
l
e
m
e
n
t
a
d
e
l
t
a
c
l
o
c
k
i
n
t
h
e
p
o
l
l
I
n
t
e
r
r
u
p
t
s
r
o
u
t
i
n
e
(
O
S
3
4
5
.
c
)
t
h
a
t
s
h
o
u
l
d
t
i
c
k
d
o
w
n
e
v
e
r
y
1
/
1
0
o
f
a
s
e
c
o
n
d
.
2
p
o
i
n
t
s
–
C
r
e
a
t
e
a
s
i
n
g
l
e
,
r
e
-
e
n
t
r
a
n
t
v
i
s
i
t
o
r
t
a
s
k
t
h
a
t
e
n
t
e
r
s
t
h
e
J
u
r
a
s
s
i
c
P
a
r
k
a
t
r
a
n
d
o
m
t
i
m
e
s
,
p
u
r
c
h
a
s
e
s
a
t
i
c
k
e
t
,
v
i
s
i
t
s
t
h
e
m
u
s
e
u
m
,
t
a
k
e
s
a
t
o
u
r
o
f
t
h
e
p
a
r
k
,
s
t
o
p
s
b
y
t
h
e
g
i
f
t
s
h
o
p
,
a
n
d
t
h
e
n
e
x
i
t
s
t
h
e
p
a
r
k
.
1
p
o
i
n
t
–
C
r
e
a
t
e
a
s
i
n
g
l
e
,
r
e
-
e
n
t
r
a
n
t
c
a
r
t
a
s
k
t
h
e
a
c
q
u
i
r
e
s
3
v
i
s
i
t
o
r
s
a
n
d
a
d
r
i
v
e
r
w
h
i
l
e
t
o
u
r
i
n
g
t
h
e
p
a
r
k
.
1
p
o
i
n
t
–
C
r
e
a
t
e
a
s
i
n
g
l
e
,
r
e
-
e
n
t
r
a
n
t
d
r
i
v
e
r
t
a
s
k
,
w
h
i
c
h
s
l
e
e
p
s
u
n
t
i
l
a
w
a
k
e
n
e
d
t
o
s
e
l
l
a
t
i
c
k
e
t
o
r
d
r
i
v
e
a
t
o
u
r
c
a
r
.
1
p
o
i
n
t
–
C
o
r
r
e
c
t
l
y
u
s
e
r
e
s
o
u
r
c
e
,
m
u
t
e
x
,
a
n
d
s
y
n
c
h
r
o
n
i
z
a
t
i
o
n
s
e
m
a
p
h
o
r
e
s
i
n
y
o
u
r
i
m
p
l
e
m
e
n
t
a
t
i
o
n
.
2
p
o
i
n
t
s
–
P
3
s
t
a
r
t
s
a
f
u
l
l
y
f
u
n
c
t
i
o
n
a
l
j
u
r
a
s
s
i
c
T
a
s
k
.
15
CS 345
Lab 3 – Jurassic Park
P
r
o
j
e
c
t
3
–
J
u
r
a
s
s
i
c
P
a
r
k
I
n
a
d
d
i
t
i
o
n
t
o
t
h
e
p
o
s
s
i
b
l
e
1
0
p
o
i
n
t
s
,
t
h
e
f
o
l
l
o
w
i
n
g
b
o
n
u
s
/
p
e
n
a
l
t
i
e
s
a
p
p
l
y
:
+
1
p
o
i
n
t
–
b
o
n
u
s
f
o
r
e
a
r
l
y
p
a
s
s
-
o
f
f
(
a
t
l
e
a
s
t
o
n
e
d
a
y
b
e
f
o
r
e
d
u
e
d
a
t
e
.
)
+
1
-
4
p
o
i
n
t
s
–
b
o
n
u
s
f
o
r
a
p
p
r
o
v
e
d
c
h
a
n
g
e
s
t
o
o
s
3
4
5
p
a
r
k
.
c
,
s
u
c
h
a
s
:
Improved interface to park
Different routes in park
Making dinosaurs individual tasks
Random lost (or consumed) park visitors (must be accounted for)
Gift shop expenditures
Having drivers do periodic maintenance on park ride
Something you think is clever…
-
1
p
o
i
n
t
–
p
e
n
a
l
t
y
f
o
r
n
o
t
r
u
n
n
i
n
g
v
i
s
i
t
o
r
,
c
a
r
,
a
n
d
d
r
i
v
e
r
t
a
s
k
s
a
t
s
a
m
e
p
r
i
o
r
i
t
y
l
e
v
e
l
.
-
1
p
o
i
n
t
–
p
e
n
a
l
t
y
f
o
r
a
l
t
e
r
i
n
g
o
s
3
4
5
p
a
r
k
.
c
w
i
t
h
o
u
t
a
p
p
r
o
v
a
l
.
-
1
0
p
o
i
n
t
s
–
p
e
n
a
l
t
y
f
o
r
n
o
t
h
a
v
i
n
g
a
S
W
A
P
a
f
t
e
r
e
v
e
r
y
C
l
i
n
e
o
f
c
o
d
e
.
-
1
p
o
i
n
t
–
p
e
n
a
l
t
y
f
o
r
e
a
c
h
s
c
h
o
o
l
d
a
y
l
a
t
e
.
16
S
t
e
p
1
:
D
e
l
t
a
C
l
o
c
k
Implement delta clock.
Design data structure to hold delta times/events.
Program an insert delta clock function
insertDeltaClock(int time, Semaphore* sem);
High priority, mutex protected
Add 1/10 second function to decrement top
event and semSignal semaphore when 0
pollinterrupts or
High priority, mutex protected.
CS 345
Lab 3 – Jurassic Park
17
P
r
o
j
e
c
t
3
A
s
s
i
g
n
m
e
n
t
Thoroughly test the operation of your delta clock before proceeding.
os345p3.c
Print Delta Clock (dc): int P3_dc(int argc, char* argv[]);
Test Delta Clock (tdc): int P3_tdc(int argc, char* argv[]);
i
n
t
d
c
M
o
n
i
t
o
r
T
a
s
k
(
i
n
t
a
r
g
c
,
c
h
a
r
*
a
r
g
v
[
]
)
;
i
n
t
t
i
m
e
T
a
s
k
(
i
n
t
a
r
g
c
,
c
h
a
r
*
a
r
g
v
[
]
)
;
S
t
e
p
2
:
C
a
r
T
a
s
k
s
Implement simple car task.
Design car functionality and Jurassic Park interface. (Don’t
worry about passengers or drivers yet.)
CS 345
Lab 3 – Jurassic Park
18
P
r
o
j
e
c
t
3
A
s
s
i
g
n
m
e
n
t
Semaphore* fillSeat[NUM_CARS]; SWAP;
Semaphore* seatFilled[NUM_CARS]; SWAP;
Semaphore* rideOver[NUM_CARS]; SWAP;
***Temporarily add the following to get the cars moving:
myPark.numInCarLine = myPark.numInPark = 4;
S
t
e
p
2
:
C
a
r
T
a
s
k
s
(
e
x
a
m
p
l
e
)
CS 345
Lab 3 – Jurassic Park
19
P
r
o
j
e
c
t
3
A
s
s
i
g
n
m
e
n
t
// For each car, do 3 times:
{ SEM_WAIT(fillSeat[carID]); SWAP; // wait for available seatSEM_SIGNAL(getPassenger); SWAP; // signal for visitor
SEM_WAIT(seatTaken); SWAP; // wait for visitor to reply
... save passenger ride over semaphore ...
SEM_SIGNAL(passengerSeated); SWAP: // signal visitor in seat
// if last passenger, get driver
{SEM_WAIT(needDriverMutex); SWAP;
// wakeup attendant
SEM_SIGNAL(wakeupDriver); SWAP;
... save driver ride over semaphore ...
// got driver (mutex)
SEM_SIGNAL(needDriverMutex); SWAP;
}
SEM_SIGNAL(seatFilled[carID]); SWAP; // signal next seat ready
}
SEM_WAIT(rideOver[myID]); SWAP; // wait for ride over
... release passengers and driver ...
Design visitor functionality and car task interface. (Don’t
worry about tickets yet.)
E
a
c
h
t
a
s
k
v
i
s
i
t
o
r
s
h
o
u
l
d
c
r
e
a
t
e
i
t
s
o
w
n
t
i
m
i
n
g
s
e
m
a
p
h
o
r
e
,
w
h
i
c
h
i
s
u
s
e
d
f
o
r
t
i
m
i
n
g
f
u
n
c
t
i
o
n
s
(
i
e
,
a
r
r
i
v
a
l
d
e
l
a
y
,
s
t
a
n
d
i
n
g
i
n
l
i
n
e
s
,
t
i
m
e
i
n
g
i
f
t
s
h
o
p
o
r
m
u
s
e
u
m
.
)
T
h
e
d
e
l
t
a
c
l
o
c
k
s
h
o
u
l
d
b
e
u
s
e
d
t
o
S
E
M
_
S
I
G
N
A
L
t
h
e
s
e
s
e
m
a
p
h
o
r
e
s
.
Park visitors should randomly arrive at the park over a 10 second
period. In addition, visitors should stand in lines for a random time
before requesting a ticket or entrance to the museum or gift shop (3
seconds maximum).
The “SWAP” directive should be inserted after every line of
code in your Jurassic Park simulation. Park critical code
must be protected by the parkMutex mutex.
The park simulation creates a “lostVisitor” task which sums
critical variables in the park to detect any lost visitors.
CS 345
Lab 3 – Jurassic Park
20
S
t
e
p
3
:
V
i
s
i
t
o
r
T
a
s
k
s
P
r
o
j
e
c
t
3
A
s
s
i
g
n
m
e
n
t
U
s
e
r
e
s
o
u
r
c
e
s
e
m
a
p
h
o
r
e
s
(
c
o
u
n
t
i
n
g
)
t
o
c
o
n
t
r
o
l
a
c
c
e
s
s
t
o
t
h
e
p
a
r
k
,
t
h
e
n
u
m
b
e
r
o
f
t
i
c
k
e
t
s
a
v
a
i
l
a
b
l
e
,
a
n
d
t
h
e
n
u
m
b
e
r
o
f
p
e
o
p
l
e
a
l
l
o
w
e
d
i
n
t
h
e
g
i
f
t
s
h
o
p
a
n
d
m
u
s
e
u
m
.
Use
mutex semaphores
(binary) to protect any critical
sections of code within your implementation, such as
when updating the delta clock, acquiring a driver to buy
a ticket or drive a tour car, accessing global data, or
sampling the state of a semaphore.
U
s
e
s
e
m
a
p
h
o
r
e
s
(
b
i
n
a
r
y
)
t
o
s
y
n
c
h
r
o
n
i
z
e
a
n
d
c
o
m
m
u
n
i
c
a
t
e
e
v
e
n
t
s
b
e
t
w
e
e
n
t
a
s
k
s
,
s
u
c
h
a
s
t
o
a
w
a
k
e
n
a
d
r
i
v
e
r
,
s
i
g
n
a
l
d
a
t
a
i
s
v
a
l
i
d
,
s
i
g
n
a
l
a
m
o
d
e
c
h
a
n
g
e
,
e
t
c
.
CS 345
Lab 3 – Jurassic Park
21
S
t
e
p
3
:
V
i
s
i
t
o
r
T
a
s
k
s
P
r
o
j
e
c
t
3
A
s
s
i
g
n
m
e
n
t
CS 345
Lab 3 – Jurassic Park
S
e
m
a
p
h
o
r
e
s
U
s
e
r
e
s
o
u
r
c
e
s
e
m
a
p
h
o
r
e
s
(
c
o
u
n
t
i
n
g
)
t
o
c
o
n
t
r
o
l
a
c
c
e
s
s
t
o
t
h
e
p
a
r
k
,
t
h
e
n
u
m
b
e
r
o
f
t
i
c
k
e
t
s
a
v
a
i
l
a
b
l
e
,
a
n
d
t
h
e
n
u
m
b
e
r
o
f
p
e
o
p
l
e
a
l
l
o
w
e
d
i
n
t
h
e
g
i
f
t
s
h
o
p
a
n
d
m
u
s
e
u
m
.
/
/
c
r
e
a
t
e
M
A
X
_
T
I
C
K
E
T
S
t
i
c
k
e
t
s
u
s
i
n
g
c
o
u
n
t
i
n
g
s
e
m
a
p
h
o
r
e
t
i
c
k
e
t
s
=
c
r
e
a
t
e
S
e
m
a
p
h
o
r
e
(
"
t
i
c
k
e
t
s
"
,
C
O
U
N
T
I
N
G
,
M
A
X
_
T
I
C
K
E
T
S
)
;
S
W
A
P
;
/
/
b
u
y
a
t
i
c
k
e
t
(
c
o
n
s
u
m
e
)
S
E
M
_
W
A
I
T
(
t
i
c
k
e
t
s
)
;
S
W
A
P
;
/
/
r
e
s
e
l
l
t
i
c
k
e
t
(
p
r
o
d
u
c
e
)
S
E
M
_
S
I
G
N
A
L
(
t
i
c
k
e
t
s
)
;
S
W
A
P
;
22
CS 345
Lab 3 – Jurassic Park
S
e
m
a
p
h
o
r
e
s
U
s
e
m
u
t
e
x
s
e
m
a
p
h
o
r
e
s
(
b
i
n
a
r
y
)
t
o
p
r
o
t
e
c
t
a
n
y
c
r
i
t
i
c
a
l
s
e
c
t
i
o
n
s
o
f
c
o
d
e
,
s
u
c
h
a
s
w
h
e
n
u
p
d
a
t
i
n
g
t
h
e
d
e
l
t
a
c
l
o
c
k
,
a
c
q
u
i
r
i
n
g
a
d
r
i
v
e
r
t
o
b
u
y
a
t
i
c
k
e
t
o
r
d
r
i
v
e
a
t
o
u
r
c
a
r
,
a
c
c
e
s
s
i
n
g
g
l
o
b
a
l
d
a
t
a
,
o
r
s
a
m
p
l
i
n
g
t
h
e
s
t
a
t
e
o
f
a
s
e
m
a
p
h
o
r
e
.
/
/
n
e
e
d
t
i
c
k
e
t
,
w
a
i
t
f
o
r
d
r
i
v
e
r
(
m
u
t
e
x
)
S
E
M
_
W
A
I
T
(
n
e
e
d
D
r
i
v
e
r
M
u
t
e
x
)
;
S
W
A
P
;
{/
/
s
i
g
n
a
l
n
e
e
d
t
i
c
k
e
t
(
s
i
g
n
a
l
,
p
u
t
h
a
n
d
u
p
)
…
}
/
/
r
e
l
e
a
s
e
d
r
i
v
e
r
(
m
u
t
e
x
)
S
E
M
_
S
I
G
N
A
L
(
n
e
e
d
D
r
i
v
e
r
M
u
t
e
x
)
;
S
W
A
P
;
23
CS 345
Lab 3 – Jurassic Park
S
e
m
a
p
h
o
r
e
s
U
s
e
s
i
g
n
a
l
s
e
m
a
p
h
o
r
e
s
(
b
i
n
a
r
y
)
t
o
s
y
n
c
h
r
o
n
i
z
e
a
n
d
c
o
m
m
u
n
i
c
a
t
e
e
v
e
n
t
s
b
e
t
w
e
e
n
t
a
s
k
s
,
s
u
c
h
a
s
t
o
a
w
a
k
e
n
a
d
r
i
v
e
r
,
s
i
g
n
a
l
d
a
t
a
i
s
v
a
l
i
d
,
e
t
c
.
/
/
s
i
g
n
a
l
n
e
e
d
t
i
c
k
e
t
(
s
i
g
n
a
l
,
p
u
t
h
a
n
d
u
p
)
S
E
M
_
S
I
G
N
A
L
(
n
e
e
d
T
i
c
k
e
t
)
;
S
W
A
P
;
{/
/
w
a
k
e
u
p
d
r
i
v
e
r
(
s
i
g
n
a
l
)
S
E
M
_
S
I
G
N
A
L
(
w
a
k
e
u
p
D
r
i
v
e
r
)
;
S
W
A
P
;
/
/
w
a
i
t
t
i
c
k
e
t
a
v
a
i
l
a
b
l
e
(
s
i
g
n
a
l
)
S
E
M
_
W
A
I
T
(
t
i
c
k
e
t
R
e
a
d
y
)
;
S
W
A
P
;
/
/
b
u
y
t
i
c
k
e
t
(
s
i
g
n
a
l
)
S
E
M
_
S
I
G
N
A
L
(
b
u
y
T
i
c
k
e
t
)
;
S
W
A
P
;
}
/
/
p
u
t
h
a
n
d
d
o
w
n
(
s
i
g
n
a
l
)
S
E
M
_
W
A
I
T
(
n
e
e
d
T
i
c
k
e
t
)
;
S
W
A
P
;
24
CS 345
Lab 3 – Jurassic Park
S
h
a
r
e
d
M
e
m
o
r
y
Shared memory can be implemented using C global
memory when protected with mutex semaphores.
/
/
p
r
o
t
e
c
t
s
h
a
r
e
d
m
e
m
o
r
y
a
c
c
e
s
s
S
E
M
_
W
A
I
T
(
p
a
r
k
M
u
t
e
x
)
;
;
S
W
A
P
/
/
a
c
c
e
s
s
i
n
s
i
d
e
p
a
r
k
v
a
r
i
a
b
l
e
s
m
y
P
a
r
k
.
n
u
m
O
u
t
s
i
d
e
P
a
r
k
-
-
;
;
S
W
A
P
m
y
P
a
r
k
.
n
u
m
I
n
P
a
r
k
+
+
;
;
S
W
A
P
/
/
r
e
l
e
a
s
e
p
r
o
t
e
c
t
s
h
a
r
e
d
m
e
m
o
r
y
a
c
c
e
s
s
S
E
M
_
S
I
G
N
A
L
(
p
a
r
k
M
u
t
e
x
)
;
;
S
W
A
P
25
CS 345
Lab 3 – Jurassic Park
P
a
s
s
i
n
g
S
e
m
a
p
h
o
r
e
s
Shared memory can be implemented using C global
memory when protected with mutex semaphores.
/
/
p
a
s
s
s
e
m
a
p
h
o
r
e
t
o
c
a
r
(
1
a
t
a
t
i
m
e
)
S
E
M
_
W
A
I
T
(
m
a
i
l
b
o
x
M
u
t
e
x
)
;
S
W
A
P
;
/
/
w
a
i
t
f
o
r
m
a
i
l
b
o
x
S
E
M
_
W
A
I
T
(
n
e
e
d
P
a
s
s
e
n
g
e
r
)
;
S
W
A
P
:
/
/
w
a
i
t
f
o
r
p
a
s
s
e
n
g
e
r
r
e
q
u
e
s
t
g
M
a
i
l
b
o
x
=
m
y
S
e
m
a
p
h
o
r
e
;
S
W
A
P
;
/
/
p
u
t
s
e
m
a
p
h
o
r
e
i
n
m
a
i
l
b
o
x
S
E
M
_
S
I
G
N
A
L
(
m
a
i
l
b
o
x
R
e
a
d
y
)
;
S
W
A
P
;
/
/
r
a
i
s
e
t
h
e
m
a
i
l
b
o
x
f
l
a
g
S
E
M
_
W
A
I
T
(
m
a
i
l
A
c
q
u
i
r
e
d
)
;
S
W
A
P
;
/
/
w
a
i
t
f
o
r
d
e
l
i
v
e
r
y
S
E
M
_
S
I
G
N
A
L
(
m
a
i
l
b
o
x
M
u
t
e
x
)
;
S
W
A
P
;
/
/
r
e
l
e
a
s
e
m
a
i
l
b
o
x
26
/
/
g
e
t
p
a
s
s
e
n
g
e
r
s
e
m
a
p
h
o
r
e
S
E
M
_
S
I
G
N
A
L
(
n
e
e
d
P
a
s
s
e
n
g
e
r
)
;
S
W
A
P
;
S
E
M
_
W
A
I
T
(
m
a
i
l
b
o
x
R
e
a
d
y
)
;
S
W
A
P
;
/
/
w
a
i
t
f
o
r
m
a
i
l
m
y
S
e
m
a
p
h
o
r
e
=
g
M
a
i
l
b
o
x
;
S
W
A
P
;
/
/
g
e
t
m
a
i
l
S
E
M
_
S
I
G
N
A
L
(
m
a
i
l
A
c
q
u
i
r
e
d
)
;
S
W
A
P
;
/
/
p
u
t
f
l
a
g
d
o
w
n
CS 345
Lab 3 – Jurassic Park
J
u
r
a
s
s
i
c
P
a
r
k
s
t
r
u
c
t
Driver Status
p
a
r
k
.
d
r
i
v
e
r
s
[
]
# of Passengers
p
a
r
k
.
c
a
r
s
[
]
.
p
a
s
s
e
n
g
e
r
s
# Exited Park
n
u
m
E
x
i
t
e
d
P
a
r
k
# Waiting to Enter Park
n
u
m
O
u
t
s
i
d
e
P
a
r
k
# Tickets Available
n
u
m
T
i
c
k
e
t
s
A
v
a
i
l
a
b
l
e
# in Park
n
u
m
I
n
P
a
r
k
# Rides Taken
n
u
m
R
i
d
e
s
T
a
k
e
n
Ticket Line
n
u
m
I
n
T
i
c
k
e
t
L
i
n
e
# in Gift Shop
n
u
m
I
n
G
i
f
t
S
h
o
p
# in Museum
n
u
m
I
n
M
u
s
e
u
m
Tour Car Line
n
u
m
I
n
C
a
r
L
i
n
e
Gift Shop Line
n
u
m
I
n
G
i
f
t
L
i
n
e
Museum Line
n
u
m
I
n
M
u
s
e
u
m
L
i
n
e
27
typedef struct
{int numOutsidePark;
// # outside of park
int numInPark;
// # in park (P=#)
int numTicketsAvailable;
// # left to sell (T=#)
int numRidesTaken;
// # of tour rides taken (S=#)
int numExitedPark;
// # who have exited the park
int numInTicketLine;
// # in ticket line
int numInMuseumLine;
// # in museum line
int numInMuseum;
// # in museum
int numInCarLine;
// # in tour car line
int numInCars;
// # in tour cars
int numInGiftLine;
// # in gift shop line
int numInGiftShop;
// # in gift shop
int drivers[NUM_DRIVERS];
// driver state (-1=T, 0=z, 1=A, 2=B, etc.)
CAR cars[NUM_CARS];
// cars in park
} JPARK;
Develop the driver task.
Design driver functionality and interface with visitor/car tasks.
Implement design and integrate with os345, visitor, and car
tasks. (Now is the time to worry about ticket sales and driver
duties.)
Add ticket sales and driver responsibilities.
When a driver is awakened, use the semTryLock function to
determine if a driver or a ticket seller is needed.
CS 345
Lab 3 – Jurassic Park
28
S
t
e
p
4
:
D
r
i
v
e
r
T
a
s
k
s
P
r
o
j
e
c
t
3
A
s
s
i
g
n
m
e
n
t
D
r
i
v
e
r
T
a
s
k
CS 345
Lab 3 – Jurassic Park
29
int driverTask(int argc, char* argv[])
{char buf[32];
Semaphore* driverDone;
int myID = atoi(argv[1]) - 1;
SWAP;
// get unique drive id
printf(buf, "Starting driverTask%d", myID);
SWAP;
sprintf(buf, "driverDone%d", myID + 1);
SWAP;
driverDone = createSemaphore(buf, BINARY, 0);
SWAP;
// create notification event
while(1)
// such is my life!!
{mySEM_WAIT(wakeupDriver);
SWAP;
// goto sleep
if (mySEM_TRYLOCK(needDriver))
// i’m awake - driver needed?
{// yes
driverDoneSemaphore = driverDone;
SWAP;
// pass notification semaphore
mySEM_SIGNAL(driverReady);
SWAP;
// driver is awake
mySEM_WAIT(carReady);
SWAP;
// wait for car ready to go
mySEM_WAIT(driverDone);
SWAP;
// drive ride
}
else if (mySEM_TRYLOCK(needTicket))
// someone need ticket?
{// yes
mySEM_WAIT(tickets);
SWAP;
// wait for ticket (counting)
mySEM_SIGNAL(takeTicket);
SWAP;
// print a ticket (binary)
}
else break;
// don’t bother me!
}
return 0;
} // end driverTask
P
r
o
j
e
c
t
3
A
s
s
i
g
n
m
e
n
t
Should this
be mutexed?
CS 345
Lab 3 – Jurassic Park
30
CS 345
Lab 3 – Jurassic Park
S
u
g
g
e
s
t
e
d
I
m
p
l
e
m
e
n
t
a
t
i
o
n
S
t
e
p
s
1
.
I
m
p
l
e
m
e
n
t
d
e
l
t
a
c
l
o
c
k
.
a
.
D
e
s
i
g
n
d
a
t
a
s
t
r
u
c
t
u
r
e
t
o
h
o
l
d
d
e
l
t
a
t
i
m
e
s
/
e
v
e
n
t
s
.
b
.
A
d
d
1
/
1
0
s
e
c
o
n
d
r
o
u
t
i
n
e
t
o
p
o
l
l
i
n
t
e
r
r
u
p
t
s
.
D
e
c
r
e
m
e
n
t
t
o
p
e
v
e
n
t
a
n
d
s
e
m
S
i
g
n
a
l
w
h
e
n
t
i
m
e
=
0
.
c
.
P
r
o
g
r
a
m
a
n
i
n
s
e
r
t
d
e
l
t
a
c
l
o
c
k
r
o
u
t
i
n
e
(
i
n
s
e
r
t
D
e
l
t
a
C
l
o
c
k
(
i
n
t
t
i
m
e
,
S
e
m
a
p
h
o
r
e
*
s
e
m
)
)
.
d
.
T
h
o
r
o
u
g
h
l
y
t
e
s
t
t
h
e
o
p
e
r
a
t
i
o
n
o
f
y
o
u
r
d
e
l
t
a
c
l
o
c
k
b
e
f
o
r
e
p
r
o
c
e
e
d
i
n
g
.
2
.
D
e
v
e
l
o
p
t
h
e
c
a
r
t
a
s
k
.
a
.
D
e
s
i
g
n
c
a
r
f
u
n
c
t
i
o
n
a
l
i
t
y
a
n
d
J
u
r
a
s
s
i
c
P
a
r
k
i
n
t
e
r
f
a
c
e
.
(
D
o
n
’
t
w
o
r
r
y
a
b
o
u
t
p
a
s
s
e
n
g
e
r
s
y
e
t
.
)
b
.
I
m
p
l
e
m
e
n
t
d
e
s
i
g
n
a
n
d
i
n
t
e
g
r
a
t
e
w
i
t
h
o
s
3
4
5
a
n
d
J
u
r
a
s
s
i
c
P
a
r
k
.
c
.
O
b
s
e
r
v
e
c
o
r
r
e
c
t
c
a
r
b
e
h
a
v
i
o
r
.
31
CS 345
Lab 3 – Jurassic Park
S
u
g
g
e
s
t
e
d
I
m
p
l
e
m
e
n
t
a
t
i
o
n
S
t
e
p
s
3
.
D
e
v
e
l
o
p
t
h
e
v
i
s
i
t
o
r
t
a
s
k
.
a
.
D
e
s
i
g
n
v
i
s
i
t
o
r
f
u
n
c
t
i
o
n
a
l
i
t
y
a
n
d
c
a
r
t
a
s
k
i
n
t
e
r
f
a
c
e
.
b
.
I
m
p
l
e
m
e
n
t
d
e
s
i
g
n
a
n
d
i
n
t
e
g
r
a
t
e
w
i
t
h
o
s
3
4
5
a
n
d
c
a
r
t
a
s
k
s
.
(
D
o
n
’
t
w
o
r
r
y
a
b
o
u
t
t
i
c
k
e
t
s
y
e
t
.
)
c
.
U
s
e
d
e
l
t
a
-
c
l
o
c
k
t
o
v
a
r
y
v
i
s
i
t
o
r
t
i
m
e
i
n
a
l
l
l
i
n
e
s
,
m
u
s
e
u
m
,
a
n
d
g
i
f
t
s
h
o
p
.
d
.
O
b
s
e
r
v
e
c
o
r
r
e
c
t
v
i
s
i
t
o
r
b
e
h
a
v
i
o
r
a
s
a
v
i
s
i
t
o
r
m
o
v
e
s
t
h
r
o
u
g
h
t
h
e
p
a
r
k
.
32
4
.
D
e
v
e
l
o
p
t
h
e
d
r
i
v
e
r
t
a
s
k
.
a
.
D
e
s
i
g
n
d
r
i
v
e
r
f
u
n
c
t
i
o
n
a
l
i
t
y
a
n
d
i
n
t
e
r
f
a
c
e
w
i
t
h
v
i
s
i
t
o
r
a
n
d
c
a
r
t
a
s
k
s
.
b
.
I
m
p
l
e
m
e
n
t
d
e
s
i
g
n
a
n
d
i
n
t
e
g
r
a
t
e
w
i
t
h
o
s
3
4
5
,
v
i
s
i
t
o
r
,
a
n
d
c
a
r
t
a
s
k
s
.
(
N
o
w
i
s
t
h
e
t
i
m
e
t
o
w
o
r
r
y
a
b
o
u
t
t
i
c
k
e
t
s
a
l
e
s
a
n
d
d
r
i
v
e
r
d
u
t
i
e
s
.
)
c
.
A
d
d
t
i
c
k
e
t
s
a
l
e
s
a
n
d
d
r
i
v
e
r
r
e
s
p
o
n
s
i
b
i
l
i
t
i
e
s
.
d
.
W
h
e
n
a
d
r
i
v
e
r
i
s
a
w
a
k
e
n
e
d
,
u
s
e
t
h
e
s
e
m
T
r
y
L
o
c
k
f
u
n
c
t
i
o
n
t
o
d
e
t
e
r
m
i
n
e
i
f
a
d
r
i
v
e
r
o
r
a
t
i
c
k
e
t
s
e
l
l
e
r
i
s
n
e
e
d
e
d
.
CS 345
Lab 3 – Jurassic Park
33
Delta Clock Problem and DC Implementation in Jurassic Park involve efficiently monitoring timed events and inter-process communication between tasks. Visitors, drivers, and cars are represented as concurrent tasks, showcasing a synchronization problem in a themed park setting. The guidelines provide flexibility in managing park visitors based on specified arguments.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Delta Clock Problem: How to efficiently monitor timed events? Examples of timed events: scheduling real-time sequencing timers timeouts Lists require each event to be examined to determined if time has expired. CS 345 Lab 3 Jurassic Park 2
DC Implementation Notice that Event1 occurs 15 tics after Event2 Suppose: 20 Event1 Event1 occurs in 20 tics Event2 occurs in 5 tics Event3 occurs in 35 tics Event4 occurs in 27 tics Event 5 occurs in 27 tics Event 6 occurs in 22 tics 5 Event2 5 Event2 35 Event3 5 12 Event2 Event7 5 12 3 Event2 Event7 Event1 27 Event4 15 3 2 Event1 Event1 Event6 2 2 5 Event6 Event6 Event4 27 Event5 5 5 0 Event4 Event4 Event5 And that Event6 occurs 2 tics after Event1 0 0 4 Event5 Event5 Event8 8 8 4 Event3 Event3 Event3 22 Event6 Linked List Delta Clock What if Event7 occurs in 17 tics? Event8 in 31 tics? CS 345 Lab 3 Jurassic Park 3
Project 3 Jurassic Park Contemporary operating systems are built around the concept of processes or tasks. These tasks usually need to share resources in a protected, prioritized, and equitable manner. Jurassic Park is a inter-process communication and synchronization problem between multiple tasks. Visitors, drivers, and cars are represented by concurrent tasks while additional tasks display the park status and check for any lost visitors. A poorly implemented solution could lead to the inter- process communication problems of starvation and deadlock. CS 345 Lab 3 Jurassic Park 4
Jurassic Park When the touring car is filled with visitors and a driver is obtained, the car enters Jurassic Park and runs a guided tour through the park. Visitors try to enter the Jurassic Park at random times. (Only a set number of visitors may be in the park at any one time OSHA requirements!) Upon being allowed in the park, a visitor must get in line to purchase a ticket. When the tour car pulls into the unloading station, the visitors exit the tour car. and the driver goes to sleep awaiting new duties. The tour car pulls forward to be loaded again. After visiting the museum, the visitor gets in the tour car line to wait until permitted to board a tour car. (As a visitor boards a tour car, he returns his ticket.) After successfully obtaining a ticket from a driver, the visitor gets in the museum line and visits the museum. (A limited number of visitors are allowed in the museum as well as the gift shop.) After the visitors exit a tour car, they get into the gift shop line until they can visit the gift shop. After visiting the gift shop, the visitors exit the park. CS 345 Lab 3 Jurassic Park 5
Project 3 Guidelines You may use the arguments to the project3 command to optionally specify the number of park visitors, in multiples of 3. (The default is 45 visitors.) Add a delta clock to your operating system. The delta clock ticks in tenth-of-a-second increments. Create a task for each park visitor (NUM_VISITORS), driver (NUM_DRIVERS), and tour car (NUM_CARS). These tasks should all run at the same priority level. Update the park data structure variables appropriately as visitor, driver, and car states change. The park is displayed using the park data struct every second by the jurassicTask task. CS 345 Lab 3 Jurassic Park 6
Project 3 Guidelines Each task (visitor, driver, and car) should create its own timing semaphore, which is used for timing functions (ie, arrival delay, standing in lines, time in gift shop or museum.) The delta clock should be used to SEM_SIGNAL these semaphores. Park visitors should randomly arrive at the park over a 10 second period. In addition, visitors should stand in lines for a random time before requesting a ticket or entrance to the museum or gift shop (3 seconds maximum). CS 345 Lab 3 Jurassic Park 7
Project 3 Guidelines Use resource semaphores (counting) to control access to the park, the number of tickets available, and the number of people allowed in the gift shop and museum. Use mutex semaphores (binary) to protect any critical sections of code within your implementation, such as when updating the delta clock, acquiring a driver to buy a ticket or drive a tour car, accessing global data, or sampling the state of a semaphore. Use semaphores (binary) to synchronize and communicate events between tasks, such as to awaken a driver, signal data is valid, signal a mode change, etc. CS 345 Lab 3 Jurassic Park 8
Project 3 Guidelines Use at least one SEM_TRYLOCK function in your simulation. The SWAP directive should be inserted between every line of code in your Jurassic Park simulation. Park critical code must be protected by the parkMutex mutex. The park simulation creates a lostVisitor task which sums critical variables in the park to detect any lost visitors. Beware! You are to implement a fair algorithm that prevents deadlock and starvation rather than detect them CS 345 Lab 3 Jurassic Park 9
Jurassic Park struct # Waiting to Enter Park numOutsidePark Tour Car Line numInCarLine # of Passengers park.cars[ ].passengers Ticket Line numInTicketLine Driver Status park.drivers[ ] # Tickets Available numTicketsAvailable # in Park numInPark # Rides Taken numRidesTaken # Exited Park numExitedPark # in Gift Shop numInGiftShop Gift Shop Line numInGiftLine # in Museum numInMuseum Museum Line numInMuseumLine CS 345 Lab 3 Jurassic Park 10
Semaphores Use resource semaphores (counting) to control access to the park, the number of tickets available, and the number of people allowed in the gift shop and museum. // create MAX_TICKETS tickets using counting semaphore tickets = createSemaphore("tickets", COUNTING, MAX_TICKETS); SWAP; // buy a ticket (consume) SEM_WAIT(tickets); SWAP; // resell ticket (produce) SEM_SIGNAL(tickets); SWAP; CS 345 Lab 3 Jurassic Park 11
Semaphores Use mutex semaphores (binary) to protect any critical sections of code, such as when updating the delta clock, acquiring a driver to buy a ticket or drive a tour car, accessing global data, or sampling the state of a semaphore. // need ticket, wait for driver (mutex) SEM_WAIT(needDriverMutex); { // signal need ticket (signal, put hand up) } // release driver (mutex) SEM_SIGNAL(needDriverMutex); SWAP; SWAP; CS 345 Lab 3 Jurassic Park 12
Semaphores Use signal semaphores (binary) to synchronize and communicate events between tasks, such as to awaken a driver, signal data is valid, etc. // signal need ticket (signal, put hand up) SEM_SIGNAL(needTicket); { // wakeup driver (signal) SEM_SIGNAL(wakeupDriver); // wait ticket available (signal) SEM_WAIT(ticketReady); // buy ticket (signal) SEM_SIGNAL(buyTicket); } // put hand down (signal) SEM_WAIT(needTicket); SWAP; SWAP; SWAP; SWAP; SWAP; CS 345 Lab 3 Jurassic Park 13
Shared Memory Shared memory can be implemented using C global memory when protected with mutex semaphores. // protect shared memory access SEM_WAIT(parkMutex); ;SWAP // access inside park variables myPark.numOutsidePark--; myPark.numInPark++; ;SWAP ;SWAP // release protect shared memory access SEM_SIGNAL(parkMutex); ;SWAP CS 345 Lab 3 Jurassic Park 14
Project 3 Jurassic Park 3 points Implement a delta clock in the pollInterrupts routine (OS345.c) that should tick down every 1/10 of a second. 2 points Create a single, re-entrant visitor task that enters the Jurassic Park at random times, purchases a ticket, visits the museum, takes a tour of the park, stops by the gift shop, and then exits the park. 1 point Create a single, re-entrant car task the acquires 3 visitors and a driver while touring the park. 1 point Create a single, re-entrant driver task, which sleeps until awakened to sell a ticket or drive a tour car. 1 point Correctly use resource, mutex, and synchronization semaphores in your implementation. 2 points P3 starts a fully functional jurassicTask. CS 345 Lab 3 Jurassic Park 15
Project 3 Jurassic Park In addition to the possible 10 points, the following bonus/penalties apply: +1 point bonus for early pass-off (at least one day before due date.) +1-4 points bonus for approved changes to os345park.c, such as: Improved interface to park Different routes in park Making dinosaurs individual tasks Random lost (or consumed) park visitors (must be accounted for) Gift shop expenditures Having drivers do periodic maintenance on park ride Something you think is clever -1 point penalty for not running visitor, car, and driver tasks at same priority level. -1 point penalty for altering os345park.c without approval. -10 points penalty for not having a SWAP after every C line of code. -1 point penalty for each school day late. CS 345 Lab 3 Jurassic Park 16
Project 3 Assignment Step 1: Delta Clock Implement delta clock. Design data structure to hold delta times/events. Program an insert delta clock function dc[5] dc[4] dc[3] dc[2] dc[1] dc[0] 10 / sem1 5 / sem2 0 / sem3 2 / sem4 4 insertDeltaClock(int time, Semaphore* sem); High priority, mutex protected Add 1/10 second function to decrement top event and semSignal semaphore when 0 pollinterrupts or High priority, mutex protected. Thoroughly test the operation of your delta clock before proceeding. os345p3.c Print Delta Clock (dc): int P3_dc(int argc, char* argv[]); Test Delta Clock (tdc): int P3_tdc(int argc, char* argv[]); int dcMonitorTask(int argc, char* argv[]); int timeTask(int argc, char* argv[]); CS 345 Lab 3 Jurassic Park 17
Project 3 Assignment Step 2: Car Tasks Implement simple car task. Design car functionality and Jurassic Park interface. (Don t worry about passengers or drivers yet.) Semaphore* fillSeat[NUM_CARS]; Semaphore* seatFilled[NUM_CARS]; Semaphore* rideOver[NUM_CARS]; Car Task For each car seat: SEM_WAIT(fillSeat[carID]); Get passenger Save passenger rideDone[] semaphore Get driver (if last passenger) Save driver driverDone semaphore SEM_SIGNAL(seatFilled[carID]); Wait until ride over SEM_WAIT(rideOver[carID]); Release driver SEM_SIGNAL(driverDone); Release passengers SEM_SIGNAL(rideDone[i]); SWAP; SWAP; SWAP; Action Park Task SEM_SIGNAL(fillSeat[carID]); (3 times, then car takes off) SEM_WAIT(seatFilled[carID]); SEM_SIGNAL(rideOver[carID]); ***Temporarily add the following to get the cars moving: myPark.numInCarLine = myPark.numInPark = 4; CS 345 Lab 3 Jurassic Park 18
Project 3 Assignment Step 2: Car Tasks (example) // For each car, do 3 times: { SEM_WAIT(fillSeat[carID]); SWAP; // wait for available seat SEM_SIGNAL(getPassenger); SWAP; // signal for visitor SEM_WAIT(seatTaken); SWAP; // wait for visitor to reply ... save passenger ride over semaphore ... SEM_SIGNAL(passengerSeated); SWAP: // signal visitor in seat // if last passenger, get driver { SEM_WAIT(needDriverMutex); SWAP; // wakeup attendant SEM_SIGNAL(wakeupDriver); SWAP; ... save driver ride over semaphore ... // got driver (mutex) SEM_SIGNAL(needDriverMutex); SWAP; } SEM_SIGNAL(seatFilled[carID]); SWAP; // signal next seat ready } SEM_WAIT(rideOver[myID]); SWAP; // wait for ride over ... release passengers and driver ... CS 345 Lab 3 Jurassic Park 19
Project 3 Assignment Step 3: Visitor Tasks Design visitor functionality and car task interface. (Don t worry about tickets yet.) Each task visitor should create its own timing semaphore, which is used for timing functions (ie, arrival delay, standing in lines, time in gift shop or museum.) The delta clock should be used to SEM_SIGNAL these semaphores. Park visitors should randomly arrive at the park over a 10 second period. In addition, visitors should stand in lines for a random time before requesting a ticket or entrance to the museum or gift shop (3 seconds maximum). The SWAP directive should be inserted after every line of code in your Jurassic Park simulation. Park critical code must be protected by the parkMutex mutex. The park simulation creates a lostVisitor task which sums critical variables in the park to detect any lost visitors. CS 345 Lab 3 Jurassic Park 20
Project 3 Assignment Step 3: Visitor Tasks Use resource semaphores (counting) to control access to the park, the number of tickets available, and the number of people allowed in the gift shop and museum. Use mutex semaphores (binary) to protect any critical sections of code within your implementation, such as when updating the delta clock, acquiring a driver to buy a ticket or drive a tour car, accessing global data, or sampling the state of a semaphore. Use semaphores (binary) to synchronize and communicate events between tasks, such as to awaken a driver, signal data is valid, signal a mode change, etc. CS 345 Lab 3 Jurassic Park 21
Semaphores Use resource semaphores (counting) to control access to the park, the number of tickets available, and the number of people allowed in the gift shop and museum. // create MAX_TICKETS tickets using counting semaphore tickets = createSemaphore("tickets", COUNTING, MAX_TICKETS); SWAP; // buy a ticket (consume) SEM_WAIT(tickets); SWAP; // resell ticket (produce) SEM_SIGNAL(tickets); SWAP; CS 345 Lab 3 Jurassic Park 22
Semaphores Use mutex semaphores (binary) to protect any critical sections of code, such as when updating the delta clock, acquiring a driver to buy a ticket or drive a tour car, accessing global data, or sampling the state of a semaphore. // need ticket, wait for driver (mutex) SEM_WAIT(needDriverMutex); { // signal need ticket (signal, put hand up) } // release driver (mutex) SEM_SIGNAL(needDriverMutex); SWAP; SWAP; CS 345 Lab 3 Jurassic Park 23
Semaphores Use signal semaphores (binary) to synchronize and communicate events between tasks, such as to awaken a driver, signal data is valid, etc. // signal need ticket (signal, put hand up) SEM_SIGNAL(needTicket); { // wakeup driver (signal) SEM_SIGNAL(wakeupDriver); // wait ticket available (signal) SEM_WAIT(ticketReady); // buy ticket (signal) SEM_SIGNAL(buyTicket); } // put hand down (signal) SEM_WAIT(needTicket); SWAP; SWAP; SWAP; SWAP; SWAP; CS 345 Lab 3 Jurassic Park 24
Shared Memory Shared memory can be implemented using C global memory when protected with mutex semaphores. // protect shared memory access SEM_WAIT(parkMutex); ;SWAP // access inside park variables myPark.numOutsidePark--; myPark.numInPark++; ;SWAP ;SWAP // release protect shared memory access SEM_SIGNAL(parkMutex); ;SWAP CS 345 Lab 3 Jurassic Park 25
Passing Semaphores Shared memory can be implemented using C global memory when protected with mutex semaphores. // pass semaphore to car (1 at a time) SEM_WAIT(mailboxMutex); SWAP; SEM_WAIT(needPassenger); SWAP: // wait for passenger request gMailbox = mySemaphore; SWAP; SEM_SIGNAL(mailboxReady); SWAP; // raise the mailbox flag SEM_WAIT(mailAcquired); SWAP; SEM_SIGNAL(mailboxMutex); SWAP; // release mailbox // wait for mailbox // put semaphore in mailbox // wait for delivery // get passenger semaphore SEM_SIGNAL(needPassenger); SWAP; SEM_WAIT(mailboxReady); SWAP; mySemaphore = gMailbox; SWAP; SEM_SIGNAL(mailAcquired); SWAP; // put flag down // wait for mail // get mail CS 345 Lab 3 Jurassic Park 26
Jurassic Park struct # Waiting to Enter Park numOutsidePark Tour Car Line numInCarLine # of Passengers park.cars[ ].passengers Ticket Line numInTicketLine Driver Status park.drivers[ ] typedef struct { int numOutsidePark; int numInPark; int numTicketsAvailable; int numRidesTaken; int numExitedPark; int numInTicketLine; int numInMuseumLine; int numInMuseum; int numInCarLine; int numInCars; int numInGiftLine; int numInGiftShop; int drivers[NUM_DRIVERS]; CAR cars[NUM_CARS]; # Tickets Available numTicketsAvailable // # outside of park // # in park (P=#) // # left to sell (T=#) // # of tour rides taken (S=#) // # who have exited the park // # in ticket line // # in museum line // # in museum // # in tour car line // # in tour cars // # in gift shop line // # in gift shop // driver state (-1=T, 0=z, 1=A, 2=B, etc.) // cars in park # in Park numInPark # Rides Taken numRidesTaken # Exited Park numExitedPark } JPARK; # in Gift Shop numInGiftShop Gift Shop Line numInGiftLine # in Museum numInMuseum Museum Line numInMuseumLine CS 345 Lab 3 Jurassic Park 27
Project 3 Assignment Step 4: Driver Tasks Develop the driver task. Design driver functionality and interface with visitor/car tasks. Implement design and integrate with os345, visitor, and car tasks. (Now is the time to worry about ticket sales and driver duties.) Add ticket sales and driver responsibilities. When a driver is awakened, use the semTryLock function to determine if a driver or a ticket seller is needed. CS 345 Lab 3 Jurassic Park 28
Project 3 Assignment Driver Task int driverTask(int argc, char* argv[]) { char buf[32]; Semaphore* driverDone; int myID = atoi(argv[1]) - 1; printf(buf, "Starting driverTask%d", myID); sprintf(buf, "driverDone%d", myID + 1); driverDone = createSemaphore(buf, BINARY, 0); SWAP; SWAP; SWAP; SWAP; // get unique drive id // create notification event } // end driverTask while(1) { mySEM_WAIT(wakeupDriver); if (mySEM_TRYLOCK(needDriver)) { driverDoneSemaphore = driverDone; mySEM_SIGNAL(driverReady); mySEM_WAIT(carReady); mySEM_WAIT(driverDone); } else if (mySEM_TRYLOCK(needTicket)) { mySEM_WAIT(tickets); mySEM_SIGNAL(takeTicket); } else break; } return 0; // such is my life!! Should this be mutexed? SWAP; SWAP; SWAP; SWAP; SWAP; // goto sleep // i m awake - driver needed? // yes // pass notification semaphore // driver is awake // wait for car ready to go // drive ride SWAP; SWAP; // someone need ticket? // yes // wait for ticket (counting) // print a ticket (binary) // don t bother me! CS 345 Lab 3 Jurassic Park 29
CS 345 Lab 3 Jurassic Park 30
Suggested Implementation Steps 1. Implement delta clock. a. Design data structure to hold delta times/events. b. Add 1/10 second routine to pollinterrupts. Decrement top event and semSignal when time = 0. c. Program an insert delta clock routine (insertDeltaClock(int time, Semaphore* sem)). d. Thoroughly test the operation of your delta clock before proceeding. 2. Develop the car task. a. Design car functionality and Jurassic Park interface. (Don t worry about passengers yet.) b. Implement design and integrate with os345 and Jurassic Park. c. Observe correct car behavior. CS 345 Lab 3 Jurassic Park 31
Suggested Implementation Steps 3. Develop the visitor task. a. Design visitor functionality and car task interface. b. Implement design and integrate with os345 and car tasks. (Don t worry about tickets yet.) c. Use delta-clock to vary visitor time in all lines, museum, and gift shop. d. Observe correct visitor behavior as a visitor moves through the park. 4. Develop the driver task. a. Design driver functionality and interface with visitor and car tasks. b. Implement design and integrate with os345, visitor, and car tasks. (Now is the time to worry about ticket sales and driver duties.) c. Add ticket sales and driver responsibilities. d. When a driver is awakened, use the semTryLock function to determine if a driver or a ticket seller is needed. CS 345 Lab 3 Jurassic Park 32
CS 345 Lab 3 Jurassic Park 33
