COMP3520 Assignment 3 2019
1
COMP3520 Operating Systems Internals
Assignment 3 – Memory Requirement
Aware Dispatcher
General Instructions
This assignment is about dynamic memory allocation and memory aware scheduling.
It consists of two compulsory tasks:
- Implement the dispatcher as described in the section“Memory Requirement Aware
Dispatcher (MRAD)”; and
- Answer the discussion document questions that are provided in a separate
document.
This assignment is an individual assignment. Whilst you are permitted to discuss this
assignment with other students, the work that you submit must be your own work. You
must not incorporate the work of any other student (past or present) into your source
code or discussion document. Also, you must not use or refer to material from pirate
websites.
You will be required to submit your source code and discussion document to Turnitin
for similarity checking as part of assignment submission. The examiner may use other
similarity checking tools in addition to Turnitin. Your source code may also be checked.
Submit your source code and discussion document to the appropriate submission
inboxes in the COMP3520 Canvas website.
Memory Requirement Aware Dispatcher (MRAD)
In this assignment, you will implement a dispatcher called the“Memory Requirement
Aware Dispatcher (MRAD)”that meets the required specifications. MRAD is a
multiprogramming system with a round robin dispatcher that supports swapping jobs
into and out of simulated physical memory of size 512 MB.
Figure: Overview of Job Scheduling in MRAD
COMP3520 Assignment 3 2019
2
A program for a round robin dispatcher is provided; however, the memory allocation
routines are incomplete. In this assignment, you need to modify this program such that
it complies with the following requirements:
- Each job is explicitly assigned a priority level (0, 1 or 2) and memory requirement
(in megabytes). For example, consider the following job list, which is in time>, , , format:
1, 1, 128, 4
3, 0, 64, 2
4, 2, 384, 6
The meaning of this job list is as follows:
1st job: Arrival at time 1 second, priority 1, requires 128 MB of simulated memory
and 4 seconds of CPU time
2nd job: Arrival at time 3 seconds, priority 0, requires 64 MB of simulated memory
and 2 seconds of CPU time
3rd job: Arrival at time 4 seconds, priority 2, requires 384 MB of simulated memory
and 6 seconds of CPU time
- The time quantum of the dispatcher is one second.
- During the lifetime of each job, its priority never changes.
- MRAD must support dynamic contiguous memory allocation for jobs as described
in exercise 5; however, the“next-fit”(not first-fit) memory partitioning scheme
must be used.
- The total amount of simulated memory available for allocation to jobs is 512 MB.
- MRAD must support Memory Aware Job Swapping as described in the following
subsection, which is titled“Memory Aware Job Swapping”.
- Whenever a job in the RR ready queue is selected for execution, MRAD launches
it if it is a new job or sends the SIGCONT signal to it if it has already been
launched. Also, MRAD calls the printPcb() and printPcbHdr() functions to print
the offset and size of the simulated memory block that has been allocated to the job.
- No more than one job may be in the running state at any time.
- Whenever a running job has run for its allotted execution time, MRAD terminates
it by sending the SIGINT signal to it.
- Whenever a job is pre-empted or swapped out, MRAD sends a SIGTSTP signal to
it.
- There are two job dispatch queues (marked“Job dispatch lists”in the figure). One
of these (priority 0 job dispatch queue) is for priority 0 jobs (high priority jobs); the
other (priority 1 or 2 job dispatch queue) is for priority 1 (normal jobs) or priority
2 jobs (low priority jobs). For each job dispatch queue, jobs are enqueued and
dequeued on a first-in-first-out (FIFO) basis according to their arrival times.
- When MRAD starts, it loads all jobs from a job list file into the appropriate job
dispatch queues before admitting jobs to the“RR ready queue”for execution. It
must reject all jobs with a memory request in excess of 512 MB (in other words,
such jobs must not be loaded from the job list file into the job dispatch queues).
- Jobs are admitted to the“RR ready queue”at the beginning of every time quantum,
subject to the requirements listed below.
a. An“arrived”job is admitted to the“RR ready queue”if and only if the job
has been allocated a suitable free simulated memory block that satisfies the
job’s memory requirement.
COMP3520 Assignment 3 2019
3
b. In admitting jobs to the“RR ready queue”, the dispatcher gives“arrived”
high priority jobs in the priority 0 dispatch queue absolute priority over jobs
in the other dispatch queue or the“Suspend queue”. No“arrived”lower
priority (i.e., priority 1 or 2) jobs (or“Suspended”jobs) can be admitted (or
re-admitted) from the priority 1 or 2 job dispatch queue (or the“suspend
queue”) to the“RR ready queue”for execution when there is one or more
“arrived”high priority jobs (i.e., priority 0 jobs) in the priority 0 job dispatch
queue waiting to be admitted into the“RR ready queue”.
c. If there are no“arrived”jobs in the priority 0 job dispatch queue, then:
i. If there is no“arrived”priority 1 job at the front of the priority 1 or
2 job dispatch queue, then the dispatcher attempts to re-admit as
many jobs (if any) in the“Suspend queue”to the“RR ready queue”
as possible in accordance with the procedure described in the
subsection“Memory Aware Job Swapping”;
ii. If there is an“arrived”priority 2 job at the front of the priority 1 or
2 job dispatch queue and there are also jobs in the“Suspend queue”,
then jobs in the“Suspend queue”will be considered for re-
admission first.
- When the dispatcher attempts to admit a job in the priority 0 dispatch queue to the
“RR ready queue”, but there is not sufficiently large free memory space available,
the dispatcher attempts to swap out one (and only one) priority 2 job that is either
running or in the“RR ready queue”as described in the subsection“Memory Aware
Job Swapping”.
a. If the job swap is successful, the priority 0 job is allocated the free memory
block that became available as a result of the job swap. Also, this job is
admitted to the“RR ready queue”.
b. If the job swap is unsuccessful, the priority 0 job must wait in the dispatch
queue until its memory requirement is satisfied; subsequently, the job is
admitted to the“RR ready queue”for execution.
- If an“arrived”job that is not currently in the“Suspend queue”cannot be admitted
to the“RR ready queue”due to memory allocation failure, then no further jobs may
be admitted to the“RR ready queue”for the remainder of the current time quantum.
However, you must not modify the printPcb() or printPcbHdr() functions in the“pcb.c”
file.
Memory Aware Job Swapping
MRAD supports swapping of jobs into and out of simulated memory. The steps to swap
a job out of simulated memory are as follows.
When a priority 0 job that has“arrived”is waiting in the job dispatch queue for
admission and there is no sufficiently large contiguous free memory space available,
the system will attempt to suspend ONE (and only one) priority 2 job either running or
in the“RR ready queue”and find a free memory block whose size is equal to or larger
than the memory size requested by the priority 0 job.
- The search for a“suitable”priority 2 job to suspend starts from the head of the“RR
ready queue”and the first such priority 2 job will be selected for swapping.
- The purpose of swapping is to find a sufficiently large free memory block for the
priority 0 job. Thus, the search may involve the free memory block merge operation.
COMP3520 Assignment 3 2019
4
a. You need to consider the case when the allocated memory block for a
priority 2 job is not large enough, but the combination of this block and its
adjacent free memory blocks will be equal to or larger than the requested
size. For example, a priority 0 job requests a 64 MB memory block. One
priority 2 job is allocated 50 MB which is smaller than 64 MB. However,
its adjacent memory block is a free memory block of size 20 MB. In this
case, this priority 2 job is swapped out and its memory is deallocated. Now,
the two free memory blocks can be merged together to become a single
memory block of size 70 MB which is larger than the requested 64 MB.
b. Note that when a simulated memory block is deallocated from a job
(whether larger than, equal to or smaller than the requested size), if there are
adjacent free simulated memory blocks, then the free blocks must be merged
to form one larger contiguous free simulated memory block.
- After the simulated memory is deallocated from the selected job, this priority 2 job
is placed at the tail end of the“Suspend queue”.
The rules for swapping a job from the“Suspend queue”into the“RR ready queue”are
as follows:
- If there are no“arrived”jobs in the priority 0 dispatch queue and there is no
“arrived”priority 1 job at the front of the other dispatch queue, then the dispatcher
attempts to admit as many jobs in the“Suspend queue”to the“RR ready queue”as
possible.
- Start at the head of the“Suspend queue”and traverse the queue. For each job in this
queue, if a simulated memory block can be immediately allocated to this job, then
the dispatcher allocates a suitable memory block to this job and admits this job to
the“RR ready queue”; otherwise, the dispatcher does not admit this job and
attempts to admit the next job in the“Suspend queue”.
- This process continues until the end of the“Suspend queue”is reached.
Additional Requirements
Source Code
The source code for a round robin dispatcher is available on the COMP3520 Canvas
website. This code consists of the files“mrad.c”,“mrad.h”,“pcb.c”,“pcb.h”,“mab.c”
and mab.h”. You may only modify this code for your MRAD implementation. A
completely new program will not be accepted for assessment.
Additionally, the source code for the test process is supplied as“sigtrap.c”. Source code
for a random job generator is supplied in“mem2_random.c”.
Your solution must be implemented in the C language. C++ features are not permitted
except those that are part of an official C standard.
Your source code needs to be properly commented in Academic English and
appropriately structured to allow another programmer who has a working knowledge
of C to understand and easily maintain your code.
You need to include a makefile that allows for the compilation of your source code
using the make command on the School of Computer Science servers.
COMP3520 Assignment 3 2019
5
You should include your University student identification number (SID) (but not your
name) in the space provided in the“mrad.c”file.
Readme File
You need to write a readme file to explain to the user how to compile and run your
dispatcher. This document must be written in Academic English and be appropriate to
audience, purpose and context. The file format should be Plain Text (txt) format.
Testing and Debugging
You are responsible for testing and debugging your source code.
It is crucial that you ensure that the source code you submit compiles correctly on the
School of Computer Science servers and that the resulting binary functions as intended.
If you submit source code that cannot be compiled on the School servers, you will
receive a failing mark for it.
Discussion Document
You are required to answer all assigned questions in a separate written document. The
questions and requirements specific to the discussion document will be provided in a
separate document.
Other Matters
Non-serious attempts, non-attempts, and acts of academic dishonesty are contrary to
the spirit of this assignment and COMP3520; accordingly, such behaviour may be
sanctioned with DISQUALIFICATION from this assignment.
You must not include frivolous or offensive material such as inappropriate filenames
in your assignment submission. Marks may be reduced for inappropriate or irrelevant
material.
Marking criteria for the source code, readme file and discussion document will be
provided separately.
更多可加 V
V：woshibb55