Program Description

At one large batch-processing computer installation, the management wants to decide what storage placement strategy will yield the best possible performance. The installation runs a large real storage computer (as opposed to virtual storage) under either fixed or dynamic partition multi-programming. Each user program runs in a single group of contiguous storage locations. Users state their storage requirements and time units for CPU usage on their Job Control Card (it used to, and still does, work this way, although cards may not be used). The operating system allocates to each user the appropriate partition and starts up the users job. The job remains in memory until completion. A total of 50,000 memory locations are available, divided into blocks as indicated in the table under Test Case for Suggested Exercise 02.

Your program should help decide which storage placement strategy (first-fit or best-fit) should be used at this installation under a) fixed partitioned multi-programming, and b) dynamic partitioned multi-programming. Your program would use the job stream and memory as indicated, and run an event-driven simulation until all the jobs have been executed with the memory as is. Note that your program need to investigate the performance of the system, using the given job stream, by measuring the following:

1. throughput, how many jobs are processed per given time unit;
2. storage utilization, the percentage of partitions never used, the percentage of partitions heavily used;
3. waiting queue length;
4. waiting time in queue;
5. internal or external fragmentation

Program Considerations

Given the jobs are served on first-come, first-served (FCFS) basis, while programming the above event-driven simulation, you must:

1. Explain how the system handles conflicts when jobs are put into a waiting queue, and there are jobs still entering the system. Which job goes first?
2. Explain how the system handles the "job clocks," which keep track of the amount of time each job has run, and the "wait clocks," which keep track of how long each job in the waiting queue has to wait.
3. Explain how you define an "event", since this is an event-driven system, and what happens in your system when the event occurs.
4. Examine the results from the best-fit run and compare them with the results from the first-fit run:
   1. Explain what the results indicate about the performance of the system for this job mix and memory organization.
   2. Is one method of partitioning better than the other? Why or why not?
   3. Could you recommend one method over the other given your sample run? Would this hold in all possible cases?
   4. Write some conclusions and recommendations.

Work Steps

• Write a ANSI C program to fulfill the following operating system tasks in main memory management using a) fixed (static) partitioned, and b) dynamic partitioned contiguous allocation methods:
  1. Your program should run to produce a screen "Welcome to Static and Dynamic Partitioned Main Memory Allocation Service!"
  2. Your program should print the menu of memory allocation schemes under the above screen, and ask the user to select:
     1. One of the two memory organization schemes: a) Static Partitioned Memory Allocation, or b) Dynamic Partitioned Memory Allocation;
     2. One of the following memory allocation schemes: a) First-Fit Allocation, b) Best-Fit Allocation
  3. Your program should ask for the following two lists after the selection of memory allocation scheme, using a) interactive input via the keyboard, and b) file input via reading an external data file (text file):
     1. Input the job list, with memory requirements (MB) for each job
     2. Input the main memory block size (MB) and/or the number of fixed partitions with the size of each partition
  4. Your program should output the memory map showing which partitions have been allocated to which jobs (programs) using the selected memory allocation scheme.
  5. Your program should produce the following measures:
     1. throughput, how many jobs are processed per given time unit;
     2. storage utilization, the percentage of partitions never used, the percentage of partitions heavily used;
     3. waiting queue length;
     4. waiting time in queue;
     5. internal or external fragmentation
  6. Your program must be well documented so that your program logic could be traced with reasonable ease and clarity.
• Design your program using structured programming approach (divide-and-conquer), such that each major service is supposed to be implemented with a specific function (procedure), including:
  1. User interface function (e.g., welcome screen)
  2. Function to Input test data (e.g., arriving job list with memory requirements, main memory block size) - interactive input and/or file input
  3. Function to output memory map with attendant internal or external fragmentation across memory partitions, if ever allocated, to any of the arriving jobs (programs) - screen output and/or file output
  4. Function to process memory requests from arriving jobs - one function per memory allocation scheme - first-fit, best-fit, next-fit, and worst-fit
  5. Function to input from external data file(s) of arriving job lists and memory block size
  6. Function to output to external data file(s) of memory maps after processing memory requests from arriving jobs
  7. Function to document suggested answer of the given test-case; namely, set of output memory maps (including internal or external fragmentation) with different input job lists and memory block sizes, using different memory allocation schemes
• State clearly any assumptions you have made when implementing the event-driven simulation (of the given test-case) for the contiguous memory allocation schemes in this Suggested Exercise 02.

Test Steps

• Compile your C program (main program plus other sub-programs) and test-run it to show how it works to satisfy the program requirements.
• Use the following input test-case when running your completed program - input through a) interactive input via the keyboard, and b) file input via reading an external data file (text file)

Job List Memory List Memory Block Size Job Stream Number Time Job Size 1 5 5760 1 9500 2 4 4190 2 7000 3 8 3290 3 4500 4 2 2030 4 8500 5 2 2550 5 3000 6 6 6990 6 9000 7 8 8940 7 1000 8 10 740 8 5500 9 7 3930 9 1500 10 6 6890 10 500 11 5 6580 12 8 3820 13 9 9140 14 10 420 15 10 220 16 7 7540 17 3 3210 18 1 1380 19 9 9850 20 3 3610 21 7 7540 22 2 2710 23 8 8390 24 5 5950 25 10 760 Job List Memory List Memory Block Size Job Stream Number Time Job Size 1 5 5760 1 9500 2 4 4190 2 7000 3 8 3290 3 4500 4 2 2030 4 8500 5 2 2550 5 3000 6 6 6990 6 9000 7 8 8940 7 1000 8 10 740 8 5500 9 7 3930 9 1500 10 6 6890 10 500 11 5 6580 12 8 3820 13 9 9140 14 10 420 15 10 220 16 7 7540 17 3 3210 18 1 1380 19 9 9850 20 3 3610 21 7 7540 22 2 2710 23 8 8390 24 5 5950 25 10 760