CPU Scheduling Algorithms

-

 Certainly, let's explain each CPU scheduling algorithm in a more formal manner:


### First Come, First Served (FCFS)

- **Description**: FCFS is a non-preemptive CPU scheduling algorithm where processes are executed in the order they arrive in the ready queue.

- **Operation**: Upon arrival, processes are added to the end of the ready queue. The CPU is allocated to the first process in the queue, which continues execution until it completes its CPU burst or enters an I/O wait state. Subsequent processes are selected for execution based on their arrival order.

- **Characteristics**:

  - **Advantages**: Simple implementation, fair execution order.

  - **Disadvantages**: Potential for poor response time and inefficient CPU utilization, especially with long-running processes.


### Shortest Job First (SJF)

- **Description**: SJF is a CPU scheduling algorithm that selects the process with the shortest expected CPU burst time for execution.

- **Operation**: Processes are selected for execution based on their CPU burst time, with the shortest job given priority. This algorithm can be preemptive or non-preemptive.

- **Characteristics**:

  - **Advantages**: Optimal average waiting time, efficient CPU utilization for short processes.

  - **Disadvantages**: Potential for starvation of longer processes if shorter ones continually arrive.


### Round Robin (RR)

- **Description**: RR is a CPU scheduling algorithm that allocates a fixed time slice to each process in a cyclic manner.

- **Operation**: Processes are placed in a ready queue and are executed for a predefined time quantum. If a process does not complete within its time slice, it is preempted and placed at the end of the ready queue.

- **Characteristics**:

  - **Advantages**: Fair allocation of CPU time, prevents process starvation.

  - **Disadvantages**: Overhead from frequent context switches, potential for increased response time with longer time slices.


### Priority Scheduling

- **Description**: Priority scheduling is a CPU scheduling algorithm that assigns priority levels to processes and executes higher-priority processes first.

- **Operation**: Each process is assigned a priority value, and the CPU scheduler selects the process with the highest priority for execution. Preemption may occur if a higher-priority process becomes available.

- **Characteristics**:

  - **Advantages**: Allows for prioritization of important tasks, suitable for real-time systems.

  - **Disadvantages**: Potential for starvation of lower-priority processes, may lead to inefficiencies if priorities are not managed effectively.


### Multilevel Queue Scheduling

- **Description**: Multilevel queue scheduling partitions the ready queue into multiple queues, each with its own scheduling algorithm and priority level.

- **Operation**: Processes are assigned to different queues based on criteria such as priority or process type. Each queue operates independently, with processes serviced according to their priority level and the scheduling algorithm of their respective queue.

- **Characteristics**:

  - **Advantages**: Allows for management of diverse process types and priorities, efficient resource allocation.

  - **Disadvantages**: Complexity in managing multiple queues and scheduling algorithms, potential for increased overhead.



**Multilevel Feedback Queue (MLFQ) Scheduling:**

- MLFQ categorizes tasks into multiple queues based on priority.

- Tasks move between queues depending on their urgency and behavior.

- Initially, tasks start in high-priority queues for prompt execution.

- Each queue has a time limit for task execution, shorter for high-priority queues.

- Tasks are selected for execution from the highest-priority non-empty queue.

- MLFQ dynamically adjusts task priorities based on their behavior during execution.

- It's effective for balancing responsiveness and maximizing CPU utilization.


**Processor Affinity:**

- Processor affinity assigns specific tasks to specific processors or cores.

- This reduces cache thrashing by keeping tasks localized to certain processors.

- Tasks can be either hard-affined (stays on one processor) or soft-affined (preferred but can move).

- Affinity improves cache locality, especially in NUMA systems.

- It enhances overall system performance by minimizing cache misses and memory access latency.

- Affinity can be applied at the thread level in multithreaded applications.

- It requires careful management to balance performance gains with overall system throughput.


**Shortest Remaining Time (SRT) Scheduling:**

- SRT prioritizes tasks based on their remaining execution time.

- When a new task arrives, it compares its time to completion with currently running tasks.

- If the new task can finish sooner, it preempts the current task and starts executing.

- Preemption involves pausing the current task, saving its state, and switching to the new task.

- SRT dynamically adjusts task priorities based on their remaining execution times.

- It minimizes response time but can increase overhead due to frequent preemptions.

- SRT is commonly used in real-time systems to meet strict deadlines.


**Real-time Scheduling:**

- Real-time scheduling organizes tasks to meet deadlines.

- Feasibility and schedulability are crucial; tasks must complete on time.

- Different scheduling policies exist, like Earliest Deadline First (EDF) and Rate-Monotonic (RM).

- Feasibility refers to the proof that tasks will complete within their deadlines.

- Schedulability means there's a feasible schedule for the tasks.

- Utilization measures how much time the scheduler is active versus allocated tasks.

- Real-time scheduling is vital in areas like embedded systems, networking, and aerospace.

Comments

Post a Comment

Popular posts from this blog

SE

-
  SDLC Models in Detail: 1. Waterfall Model: - This is the basic/classic SDLC model - The phases happen in a strict linear sequence - requirements, design, implementation, testing, deployment, maintenance - Each phase must be completed fully before moving to the next phase - It is like a "waterfall" of progress flowing steadily downwards - Easy to understand and use, but very rigid and no room for revisions once a phase is over 2. Iterative Waterfall Model:  - Provides a feedback path to previous phases to allow changes/revisions - For example, if an issue is found in testing, you can loop back and rework the design - More flexible than the basic waterfall, but still quite rigid and sequential 3. Incremental Model: - The product is built and delivered in incremental releases - For example, an email app may release basic emailing first, then add calendaring, contacts, etc. in later increments   - Each increment goes through the full SDLC cycles - Allows faster deliver...
Read more

2.16 - 2.20

-
2.16 **Evolution of C++:** - Bjarne Stroustrup at Bell Laboratories made the first modifications to C in 1980, adding features from Simula 67 and Smalltalk. - These modifications included classes, derived classes, public/private access control, constructor and destructor methods, etc., resulting in "C with Classes" in 1983. - In 1984, virtual methods, method name and operator overloading, and reference types were added, resulting in C++. - The Cfront implementation of C++ appeared in 1985, followed by further evolutions leading to Release 2.0 in 1989 and Release 3.0 in 1990. - Key additions included multiple inheritance, abstract classes, templates, and exception handling. **Language Overview:** - C++ supports both procedural and object-oriented programming, with functions and methods. - Operators and methods can be overloaded, and dynamic binding is achieved through virtual methods. - Templated methods and classes allow for parameterization. - Multiple inheritance is support...
Read more

Synchronization

-
Image
1. **Synchronization Hardware:**    - Imagine you have a group project where each team member needs to work on a specific part simultaneously. Synchronization hardware ensures that everyone knows when to start and finish their task, preventing chaos and ensuring smooth collaboration. 2. **Atomic Operations:**    - Think of atomic operations as a "do not disturb" sign on a door when someone is inside doing something important. It guarantees that either the entire task is completed successfully, or none of it happens at all, avoiding halfway-done tasks and maintaining consistency. 3. **Memory Barriers and Fences:**    - Picture a bulletin board where everyone posts updates and announcements. Memory barriers and fences act like moderators, making sure that everyone sees the updates in the correct order and preventing misunderstandings or outdated information. 4. **Cache Coherence Protocols:**    - Imagine you and your friends have copies of the same ...
Read more