CS计算机代考程序代写 compiler Lab 3 Multiprocess

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

lab3:

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.