Operating Systems - Projects and Exercises

The various methods of dynamic segment partitioning are described in Stallings chapter 7.

If you wish to implement Best Fit, First Fit, Next Fit, or Worst Fit memory allocation policy, it is probably best to do this by describing the memory as a structure in a linked list:

struct mab {
    int offset;
    int size;
    int allocated;
    struct mab * next;
    struct mab * prev;
};

typedef struct mab Mab;
typedef Mab * MabPtr; 

For the Buddy system, you will need to implement this structure as the node for a Tree with Right and Left pointers.

Either way, the following set of prototypes give a guide as to the functionality you will need to provide:

MabPtr memChk(MabPtr m, int size);   // check if memory available
MabPtr memAlloc(MabPtr m, int size); // allocate memory block
MabPtr memFree(MabPtr m);            // free memory block
 
MabPtr memMerge(MabPtr m);           // merge two memory blocks
MabPtr memSplit(MabPtr m, int size); // split a memory block

Allocating memory is a process of finding a block of 'free' memory big enough to hold the requested memory block. The free block is then split (if necessary) with the right size block marked as 'allocated' and the remaining block (if any) marked as 'free'.

Freeing a memory block is done by changing the flag on the block to 'free'. After this the blocks on both sides of the newly 'freed' block are examined. If either (or both of them are 'free') the 'free' blocks must be merged together to form just one 'free' block.

The mab structure above has been constructed with a reverse link as well as a forward link. This makes it easier to check for adjacent unallocated blocks that need to be merged when freeing up a memory block. Without the reverse link, you will need to do a separate pass through the memory arena after marking a block as free to merge any adjacent free blocks.

You can make up your own test program or go directly to implementing the routines in your Feedback dispatcher. For this you will need to insert a separate queue in between the input queue and the Feedback queues as indicated in the project 2 specification.

Implementing the extra stage, processes are passed from the input queue (Job Dispatch List) to the Feedback pending queue (User Job Queue) when they have "arrived". They are dequeued and enlisted on the appropriate Feedback queue when sufficient memory is available for them in the memory arena - the memory is allocated when they are enqueued and deallocated when they are terminated.

The modified logic (highlighted in red) will be:

1. Initialize dispatcher queues (input queue, user job queue, and feedback queues);
2. Fill input queue from dispatch list file;
3. Start dispatcher timer (dispatcher timer = 0);
4. While there's anything in any of the queues or there is a currently running process:
   1. Unload pending processes from the input queue:
      While (head-of-input-queue.arrival-time <= dispatcher timer)
      dequeue process from input queue and enqueue on user job queue;
   2. Unload pending processes from the user job queue:
      While (head-of-user-job-queue.mbytes can be allocated)
      dequeue process from user job queue, allocate memory to the process and enqueue on highest priority feedback queue (assigning it the appropriate priority);
   3. If a process is currently running:
      1. Decrement process remainingcputime;
      2. If times up:
         1. Send SIGINT to the process to terminate it;
         2. Free memory allocated to the process;
         3. Free up process structure memory;
      3. else if other processes are waiting in any of the feedback queues:
         1. Send SIGTSTP to suspend it;
         2. Reduce the priority of the process (if possible) and enqueue it on the appropriate feedback queue
   4. If no process currently running && feedback queues are not all empty:
      1. Dequeue a process from the highest priority feedback queue that is not empty
      2. If already started but suspended, restart it (send SIGCONT to it)
         else start it (fork & exec)
      3. Set it as currently running process;
   5. sleep for one second;
   6. Increment dispatcher timer;
   7. Go back to 4.
5. Exit.

or something like that!

Try this with the following job list with a quantum of 1 sec and available memory of 1024 Mbyte:

0, 1, 1, 192, 0, 0, 0, 0
0, 1, 3, 32, 0, 0, 0, 0
0, 1, 1, 416, 0, 0, 0, 0
0, 1, 3, 32, 0, 0, 0, 0
0, 1, 1, 160, 0, 0, 0, 0
0, 1, 3, 128, 0, 0, 0, 0
7, 1, 2, 108, 0, 0, 0, 0
7, 1, 2, 256, 0, 0, 0, 0
7, 1, 2, 80, 0, 0, 0, 0

This interesting mixture should run processes 0-5 in the first 6 seconds and leave the memory arena as:

offset	size	allocated
0	192	FALSE
192	32	TRUE
224	416	FALSE
640	32	TRUE
672	160	FALSE
832	128	TRUE
960	64	FALSE

with the Next Fit pointer at offset 960. This will be the case whichever of the four allocation policies you are using. The next three processes should then be loaded into the queue and dequeued, enlisted and then executed in the order: process 6, 7, then 8.

Under First Fit, the 108 Mbyte, 256 Mbyte, and 80 Mbyte processes will be allocated at offset 0, 224, and 108 respectively.

Under Next Fit, they will be allocated at offset 0, 224, and 480 respectively.

Under Best Fit, they will be allocated at offset 672, 224, and 480 respectively.

Under Worst Fit, they will be allocated at offset 224, 332, and 0 respectively.

N.B. The final version of the hostd dispatcher normally reserves the first 64 Mbyte of memory for Real Time processes so that 64 should be added to all of the above offsets. However when run with the -mnr option hostd will not pre-allocate the Real Time memory block. Run the command line:

hostd -h

to find out which version of the dispatcher you have and the command line switches in hostd to change the memory allocation model and printout options (your hostd does not need to provide this extended functionality).

Code should be in 'straight' C using the compiler of your choice (cc or gcc).

Always use nice to execute your test programs at lower priority to ensure they do not inconvenience other users if they go 'haywire'. e.g.:
 
   >nice a.out

The descriptions of the system functions above are drawn from sources that include manuals on the Sun Solaris system and the MAC OS X Darwin/BDS system, and also from 'Advanced Programming in the UNIX Environment', W. Richard Stevens, Addison-Wesley, 1993.