Purpose
To write a program which simulates a few methods of managing critical sections between several processes.
Worth and Time Frame
The Problem
Lecture described several ways of dealing with mutual exclusion
(Sleep/wake
Busy waiting
TSL Instruction
Disabling interrupts
Peterson's)
when dealing with critical regions. Select two and write a program to simulate a multi-processing system which implements those two methods.
Description
Your program needs to read and "execute" 1-100 processes. Each process will contain several (non)critical sections. The output of the program should be a listing (table) of the process ID and it's time of completion since time 0 (to be explained later).
Operation
Your program, like a computer, needs to prep the processes at first. The program will read/open all the processes and once they're all ready to go, you begin executing process #00. This is time 0.
As a process finishes, print out the process that finished and the total time the process took to complete using the mutual exclusion method used. Since there will be two methods used, you'll have two tables to print out.
See if you can catch "deadlocks": race conditions where no processes are running anymore. Hint: they may not occur! Try and force one by creating process files with values that will result in one.
Process Files
For this assignment, a process will be a file of the namepXX.txtwhereXXis a two digit number ranging from 00 to 99. These represent process IDs. Your program needs to support up to 100 processes.
The process file will primarily contain nothing but a list of positive integers, one integer per line. Each integer represents milliseconds (i.e. 500 == 0.5 seconds).
Also in this filemay becomments and/or blank lines. Comment lines have, optionally, tabs/spaces followed by a hash/pound symbol '#'.
Example:
# Process #00
500
# first critical section
1500
200
# Second critical section
15
5000
# End of Process #00
Since processes typically have "setup" at their beginning, the first integer will represent anon-critical region. The second integer will be acritical region. The third, a non-critical, then 4thcritical, etc. "Odd integer-containing lines" are non-critical regions, "even integer-containing lines" are critical regions.
Note: "" are around "odd" and "even" because the process file may have comments in them!!
Process files may have at most 10000 integers with each integer being a positive value between 1 and MAXINT, inclusive, where integers are 4 bytes (or however many bytes your system supports for integers).
CPU Details
Timing
For this project, have your "CPU" give a 500ms time slice to a process before switching it out and moving to another process.
Process Priority
For this project, when a process's time slice is up, move on to the next PID that has not completed. For example, if you initially had PIDs from 00 to 15 but 14 has finished and the CPU is currently on 13, when 13's time slice is done, move on to PID 15 (since 14 has finished).
Execution
Executing your program should be as simple as:
$ ./homework2 # Bash, Perl, Python, C, C++, etc.
or
$ java homework2 # Java
or
$ {other??}
The program should look for process files in the current directory. Read and account for process files sequentially, starting at 00, until you don't find one.
For example, if filep01.txtthroughp99.txtexist, running your program should quit almost immediately becausep00.txtwasn't found.
Another example, ifp00.txtthroughp99.txtall exist EXCEPT forp10.txt, your program should only processp00.txtthroughp09.txtsincep10.txtwon't be found.
Process Script
Not sure if anyone wants this, but here is a Bash script to create a random set of
pXX.txt
files. You can optionally give 3 arguments:
#!/bin/bash
NUM_PFILES=55 # Default: 55 pXX.txt files
MIN_SECTIONS_PER_PFILE=4 # Default: At least 4 sections per process
MAX_SECTION_TIME=1000 # Default: 1 second per (non)critical section
if [[ ! -z $1 ]]; then # Get values from user if provided.
NUM_PFILES=$1
fi
if [[ ! -z $2 ]]; then
MIN_SECTIONS_PER_PFILE=$2
fi
if [[ ! -z $3 ]]; then
MAX_SECTION_TIME=$3
fi
for P in $(seq -w 0 55); do
# Get a random number between MIN_SECTIONS_PER_PFILE and 10000
NUM_SECTIONS=$(( ( $RANDOM % ( 10000-$MIN_SECTIONS_PER_PFILE ) ) + $MIN_SECTIONS_PER_PFILE ))
for N in $(seq $NUM_SECTIONS); do
echo $(( $RANDOM % $MAX_SECTION_TIME )) >> p$P.txt # Keep the sections reasonable for now
done
done
Set the variables in the script or pass in the 3 values:
- Number of pXX.txt files to create (default: 55)
- Minimum number of sections to have per pXX.txt file (default: 4 )
- Maximum amount of time per section (default: 1000)