Operating Systems CSCI 330/509 Spring 2019 XXXXXXXXXX1/10
NEW YORK INSTITUTE OF TECHNOLOGY
Spring 2019
Programming Assignment #3
Memory Fragmentation
Students who submit late assignments will receive up to 50% credit. This is an individual assignment, not a group assignment.
Students are expected to comply with NYIT’s Academic Integrity Policy and complete this assignment on their own.
For this assignment please submit a single zip file. The zip file will contain:
1. Your code;
2. README pdf document with:
a. clear description of your program design;
. Instructions on how to run your code;
3. Full output of your program, not just one screenshot;
Your objective is to create a program that:
(a) Simulates several users working on a single computer system - creating and terminating processes (each process
epresented by PCB). Processes’ PCBs are added to and deleted from linked list that emulates job queue. (This part is
already completed in two previous assignments)
(b) Emulates contiguous memory allocation and deallocation when processes are created and terminated. Frequent
contiguous memory allocation and deallocation will lead to memory fragmentation – and you will need to make
observations and conclusions about memory fragmentation at the end of the assignment.
You may write your program in Java, C, C++ or Python.
Prerequisites:
This programming assignment is designed to be built on top of previously completed programming assignments #1 and #2.
Prior to starting this assignment, you should already have a program that emulates creation and termination of processes.
Program Requirements/ Details:
Scenario that your program should emulate:
1. (Already completed in Assignment #1) Computer system has 5 users. Randomly selected user wakes up every
(randomly selected) interval 1-5 seconds - and creates a process. Meaning, user creates Process Control Block (PCB)
object. Created PCBs are added to a linked list.
2. (Already completed in Assignment #2) Every second time when user wakes up, in addition to adding new process, user
also deletes one random process from a linked list of PCBs.
Operating Systems CSCI 330/509 Spring 2019 XXXXXXXXXX2/10
3. (New, Assignment #3) Program should emulate contiguous memory allocation/deallocation when processes are
created and terminated:
Program should keep track of free memory on your emulated system. Suggested way of doing this - is to keep
linked list of free memory chunks. For instance, in the beginning, there is only one free memory chunk (chunk
starts from frame 0 and ends at frame XXXXXXXXXX), meaning memory is completely free;
Why XXXXXXXXXX? We will assume our emulated computer has 8G of RAM. RAM is divided into 4K frames. Meaning, system
contains XXXXXXXXXX / 4096 = XXXXXXXXXXframes.
3.1 When new process is created, memory is allocated to a process using contiguous allocation, “first-fit” option,
program should:
3.1.1 Find first fitting free memory chunk from the linked list, based on “memory size” property of the process;
3.1.2 Update “First Frame” and “Last Frame” properties of the process - reflecting contiguous memory that was
allocated to process;
3.1.3 Update an entry in linked list of free memory chunks, indicating that memory was allocated to process and
no longer free;
3.2 When process is terminated, memory is deallocated - and returned to the linked list of free memory chunks;
3.3 When there is a need, two adjacent free memory chunks on the list need to be merged - in order to maintain
contiguous allocation;
Here is what your program should accomplish:
Every 1 to 5 seconds random user wakes up and creates one PCB object (process) described above.
You should add newly created PCB to a linked list, which will emulate computer’s job queue. (should be already accomplished in
first assignment)
Every second time when user wakes up, in addition to creating one process, user also deletes one randomly selected process
from a job queue. Meaning, user’s rate of creating processes is two times faster than process termination rate. (should be
already accomplished in second assignment)
Your program keeps track of free memory on the system;
When process is created, memory is allocated to the process - using contiguous allocation, “first-fit” option;
When process is terminated, memory is deallocated and returned to a free memory pool;
You keep creating and terminating processes until there is a new process that does not have contiguous chunk available to
accommodate new process memory requirements.
Every 20 seconds you should show following report indicating (see sample output at the end of this document):
1. How many processes every user cu
ently owns; (no need to show this in Assignment #3)
2. Cu
ent total number of jobs in a queue;
3. Number of processes created since last report;
4. Number of processes terminated since last report;
5. Last created PID;
6. Summary of free memory on the system:
a. Number of free contiguous chunks
. Biggest chunk size
c. Total free memory
7. Full cu
ent list all free memory chunks
Operating Systems CSCI 330/509 Spring 2019 XXXXXXXXXX3/10
For this assignment, do not limit number of created processes (that was previously limited to 40).
Keep creating processes until there is a new process that does not have free contiguous memory chunk available to
accommodate new process memory requirements.
At the end, just like in previous assignments, you should print full cu
ent status of your job queue. Meaning – all details of
every PCB present in a queue.
Questions/Observations/Conclusion:
When your program stops (because there is not enough contiguous memory to accommodate new process) answer following
questions:
1. Free memory is cu
ently fragmented in how many pieces?
2. What is the size of largest piece?
3. How much memory was requested by last process?
4. Is there enough total free memory to accommodate this process?
5. Is there enough contiguous memory to accommodate this process?
6. White a free-form paragraph with your observations about fragmentation and methods to solve it.
Suggestions / Considerations:
1. Study Chapter “Main Memory” and get familiar with the concepts of contiguous allocation, “first-fit” option.
2. If you want, you can create and code singly linked lists on your own, manually, from the scratch. However, it is
completely acceptable if you utilize existing linked list class (such as LinkedList in Java);
3. Specifics and particulars of your output (graphics or character-based, specific format and visual layout) are entirely up
to you – the only requirement here is: produced output should clearly show that program goals and requirements are
accomplished. Sample output attached below, it is only an example to help illustrate program’s functionality;
Sample output:
un:
Users starting to create processes.. updates every 20 seconds
===> Sun Mar 10 12:56:25 PDT 2019
============== PROCESSES QUEUE SUMMARY =============
Total number of processes cu
ently in queue : 0
Last created Process ID : 0
Number of processes created since last report : 0
Number of processes terminated since last report: 0
----------------------------------------------------
============================================== FREE MEMORY SUMMARY ===============================================
Number of free contiguous chunks:1 Biggest chunk size (frames): XXXXXXXXXXTotal free memory (frames):2097153
------------------------------------------------------------------------------------------------------------------
================== FREE MEMORY CHUNKS ===================
FIRST FRAME:0 LAST FRAME: XXXXXXXXXXSIZE:2097153
---------------------------------------------------------
===> Sun Mar 10 12:56:47 PDT 2019
============== PROCESSES QUEUE SUMMARY =============
Total number of processes cu
ently in queue : 4
Last created Process ID : 8
Operating Systems CSCI 330/509 Spring 2019