You will write a simulator that allocates processes to a CPU and manages memory allocation among the running processes.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

COMP30023 Project 2 Process and Memory Management

Background

 In this project, you will familiarise yourself with process scheduling and memory management. You will write a simulator that allocates processes to a CPU and manages memory allocation among the running processes. You will also get to experiment with several algorithms in order to see under which scenarios some scheduling and memory allocation choices perform better than others. Finally, you will be required to improve over baseline algorithms specified in the project spec by implementing algorithms of your choice and justifying why you chose them.

Many details on how scheduling and memory allocation work have been omitted to make the project fit the timeline.

This project has higher weight than the first project.  Hence,  we advise you to start working on it soon  after you finish reading the spec.

 1 Process Scheduler

The program will be invoked via command line. It will be given a description of arriving processes, system properties and algorithm names to be used for scheduling these processes on CPU and memory allocation. You do not have to worry about how processes get created or executed in this simulation. The first process always arrives at time 0 which is when your simulation begins.

 

Scheduling processes Processes will be allocated CPU time depending on the time when they arrive and a scheduling algorithm. You will implement two baseline scheduling algorithms:

First-come ftrst-served (ff) This is a “non-preemptive” algorithm which means that once a process begins executing, it continues executing until its total running time reaches the specified job-time. Every process that arrives starts executing only after every process that arrived before it has completed. If more than one process arrives at the same time, they are executed in increasing order of their process-ids.

Round-robin (rr) Every process is executed on a CPU for a limited time interval at a time, called quantum. Once process’s quantum has elapsed or the process has completed, the CPU is given to the next process in the queue. Any new process that has arrived in the meantime is placed in the end of the queue. If more than one process arrives at the same time, they are placed in the queue in the increasing order of their process id (i.e., the process with the smallest id would be executed first). The process whose quantum has just elapsed is suspended and placed in the queue unless it has completed. Note that if the quantum of process p has elapsed at time t then any uncompleted process that has arrived before or at time t will be given CPU time before p’s next quantum.

The simulation should terminate once all processes have run to completion.

2  Memory Management

 When the process arrives, all pages that it requires are initially stored on disk. Before the process can be executed on the CPU, it needs to be given space in memory (RAM) in order to copy some or all of its pages from disk to memory.

Note: The “unlimited memory” option lets you work on scheduling algorithms, finish and test them before moving to this part of the project. If the memory is unlimited then memory management and any time delays associated with it should be ignored (i.e., there can be unlimited number of processes in memory).

The maximum memory size available to CPU will be indicated through a command line argument. You can assume that the memory is empty at the beginning of your simulation. Memory will be split into 4KB pages. You are required to implement two strategies for allocating memory to a process:

Swapping-X (p) 1 The process can be executed only if all pages it requires are in memory. If there  are not enough empty pages to fit a process, then pages of another process or processes need to be swapped to disk to make space for this process. When choosing a process(es) to swap, choose the one that was least-recently-executed among other processes (excluding the current one) and evict all of its pages (as a result this strategy evicts least-recently used pages). If there is still not enough space, continue evicting other processes following the same policy on least-recently-executed process until there is sufficient space.

In order to simulate the time it takes to load a process in memory, the load time of the process is calculated by adding 2 seconds2 for every page required by the process.

Example: If the process’s memory requirement is 32KB and its pages are not in memory, then the load time is 2 × 32KB/4KB.

Virtual memory (v) Since virtual memory mimics availability of larger memory, we will assume that a process can be executed if it is allocated at least 16KB of its memory requirement (i.e., 4 pages) or all memory it requires if its requirement is less than 16KB. However, if there are more empty pages available, the process should be given either all of the empty pages or enough to meet its memory requirements (e.g., if the process requires 7 pages and there are 6 empty pages then it should be given all 6 pages; if the process requires 7 pages and there are 10 empty pages, then it should be given 7 of these pages).

Similar to swapping, if there are not enough empty pages for the process that is scheduled to be executed, pages of the least-recently-executed process need to be evicted one by one until there are 4 empty pages or less, if the process needs less memory. The lowest number pages belonging to the processes must be evicted first (e.g., if the least-recently-executed process was allocated pages 1,5,7,9, and 2 pages need to be evicted, pages 1,5 must be evicted). In contrast, for the swapping option all pages of the least-recently-executed process would be removed.

The load time of the process is computed in the same manner as for the swapping setting above: 2 seconds for every loaded page.

In order to simulate the time it takes to serve a page fault (i.e., due to accesses to pages that have not been loaded) during process execution, add the following penalty to the remaining execution time of the process: 1 second for every page of the process that is not in memory. You do not need to worry about swapping the pages of the same process and handling page faults.

Example: Consider a process with memory requirement of 32KB. If half of it is already in memory and it has 16 seconds remaining till completion when it starts executing, then its remaining running time is extended to 16 + 16KB/4KB.

each page is numbered, starting from 0. For example, if the total memory size is 200KB then there are 50 pages in total with page numbers from 0 to 49.

1This option is a relaxation of “Swapping” as defined in the lecture where the process has to be allocated to a continuous block of memory.

2Though we use seconds in the simulation, think of them simply as time units. In real systems, these events are orders of magnitude faster.

Each process is allocated pages in increasing order of the page numbers, that is the first process that arrives is always given a memory page 0.

The delay for both options is added for every page that is loaded regardless of whether there was already an empty spot or eviction was required.

 A process that has 0 seconds left to run, should be ’evicted’ from memory before marking the process as ‘finished’.

The quantum for rr starts after the process’s pages have been loaded. Quantum is subtracted from the remaining execution time that includes page fault penalties. You can assume that we will not give you processes that would run infinitely due to execution time continuing to increase from page faults.

Note that with first-come-first-served scheduling process’s pages are loaded into memory only once at the beginning of its execution and, similarly, removed only once immediately before it is marked as ‘finished’.

3   BYO Algorithms

You will notice that the algorithms that you are required to implement for scheduling and memory allocation may not be ideal for certain workloads in terms of completion time. We will refer to these algorithms as baseline algorithms. To this end, you are asked to implement:

Customised Scheduling (cs) a third scheduling algorithm that is different from first-come first-served and round-robin algorithms. Note that round-robin algorithm with a different quantum time does not qualify as a different algorithm.

Customised Memory Management (cm) a memory replacement policy that is different from least- recently-executed process but follows the same time penalties for loading pages and page faults as described in Section 2.

In addition to implementing the algorithms, you will need to justify your choices with a short report (maximum length of 200 words) articulating for each algorithm (1) its short description; (2) scenarios where it performs better than the baselines and why; (3) scenarios where it does not perform well and why (if applicable). In order to support your choice, you are also required to submit two benchmarks on which your algorithms outperform the baseline algorithms. That is, one of the benchmark files should demonstrate the superiority of the scheduling algorithm that you choose over rr and ff, and another one would show the superiority over the swapping and virtual memory configurations. The superiority is defined through improvements on performance statistics as described in Sections 5 and 6.

Note that (1) you can implement any of the algorithms you find in the textbook or online as long as you can justify why you chose them; (2) you can make progress on this part of the project independent of ff,rr and with partially finished p,v algorithms.

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of