Project planning diagram

CRITERIA

Studied Algos

CPU scheduling

Innovative Approaches to CPU Scheduling

A New Round Robin Algorithm for Task Scheduling in Real-time System

Simulation and Conclusion

Images

Code

Discussed Algorithms

RTOS

MMRR SCHEDULING

"A NEW OPTIMIZED CPU SCHEDULING ALGORITHM"

OPRR SCHEDULING

Simulation and Conclusion

Code

Discussed Algorithms

A new scheduling algorithm for server farms load balancing

Code

Algorithms

Simulation and Conclusion

Server Farms

HHRN SCHEDULING

A New Combination Approach to CPU Scheduling based on Priority and Round-Robin Algorithms for Assigning a Priority to a Process and Eliminating Starvation

Socket Types

Code

Conclusion and Simulation

Literature Review

MIX PI_RR SCHEDULING

Conclusion and Sim

The Median Mean Round Robin (MMRR) algorithm enhances the traditional RR by dynamically calculating time quantum based on the median and mean of burst times, reducing waiting time, turnaround time, and context switches. It outperforms other algorithms like ADRR and HYRR, making it effective for real-time systems. Future work will explore combining dynamic and fixed quantum values.

Why is CPU scheduling Important

CPU scheduling is important in operating systems because it ensures efficient utilization of the CPU by deciding which process to run when multiple processes are ready. It improves system performance, minimizes waiting and turnaround times, and ensures fairness among processes, ultimately optimizing the user experience

Types:

1. real-time strict system: smallest time error can have fatal human and economic consequences. Most avionics, car, and other applications are strict real-time. 2. Real-time flexible system: a system that is subject to flexible time constraints and can accept a number of timing faults. 3. A real-time mixed system: is one in which time restrictions are both strict and flexible. A real-time task is made up of a set of instructions that can be executed in order on one or more processors while keeping time limitations in mind.

RTOS (Real Time Operating Systems)

A reactive system that must meet time limitations is known as a real-time system.The most important constraint to meet is time constraints.

Round Robin

Priority

FCFS

Server farms face multiple challenges in managing processes and allocating resources, such as:

• Handling a high volume of user requests.
• Dealing with diverse computational needs across processes.
• Preventing starvation of long-running processes.
• Minimizing waiting times for time-sensitive tasks.

The HRRN algorithm addresses these challenges effectively through:

• Dynamic Priority Allocation
• Starvation Prevention
• Adaptive Scheduling

Server Farms

Server farms, also referred to as data centers, are essential components of the modern technological ecosystem. These facilities consist of large clusters of servers working together to provide computational power, storage, and networking services to support various applications and platforms. Server farms are the backbone of modern digital infrastructure, enabling services like cloud computing, social media, e-commerce, and big data processing. While they offer unparalleled computational power and storage capabilities, challenges like energy consumption and scalability demand innovative solutions. As technology evolves, server farms must continuously adapt to meet the needs of an increasingly digital world.

Conclusion and Sim

The Optimized Round Robin algorithm dynamically calculates the time quantum based on process burst times, reducing waiting time, turnaround time, and context switches compared to standard Round Robin. This approach improves scheduling efficiency, with future work focusing on refining dynamic or specific time slices for further performance gains.

• Requires Continuous Calculation
• Not Suitable for Real-Time Processes
• Complexity with Large Queues

Disadvantages of HRRN Scheduling

Advantages of HRRN Scheduling

• Reduces Waiting Time
• Prevents Starvation
• Simple and Effective
• Wide Applicability

• Throughput: The number of processes completed per unit time. • Priority: The importance assigned to processes to decide execution order. • Fairness: Ensuring that all processes receive equal opportunities to execute without starvation. • Time Quantum: A small, fixed unit of time allocated to each process in Round Robin scheduling.

Criteria

