The Simulation:

In this exercise we will simulate the way an Operating  System (OS) allocates and frees computer memory blocks.

A block in computer memory can be defined by a structure that contains two fields: one field with its original address (the first address of the block) and the second field with the block size.

In our program we will arrange the free memory blocks in two linked lists that share the same structures in the memory. So each structure has two other fields: a pointers next_size and a pointer next_address.
The two linked lists are:

• Linked list that is sorted by block size (SLL).
• Linked list that is sorted by memory address of the block (ALL).

Before we can allocate any memory block we need to check in the SLL whether there is a free block that its size is at least N.
There are two possibilities:

• There are such blocks. The OS chooses the smallest block as the optimal choice and removes from the free memory the upper part of size N of this block. In our simulation, we can now update the two lists: SLL and ALL. We also need to add two new events in the tree of events (ET):
• At time T this allocation of memory.
• At time T+D the future release of this block.
• There is no appropriate free block of size N (or more). In this case, this request is put at time T in a waiting queue defined by a linked list (QL). This request will wait until a valid block will be released. At time T this event is also added to the tree of events (ET).

The Program:

Write a program that reads from the user a positive integer M which is the total size of the available memory and display the following menu:

1. Request of a memory block
2. Display the history of the events
3. Display the memory map
4. Exit

The program will execute the following actions for each menu option above:

1. Request of a memory block:

The program reads three input data from the next line of a text file named "requests.dat". Each line in this file contains three data for one memory request:

• T: the time of the memory request: a positive integer greater than the time of the previous request. The time of the first request is zero.
• N: the size of memory request: a positive integer.
• D: the duration of memory allocation: a positive integer.

At time T, before your program decides what to do with this new request, many actions as one set must be executed.
The program uses a current time variable. For each action set its value starts at the time of the precedent request and ends at T.
Between this precedent request time and the current request time (T) there can be many activities of blocks released and allocation of memory for requests in waiting list (QL)that can be satisfied:

The first priority is to check if there is in the ET a release operation between these two times and to execute it.
Pay attention : After your program releases a block back to the free memory area, it is possible that this released block can be united in a bigger successive memory block. It can be united to the block just above it or/and to the block just below it.

The second priority is to scan the queue of  waiting allocation list (QL)from the oldest unsatisfied request and see if now the OS can satisfy those requests pending.

The third priority is to try to satisfy the request that just enters.

The priority level is checked only in case of several events occur at the same time. In order to execute an event according to its priority level, the time of the event is defined not as an integer but as a float value equal to the regular time (integer) + priority (1-3)/10.
For example an allocation event at time point 24 have time value 24.2 (priority 2).
In such way we can automatically order events according to their correct time and priority.
 

2. Display the history of the events:

The program displays on the screen and also writes to a file named "history.dat" the history of the events in the following format:

• The time of the last request
• The list of all the events in chronological order including future events with the header:

The possible event types are:

• REQUEST when a request is entered.
• ALLOCATION if there is a valid block to allocate
• QUEUE if there is no valid block free to request
• RELEASE to free memory at end of allocation.

The program displays on the screen and writes to a file named "memory.dat" the memory map in the following format:

• The time of the last request
• The map of the memory after the last request with the header:

Status: Free or Allocated

Release time: For status "allocated" the time when this block will be freed, for status "free" the minus sign ("-").

4. Exit

End of program.
 

Important notes:

• The program must use at least 4 functions:
• Allocate - to manage the two Linked Lists after allocation of memory
• Release - to manage the two lists to free memory
• Queue - to manage the linked list of waiting requests
• History - to manage the tree of events
• Work may be done by couple of students (two students, no more!) and only one work will be submitted with the name id1_id2.cpp (id1 and id2 are id# of the two students.)
• At the beginning of the program write also in comment names and id# of the two students. Instructions how and where to submit your program are in the home page.
• Don't forget to check that the input data are valid and not out of the defined range.
• Don't forget to write clear comments, a nice presentation of the program, meaningful variable names and a friendly interface.
• Also, do not use anything you didn't learn in class.
• It is very recommended that you check that your programs compiles and runs properly on Microsoft® Visual C++ 6.00, before you submit them.

Last date to submit your work:  Monday, January 28, 2002 (At midnight, between Monday and Tuesday).
 

GOOD LUCK !
 

Zion, Tania, Tal, Olga and Eliezer.