CPSC 457 L04 Assignment 3 (Winter 2001) 
Variable Memory Partitioning with Compaction

Assume an operating system running in batch mode during the night, where user jobs, on arrival from a terminal or workstation, are immediately queued on the system job disk. All times are in milliseconds. Arrival times of jobs are listed in the simulation file JFILE below. The vital statistics for each job is a record in JFIILE:
 
Job Id
Arrival
Time
CPU burst
(time/length)
IO Burst
(time/length)
Memory
Space
(MSPACE)
Total Bursts
(BURSTS)
03
005
16
41
1150K
8
06
008
27
24
960K
6
08
013
32
16
850K
4
...
...
...
...
...
...
Range
(0-99)
(2-40)
(6-60)
(400K-1500K)
(1-9)

Assume that a job is placed in the job queue as soon as it arrives. A job is loaded into memory as space in memory permits. Memory available for jobs is 4.0 Megabytes in units of 200K.

BURSTS gives the number of CPU bursts for a job; there is one less I/O burst. Each initial cpu or I/O burst for a job is as given in JFILE. Each subsequent CPU or I/O burst for a job is the same as the initial length plus a value selected randomly from the set [- 15, - 10, -5, 0, +5, +10, +15], or as your TA decides.

Jobs in the job queue are selected by the job scheduler for execution in FIFO order (but see below). The CPU scheduler selects jobs in the ready queue in FIFO order. An executing job cannot be preempted. Assume sufficient I/O processors to guarantee each job in memory its own I/O processor, so that there are no I/O queues.

A job can be loaded into memory for execution only if there is contiguous space for it. The required memory space for a job is given by MSPACE in JFILE. Fragmentation of memory is allowed, and once in memory, a job cannot be moved until job completion. The next job loaded from the job queue into memory is the first one in FIFO order that fits a vacant memory slot.

Write a simulation program to simulate execution of the jobs. Assume about 20 jobs arriving and being executed, and thus about 20 records in JFIILE. The following simplifying time allocation assumptions should be used:
 

In addition, memory is compacted every time the 5th process terminates. Assume that compaction costs 0.2 per KB moved. For simplicity, you can assume that all the processes that are residing in memory are moved when compaction takes place.

        (1) On completion of 4 jobs, and verify with a manual computation.
        (2) For all the jobs processed (about 20) [2%]         (1) at each job completion, and use to output an average
            memory utilization overall.
        (2) Confirm the memory utilization at the point of completion of 4
             jobs with a manual computation. [1.5%]