Answered step by step
Verified Expert Solution
Question
1 Approved Answer
You are required to apply the concepts of data structures and algorithms that you have learned in this course to design, analyze, implement, test, and
You are required to apply the concepts of data structures and algorithms that you have learned in this course to design, analyze, implement, test, and document a System for Deterministic Modeling of CPU Scheduling Algorithms described below: A. Each process P in the system can have the following attributes: A1. Arrival Time: the time when process P first makes a request to the CPU Scheduler to execute on the CPU. Each Arrival Time can be expressed as a nonnegative integer. A2. Sequence of CPU Computation Time and 1/0 Time Requirements which can each be expressed as a nonnegative integer (see example below). A3. Process Priority, expressed as a nonnegative number. (Process Priority Numbers will only be used when Priority Scheduling is applied. Lower Process Priority Numbers correspond to higher process priorities.) For example, for some process P: Arrival_Time(P) = 8; The Sequence of CPU Computation Time and I/O Time Requirements of process P could have 5 components as follows: (1) CPU_time(P) = 10; (P needs to execute 10 time units on the CPU at first) (2) I/O_time(P, 0) = 15; (then P needs to do I/O for 15 time units on I/O device 0) (3) CPU_time(P) = 16 (then P needs to execute 16 time units on the CPU) (4) I/O_time(P, 1) = 20; (then P needs to do 1/0 for 20 time units on 1/0 device 1) (5) CPU_time(P) = 8. (then P needs to execute 8 time units on the CPU before terminating) Process_Priority(P) = 2. Please note that the 10 time requirements only includes the time that is needed when a process P is actually doing I/O; it DOES NOT include the time that it may need to spend waiting in an 1/0 queue before the 1/0 device becomes available. B. At any point in time, each process P in the system can be in any one of the following states, according to Section 5.1, Basic Concepts, Section 5.2, Scheduling Criteria, Section 5.3, Scheduling Algorithms (pages 200 to 214), Section 5.8.1, Deterministic Modeling, (pages 245-247), of Chapter 5, CPU Scheduling, in the book authored by Silberschatz, Galvin, and Gagne, Operating System Concepts, Tenth Edition, Wiley, 2018. (a) New: P has not arrived yet; (b) Running: P has been selected by the CPU scheduler for execution on the CPU, and is currently executing on the CPU; (c) Ready: P has already arrived, and P is currently waiting in the ready queue to be scheduled by the CPU Scheduler for execution on the CPU; (d) Waiting for 1/0: P had previously made an I/O request to the I/O scheduler in order to perform 1/0 on an 1/0 device, and P is either currently performing 1/0 on an 1/0 device or is currently waiting in an 1/0 queue so that it can be scheduled by the I/O Scheduler to perform 1/0 on an 1/0 device; (e) Terminated: P has completed its sequence of CPU computation time and I/O time requirements. C. The System for Deterministic Modeling of CPU Scheduling Algorithms must provide the ability to use any one of the scheduling algorithms described in Section 5.3, Scheduling Algorithms of the above mentioned book, to schedule a set of processes as described in Section 5.1, Basic Concepts of the above mentioned book on a single CPU. In particular, the System for Deterministic Modeling of CPU Scheduling Algorithms allows all of the following scheduling algorithms described in Section 5.3, Scheduling Algorithms, of the above mentioned book to be used: C2. Nonpreemptive Shortest-Job-First (SJF) Scheduling Nonpreemptive Shortest-Job-First (SJF) scheduling is explained in detail in Section 5.3.2. Shortest-Job-First Scheduling, of the above mentioned book, in Operating System_Concepts_CPU_Scheduling.pdf. C3. Preemptive SJF (Shortest-Remaining-Time-First) Scheduling Preemptive SJF (Shortest-Remaining-Time-First) scheduling is also explained in detail in Section 5.3.2. Shortest-Job-First Scheduling, of the above mentioned book, Operating System Concepts_CPU_Scheduling.pdf. C4. Nonpreemptive Priority Scheduling Nonpreemptive Priority scheduling is explained in detail in Section 5.3.4. Priority Scheduling, of the above mentioned book, in Operating System_Concepts_CPU_Scheduling.pdf. C5. Preemptive Priority Scheduling Preemptive Priority scheduling is also explained in detail in Section 5.3.4. Priority Scheduling, of the above mentioned book, in Operating System_Concepts_CPU_Scheduling.pdf. C6. Preemptive Round-Robin (RR) Scheduling Preemptive Round-Robin (RR) scheduling is explained in detail in Section 5.3.3. Round-Robin Scheduling, of the above mentioned book, in Operating System_Concepts_CPU_Scheduling.pdf. D. The following can be assumed regarding 1/0 devices and the I/0 Scheduler: Dl. There can exist any number of I/O devices in the system; D2. There is only one 1/0 queue for each I/O device; D3. I/O queues are scheduled by Nonpreemptive FCFS scheduling. E. For any given set of processes for which the Arrival Time, Sequence of CPU Computation Time and I/O Time Requirements, and Process Priority are given for each process, the system will be able compute the following for any of the CPU scheduling algorithms described above, you may assume that the context switch time is 0) according to the definitions provided in Section 5.2, Scheduling Criteria, p. 204-205 of the above mentioned book in Operating System_Concepts_CPU_Scheduling.pdf: E1. Average Waiting Time; E2. Average Turnarounnd Time. 1.3. Requirements regarding the design, analysis, implementation, testing, and documentation of the software in the System for Deterministic Modeling of CPU Scheduling Algorithms (a) When designing the software to implement the System for Deterministic Modeling of CPU Scheduling Algorithms, you must apply best practice software engineering principles and carefully choose appropriate data structures and methods. Furthermore, in your report/documentation you must justify and explain why you chose each particular data structure and method. (b) You must analyze the asymptotic run times and space usage of your methods in the report. (c) You must describe in detail any problems or difficulties that you had encountered, and how you solved or were able to overcome those problems or difficulties in the report. (d) Additional Requirements: (dl) You must make sure that your code has very detailed comments. (d2) You must make sure that your code compiles correctly. (d3) You must make sure that your code does not generate non-recoverable exceptions. (04) You must make sure that your code is able to handle incorrect input. Failure to satisfy all the requirements above will result in a low mark for the assignment. You are required to apply the concepts of data structures and algorithms that you have learned in this course to design, analyze, implement, test, and document a System for Deterministic Modeling of CPU Scheduling Algorithms described below: A. Each process P in the system can have the following attributes: A1. Arrival Time: the time when process P first makes a request to the CPU Scheduler to execute on the CPU. Each Arrival Time can be expressed as a nonnegative integer. A2. Sequence of CPU Computation Time and 1/0 Time Requirements which can each be expressed as a nonnegative integer (see example below). A3. Process Priority, expressed as a nonnegative number. (Process Priority Numbers will only be used when Priority Scheduling is applied. Lower Process Priority Numbers correspond to higher process priorities.) For example, for some process P: Arrival_Time(P) = 8; The Sequence of CPU Computation Time and I/O Time Requirements of process P could have 5 components as follows: (1) CPU_time(P) = 10; (P needs to execute 10 time units on the CPU at first) (2) I/O_time(P, 0) = 15; (then P needs to do I/O for 15 time units on I/O device 0) (3) CPU_time(P) = 16 (then P needs to execute 16 time units on the CPU) (4) I/O_time(P, 1) = 20; (then P needs to do 1/0 for 20 time units on 1/0 device 1) (5) CPU_time(P) = 8. (then P needs to execute 8 time units on the CPU before terminating) Process_Priority(P) = 2. Please note that the 10 time requirements only includes the time that is needed when a process P is actually doing I/O; it DOES NOT include the time that it may need to spend waiting in an 1/0 queue before the 1/0 device becomes available. B. At any point in time, each process P in the system can be in any one of the following states, according to Section 5.1, Basic Concepts, Section 5.2, Scheduling Criteria, Section 5.3, Scheduling Algorithms (pages 200 to 214), Section 5.8.1, Deterministic Modeling, (pages 245-247), of Chapter 5, CPU Scheduling, in the book authored by Silberschatz, Galvin, and Gagne, Operating System Concepts, Tenth Edition, Wiley, 2018. (a) New: P has not arrived yet; (b) Running: P has been selected by the CPU scheduler for execution on the CPU, and is currently executing on the CPU; (c) Ready: P has already arrived, and P is currently waiting in the ready queue to be scheduled by the CPU Scheduler for execution on the CPU; (d) Waiting for 1/0: P had previously made an I/O request to the I/O scheduler in order to perform 1/0 on an 1/0 device, and P is either currently performing 1/0 on an 1/0 device or is currently waiting in an 1/0 queue so that it can be scheduled by the I/O Scheduler to perform 1/0 on an 1/0 device; (e) Terminated: P has completed its sequence of CPU computation time and I/O time requirements. C. The System for Deterministic Modeling of CPU Scheduling Algorithms must provide the ability to use any one of the scheduling algorithms described in Section 5.3, Scheduling Algorithms of the above mentioned book, to schedule a set of processes as described in Section 5.1, Basic Concepts of the above mentioned book on a single CPU. In particular, the System for Deterministic Modeling of CPU Scheduling Algorithms allows all of the following scheduling algorithms described in Section 5.3, Scheduling Algorithms, of the above mentioned book to be used: C2. Nonpreemptive Shortest-Job-First (SJF) Scheduling Nonpreemptive Shortest-Job-First (SJF) scheduling is explained in detail in Section 5.3.2. Shortest-Job-First Scheduling, of the above mentioned book, in Operating System_Concepts_CPU_Scheduling.pdf. C3. Preemptive SJF (Shortest-Remaining-Time-First) Scheduling Preemptive SJF (Shortest-Remaining-Time-First) scheduling is also explained in detail in Section 5.3.2. Shortest-Job-First Scheduling, of the above mentioned book, Operating System Concepts_CPU_Scheduling.pdf. C4. Nonpreemptive Priority Scheduling Nonpreemptive Priority scheduling is explained in detail in Section 5.3.4. Priority Scheduling, of the above mentioned book, in Operating System_Concepts_CPU_Scheduling.pdf. C5. Preemptive Priority Scheduling Preemptive Priority scheduling is also explained in detail in Section 5.3.4. Priority Scheduling, of the above mentioned book, in Operating System_Concepts_CPU_Scheduling.pdf. C6. Preemptive Round-Robin (RR) Scheduling Preemptive Round-Robin (RR) scheduling is explained in detail in Section 5.3.3. Round-Robin Scheduling, of the above mentioned book, in Operating System_Concepts_CPU_Scheduling.pdf. D. The following can be assumed regarding 1/0 devices and the I/0 Scheduler: Dl. There can exist any number of I/O devices in the system; D2. There is only one 1/0 queue for each I/O device; D3. I/O queues are scheduled by Nonpreemptive FCFS scheduling. E. For any given set of processes for which the Arrival Time, Sequence of CPU Computation Time and I/O Time Requirements, and Process Priority are given for each process, the system will be able compute the following for any of the CPU scheduling algorithms described above, you may assume that the context switch time is 0) according to the definitions provided in Section 5.2, Scheduling Criteria, p. 204-205 of the above mentioned book in Operating System_Concepts_CPU_Scheduling.pdf: E1. Average Waiting Time; E2. Average Turnarounnd Time. 1.3. Requirements regarding the design, analysis, implementation, testing, and documentation of the software in the System for Deterministic Modeling of CPU Scheduling Algorithms (a) When designing the software to implement the System for Deterministic Modeling of CPU Scheduling Algorithms, you must apply best practice software engineering principles and carefully choose appropriate data structures and methods. Furthermore, in your report/documentation you must justify and explain why you chose each particular data structure and method. (b) You must analyze the asymptotic run times and space usage of your methods in the report. (c) You must describe in detail any problems or difficulties that you had encountered, and how you solved or were able to overcome those problems or difficulties in the report. (d) Additional Requirements: (dl) You must make sure that your code has very detailed comments. (d2) You must make sure that your code compiles correctly. (d3) You must make sure that your code does not generate non-recoverable exceptions. (04) You must make sure that your code is able to handle incorrect input. Failure to satisfy all the requirements above will result in a low mark for the assignment
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started