COMP2007_CW
操作系统与并发代写 Section 1- Introduction This coursework will be required to compile and run through on the SCHOOL’s servers.1.Goal: Make use of operating system
Section 1- Introduction
This coursework will be required to compile and run through on the SCHOOL’s servers.
1.
Goal: Make use of operating system APIs (specifically, the POSIX API in Linux) and concurrency directives to implement a process and I/O simulator. Onclude multiple process queues (which use the principle of bounded buffers), simulation of multiple CPUs, a readers-writers implementation with fairness for multiple devices, and a disk scheduler. The final simulator will have some principles embedded in it that you would find in common operating systems.
To complete the task you should know:
- Some operating system APIs.
- Implementations of process tables, process queues, and disk schedulingalgorithms.
- The basics of concurrent/parallel programming using operating system functionality.
- Critical sections, semaphores, mutexes, and mutual exclusion.
- Bounded buffers and readers-writers.
- C-programming.
(Use Section 3. It will get more complex and builds up key insights)
2.Helpful resources 操作系统与并发代写
Linux. The use of POSIX APIs, and the specific use of threads and concurrency directives – richard.esplins.org/static/downloads/linux_book.pdf
Data structures and concurrency / parallel programming-
- – Tanenbaum, Andrew S. 2014 Modern Operating Systems. 4th ed. Prentice Hall Press, Upper Saddle River, NJ, USA.
- – Silberschatz, Abraham, Peter Baer Galvin, Greg Gagne. 2008. Operating System Concepts.
8th ed. Wiley Publishing.
- – Stallings, William. 2008. Operating Systems: Internals and Design Principles. 6th
Prentice Hall Press, Upper Saddle River, NJ, USA.
3.MUST USE
- Functions to simulate processes and I/O access, definitions of key data structures, and definitions of constants (coursework.h and coursework.c).
- A generic implementation of a linked list (linkedlist.h and linkedlist.c) .
Section 2 – Requirements 操作系统与并发代写
1.Overview
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 below.
2.Components
1.
This part describes the functionality of the individual components in a full implementation of this coursework.
2.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).
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 implemented such that fairness between I/O and CPU bound processes is maintained. If the runPreemptiveProcess() function returns a process in:
- The READY state – re-added to the appropriate ready queue.
- The TERMINATED state – added to the terminated queue.
- The BLOCKED state – added to the appropriate I/O queue.
4.Input/Output Simulators 操作系统与并发代写
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.Reader-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.
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.
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 in the folder (“outputs”). 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.
Section 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 (coursework.h, coursework.c, linkedlist.h and linkedlist.c)
1.Process Simulation – Part 1
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 0).
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.
2.Simulation of a Single Process
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. Processes returned in the READY state are re-added to the tail of the ready queue. Processes returned inthe TERMINATED state are added to the tail of the terminated queue. Once all processes have finishedrunning, 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 screenand match the syntax of the output sample provided i
3.Parallelism 操作系统与并发代写
Single Process Simulator
This step introduces parallelism into your code by implementing the process generator, process simulator 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 returned 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. 8
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.
Parallel Process Simulator
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.
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 adding 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 simulator5.c. The output generated by your code should be written to the screen and match the syntax of the output sample provided
2.Input/Output Simulation – Part 2 操作系统与并发代写
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 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.
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 simulator5.c. The output generated by your code should be written to the screen and match the syntax of the output sample provided.
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.
3. Generic Input/Output 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
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.