• Turnaround Time: The total time taken from the submission of a process to its completion. • Waiting Time: The time a process spends in the ready queue, waiting for the CPU. • Context Switching: The overhead caused by switching the CPU's focus from one process to another. • Response Time: The time from the submission of a request until the first response is produced. • CPU Utilization: The average fraction of time during which the CPU is actively executing processes.

The Shortest Remaining Process Time (SRPT) algorithm offers the best performance but suffers from starvation. In contrast, First-Come-First-Served (FCFS) is fair but results in high average turnaround time. Scheduling algorithms closer to SRPT, such as HRRN (Highest Response Ratio Next), achieve better performance. The proposed algorithm utilizes HRRN in server farms to distribute incoming jobs effectively. HRRN offers performance comparable to SRPT while overcoming starvation issues. By employing HRRN in server farm dispatchers, overall system performance is enhanced, ensuring both fairness and efficiency.

Simulation and Conclusion

Proposed Algorithm (HRRN)

HRRN is discussed in this paper and shown how to evaluate it. HRRN is a variation on SRPT to solve a problem whereby long tasks may never get CPU time. The HRRN algorithm fixes this by adjusting the priority of processes which are waiting to be run.

Discussed Algorithms

• FCFS
• Simple
• Convoy effect, long waiting times
• SRPT
• minimize avg waiting and turnaround time
• Starvation for long processes if short ones keep arriving
• Multilevel Queue
• Handles diversity of priority
• Complex management, Starvation in low priority queue
• Round Robin

• Fairness :)
• Fairness :(

Discussed Algos

IRR: Works similar to Round Robin (RR) with a small improvement. After the time quantum of a process completes, if the remaining burst time is less than 1 time quantum, the CPU is reallocated to the process to finish execution; otherwise, the process is moved to the tail of the ready queue. AAIRR: Focuses on improving the Improved Round Robin (IRR) algorithm by reducing waiting and turnaround times significantly. It operates in three stages, ensuring the shortest remaining processes are prioritized after completing the first process allocation.

Simulation and Conclusion

The Mix PI-RR Scheduling Algorithm combines Priority Scheduling and Round-Robin with Priority Inheritance to address starvation and ensure fairness. It dynamically adjusts priorities, enabling efficient CPU utilization and responsiveness in multi-tasking systems. By balancing fairness and efficiency, it resolves key challenges in traditional scheduling methods. This adaptable and innovative solution is ideal for dynamic and real-time computing environments.

• Increased Complexity
• Overhead in Priority Adjustment
• Potential Context-Switching Overhead

• Limited Scalability for Large Systems

Disadvantages of PI_RR Scheduling

Advantages of PI_RR Scheduling

• Fairness
• Starvation-Free
• Efficiency

Literature Review

Key Findings from Previous Research:1. Priority Inheritance Protocols:

• Prevent priority inversion by elevating priority temporarily.
• Limited to resolving resource-locking scenarios.

2. Multi-Level Feedback Queues:

• Dynamic adjustment of process priority.
• High complexity and management overhead.

3. Hybrid Approaches:

• Combine strengths of algorithms like SJN and RR.
• Often fail to resolve starvation comprehensively.

Research Gap:

• A need for a fair, efficient, and starvation-free algorithm adaptable to dynamic environments.

1. Arrange all the processes in an ascending order according to their burst time 2. TQ ←└ (median + mean) / 2┘ 3. While (ready queue! =NULL) 4. If (remaining burst time < 0.5 * TQ) 5. Allocate CPU again to the current running process for the remaining burst time. Else 6. Put the remaining of the current process at the end of the ready queue. 7. Go to step 4

Proposed Alg (MMRR)

Discussed Algos

RR: All previous works based on Round Robin edit the time slice method.ADRR: Shortest burst time equals the time quantum. (Amended dynamic) HYRR: mean burst time and minimum burst time are used to calculate time quantum. (Hybrid) EDRR: a dynamic time quantum that would let a process to complete if the remaining execution time was less than or equal to 0.2th of the total execution time. the starting time quantum equals 0.8th of the maximal burst time. (effecient costumize)