CSC465: Operating Systems; Spring 2019
Assignment 4
Due Date: April 24, 2019 — Due Time: 23:59
Project: Memory Management [100 points]
In this project you will write a C program to simulate the behavior of a computer system with a memory of 200 KB and a segmentation-based memory management system that uses the first-fit strategy. You will be given, as input, a succession of processes that, either, need to be loaded into memory or removed from memory. Each process will be identified by a process id, a list of segment ids and their sizes (in KB) and the process’ status (new, in, out, terminated). Each time a new process is encountered, a segment table is created, the process is placed in memory and the segment table filled out as appropriate. Each time a process is swapped out of memory, its segment table entries are removed (set to -1), but the table is not removed. When a process is swapped back into memory, the segment table is filled up again. When a process is terminated, the segment table is removed. You will need to design an approach that will allow you to keep track of the location and size of the holes in memory.
The input to your program could be the following list of processes where each tuple corresponds to (id, status):
(1, new), (2, new), (1, out), (3, new), (4, new), (2, out), (1, in), (3, terminated), (2, in), (5, new), (6, new), (7, new), (5, out), (4, terminated), (8, new)
[Note: this is a partial list of processes… In reality, all the process would terminate after having been loaded, potentially swapped out, reloaded (possibly many times), and finally terminated]
Each process contains the list of segments shown below:
1: ((1, 5KB), (2, 10KB), (3, 3KB), (4, 2KB))
2: ((1, 15), (2, 10), (3, 5))
3: ((1, 5KB), (2, 5KB), (3, 5KB))
4: (1, 4KB), (2, 4KB))
5: ((1, 15), (2, 10))
6: ((1, 3KB), (2, 6KB), (3, 0KB))
7: ((1, 5KB))
8: ((1, 5KB), (2, 9KB), (3, 5KB))
Part A [20%]: Prior to writing your program, manually trace the behavior of the memory management system. Please draw the state of the memory (showing the size and location of each segment as well as the size and location of each hole) after each 5 operations (i.e., after (4,new); after (5 new); and after (8, new)).
Part B [80%]: Write the C program that simulates this memory management system.
At each new input triplet operation, please print the segment table of the process named in the operation indicated by the triplet. If process X has been terminated, simply print: “Process X’s segment table has been deleted”. If process X has been swapped out, simply print: “Process X’s segment table entries have been set to -1”.
The holes present in memory should be maintain in the form of a linked list which gets traversed from the beginning until an adequately sized hole is found every time a segment needs to be loaded in memory.
At the end of the input, once the program terminates, please print the position and size of all the holes present in memory.
Use the result of your program to verify the results you obtained in Part A.
Please upload a zipped directory containing:
• A File with the handwritten answer to Part A. (A scan of your answer is fine).
• Your well commented code
• A README file explaining how to compile and run your code
• Screen shots showing the results of your algorithms on:
• The given input
• Another input string of your choice
Here is the automatic grading program for assignment 4. You call the get_input function repeatedly to get the next instruction. The instructions come in the form of Process structs which have 3 elements, the pid (1,2,3,…8 in the example), the status (0,1,2,3 representing new, in out, terminated), and a an array of segments. The full definition is in ASSN4_declarations.h
. Calling get_input repeatedly is supposed to model the processes coming in.
At the end of the program, pass a pointer to the head node of your linked list of holes to the done function.
An example of use is shown in ASSN4_Example.c.
You can run the example using: gcc ASSN4_Example.c ASSN4_grader.o -o ASSN4_Example; ./ASSN4_Example
ASSN4_declarations.h
typedef struct {
int pid; // process name
int status; // process status
int (*segments)[4][2]; // segments
} Process;
Process get_input();
void done(void *x);
void printer(int (*p)[][2]); // for the example program. Dont use this
ASSN4_Example.c
#include
#include “ASSN4_declarations.h”
// run with gcc ASSN4_Example.c ASSN4_grader.o -o ASSN4_Example; ./ASSN4_Example
void main()
{
printf(“%3s, %7s %20s\n”, “pid”, “status”, “—————segments—————” );
Process x = get_input();
/* Call get_input function in a loop to get all the input
Use the test x.pid!=-1 to see when the input is over */
while (x.pid!=-1) {
printf(“%3d, %7d, “, x.pid, x.status);
printer(x.segments);
x=get_input();
}
}