联系QQ:928900200
CSCI 3120 Operating Systems
Summer 2014 Handout 3
Assignment 2
Date
Due: June 5, 2014 by 9:00 pm electronically in the SVN
directory
https://svn.cs.dal.ca/3120/<your id>/a2 where
<your id> is your bluenose username.
Problem
1
(5 marks)
a) Describe the actions taken by a
kernel to context-switch between heavyweight processes.
Indicate
if the order of certain actions is important.
b) What, if
anything, changes for a context switch between threads?
Problem
2
(3 marks) Page 153, problem 3.18
What are the
bene ts and the disadvantages of each of the following? Consider both the
system
level and the programmer level. (note, item b is
intentionally missing)
a) synchronous and asynchronous
communication
c) send by copy and send by
reference
d) xed-sized and variable-sized
messages
Problem 3
(3 marks) Page 193, problem
4.18
Consider a multicore system and a multi-threaded program
written using the many-to-many
threading model. Let the number
of user-level threads in the program be grater than the
number
of processing cores in the system. Discuss the
performance implications of the following scenarios.
a) The
number of kernel threads allocated to the program is less than the number of
processing
cores.
b) The number of kernel
threads allocated to the program is equal to the number of
processing
cores.
c) The number of kernel
threads allocated to the program is greater than to the number
of
processing cores but less than the number of user-level
threads..
1
Problem 4
(4
marks)
Consider the following set of processes, with the length
of the CPU burst given in milliseconds
process burst time
arrival time priority
P1 9 0 3
P2 5 2
2
P3 3 3 5
P4 8 5 4
P5 2 6
1
Draw four Gantt charts that illustrate the execution of these
processes using the following
scheduling algorithms: FCFS, SJF,
nonpreemptive priority where a smaller priority number implies
a
higher priority, and preemptive priority where a smaller priority number implies
a lower priority.
Problem 5
(3
marks)
Here is the shortest remaining time rst schedule for the
processes of problem 4:
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7
--- - ----- --- ------- -------------
-----------------
P P P P P P P
1 2 3 5 2 1
4
Calculate the average wait time, average turnaround time, and
average normalized turnaround
time of this
schedule.
Problem 6
(20
marks)
Objective
The objective of this question
is to have you become familiar with programming with the
pthread
library interface and to try a program design that uses
communicating threads and uses polling
to
synchronize.
Overview
You are
going to design a program using a model-view-controller framework. Your program
will
have one main task to accomplish. A \model" thread will
handle that task. You will have separate
threads that provide
windows into the model‘s calculations. These threads are the viewers.
You
will have one additional thread, called the controller, that
will accept input from the user and relay
user commands, as
appropriate, to the model and view threads.
All communication
will be through shared memory.
2
The
task
You have a choice of tasks to accomplish in this framework.
Choose one of the tasks. Both are
essentially the same at their
core and create a time series of results.
Task 1: The game of
life
In the game of life, you are given a two-dimensional grid.
Some cells are set as \alive" and the
others are \dead" as part
of the initial con guration. As we move from one time step to the
next,
cells either become/stay alive or die. The rules work as
follows:
a cell that is currently alive will die in the next
con guration if it has fewer than 2 or more
than 3 neighbouring
cells that are alive.
a cell that is currently alive with 2 or
3 alive neighbours stays alive.
a dead cell with exactly 3
alive neighbours becomes alive.
a dead cell with more than or
fewer than 3 alive neighbours remains dead.
For this task, a
neighbour of a cell is a cell that is immediately touching the current cell to
the
north, east, west, south, northeast, southeast, southwest,
or northwest.
The task is to run iterations of this game and to
report on each iteration.
Represent a cell that is alive with
the value 1 and a cell that is dead with the value 0.
For
example, a 4x4 grid that starts with a vertical bar of live cells works as
follows with the
legend \.1*" :
iteration 0
(start)
.*..
.*..
.*..
....
iteration
1
....
***.
....
....
iteration
2
.*..
.*..
.*..
....
Sample
starting patterns for the grid can be found at
http://en.wikipedia.org/wiki/Conway‘s Game of
Life
3
Task 2: Finite element method
calculation
A nite element method is an approach to calculate
the value of some function over a complicated
surface. The
surface is divided into small areas ( nite elements) and these nite elements
are
connected together through some form of adjacency. You then
iteratively calculate a value for each
nite element based on the
values of its neighbouring elements in the previous
iteration.
In this example, the nite elements will be the cells
of a two-dimensional grid. All cell values
start with value 0
except for the cells on the left and right edges. You will be given xed
values
for the left and right edge elements of the grid; these
cell values do not change across all iterations.
The value of a
cell in the grid at the next iteration is the average value of its neighbouring
cells
(north, south, east, and west) in the current iteration
(normally, the function is more complex than
just an average). A
cell at the top or the bottom has 3 neighbours rather than 4, which is
factored
in to the average calculation.
For
example, consider this rst version of a 4x4 grid where the values may represent
tempera-
tures and where we have a hot spot in one corner (100)
and one edge that is cooled (10):
iteration 0
(start)
100 0 0 10
90 0 0 10
80
0 0 10
70 0 0 10
iteration 1
100
33.3 3.3 10
90 22.5 2.5 10
80 20.0 2.5
10
70 23.3 3.3 10
iteration
2
100 41.9 15.3 10
90 36.5 9.6
10
80 32.1 9.0 10
70 31.1 11.9
10
iteration 3
100 50.6 20.5
10
90 43.2 17.7 10
80 39.2 15.9
10
70 38.0 16.7 10
iteration
4
100 54.6 26.1 10
90 49.4 22.4
10
80 44.3 20.9 10
70 42.0 21.3
10
In a well-behaved system, we hope that these iterations
ultimately converge to a stable set of
values across the grid
that represent the value of the function as applied across the whole
grid.
4
Threads
I describe the
tasks of each thread. How the threads coordinate among themselves will be
described
separately.
Controller
The
controller thread will gather input from the user to modify the behaviour of the
model and
the view threads. Commands to the controller
are:
start view <type> < le> where \type" is
either \full" or \summary" (explained later). This
command
begins a new view thread for the speci ed elements, assigns a view number to
it,
and prints that view number to the user. There will be at
most 3 views.
view < X > legend <legend info>
where X is the view number that we are modifying and
\legend
info" is a string that alternates a character and a number (with a space
between
each), like \e 10 f 20 g" and means that when printing
the grid, any value < 10 is printed as
\e", any value 10
and < 20 is printed as f, and any value 20 is printed as g. This
legend
can have more than just two boundary
cases.
model < lename> to have the model switch its
operation to use the content of < lename>
as a starting
con guration for a new set of iterations on the grid.
end { to
end the operation of the whole system
cleanly.
Model
The model does the calculations
of one of the two tasks previously described. Which one is up
to
you to choose.
The model will have a
\published" grid and a \work" grid. View threads will look at the
content
of whatever is identi ed as the published grid to
display.
When started, the model should be passed a le name that
contains the initial con guration
for the problem. Put that con
guration into the published grid. Then, it creates the next
iteration
of the problem in the working grid. When done, it will
make the information of the working grid
available as the
published grid.
When the controller gives the model thread a new
lename, the controller gets to nish its
current grid and
publishes it before starting with the content of the new
lename.
Along with the published grid, the model grid updates an
interaction count number to let the
view threads know the
iteration number of the published grid.
View
A
view thread copies information about the published grid into a le. The lename is
provided as
the view is created.
There are two
types of views: a full view and a summary view. A full view will print
the
iteration number of the grid and will then print the entire
contents of the grid to the le. It will
use a legend to
translate the values of the grid into single characters. The operation of the
legend
has been done in the controller part of this write-up.
Without a legend speci ed, the full view
will
5
use the legend \. 1 *" | so anything less
than 1 will be a period and any value 1 or more is a *.
If the
legend is a single character (no cases) then print the values of the grid
directly using 4 digits
with 1 decimal point of
precision.
For example, a full view of the FEM \iteration 4"
sample data in this description with legend
\. 25 : 50 * 75 #"
would appear as:
iteration
4
#*:.
#:..
#:..
*:..
A
summary view prints the iteration number of the published grid and then prints a
value that
represents the grid. If you are programming the game
of life then you print the number of cells
that are alive. If
you are programming the nite element model then you print the average
value
of all cells to 1 decimal point of
precision.
When the view is asked to end, it closes its
le.
Data structures
The model and all views must
be able to see the published grid and the iteration
count.
Messages
All messages will be passed
through shared memory. So a message is passed from the controller
to
the model by both threads having access to a common variable
value. I recommend putting all the
values in one struct and
passing a pointer to that struct to the threads as they are
created.
The controller must be able to send the following
information to the model:
a le name
the
number of view threads that need to read the published grid
The
model must be able to send the following information to the controller in
response to a
message from the controller:
the
iteration number when the new number of view threads send by the controller to
the
model should begin printing the published
grid
The controller must be able to send the following
information to the view threads:
a new print
legend
The view thread has no information to return to the
controller.
How will the threads know that there is a message
waiting? They will look to a shared variable
value. The
controller will share a value with the model thread and with each view thread.
We‘ll
generically call these variables \message ready"
variables. All these variables begin with a value of
0. When the
controller has data to send to the model thread, it will wait for the \message
ready"
variable with the model thread to be 0, will copy the
values to send to a place where the
model
6
thread can nd them, and will then set
the \message ready" variable value to 1. If the controller
needs
a response, it can then wait for the variable value to return back to 0 and read
the response
from memory.
The model and the view
threads will periodically poll the shared \message ready" variable
that
they share with the controller. If the value is 1, it will
copy out the message information, set-up
any response
information needed (model to controller) and then set the \message ready"
variable
value back to
0.
Synchronization
Synchronization is about how
the threads coordinate among themselves. For example, you
don‘t
want a view thread to be printing the published grid if
the model thread is changing it at the same
time. Here is how
the synchronization will work:
A view thread will know which
iteration grid it has last printed. The view thread will poll
the
iteration number for a change. When the iteration number of
the published grid increases then the
view thread will print the
new grid and will again wait for the iteration number to
increase.
The view threads and the model thread will need to
share one variable, call it \printed" for
now. When a view
thread nishes printing the current grid, it will increment the \printed"
variable
by 1.
The model thread will create its
working grid values. Once the working grid is ready to
be
published, it will poll the \printed" variable. Once the
\printed" variable‘s value matches the
number of view threads
that the controller has told to the model thread, the model thread
sets
\printed" to 0, updates the published grid, and nally
increments the iteration number by 1. It
can then go on to
calculate the next working grid while the view threads copy out the
published
grid.
When a view thread is to be
created, the controller will rst notify the model of the new
number
of view threads, will get back which iteration the view
thread can begin to look at the published
grid, and will then
pass this grid value to the new view thread as part of its start-up
information.
Model pseudocode
The model requires
the most synchronization, so I will provide some pseudocode for it. There
are
still details for you to ll in, especially where to connect
with the shared data.
loop:
/* Poll for
instructions from controller */
if "message ready" from
controller = 1:
determine the type of
message
make a copy of the appropriate variable values from the
message
if being notified of new view
threads
put next grid iteration number where the controller can
find it
if being notified of a new file
name
remember the new file name
set "message
ready" from controller = 0
7
if I have a new
file name
load the new file name as the working
grid
else
calculate next iteration of the
grid
/* Poll for all the viewers to be done with the earlier
published grid */
while printed < number of view threads for
the current grid iteration
do nothing
printed =
0
/* Publish the next grid */
make the
calculated grid available as the published grid
increment
current grid iteration number by 1
include a delay to slow down
the model
Input le formats
The input le for the
game of life has two integers on the rst line as the number of rows and
then
the number of columns in the grid. Each subsequent row will
contain a number of characters that
matches the number of
columns and is either 0 for a dead cell or 1 for a live
cell.
For example, the le for the game of life example given
earlier is:
4
4
0100
0100
0100
0000
The
input le for the nite element model has two integers on the rst line as the
number
of rows and then the number of columns in the grid. The
next line has a list of space-separated
integers that correspond
to the top-to-bottom values of the left column in the grid (so a number
of
integers matching the number of rows). The rows after that
has a list of space-separated integers
that correspond to the
top-to-bottom values of the right column in the grid.
For
example, the le for the nite element model given earlier is:
4
4
100 90 80 70
10 10 10
10
Moving forward
DO NOT START WRITING THIS
PROGRAM WITH THREADS! Implement the model and
views as functions
and then have some unthreaded program call the model to calculate one
iteration
of the grids followed by calling the view function and
then calling a controller function to look for
user data. Only
after you have the whole ow working should you begin to add the
threading.
8
Plan out all your data structures
and code before starting. It will save you headaches later
on.
To start, assume that the grid size is no bigger than
100x100. Once your code is working you
can then worry about
always allocating the appropriate grid size as given in the
le.
Avoid global variables if you can. This assignment can be
done with no global variables.
However, if it‘s easier to start
with global variables then use them to get going.
Grading
Scheme
documentation, coding style, modularity, error codes,
memory management | 3
the model calculation works |
3
the viewer operations work, including the legend functions |
2
the controller gets appropriate commands |
2
the model, viewer, and controller interoperate properly as
threads, including using several
viewers at once |
5
your solution that includes threads provides isolation of
information between threads and
does not use global variables |
2
test cases | 3
9