COMP30023 Computer Systems 2023 Project 1 - Process Management
COMP30023: Computer Systems Project 1: Process Management
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:
- 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.
- 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.
- 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).
- Determine the process (if any) which runs in this cycle. Depending on the scheduling algorithm (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:
- 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.
- 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.
- 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.
- 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.
- 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.
- 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 FINISHED state. – If the process requires more CPU time, the process continues to run for another quantum.
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 FINISHED 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:
- 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.
- 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.
- 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.
- 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
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:
- When a scheduling algorithm selects a process to run for the first time, the process is created.
- 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.
- 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
- 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.
- 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).
- 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
- 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.
- 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
- 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.
- Send a SIGCONT signal to process.
- 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. 2 Hint:
You should use pipes and dup2 to write to and read from process – See Practical 3 Section 4.
Terminating process
- 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.
- Send a SIGTERM signal to process.
- 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
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, 232 ) 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, 232 ) 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 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:
(With best-fit memory strategy) (If completing Task 4)
5.2 Task 5: Performance Statistics
When the simulation is completed, 3 lines with the following performance statistics about your simulation performance should be printed: • Turnaround time: average time (in seconds, rounded up to an integer) between the time when the process is completed (transitioned to FINISHED state) and when it arrived. • Time overhead: maximum and average time overhead when running a process, both rounded to the first two decimal points, where overhead is defined as the turnaround time of the process divided by its service time (i.e., the one specified in the process description file). • Makespan: the simulation time (in seconds) of when the simulation ended. Example: Consider the above processes.txt with -q 3. Then the following lines may be printed: Turnaround time 32 Time overhead 1.08 1.04 Makespan 120
6 Marking Criteria
The marks are broken down as follows: Task # and description
- Shortest Job First Algorithm (Section 3.1)
- Round Robin Algorithm (Section 3.2)
- Best Fit Memory Allocation (Section 3.3)
- Controlling Real processes (Section 3.4)
- Performance statistics computation (Section 5.2)
- Build quality
- Quality of software practices
