2 Requirements
2.1 Overview
Copyright By PowCoder代写 加微信 powcoder
A full implementation of this coursework will contain the following key components, all implemented
as threads:
� A process generator.
� Process simulators.
� A readers-writers implementation with fairness for multiple devices.
� A disk scheduler.
� A process terminator.
Each of these components is described in more detail in Section 2.2. In addition, the following data
structures will be required:
� A pool of available PIDs.
� A process table.
� Ready queues, implemented as linked lists.
� I/O Queues, implemented as linked lists.
� A terminated queue, implemented as a linked list.
The architecture for a full implementation of the coursework, and the interaction between the different
components, is shown in Figure 1.
Terminator
Ready Queue PID Pool
Terminated Queue
I/O Queues
Controllers
(readers writers / hard drive)
Figure 1: System Architecture
2.2 Components
This section describes the functionality of the individual components in a full implementation of this
coursework.
2.2.1 The Process Generator
The process generator creates a pre-defined number of processes and adds them to the process table
(indexed by PID) and relevant ready queue. The maximum number of processes in the system, at any
one point in time, is restricted to MAX_CONCURRENT_ PROCESSES. The process generator goes to sleep
when this maximum is reached, and is woken up when space becomes available (e.g., when a process
has finished and is removed by the process terminator).
2.3 Process Simulator
The process simulators remove processes from the ready queues and simulate them in a preemptive
round robin fashion using the runPreemptiveProcess() function. The simulators must be imple-
mented such that fairness between I/O and CPU bound processes is maintained. If the runPreemptiveProcess()
function returns a process in:
� the READY state, it is re-added to the appropriate ready queue.
� the TERMINATED state, it is added to the terminated queue.
� the BLOCKED state, it is added to the appropriate I/O queue.
2.4 I/O Simulators
2.4.1 Hard Drive
The hard drive simulator emulates read-write operations for a traditional rotational drive using a “look
scan” algorithm. The disk simulator is woken up when new requests are added to its queue, and goes
dormant when its queue is empty (i.e., all currently available requests have been processed). Once all
processes have finished, the disk simulator thread ends gracefully.
2.4.2 Readers-Writers
The reader-writer implementation for multiple devices enables parallel reading and serialised writing.
The reader-writer removes processes blocked on I/O from its associated device queue and processes
them. To maximise fairness, requests are processed in the order in which they show up (whilst allowing
parallel readers and serialised writers). To clarify, read (R) and write (\verbW—) requests arriving
in the order RRR W RRRRR WW RRR are processed as:
� three readers in parallel,
� a single writer,
� five readers in parallel,
� two writers sequentially,
� three readers in parallel.
Note that the implementation should accommodate multiple – simulated – I/O devices, each one having
their own readers and writers, and their own own associated queues. The number of readers and writers
per device is configurable through the NUMBER_OF_READERS and NUMBER_OF_WRITERS constants in the
coursework.h header file, as is the number of I/O devices.
2.5 Process Terminator
The process terminator removes finished processes from the system, frees up associated resources (e.g.,
page table entry, PID, memory), and prints the process’ turnaround and response times on the screen.
The “terminator” is woken up when processes are added to its queue, and goes to sleep when the
queue is empty. Once all processes have terminated, the “terminator” prints the the average response,
average turnaround, and average number of tracks crossed on the screen.
2.6 Output Sample
To track progress of the simulation, progress messages are printed on the screen. A sample of a
successful implementation in which hard drive requests are processed in FCFS is available for download
from Moodle. The output generated by your code should match the syntax of the sample provided.
Numeric values can of course differ due to non-deterministic nature of multi-threaded code.
3 Breakdown
To make this coursework as accessible as possible, it is recommended to approach it in the steps outlined
below. The first part focuses on the development of a simulation framework for process scheduling,
the second part on the implementation of “device controllers” for I/O simulation.
Recall from above that you must use the functions and data structures defined in the files provided
in Moodle (coursework.h, coursework.c, linkedlist.h and linkedlist.c), and that only the final
version of your code should be submitted in Moodle for marking.
3.1 Part 1 – Process Simulation
This part does not simulate I/O. That is, the runPreemptiveProcess() function – used to simulate
processes running on the CPU – should be called with the second and third parameter set to false (or
3.1.1 Simulation of a Single Process
In the main function of your code, create a single process using the generateProcess() function
and simulate it running in a round robin fashion using the runPreemptiveProcess() function. Note
that the generateProcess() function returns an initialised “process control block” that is stored in
dynamic memory.
Save your code as simulator1.c. The output generated by your code should be written to the screen
and match the syntax of the output sample provided in Moodle.
3.1.2 Simulation of Multiple Processes
In the main function of your code, create a pre-defined number of processes (NUMBER_OF_PROCESSES)
and add them to a ready queue (implemented as a linked list). Once all processes have been generated,
simulate them in a round robin fashion using the runPreemptiveProcess() function provided. Pro-
cesses returned in the READY state are re-added to the tail of the ready queue. Processes returned in
the TERMINATED state are added to the tail of the terminated queue. Once all processes have finished
running, remove them from the terminated queue one by one and free any associated resources.
Tip: note that a macro to initialise a linked list structure is provided and can be used as:
LinkedList oProcessQueue = LINKED_LIST_INITIALIZER.
Save your code as simulator2.c. The output generated by your code should be written to the screen
and match the syntax of the output sample provided in Moodle.
3.1.3 Parallelism
Single Process Simulator
This step introduces parallelism into your code by implementing the process generator, process simula-
tor and process terminator as threads. The process generator adds processes to the ready queue, goes
to sleep when there are MAX_CONCURRENT_PROCESSES in the system, and is woken up when space for
new processes becomes available again. The process simulator removes processes from the ready queues
and runs them in a round robin fashion using the runPreemptiveProcess() function. Processes re-
turned in the READY state are re-added to the ready queue, processes returned in the TERMINATED state
are added to the terminated queue, and the process terminator is woken up. The simulator finishes
when all processes have finished.
Save your code as simulator3.c. The output generated by your code should be written to the screen
and match the syntax of the output sample provided in Moodle.
Parallel Process Simulators
Extend the code above to have a configurable number of process simulators. Note that all simulators
must terminate gracefully once all processes have finished.
Save your code as simulator4.c. The output generated by your code should be written to the screen
and match the syntax of the output sample provided in Moodle.
3.1.4 Process Table
Add a process table to your code, implemented as an array of size SIZE_OF_PROCESS_TABLE and
indexed by PID. The process generator is now responsible for adding new processes to the process
table, in addition to the ready queue. The termination daemon is now also required to remove finished
processes from the process table.
Note that the implementation above requires to add a “pool” (implemented as an array) of available
PIDs. That is, when a process is created using the generateProcess() function, a PID is removed
from the pool. When it is cleaned up (by the process terminator), the PID is re-added to the pool.
Although this can be implemented using counting semaphores, your implementation must use binary
semaphores only to manage the PID pool.
Save your code as simulator5a.c. The output generated by your code should be written to the screen
and match the syntax of the output sample provided in Moodle.
3.2 Part 2 – I/O Simulation
This part simulates I/O operations. It distinguishes between emulating I/O controllers for traditional
rotational hard drives, and an implementation of a reader-writer approach for a generic device. The
runPreemptiveProcess() function in this part should be called with the second and third parameter
set to true (or 1) as appropriate, and processes can now also be returned in the BLOCKED state. Note
that the the device number and device type in the process control block enable you to identify the
type of I/O request and to which device it applies.
3.2.1 Hard Drive Access: FCFS
Add an appropriate queuing structure to your code to simulate disk access. Disk requests are added
to the queue when they become available, and processed in FCFS order. Similar to, e.g., the process
terminator, the “disk controller” goes to sleep when there are no requests available, and is woken up
when new requests are added. To emulate disk access times, the simulateIO() function should be
called as requests are processed. Once the I/O request for a given process is dealt with, the process
enters the READY state and is added to the appropriate ready queue. Your implementation must ensure
fairness between I/O and CPU bound processes.
Save your code as simulator5b.c. The output generated by your code should be written to the screen
and match the syntax of the output sample provided in Moodle.
3.2.2 Hard Drive Access: LOOK-SCAN
Modify the code above to implement a LOOK-SCAN algorithm.
Save your code as simulator6.c. The output generated by your code should be written to the screen
and match the syntax of the output sample provided in Moodle.
3.2.3 Generic I/O Device
Single Device
Add a “device controller” and an appropriate queue structure to your code to simulate a single generic
I/O device. Requests must be processed using a reader-writer approach with fairness (see above),
allowing for parallel leading and serialised writing. Call the simulateIO() function to emulate I/O
access times.
Save your code as simulator7.c. The output generated by your code should be written to the screen
and match the syntax of the output sample provided in Moodle.
Multiple Devices
Extend the code above to handle multiple independent I/O devices. Every device should have its own
queue structure and act independent of one another. For instance, read and write requests on different
devices can happen with full parallelism, however, write requests on the same device are serialised.
Save your code as simulator8.c. The output generated by your code should be written to the screen
and match the syntax of the output sample provided in Moodle.
Requirements
Components
The Process Generator
Process Simulator
I/O Simulators
Hard Drive
Readers-Writers
Process Terminator
Output Sample
Part 1 – Process Simulation
Simulation of a Single Process
Simulation of Multiple Processes
Parallelism
Process Table
Part 2 – I/O Simulation
Hard Drive Access: FCFS
Hard Drive Access: LOOK-SCAN
Generic I/O Device
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com