COMP30023: Computer Systems
Project 1: Process Management
Released: March 24, 2023 AEDT
Due: 9am April 17, 2023 AEST
Weight: 15%
1 Overview
In this project, you will implement a process manager capable of allocating memory to processes
and scheduling them for execution. This project has two phases. In the first phase, a scheduling
algorithm will allocate the CPU to processes, making the assumption that memory requirements
are always satisfied. In the second phase, a memory allocation algorithm will be used to allocate
memory to processes, before the scheduling takes place. Both the memory allocation and the
process scheduling are simulated. There is also a challenge task that requires controlling the
execution of real processes during the process scheduling. Process scheduling decisions will be
based on a scheduling algorithm with the assumption of a single CPU (i.e, only one process can
be running at a time).
2 The Process Manager
The process manager runs in cycles. A cycle occurs after one quantum has elapsed. The process
manager has its own notion of time, referred to from here on as the simulation time. The simulation
time starts at 0 and increases by the length of the quantum every cycle. Hence, at any given cycle,
the simulation time is equal to the number of completed cycles times the length of the quantum:
TS = N × Q
where TS is the current simulation time, N is the number of cycles that have elapsed, and Q is the
length of the quantum. For this project, Q will be an integer value between 1 and 3 (1 ≤ Q ≤ 3).
At the start of each cycle, the process manager must carry out the following tasks in sequence:
1. Identify whether the currently running process (if any) has completed. If so, it should be
terminated and its memory deallocated before subsequent scheduling tasks are performed.
2. Identify all processes that have been submitted to the system since the last cycle occurred
and add them to the input queue in the order they appear in the process file. A process is
considered to have been submitted to the system if its arrival time is less than or equal to
the current simulation time Ts.
The input queue contains processes that have been submitted to the system and are waiting
to be brought into memory (from disk) to compete for CPU time. At no time should the
input queue contain processes whose arrival time is larger than the current simulation time.
3. Move processes from the input queue to the ready queue upon successful memory allocation.
The ready queue holds processes that are ready to run.
The process manager will use ONE of the following methods to allocate memory to processes:
• Assume that the memory requirements of the arrived processes are always immediately
satisfied (e.g., there is an infinite amount of memory). All the arrived processes will
automatically enter a READY state, and be placed at the end of the ready queue in
the same order as they appear in the input queue. OR,
• Allocate memory to processes in the input queue according to a memory allocation
algorithm. Processes for which memory allocation is successful enter a READY state,
and are placed at the end of the ready queue in order of memory allocation to await
CPU time (Section 3.3).
1
4. Determine the process (if any) which runs in this cycle. Depending on the scheduling algo rithm (Section 3.1, 3.2), this could be the process that was previously running, a resumed
process that was previously placed back into the ready queue, or a READY process which
has not been previously been executed.
After completing these tasks, the process manager should sleep for Q seconds, after which a new
cycle begins.
2.1 Process Lifecycle
The lifecycle of a process is as follows:
1. The process is submitted to the manager via an input file (See Section 4 for more details).
Note that you may read all the processes in the input file into a data structure and use said
data structure to determine which processes should be added to the input queue based on
their arrival time and the current simulation time.
2. The process is in a READY state after it has arrived (arrival time less than or equal to the
simulation time), and memory has been successfully allocated to it.
3. Once a process is in the READY state, it can now be considered by a process scheduling
algorithm as a candidate to enter the RUNNING state, i.e., be allocated to the CPU.
4. Once a process is in the RUNNING state, it runs on the CPU for at least one quantum. If
the scheduling algorithm decides to allocate CPU time to a different process, the RUNNING
process is suspended and placed in the ready queue. At this point, the state of the process
will change from RUNNING to READY.
5. The total time a process gets to run on the CPU (i.e., is in the RUNNING state) must be
equal to or greater than its service time. Note that the service time of a process is the amount
of CPU time (not wall time) it requires before completion.
6. After the service time of a process has elapsed, the process moves to the FINISHED state.
When a process terminates, its memory must be deallocated and it should cease competing
for the CPU (must not enter the ready queue).
2.2 Program termination
The process manager exits when all the processes in the input file have finished execution, that is,
there are no more processes in the input queue and no READY or RUNNING processes.
3 Programming Tasks
3.1 Task 1: Process Scheduling (Non-preemptive)
In this task, your program selects the next process to run among the READY processes based on
the Shortest Job First (SJF) scheduling algorithm.
Shortest Job First (SJF): The process with the shortest service time should be chosen among
all the READY processes to run. The process should be allowed to run for the entire duration
of its service time without getting suspended or terminated (i.e., non-preemptive). If there is a
tie when choosing the shortest process (i.e. two or more processes have the same service time),
choose the process which has the earlier arrival time. If there are two or more processes that have
the same service time as well as the same arrival time, select the process whose name comes first
lexicographically.
In the case of SJF, after one quantum has elapsed:
– If the process has completed its execution, the process is terminated and moves to the FIN ISHED state.
– If the process requires more CPU time, the process continues to run for another quantum.
2
3.2 Task 2: Process Scheduling (Preemptive)
In this task, your program selects the next process to run among the READY processes based on
the Round Robin (RR) scheduling algorithm.
Round Robin (RR): The process at the head of the READY queue is chosen to run for one
quantum. After a process has run for one quantum, it should be suspended and placed at the tail
of the ready queue unless there are no other processes currently in the ready queue.
In the case of RR, after one quantum has elapsed:
– If the process has completed its execution, the process is terminated and moves to the FIN ISHED state.
– If the process requires more CPU time and there are other READY processes, the process
is suspended and enters the READY state again to await more CPU time.
– If the process requires more CPU time and there are no other READY processes, the process
can continue to run for another quantum.
3.3 Task 3: Memory Allocation
In this task, you have to implement an additional memory allocation phase before your program
starts the scheduling phase of the simulation. Note that memory allocation is also simulated, i.e.
the process manager only has to track of and report simulated memory addresses.
In each process management cycle (i.e., after each quantum), your program must attempt to
allocate memory to all the processes in the input queue, serving processes in the order of appearance
(i.e. from the first process in the input queue to the last), and move successfully allocated processes
to the ready queue in order of allocation. Processes for which memory allocation cannot be currently
met should remain in the input queue.
Processes whose memory allocation has succeeded are considered READY to run. The input queue
should not contain any READY processes.
When allocating memory to a particular process, you are required to implement the Best Fit
memory allocation algorithm1 as explained in the lectures and in the textbook.
Important Notes:
1. The memory capacity (in MB) of the simulated computer is static. For this project, you will
assume a total of 2048 MB is available to allocate to user processes.
2. The memory requirement (in MB) of each process is known in advance and is static, i.e., the
amount of memory a process is allocated remains constant throughout its execution.
3. A process’s memory must be allocated in its entirety (i.e., there is no paging) and in a
contiguous block. The allocation remains for the duration of the process’s runtime (i.e.,
there is no swapping). Always choose the block with the lowest sequence number. e.g.
Consider a sequence number [0..2048) for all the blocks. If there are 2 equal-sized blocks, say
[100, 199], and [300, 399], choose the block starting at address 100.
4. Once a process terminates, its memory must be freed and merged into any adjacent holes if
they exist.
3.4 Task 4 (Challenge Task): Creating and Controlling Real Processes
If you choose to complete this task, every process scheduled by the manager should trigger the
execution of a process.c program, supplied as part of this project.
Include the following line in your code for this task to be marked:
#define IMPLEMENTS_REAL_PROCESS
1Hint: Best Fit algorithm selects the smallest available contiguous block of memory that is big enough to
accommodate the memory requirement of a process.
3
Get a copy of process.c from the Project 1 repository on GitLab. Compile this into an executable
named process, which will be exec-ed by your code. In the marking environment, the process
executable will be automatically placed into the same directory as your program.
Implement these additional steps in your program:
1. When a scheduling algorithm selects a process to run for the first time, the process is created.
2. In the case of RR, after one quantum has elapsed:
– If the process has completed its execution, the process is terminated.
– If the process requires more CPU time and there are other READY processes, the
process is suspended and enters the READY state again to await for more CPU time.
The next time that the suspended process is scheduled, it is resumed.
– If the process requires more CPU time and there are no other READY processes, the
process is continued to run for another quantum.
3. In the case of SJF, after one quantum has elapsed:
– If the process has completed its execution, the process is terminated.
– If the process requires more CPU time, it is continued to run for another quantum.
The command line specification for process is as follows:
Usage: process [-v|--verbose]
Creating process
1. fork() and exec an instance of process from your program.
Provide the name of the scheduled process as a command line argument.
Optionally specify the -v flag to get process to print debug logs to standard error.
2. Send the 32 bit simulation time (See Section 5.1 RUNNING) of when the process starts running
to the standard input of process2
, in Big Endian Byte Ordering (See Section A).
3. Read 1 byte from the standard output of process, and verify that it’s the same as the least
significant byte (last byte) that was sent.
Suspending process
1. Send the 32 bit simulation time of when the process is suspended (Similar to FINISHED – See
Section 5.1) to the standard input of process, in Big Endian Byte Ordering.
2. Send a SIGTSTP signal to process, and wait for process to enter a stopped state. e.g.:
kill(child_pid, SIGTSTP);
pid_t w = waitpid(child_pid, &wstatus, WUNTRACED); // See $ man 2 waitpid
if (WIFSTOPPED(wstatus)) {
// Loop until this condition is met (Loop ommitted for brevity)
}
Resuming or Continuing process
1. Send the 32 bit simulation time of when the process is resumed or continued (See Section 5.1
RUNNING) to the standard input of process, in Big Endian Byte Ordering.
2. Send a SIGCONT signal to process.
3. Read 1 byte from the standard output of process, and verify that it’s the same as the least
significant byte (last byte) that was sent.
2Hint: You should use pipes and dup2 to write to and read from process – See Practical 3 Section 4.
4
Terminating process
1. Send the 32 bit simulation time of when the process is finished (See Section 5.1 FINISHED)
to the standard input of process, in Big Endian Byte Ordering.
2. Send a SIGTERM signal to process.
3. Read a 64 byte string from the standard output of process, and include it in the execution
transcript (Section 5.1) for marking.
4 Program Specification
Your program must be called allocate and take the following command line arguments. The
arguments can be passed in any order but you can assume that all the arguments will be passed
correctly, and each argument will be passed exactly once.
Usage: allocate -f -s (SJF | RR) -m (infinite | best-fit) -q (1 | 2 | 3)
-f filename will specify a valid relative or absolute path to the input file describing the processes.
-s scheduler where scheduler is one of {SJF, RR}.
-m memory-strategy where memory-strategy is one of {infinite, best-fit}.
-q quantum where quantum is one of {1, 2, 3}.
The filename contains the list of processes to be executed, with each line containing a process.
Each process is represented by a space-separated tuple (time-arrived, process-name, service-time,
memory-requirement).
You can assume:
• The file will be sorted by time-arrived which is an integer in [0, 2
32) indicating seconds
• All process-names will be distinct uppercase alphanumeric strings of minimum length 1 and
maximum length 8.
• The first process will always have time-arrived set to 0.
• service-time will be an integer in [1, 2
32) indicating seconds.
• memory-requirement will be an integer in [1, 2048] indicating MBs of memory required.
• The file is space delimited, and each line (including the last) will be terminated with an LF
(ASCII 0x0a) control character.
You can read the whole file before starting the simulation or read one line at a time.
Note that there can be inputs with large gaps in the process arrival time, like in a batch system.
We will not give malformed input (e.g., negative memory requirement or more than 4 columns in
the process description file). If you want to reject malformed command line arguments or input,
your program should exit with a non-zero exit code per convention.
Example: ./allocate -f processes.txt -s RR -m best-fit -q 3.
The allocation program is required to simulate the execution of processes in the file processes.txt
using the Round Robin scheduling algorithm and the Best Fit memory strategy with a quantum
of 3 seconds.
Given processes.txt with the following information:
0 P4 30 16
29 P2 40 64
99 P1 20 32
The program should simulate the execution of 3 processes where process P4 arrives at time 0,
needs 30 seconds of CPU time to finish, and requires 16 MB of memory; process P2 arrives at time
29, needs 40 seconds of time to complete and requires 64 MB of memory, etc.
5
5 Expected Output
In order for us to verify that your code meets the above specification, it should print to standard
output (stderr will be ignored) information regarding the states of the system and statistics of
its performance. All times are to be printed in seconds.
5.1 Execution transcript
For the following events the code should print out a line in the following format:
• If completing memory management (Task 3.3), when a process is allocated memory with the
best-fit memory strategy and becomes READY: