Lab 3 Multiprocess
AU 2021 CSE 2421 Lab 3
Dates
Early before 11:58 PM Monday 27-September-2021
On time before 11:58 PM Thursday 30-September-2021
Late until 11:58 PM Friday 1-October-2021
Topics
Structs
Dynamically allocated memory
Function pointers
Version
Version 2 – see highlighted text on page 4
Table of Contents
AU 2021 CSE 2421 Lab 3 ………………………………………………………………………………………………………………. 1
Dates …………………………………………………………………………………………………………………………………………. 1
Early before 11:58 PM Monday 27-September-2021 ………………………………………………………………… 1
On time before 11:58 PM Thursday 30-September-2021 ………………………………………………………….. 1
Late until 11:58 PM Friday 1-October-2021 …………………………………………………………………………….. 1
Topics ………………………………………………………………………………………………………………………………………… 1
Version ………………………………………………………………………………………………………………………………………. 1
Version 1 ………………………………………………………………………………………………………………………………… 1
Changes Compared to Lab 2 …………………………………………………………………………………………………………. 2
Multiple processes at one time …………………………………………………………………………………………………. 2
Refactoring ……………………………………………………………………………………………………………………………… 3
The main loop …………………………………………………………………………………………………………………………. 3
Structs ……………………………………………………………………………………………………………………………………. 3
Simulation Structure …………………………………………………………………………………………………………….. 3
Process Structure …………………………………………………………………………………………………………………. 4
Input ………………………………………………………………………………………………………………………………………….. 4
Output ……………………………………………………………………………………………………………………………………….. 4
Dynamic memory …………………………………………………………………………………………………………………….. 4
Ending the simulation ………………………………………………………………………………………………………………….. 5
Event Changes …………………………………………………………………………………………………………………………….. 5
Start Event ………………………………………………………………………………………………………………………………. 5
End Event ……………………………………………………………………………………………………………………………….. 6
Time Check ……………………………………………………………………………………………………………………………… 6
IO Call …………………………………………………………………………………………………………………………………….. 6
IO Complete ……………………………………………………………………………………………………………………………. 6
Run ………………………………………………………………………………………………………………………………………… 6
The Linked List Library …………………………………………………………………………………………………………………. 6
Building with the list library ………………………………………………………………………………………………………. 6
Typedef signatures …………………………………………………………………………………………………………………… 7
Action Functions ………………………………………………………………………………………………………………….. 7
Comparison Function ……………………………………………………………………………………………………………. 7
Criteria Functions …………………………………………………………………………………………………………………. 7
Library functions ……………………………………………………………………………………………………………………… 7
Insert ………………………………………………………………………………………………………………………………….. 7
deleteSome …………………………………………………………………………………………………………………………. 7
Iterate ……………………………………………………………………………………………………………………………………. 8
Prototypes and the list ……………………………………………………………………………………………………………… 8
Multiple Files ………………………………………………………………………………………………………………………………. 9
No Global Variables! Code Must Compile! …………………………………………………………………………………….. 9
Submission …………………………………………………………………………………………………………………………………. 9
Changes Compared to Lab 2
Multiple processes at one time
Lab 3 will hold as many processes as it needs. A start event does not overwrite an existing process like it
did in lab 2. Since we have more than one process, we will have lists to hold all of them. We need 4
lists, corresponding to the 4 states a process can be in. If a process changes state, it will have to move
from one list to another. Completed processes are deleted shortly after they complete.
Refactoring
Event code and output code will require the most refactoring. The ideas in the event code will be kept,
but the implementation will change. Both need to be refactored to deal with structs and with the linked
list library.
The main loop
The main loop remains wrapped around the same reading of the input as before. Inside that loop if we
have a valid event we will need to:
Increment the step
Clear all completed processes off that list
Handle the event
Output everything
Structs
Lab 3 needs 2 different kinds of structures, a simulation structure and a process structure.
Lab 3 uses structs, so we don’t have to pack and unpack the psw quite so often. Text printing will need
to pack the psw in order to print it. Reading in a new process event will need to unpack the read-in psw
to get the PID and priority out of it.
Be sure to pass pointers to the structures instead of the structures themselves. You can’t avoid this for
process structures and it is a very good idea for the simulation structure.
Simulation Structure
This structure holds our “world” data. It will need a void pointer to act as the head of the list for the 4
lists we need. We need one for completed, blocked, ready, and running processes. We also store the
step number here. Your code will need exactly one of simulation structure. It should not be dynamically
allocated.
Regarding those 4 head pointers:
They should be initialized to NULL.
They can be compared to NULL to see if a list is empty
They can be passed to functions such as iterate
Their address can be passed to functions such as insert and deleteSome
No other operations can be done on them.
Process Structure
This structure holds the 4 data items we used to pack into the psw, plus an integer to hold the “run
time” for the process. We won’t store a psw for our processes when the struct gives far easier access to
the data. This structure also holds a pointer back to the simulation structure that the process is part of.
This design choice makes the code far easier to write. Your code will dynamically allocate a new process
structure every time it handles the start event. It will free that structure when the process is removed
from the simulation.
Input
Input is identical to lab 2. We read it the same way.
Output
Output is grouped by state for both text and graphics and ordered within each state. Lab 3 output is in
priority order. Text output will print a header line showing what section is being listed. In the output
below there is one process in the system and it is on the ready list.
Step 1:
List __PSW__ PRI PID TICKS STATE
COMPLETED
BLOCKED
READY
0x800012D687000402 128 1234567 4 2
RUNNING
Step 2:
List __PSW__ PRI PID TICKS STATE
Note that after the printing for as step is done an extra blank line gets printed at the end.
In text mode, when a process is taken out of the system, print a message showing the runtime as well as
the number of processes that have been freed.
In graphics mode, always pass 0 as the value for event. [not step, pass step to os_clear as before]
Your master output function should call your printed output routine if in text mode and it should call
your drawn output routine if in graphics mode. Both of those will need to do any output setup, call
iterate 4 times, and then do any output finalization. These two and anything they call already know
what mode they are in and won’t need to check.
Dynamic memory
Once a process is read in successfully, it should be copied to dynamic memory supplied by calloc or
malloc. Each time a process is allocated or freed, a diagnostics message must be printed that includes
the count so far of allocations or frees. See below for examples, see any of the supplied output files for
a full set. All code that allocates or frees processes must be together in a separate C code file away from
other code. If allocation fails, an error message should be printed. If your code uses malloc, change the
message to match.
DIAGNOSTIC: allocate_process. 1 allocated so far.
ERROR: allocate_process: calloc failed
DIAGNOSTIC: recycle_process on PID 1234567 which ran 0. 1 freed
Our code is required to free any dynamic memory it allocates before the program ends. Your allocation
routine and your free routine should have static ints to store the count of the number of processes that
have been allocated and freed. The counts should match.
Ending the simulation
When the core simulation loop stops, run delete on all lists to purge them, recovering all allocated
memory. Use a criteria function that always returns true and a disposal function that causes the process
structure to be freed.
Event Changes
The event code from lab 2 is based on fundamental assumptions that are no longer true in lab 3. The
master event handler will need the event number, the read-in value, and the pointer to the simulation
structure. It will use a jump table to call the correct handler. All of the handlers will need the same
signature, so they should be passed the pointer to the simulation structure and the read-in value.
Any moves from one list to another will be accomplished by using delete. That will search the source list
for processes that need to move and will delete them from that list. The disposal function in such cases
will call insert to put the process on the destination list. That function will also do any appropriate
changes to state and ticks.
If an event needs to find a PID and can’t find it in the expected list or lists, print an error message. Check
the return value coming from delteSome.
Start Event
To handle the start event, unpack the PID and priority from the read-in value. If your dynamic allocation
routine successfully gives you a process structure, fill in the new process members and insert it into the
ready list of the simulation structure. It will have a runtime of zero, state will be READY, and it will have
default ticks.
Implement this event first and then test. Use the z2t1 test file (just the first line of zclean). Don’t bother
with other events until this one works. Build a little, test a little! Once this works, you can take a break
from events and test output routines.
End Event
Run delete on the running, ready, and blocked lists looking for the read-in PID. Between them there
should be exactly 1 delete taking place. The delete will move the process to the completed list (and
change its state). The criteria function used by delete will need the read-in PID.
Time Check
Iterate the running list, decrementing any ticks values above zero. It also increments the run time
variable held by each running process. Then make a separate call to delete from the running list using a
criteria function that looks for zero ticks. These will be moved to the ready list and have their state
changed.
IO Call
Delete from the running list, looking for the process with the read-in PID. Move it to the blocked list.
Change the state. Check that exactly one process was moved.
IO Complete
Delete from the blocked list, looking for the read-in PID. Move to the ready list, changing state. Check
that exactly one process got moved.
Run
Delete from the ready list, moving to the running list. Change state and give it the default number of
ticks. Check that exactly one process got moved.
The Linked List Library
There are various functions provided in the linked list library. Please make sure that your code only has
one function processing a given list at a time. The list code is not re-entrant safe. You can be deleting
on one list at the same time you insert into another, but never have two operations live on the same list
at the same time.
The list is fully generic. Your code doesn’t know the type of the list nodes. The list code doesn’t know
the types of your data that you are putting on the list. It also doesn’t know the names of any functions
in your code the list might need to do its job.
Your code is required to assign any void pointer value it got from the list to a strongly typed pointer. Do
not cast void pointers, assign them and then use the strongly typed pointer.
The linked list zip file contains node.h file. Delete it after you unzip it. Your code must not use this
information.
Building with the list library
Your makefile might need something like this:
# all of my dependencies must be dot o files
gcc -g -o $@ $^ -L. -los -llinkedlist –lncurses
Typedef signatures
These signatures make using the required function pointers easy.
Action Functions
typedef void (* ActionFunction)( void *data);
Action functions are used to do things to the data you stored on the list. The action function is given a
pointer to a process structure. An example action function would be one that outputs a process.
Another use of an action function is to deal with the data held by a node that is about to be deleted. It
should either be freed or placed on a different list.
Comparison Function
typedef int (* ComparisonFunction)(void *data1, void *data2);
A comparison function takes two pointer to process and returns a Boolean indicating true when the first
process belongs earlier in the list than the second process. You will write comparison functions and pass
their address to parameters of this type.
Criteria Functions
typedef int (* CriteriaFunction)(void *data, void *helper);
A criteria function is used to give back a Boolean value. The data value will be a process structure and
the helper value will be a pointer to some chunk of data that may be helpful when making the decision.
Some criteria functions will ignore the helper value since they can make their determination based on
the process alone. Other criteria functions will need the helper value, most often a pointer to a PID that
the criteria function is searching for. The “always true” criteria function will ignore both parameters.
Library functions
Insert
/* int returns FALSE when it fails to do the insert */
int insert(void *p2head, void *data, ComparisonFunction goesInFrontOf, int text);
Because of call-by-value, the first parameter is the address of the head pointer of the list you want to
insert the process on. The data will be a pointer to a process. The comparison function will check
priority to keep the list in priority order. The text parameter will always be passed TEXT.
deleteSome
int deleteSome(void *p2head, CriteriaFunction mustGo, void *helper,
ActionFunction disposal, int text);
This function is used to remove nodes from a linked list. It gets passed the address of a head pointer
since it may need to alter that pointer. The criteria function passed yields true if the node needs to be
removed. The helper is a pointer to a data item that might be useful to the criteria function, such as the
address of a PID. The text parameter will always be passed TEXT.
A common use of deleteSome is to move a process from one list to another. The criteria function,
possibly with the help of the helper value, decides if the process needs to leave the list. If so, the action
function will be called. The action function then uses the Simulation pointer held by the process
structure to put the process on a different list by calling insert. If that insert fails, the action function
should free the process in order to avoid a memory leak.
deleteSome returns the total number of nodes deleted.
Iterate
void iterate(void *head, ActionFunction doThis);
Iterate walks through the list, passing each data item on the list in turn to the action function. The
action function does whatever it does to the process structure (we only have process structures on our
lists) and then goes on to the next node in the list. Since iterate does not cause any nodes to enter or
leave the list, the first parameter is a head pointer not the address of the head pointer like insert and
deleteSome need.
Prototypes and the list
The list really doesn’t care what type it holds, as long as your code coughs up a pointer to that data. The
easiest way to do prototypes with the list – strongly suggested – is to use strings. They are pointer
friendly and print easily and recognizably. Consider this code:
rval = insert ( &list, “Go Bucks!”, first_letter, 1);
Here list is a pointer to void, first_letter is a comparison function that compares the first character of
two strings and returns the result of numerically comparing them. Then call
iterate(list, print_string);
Here print_string is an action function that prints a string (pointer to char) that came in as a pointer to
void.
Don’t bother with process structures when prototyping the list. Make sure that you can use all three of
the list functions. Start with insert and use iterate to test it. Then do a few insertions and delete one
thing from the list and use iterate to print what’s left. Say you insert stirrings that start with both upper
and lower case characters and you delete strings that start with a lower case letter.
Your last list prototype might be:
Have two lists, declare both void pointers outside any block, making them global. This is the one
time in this class that you can get away with this.
Load one with insert, use iterate to print both lists
Use deleteSome to pull certain items off the first list
The disposal function should put those items on the other list. You’ll need to exploit the fact
that the second list is a global.
Print both lists using iterate
Moving data between lists is a core functionality in this lab, prove it in a prototype before you bury it
hip-deep inside an event handler with structs, pointers, and dynamic memory.
Multiple Files
Your code will be split over at least 5 files:
All functions that pack and unpack the psw will be grouped together in a separate file. Only this
file can include the bit position defines. Consider writing this file first and incrementally testing
the functions with prototypes.
All functions that know what the event numbers are get grouped together in a separate file
along with the individual event handlers. This is the 6 event handlers and the code that selects
them given an event number. The code to validate an event number lives here. Only this file
can include the event number defines. This is the core functionality of the lab but the parts can
be tested individually with prototypes.
The main function shall be in the lab2.c file, along with only the highest level functions.
All output functions that print or draw a process will be in a separate file.
The code to allocate and free dynamic memory for processes must be in a separate file.
The linked list will need various callback functions. Output related functions are mandated to be in the
output file. Nearly all of the rest of the callback functions could be placed in a separate file. This will
make them easier to write since there will be functions with similar structure already in the file when
you need to create another. Consider putting your criteria, action, and comparison functions in groups
in that file.
No Global Variables! Code Must Compile!
Global variables is a -10 penalty. Errors or warnings in compilation means no credit for the lab, though
you might get 2 points if your prototypes are there and compile cleanly.
Submission
Effectively: Same as lab 1. Your zip file needs to contain README_LAB3, all the code to be graded, and a
makefile sufficient to build all of the targets that are to be graded. Those targets include lab3 and at
least 4 working prototypes. Do not include any .o files or the lab3 executable. Any file you edited by
hand (other than test data) probably needs to be included. Files generated by the compiler should not
be included.
All files that you edit by hand must have your name in them.
Any code that comes from the instructor’s lab 2 must retain proper attribution.
README_LAB3 text:
THIS IS THE README FILE FOR LAB 3.
BY SUBMITTING THIS FILE TO CARMEN, I CERTIFY THAT I HAVE PERFORMED ALL
OF THE WORK TO DETERMINE THE ANSWERS FOUND WITHIN THIS FILE
MYSELF WITH NO ASSISTANCE FROM ANY PERSON OTHER THAN THE
INSTRUCTOR OF THIS COURSE OR ONE OF OUR UNDERGRADUATE GRADERS.
The readme should contain your name, the number of hours you worked on the lab, and any
comments you want to add. Of particular interest are what was hard or easy about the lab or
places where programming reinforced what we went over in class.