|
Programming Assignment #1 --- POSIX Threads
Your task in this assignment will be to write a routine which creates
threads, has them do work in parallel, and then terminates when the last
thread has completed.
The Setup:
There are several students sitting near each other rooting for their
favorite teams. Each student will cheer for his or her team some
given number of times, with a random pause (between 2 and 5 seconds) between
each cheer. For some reason, there may be as many as 10 teams present,
with one cheering for each team.
The Program:
Your task is to write a program which will simulate this cheering.
The program should be called cheer.c, ands the Makefile should
generate an executable called cheer. When the program
is run from a commandline prompt, arguments may be given to specify which
teams should be cheered for, and how many times. The main()
routine then creates a thread for each team, and each thread is responsible
for cheering the specified number of times and for the correct team.
A cheer for a particular team looks like this: "Go Pirates!"
A sample run would look something like this:
csci 02% cheer Mets 3 Yankees 1 Cardinals 4 Twins 3
Go Mets!
Go Yankees!
Go Cardinals!
Go Twins!
Go Cardinals!
Go Mets!
Go Mets!
Go Twins!
Go Cardinals!
Go Twins!
Go Cardinals!
csci02%
Note that a second run with the same commandline arguments would probably
not generate the same output, since each fan waits a random amount of time
between successive cheers.
Grading:
5 points: Comments and Function contracts
10 points: Design of the thread function
10 points: Clarity of the main() function
5 points: The Makefile
Resources:
Sun
Microsystems' Threads Page
Of particular interest on that page are the pthread_* functions, particularly
the create, yield, join and exit functions.
Since the version of UNIX that we will be using is Sun's Solaris
(running on Dell machines), it is best to go to Sun's site for information
about how threads and processes are implemented there. Here are some
articles that you may find useful:
The Lightweight
Process Pool
A Primer
on Signals, Part 1
The Solaris[tm]
operating environment process model, Part 6
Hints:
You might want to check out the man pages for:
pthread_create
pthread_join
pthread_exit
sleep
To compile your program, you will need to link in the pthread library.
So a typical compile command might look like:
gcc myprogram.c -lpthread
Submission:
To turn in your program, you use the electronic handin procedure:
/export/stu/classes/cs4630rh/bin/handin cs4630rh 1 cheer.c Makefile |
|
Programming Assignment #2 --- Writing a
Scheduler
Note: sched.c was update on 2/25. You should download
the new version, as it has 2 small changes...
Your task in this assignment will be to write a scheduler function which
will implement a two-queue round-robin scheduler.
The Setup:
Our scheduler will be implemented as a function that every thread should
invoke frequently - a few hundred times per second, in fact. Every
time the scheduler() function is called, the scheduler makes a decision
as to which thread should be running at that time. It uses the thr_suspend()
and thr_continue() functions to make sure that only one thread can
run at a time.
Each thread can have either low priority (0) or high priority (1).
The scheduler maintains a queue for each of these priority levels.
Our timeslices are 3 seconds in length, and our "starvation duration" is
20 seconds. This means that when a thread is put on the CPU (which
means that it has been "continued" in our scenario) the scheduler should
make sure that after 3 seconds, it will take that thread off the CPU (by
"suspend"ing it) and make a new scheduling decision. But if 20 seconds
have elapsed with only high-priority threads being run, then the scheduler
will schedule a waiting low-priority job, if there are any.
A Thread Control Block (TCB), implemented as a global structure, contains
pointers to the first thread in each queue. It also contains the
time information mentioned in the preceding paragraph. Threads are
responsible for registering and deregistering themselves with the TCB.
What You Need to Do:
Create the three functions thr_register, thr_deregister
and scheduler:
| void thr_register(int priority, thread_t id);
This function adds the thread to the appropriate queue. (Be careful
when this thread is the first in its queue.) |
void thr_deregister(thread_t id);
This function finds which queue the thread is in and removes it from
that queue. |
void scheduler();
This function looks at the timing information in the TCB, as well as
which queues have available threads, and decides which thread should be
allowed to continue. Most of the time the scheduler will simply return
without having to suspend any thread, because the current timeslice has
not expired.
Our scheduling policy is as follows: The scheduler will always
try to schedule a high-priority thread first. But if 20 seconds have
elapsed with only high-priority threads being scheduled, then the scheduler
will schedule a low-priority thread, if there are any waiting. Within
each priority level, threads are scheduled in round-robin fashion. |
Feel free to modify any of the structures that I have given you in the
header file (see "Resources" below). For example, if you feel that
the TCB needs to have some more fields, go right ahead and add them.
But, as always, make sure your comments explain what that field is for.
Or if you'd like to implement your queues as doubly-linked lists (instead
of the singly linked lists that I have implicitly indicated) then go right
ahead. But please let me know in your comments.
Resources:
I have created two files to get you started: sched.h
and (as updated on 2/25) sched.c
Also, you will probably want to refer to the following functions which
can be found on Sun's
Thread page: thr_suspend, and thr_continue, as well as
the usual pthread_create and pthread_join that you have already
used.
Handing it in:
You will use the electronic handin proceduer, just as you used it for
the first assignment. More details will come, but basically it will
amount to handing in your new versions of sched.h and sched.c, as well
as a Makefile. For now, work on getting the scheduler working.
To hand it in, type: /export/stu/classes/cs4630rh/bin/handin
cs4630rh 2 file1 file2 file3 ...
Where file1, file2, file3, ... refers to all the files you want
me to take a look at.
Notes:
This project contains some data structures that are shared among threads.
In this assignment, as written, there should be only one thread running
at a time, so we don't have to worry about simultaneous access to shared
resources (race conditions). Your next assignment will ask you to
solve this "problem" by using the mutex and semaphore libraries provided
by Solaris. |
|
Programming Assignment #3 --- Simulated
Memory Management
This assignment has two parts, and the first part has two options.
Part 1:
->option 1:
Add the code necessary to your sched.c from Assignment #2 so that the
conflict in access to shared memory structures is avoided. The easiest
way to do this is to use the mutex provided by Sun's thread library.
You can read all about them here,
with examples. I gave another example out in class, which can be
found here.
->option 2:
Implement a solution to the dining philosopher's problem. The
pseudocode for this can be found in your book or in a thousand places on
the web. Your implementation must be in C++, and must use the sem_*()
functions from Sun's thread library. Your program should take two
commandline arguments: The first is the number of philosophers (an
integer larger than 2), and the second is the number of times each philosopher
should eat (an integer in the range 1..1000.). Each philosopher should
start out thinking, and announce when he has begun to eat, and when he
has begun to think. Your makefile should specify that your compiled
program is called "dine."
Thus, the following might be a transcript: (Of course, it would
be more interesting with more than three philosophers.)
dine 3 2
Philosopher 1 thinking
Philosopher 1 eating
Philosopher 2 thinking
Philosopher 3 thinking
Philosopher 1 thinking
Philosopher 2 eating
Philosopher 2 thinking
Philosopher 3 eating
Philosopher 3 thinking
Philosopher 1 eating
Philosopher 1 thinking
Philosopher 2 eating
Philosopher 2 thinking
Philosopher 3 eating
Philosopher 3 thinking
Part 2:
We saw four algorithms for placing processes into holes in memory:
best fit, worst fit, next fit and first fit. Your job is to write
a simulator which will take processes of varying sizes, load them into
memory according to each of those rules, and swap processes out as needed
to create a larger hole. Let us make the following assumptions:
-
Memory is of size 128MB
-
The size of each process will be some whole number of megabytes in the
range 1..128
-
An initial list of processes and their sizes is loaded from a file, which
is the only commandline argument. These processes should be loaded
into a queue of processes waiting to be loaded into memory.
-
Memory is initially empty. (We will ignore the operating system.)
-
If a process needs to be loaded but there is no hole large enough to accomodate
it, then processes should be swapped out, one at a time, until there is
a hole large enough to hold the process that needs to be loaded.
-
If a process needs to be swapped out, then the process which has been "in
memory" the longest should be the one to go.
-
When a process has been swapped out, it goes to the end of the queue of
processes waiting to be swapped in (see next item).
-
Once a process has been swapped out for a third time, we assume that that
process has run to completion, and it is not requeued. Note:
not all processes will be swapped out for a third time.
You can use whatever data structure you wish (eg. linked list, bitmap)
to simulate memory usage, but please make sure that the comments in the
file clearly indicate what data structure you are using and how it is implemented.
The "process file" will be in the following format: Process id
(a single letter) <space> process size (an integer). Here is a
sample process file:
A 13
B 99
C 2
D 2
E 44
F 32
G 2
H 9
Your program should do the following:
-
Each time a process is loaded into memory, a line should be printed along
these lines
F loaded, #processes = 5, #holes = 3, %memusage = 41, cumulative
%mem = 40
%memusage refers to the percent of memory that is currently
occupied by processes, and cumulative %mem gives the average of
all the
%memusages up until and including the current process
load.
-
When the queue is empty, a line such as the following should be printed:
Total loads = 33, average #processes = 14.4, average #holes = 6.3,
cumulative %mem = 62
This program should be called holes.c, and should take a single commandline
argument as indicated above: a.out testfile1 |