Simulate Processes in a System
AU21 CSE 2421 Lab 2 – Process Control
Version
V0.99 Thursday evening 2-Sept-2021 (lacks graphics and timing)
V1.0 has graphics and timing (Monday evening 6-Sept-2021)
Dates
Early before 11:58 PM Saturday 11-September-2021
On time before 11:58 PM Monday 13-September-2021
Late until 11:58 PM Tuesday 14-September-2021
Contents
AU21 CSE 2421 Lab 2 – Process Control …………………………………………………………………………………………. 1
Version ………………………………………………………………………………………………………………………………………. 1
V0.99 Thursday evening 2-Sept-2021 (lacks graphics and timing) ………………………………………………….. 1
V1.0 has graphics and timing (Monday evening 6-Sept-2021) ……………………………………………………….. 1
Dates …………………………………………………………………………………………………………………………………………. 1
Early before 11:58 PM Saturday 11-September-2021 ……………………………………………………………….. 1
On time before 11:58 PM Monday 13-September-2021 ……………………………………………………………. 1
Late until 11:58 PM Tuesday 14-September-2021 ……………………………………………………………………. 1
Required Reading ………………………………………………………………………………………………………………………… 2
The Unusual ……………………………………………………………………………………………………………………………….. 2
Overview ……………………………………………………………………………………………………………………………………. 3
Topics ………………………………………………………………………………………………………………………………………… 3
State Data…………………………………………………………………………………………………………………………………… 3
The Process Status Word ……………………………………………………………………………………………………………… 4
Casting ……………………………………………………………………………………………………………………………………….. 4
Events ………………………………………………………………………………………………………………………………………… 5
Input ………………………………………………………………………………………………………………………………………….. 5
Output ……………………………………………………………………………………………………………………………………….. 6
Text Output …………………………………………………………………………………………………………………………….. 6
Normal Output …………………………………………………………………………………………………………………….. 6
Diagnostics ………………………………………………………………………………………………………………………….. 6
Debug Messages ………………………………………………………………………………………………………………….. 6
File Input and Output ……………………………………………………………………………………………………………. 7
Graphical Output……………………………………………………………………………………………………………………… 8
Using the libos library ………………………………………………………………………………………………………………. 8
Step zero: ………………………………………………………………………………………………………………………….. 10
Step one: …………………………………………………………………………………………………………………………… 11
Step two: …………………………………………………………………………………………………………………………… 12
Step three ………………………………………………………………………………………………………………………….. 12
Integration: ……………………………………………………………………………………………………………………….. 12
Multiple Files …………………………………………………………………………………………………………………………….. 12
No Global Variables! Code Must Compile! …………………………………………………………………………………… 13
I got the lab done and I’m bored …………………………………………………………………………………………………. 13
Plan of Attack ……………………………………………………………………………………………………………………………. 13
Submission ……………………………………………………………………………………………………………………………….. 14
Required Reading
By inclusion, the following 2 documents are part of this lab:
Thoughts on lab 2 and single purpose
https://piazza.com/class_profile/get_resource/ks85udc0zya139/ks85uhpj9zi1aj
Doing labs in this class
https://piazza.com/class_profile/get_resource/ks85udc0zya139/ks85ufpzeqg174
These are on piazza in the Labs section of the resources.
The Unusual
Any of the following are -10
https://piazza.com/class_profile/get_resource/ks85udc0zya139/ks85uhpj9zi1aj
https://piazza.com/class_profile/get_resource/ks85udc0zya139/ks85ufpzeqg174
Global variables
#include of code files / including executable code
Overview
Labs 2-4 deal with the simulation of the part an operating system that deals with processes (running
programs). Our simulation takes cues from real operating systems, but it is simplified and changed to
make the task appropriate to this class. Systems 2 will deal with this in far more depth. Lab 2 is “a day
in the life of a process, the movie version.” We will look at events that happen to a process and track
some of the state data needed to manage it.
Lab 2 is the basis for labs 3 and 4 where the world gets more complicated.
This lab has a primary mission of teaching you about C programs. It might not be completely accurate
about how the “system” works. Some of the technical details are to give you experience with aspects of
the language more than anything else.
Our simulation will create processes and change their state. We will do one at a time, but our code will
be written expecting an environment where we have more than one in the simulation at a time (lab 3).
Topics
Basic I/O
Multiple file development
Bitwise operations
Basic C control structures (functions, loops, if, switch, etc)
Careful use of type and the ramifications of using various sizes of data
Building with libraries
Measuring real-time performance
State Data
For the simulation itself, we keep one data item:
Step number. Start at zero and go up by one each time a valid event is read. Use the easiest
data type for simple decimal numbers. The first line of table data will be step 1.
The current PSW (see below) that holds the data for one process
For our simulation, a process has the following data:
State: Use unsigned char for state. Use #defines for the following valid values
o RUNNING is 1
o READY is 2
o BLOCKED is 128
o COMPLETE is 255
Priority: Use unsigned char for priority. In Linux, values of 0 to 99 are for real-time processes
and 100-139 is for user processes.
PID: The abbreviation is for “process ID,” PID can run as high as 2^22, so it fits just fine in an int.
You can use pid as a variable name, but not PID.
Ticks: Use an unsigned short for ticks. The operating system evaluates long running processes
and periodically will suspend them, moving them to the READY state and placing them in the
correct place on that queue. This allows other processes a chance to run. Each tick represents
a certain amount of time. Each time our system checks the processes that are in the RUNNING
state, it decrements the number of ticks. When ticks hits zero, the process is suspended.
We will pack those 4 items into the PSW, see next section.
The Process Status Word
In lab 2, your program will store the four items of state data above in an unsinged long, the process
status word (PSW). [The name is pirated from some microprocessors that have a processor status
word.] Your code will pass the PSW instead of passing the four state variables. More importantly, a new
PSW can be returned by functions that modify the process state. That means your code will need the
capability to pack and unpack the PSW into and from its four parts. The bit layout of the 64 bit unsinged
long must be as follows:
Going from most significant bits of the PSW to least significant:
8 bits for priority
32 bits for PID
16 bits for ticks
8 bits for state
You might want to look carefully at bitwise AND and OR. Along with that, bit shifting might be useful.
The truly adventurous student might consider a few C macros. Use #define for the constants, do not use
macros with code in them. You can use psw as a variable name but not PSW.
Any code that knows the layout of the PSW must be in a separate file from all other code.
Casting
Your code will do conversions between different sized data items. Your code may need explicit casts to
operate correctly. Anytime your code converts to a smaller sized variable from a larger sized one, an
explicit cast is required. Doing so tells anyone who reads your code that you understand that
truncation is taking place and you are doing so intentionally. In some development environments, this
prevents a warning. Consider the following gcc flag:
-Wconversion
Add this flag to your makefile along with the 4 we talked about in class and on the slides. You should fix
your code so that there are no warnings.
Events
In our simulation, we will simulate the following events:
Process start – the process is created and made ready to run. It is given the default number of
ticks and put in the ready state.
Process end – the process has completed and the O/S should do any final cleanup. Set ticks to
zero and state to complete. Valid in any state.
Time check – decrement the ticks of all running processes that have ticks > 0. After that,
suspend any that are at zero ticks. Ignore processes that are not running. (In lab 2 we only
have 1 process.)
I/O call – block a running process until the initiated I/O is complete
I/O complete – ready a process that was blocked on an I/O call
We will also simulate a synthetic event:
Run – if the process is in the READY state, set it to RUNNING. Give it the default number of ticks.
Input
The input file is arranged in pairs of numbers. The first number is the event, is a decimal number
between 0 and 5, matching the order of the events given above. A value of 1 for the event means
process end and a value of 5 is the run event. The second number is the parameter, given in hex, to be
interpreted as follows:
0. For process start, the parameter is a PSW
1. For process end, the value is the PID of the process to end
2. For time check, the value is ignored
3. For I/O call, the value is a PID of the process that will block
4. For I/O complete, the value is the PID of the process that will be made ready
5. For run, the value is the PID of the process to make running.
If scanf ever fails to read as expected, end the simulation and do final cleanup. Be sure to print the
value that scanf returned that was unexpected. If the event is invalid, print an error and end the
simulation after cleanup. On a clean read of a valid event process the event (if possible) and be sure
that any changes to the existing PSW are remembered.
Avoid “magic” numbers in your C code, such as 3 to mean the time check event. Instead have a #define
for each state using a descriptive name for the macro. Put those in a header file. (You will need to do
something similar for the state values.)
There are sample input files and corresponding output files. See the output section for more.
Output
Our labs 2-4 will have a text and graphical output mode. Do text output first. We control the output
mode by modifying the debug.h file. That file is on piazza.
Text Output
In debug.h there is a define symbol TEXT that indicates that printing is enabled or disabled. Read the
comments in debug.h to understand how to use that file. Any call to printf that could run after graphics
are initialized must be protected by one of two constructs, typically done as:
if(TEXT)printf(
if(DEBUG)printf(
You can also have entire output functions protected this way so that you don’t have to protect each
individual printf statement:
if(TEXT) print_header();
Normal Output
Normal output will be a table showing the step number and the new values of the psw, packed and
unpacked. All columns will have fixed widths and must line up.
The three lines below show the correct formatting for the header and the regular text output lines. Your
output format must exactly match. The values shown here are artificial but the sizes are right.
STEP EVENT __PSW__ PRI PID TICKS STATE
0 1 0x0000000000000000 0 0 0 0
1234 1 0x8B004000003039FF 139 4194304 12345 255
Diagnostics
The program will have error messages for cases where things do not go according to plan. See sample
output files. Error messages begin with
ERROR: function_name:
and tell what the error is. These appear in TEXT mode.
Debug Messages
Debug messages allow your code to tell you what it is thinking. You can put them anywhere since they
do not count against the 10 line limit. As a minimum, debug messages are required in the event
handlers (see samples). These will only appear if debug.h is set to show them (VERBOSE is true and
GRAPHICS is false). ALL debug messages must begin with
DEBUG: function_name:
and carry sufficient information for you to know what is going on. In your code, debug message look like
this:
if(DEBUG)printf(“DEBUG: end_process: PID %d\n”, pid);
Note that debug messages do not count towards the ten-line limit. I strongly suggest having debug
messages both in your 6 event handlers and in your psw code that packs and unpacks the psw. You
must have a full set of debug messages in at least one of those two files. One of the example output
files shows a full set in the event handlers because the psw functions in the instructor code was fully
tested in a prototype. Error messages count towards having a full set of debugs since the error message
print anytime a debug message prints. A full set of messages means that all execution paths have debug
output so that you know what each routine is doing.
File Input and Output
Consider the following Linux commands:
lab2 < zclean.txt lab2 < zclean.txt > zclean.mine.txt
diff zclean.output.txt zclean.mine.txt
Your tabular output with this particular file should match the tabular portion of the reference output
file. The runtime numbers do not have to match. Runtimes will vary on a per-run basis. Files created
with DEBUG true are not required to match and your error messages do not have to exactly match but
you must have corresponding error messages to what you see in the output. The zclean input file has no
errors, so that output must match the reference output. Here is an example diff command where the
lab output matches the reference output except for the runtime message at the end. Output like this
from diff indicates that the formatting of the lab is correct and that the output is right.
[kirby.249@cse-sl3 lab2]$ diff zclean.mine.txt zclean.output.txt
14c14
< Total run time is 0.000098228 seconds. --- > Total run time is 0.000099897 seconds.
[kirby.249@cse-sl3 lab2]$
Here are the error messages generated by the zevents input file:
ERROR: time_check IGNORED, PID 0 is not running.
ERROR: end_process: could not find PID 1
ERROR: run_process: PID 0 is not READY
ERROR: begin_IO: could not find PID 1
ERROR: end_IO: could not find PID 1
ERROR: run_process: could not find PID 1
ERROR: valid_event: 9 is an invalid event. TERMINATING.
Note that the text output files changed with the full lab write-up. They have a final line of output that
gives the total runtime of the program. That is the only difference in the text output.
The final line of text output needed is the total runtime. The graphical output section describes how to
build with the supplied library “libos” used in this lab. Be sure to unzip it and look at the libos.h header
file. One of the functions available in that library is the now()function. Now returns a double, in
seconds, that relates to the system real time clock. Call it as the very first line of executable code in
main and then call it again at the end of main. The differences between the two values is the runtime in
seconds. Print that difference with a precision of 9 decimal places as shown below. The time required
by the final printf call itself won’t be included in the runtime time. This second call to now and the printf
come after graphics are torn down, so that last printf doesn’t need to be protected by an if (TEXT)
construct.
Total run time is 0.000145435 seconds.
You can leave off the total runtime until you tackle graphical output, but don’t forget it.
Graphical Output
The picture below is a screenshot of a prototype that tests the graphics library.
Your lab 2 output will never have more than one process showing at a time.
Using the libos library
Get the zip file from piazza and unzip it to your folder. Take a look at the header file to know what
capabilities the library offers. There are makefile samples in the text that follows.. All of the library calls
start with os_ in the function name. The “os” stands for “operating system simulation library.” None of
your functions should start with “os_” unless you are using test code to be replaced.
Here is the header file:
If you are using PuTTY to connect, Go to the Window->Translation part of the configuration dialog and
change from UTF-8 to Latin so that you get the right characters.
Step zero: Before calling anything, add to your makefile so that it brings along the two libraries and
cleanly compiles. Here “p1” means “prototype one.”
# A typical prototype. But use a better name.
# Be sure to mark it as to be graded if that is the case
p1: p1.o
#link everything together to get p1 the executable
gcc -g -o $@ $^ -lncurses -L. -los
Note the items in the line in the makefile that links everything:
-L.
means search . for libraries as well as the usual places. Our
libos library is in . (the current folder)
-los
means link in the libos.a file – it needs to be in this folder
-lncurses
means link in the new curses library (it will be found in the
usual place that standard libraries are found)
Use this sample p1.c code:
#include “libos.h”
main() {}
If that fails to compile or link, fix that first before trying to touch the library. In other words, if you can’t
build, don’t bother writing more C code.
Step one: Now that you can compile against the library, start using it. Read the libos.h file to find the
functions that are available to you. See also Supplied Library section below here.
The first two functions to find are os_initialize and os_teardown. If you call os_initialize your code must
check the return value! (So put it in an if statement, because if it fails you aren’t doing graphics.) After
you make a successful call to os_initialize, your code really needs to call os_teardown before it exits or
your terminal may be left in a bad state. (See the fix below if that happens.)
This line of code may be handy:
if( TEXT || ( GRAPHICS && os_initialize()) )
By themselves, init and teardown don’t do anything exciting. But we need them to get graphics going
and to tear it down when done. So the next function on your list is os_refresh. This function tells the
system to output everything that has been drawn since the last refresh call. Your code will want to call
it every time you want to make updates visible. Do all of your drawing for one update cycle before
calling refresh. In lab 2 we only have a single call to do drawing since we only have one process to
simulate.
So the first experiment is to use these functions:
os_initialize() /* only do the rest of the code if that returned a true value! */
os_refresh() /* do something visible */
getchar() /* make it wait so we get to see it */
os_teardown() /* return the terminal to the normal state. */
You need to call getchar() to make the program wait on input from you. Press any key to go on. You will
know it works when you see it take control of your screen. The init call will need a small number such as
4 as the number of cores in the simulation:
os_initialize(4); /* pretend we have a 4 core system */
If your terminal is left in a screwed up state blindly press enter and type the following command and
press enter again:
stty sane
If your code crashes without a graceful exit, you will want to know that command. Another handy
command is:
clear
Step two: Your next experiment is to get ready to draw something. Clone your experiment one code
and add the following call just before the os_refresh() call
os_clear(1); /* the one is the step number */
We use this call to clear the drawing area, something we will need to do at the start of each simulation
step before we output our newly updated process to its new position. If you forget to call it, we will
draw over top of everything we have previously drawn. So in regular use, we will call os_clear and then
draw all of our processes. We still need to draw a process.
Step three: Step two gave us a nice backdrop, but we want to show a process. Clone your step two
code. Just before the os_refresh call add:
/* (event, priority, pid, ticks, state) */
os_process(0, 0, 1234567, 12345, 1);
/* if you have the #define handy use the following instead */
os_process(0, 0, 1234567, 12345, RUNNING);
Integration: About now you should either make any last prototypes needed to get comfortable with
the clear / draw / refresh sequence needed to do the output you need. In the experiments we use
getchar() to pause the program. In your lab 2 submission you will call millisleep with a value of 1,000
milliseconds. When debugging, if you have to, you can use a larger number to slow things down or a
smaller number to make them go faster.
Multiple Files
As of the first version of this write-up, the instructor lab code is 21 functions in 5 files. Your code will be
split over at least 4 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 functions that generates table data (header and rows) will be grouped together in a separate
file.
Your prototypes will add additional files to this list. It is fine if your prototypes link any of the above
files. Between the pack/unpack function and the event handlers, there’s plenty of things to test
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.
I got the lab done and I’m bored
You might glance at commands such as top, sar and vmstat on stdlinux, along with their man pages.
24 iostat, vmstat and mpstat Examples for Linux Performance Monitoring
If you want to know the details of how real operating systems do process control, the Linux source code
is a free download.
https://github.com/torvalds/linux
This tour of the linux code is lovely for explaining the x86 boot sequence
https://tldp.org/LDP/khg/HyperNews/get/tour/tour.html
Plan of Attack
DO NOT ”just code the whole thing the night before.” Start now. Look for small, understandable
chunks and prototype them. Late on you will integrate this code. Integration fails if the underlying code
isn’t reasonably sound.
Anything you don’t know how to do calls for a small prototype to teach yourself how to do it. Never
coded scanf before? Write a prototype, and use lots of printfs to show that it works. Add to it and
expand it a bit and you have you read code and possibly the outer loop done. Don’t make it too
complex without moving to your actual code. Fail fast, fail in the small.
24 iostat, vmstat and mpstat Examples for Linux Performance Monitoring
https://github.com/torvalds/linux
https://tldp.org/LDP/khg/HyperNews/get/tour/tour.html
Do not get blocked on one thing, there’s plenty here to work on while getting unblocked. Your
prototypes should generate one of two things, working code or a small list of questions.
Do the text output first. Once you have that done, add a parallel output system to do graphics. Modular
code is a must.
Push details down to the lowest level possible.
Refactor ruthlessly. If you need to change a design, redesign and then change the code to fit the new
design.
Small functions that have minions to handle the details win the day.
DEBUG messages and VERBOSE mode are your friend.
Submission
Effectively: Same as lab 1. Your zip file needs to contain README_LAB2, all the code to be graded, and a
makefile sufficient to build all of the targets that are to be graded. Those targets include lab2 and at
least 4 working prototypes. Do not include any .o files or the lab2 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.
README_LAB2 text:
THIS IS THE README FILE FOR LAB 2.
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.