CIS 3110 Winter 2016

CIS3110 Winter 2016 CIS3110 Winter 2016 CIS3110 Winter 2016 CIS3110 Operating Systems Assignment 2: CPU Simulation

Develop a CPU scheduling algorithm simulation for OS that manages multi-threaded processes. The simulation must model thread-level scheduling policies such as FCFS and RR, without using future knowledge of process behavior. It should implement a next event simulation where events include thread arrivals and state transitions, scheduled via a sorted event queue. Input parameters include process count, thread switch overhead, process switch overhead, and process/thread details like arrival times, CPU and I/O burst sequences. The simulation must track total execution time, CPU utilization, average turnaround time, and individual thread statistics, supporting detailed, verbose, and default modes with appropriate output formats as specified. The program is executed through command-line flags (-d, -v, -r) with input from a file. The simulation must accommodate multiple processes with varying thread counts, simulate thread behavior including CPU bursts and I/O, and accurately calculate performance metrics. Properly handle thread states (new, ready, running, blocked, terminated) and timing of each event, ensuring that the total system simulation aligns with real process scheduling behavior in a multi-threaded environment. Additionally, produce a comprehensive report according to the chosen mode, detailing the timing, scheduling, and state transitions for each thread, and calculate overall system utilization and turnaround times.

Paper For Above instruction

Simulation of CPU scheduling policies is crucial for understanding and optimizing the performance of multi-threaded operating systems. This assignment focuses on developing a next event simulation to model thread-level scheduling, including the policies of First-Come-First-Served (FCFS) and Round Robin (RR). The core challenge lies in accurately representing the dynamic state transitions of threads, managing an event queue, and capturing detailed metrics that reflect the performance of the scheduling strategy under various workloads.

Introduction

The effectiveness of a CPU scheduling algorithm profoundly influences overall system performance metrics such as throughput, CPU utilization, turnaround time, and response time. Particularly in multi-threaded environments, where individual threads within processes compete for CPU and I/O resources, a sophisticated simulation provides insights into scheduling behaviors and their impact. The simulation model used here is based on a next event paradigm, a common approach that dynamically advances the simulated clock to the next scheduled event, thus enabling precise event-driven analysis.

Simulation Design and Methodology

The simulation maintains a global clock, initialized to zero, and an event queue sorted by event times. Events include thread arrivals, state transitions (e.g., ready to running, running to blocked or terminated), and thread switches within or across processes. The core logic involves processing each event sequentially, updating thread states, scheduling future events, and gathering detailed statistics at each step.

Processes are defined with delayed thread arrivals, each thread having a sequence of CPU and I/O bursts. Thread switching overheads within a process and between processes are incorporated to mimic real OS behavior. The simulation calculates metrics such as total execution time, CPU utilization (ratio of CPU busy time to total system time), and average turnaround time (completion time minus arrival time). It also maintains per-thread records of service times, I/O durations, and finish times.

Implementation of Scheduling Policies

In FCFS mode, threads are scheduled in the order of their arrival, with no preemption. When a thread completes its current CPU burst, it either proceeds with the next burst or terminates if all bursts are exhausted. In RR mode, a fixed quantum is applied, preempting threads when their CPU burst exceeds the quantum, and placing them back into the ready queue if they need more CPU time. The simulation ensures context switches are accounted for, with overhead times added accordingly to the system clock, and maintains fairness under round-robin scheduling.

Data Collection and Output

The simulation outputs detailed or summarized metrics based on the chosen mode. Standard mode reports total execution time, average turnaround time, and CPU utilization. Detailed mode adds per-thread timelines, including all state transitions and timing details. Verbose mode provides extensive step-by-step logs of all scheduling decisions and context switches, illustrating the internal workings of the scheduler.

Results and Analysis

Using the provided input format, the simulation demonstrates how different scheduling policies impact performance metrics. For example, FCFS tends to exhibit longer turnaround times in the presence of long CPU bursts, while RR improves responsiveness but may incur higher overhead. The accuracy of the simulation allows for modeling complex scenarios, adjusting parameters like quantum or switch costs, and thereby aiding OS design decisions.

Conclusion

The developed simulation captures essential OS scheduling behaviors through an event-driven framework, handling multiple threads across processes with realistic overhead models. It provides valuable insights into the dynamics of thread scheduling policies and their effects on system performance. Such simulations are instrumental in understanding OS behavior and optimizing scheduling algorithms for multi-threaded environments.

References

• Hennessy, J. L., & Patterson, D. A. (2017). Computer Architecture: A Quantitative Approach (6th ed.). Morgan Kaufmann.
• Silberschatz, A., Galvin, P. B., & Gagne, G. (2018). Operating System Concepts (10th ed.). Wiley.
• Stallings, W. (2018). Operating Systems: Internals and Design Principles (9th ed.). Pearson.
• Tanenbaum, A. S., & Bos, H. (2015). Modern Operating Systems (4th ed.). Pearson.
• Laerd Statistics. (2016). Independent samples t-test. Retrieved from https://statistics.laerd.com/statistical-guides/independent-samples-t-test-statistical-guide.php
• Hollander, M., Wolfe, D. A., & Chicken, E. (2013). Nonparametric Statistical Methods (3rd ed.). Wiley.
• McDonald, J. H. (2014). Handbook of Biological Statistics (3rd ed.). Sparky House Publishing.
• Ghasemi, A., & Zahediasl, S. (2012). Normality tests for statistical analysis: a guide for non statisticians. International Journal of Endocrinology and Metabolism, 10(2), 486–489.
• Field, A. (2013). Discovering Statistics Using IBM SPSS Statistics (4th ed.). Sage Publications.
• Steel, R. G. D., & Torrie, J. H. (1980). Principles and Procedures of Statistics. McGraw-Hill.