Priority Scheduling

Priority Scheduling is a CPU scheduling algorithm where processes are assigned priorities, and the process with the highest priority is selected for execution. Let’s delve into the details:

Priority Assignment:
  • Each process is assigned a numerical priority value.
  • Lower numbers indicate higher priority (i.e., process with priority 1 has the highest priority).
  • Priority can be based on various factors such as memory requirements, time constraints, importance, etc
Types of Priority Scheduling:

Preemptive Scheduling:
  • In preemptive priority scheduling, tasks are assigned priorities.
  • If a higher-priority task arrives while a lower-priority task is running, the lower-priority task is preempted, and the higher-priority task starts executing.
  • Example: Real-time systems where critical tasks need immediate attention.
Non-Preemptive Scheduling:
  • In non-preemptive priority scheduling, the CPU is allocated to a specific process.
  • The process that holds the CPU continues until it releases it (e.g., by completing its execution or blocking).
  • No preemption occurs during execution.
  • Suitable for various hardware platforms without special timers or hardware support.

Characteristics of Priority Scheduling:
  • Processes are scheduled based on their assigned priorities.
  • If two jobs have the same priority, they are executed on a first-come, first-served basis.
  • Newer processes with higher priority can preempt currently running processes.
  • Priority numbers determine the order of execution.
Example: Consider the following processes:

Process    Priority    Burst Time    Arrival Time
P1             1                 4                 0
P2             2                 3                 0
P3             1                 7                 6
P4             2                 2                11
P5             3                 4                12

Execution steps: ( Non preemptive)
  • At time = 0, P1 and P2 arrive. P1 (priority 1-high priority) starts execution.
  • At time = 4, P1 completes, and P2 (priority 2) starts.
  • At time = 6, P3 (priority 1) arrives 
  • At time=7, P3 starts execution
  • At time =14 ,P4 starts execution( high priority)
  • At time=16 ,P5 starts execution
  • At time=20 , P5 finish execution
Gant Chart

Average waiting Time: (0+4+1+3+4)/5=2.4ms
Average Turn around Time:(4+7+8+5+8)/5=6.4ms

Execution steps: ( Preemptive)
  • At time = 0, P1 and P2 arrive. P1 (priority 1-high priority) starts execution.
  • At time = 4, P1 completes, and P2 (priority 2) starts.
  • At time = 6, P3 (priority 1) arrives and preempt P2
  • At time=13, P2 resumes execution
  • At time =14 ,P4 starts execution( high priority)
  • At time=16 ,P5 starts execution
  • At time=20 , P5 finish execution
Gant Chart


Average waiting Time: (0+11+0+3+4)/5=3.6ms
Average Turn around Time:(4+14+7+5+8)/5=7.6ms

Advantages:
  • Ensures high-priority tasks get prompt attention.
  • Useful for real-time systems and critical applications.
  • Priority scheduling can reduce the average waiting time for processes that require a significant amount of CPU time.
Disadvantages:
  • May lead to starvation if lower-priority tasks never get a chance.
  • Priority inversion can occur when a low-priority task holds a resource needed by a high-priority task.
//************************************************************
// C Program Round Robin -Non Preemptive version with some restrictions
//*************************************************************
#include <stdio.h>

struct Process {
    int processNo;
    int arrivalTime;
    int burstTime;
    int priority;
};

void sortProcesses(struct Process proc[], int n) {
    // Sort processes based on arrival time and priority
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (proc[j].arrivalTime < proc[i].arrivalTime ||
                (proc[j].arrivalTime == proc[i].arrivalTime && proc[j].priority < proc[i].priority)) {
                // Swap processes
                struct Process temp = proc[i];
                proc[i] = proc[j];
                proc[j] = temp;
            }
        }
    }
}

void calculateWaitingTime(struct Process proc[], int wt[], int n) {
    wt[0] = 0; // Waiting time for the first process is zero
    int pstart[n];
    pstart[0]=0;
    for (int i = 1; i < n; i++) {
        pstart[i]=pstart[i-1]+proc[i - 1].burstTime;
        wt[i] = pstart[i]-proc[i].arrivalTime;
    }
}

void calculateTurnaroundTime(struct Process proc[], int wt[], int tat[], int n) {
    for (int i = 0; i < n; i++) {
        tat[i] = proc[i].burstTime + wt[i];
    }
}

int main() {
    int n;
    printf("Enter the number of processes: ");
    scanf("%d", &n);

    struct Process proc[n];
    int wt[n], tat[n];

    printf("Enter process details (arrival time, burst time, priority):\n");
    for (int i = 0; i < n; i++) {
        proc[i].processNo = i + 1;
        printf("P%d: ", i + 1);
        scanf("%d %d %d", &proc[i].arrivalTime, &proc[i].burstTime, &proc[i].priority);
    }

    // Sort processes based on arrival time and priority
    sortProcesses(proc, n);

    // Calculate waiting time and turnaround time
    calculateWaitingTime(proc, wt, n);
    calculateTurnaroundTime(proc, wt, tat, n);

    // Display results
    float awt=0,atat=0;
    printf("\nProcess\tArrival Time\tBurst Time\tPriority\tWaiting Time\tTurnaround Time\n");
    for (int i = 0; i < n; i++) {
        printf("P%d\t%d\t\t%d\t\t%d\t\t%d\t\t%d\n", proc[i].processNo, proc[i].arrivalTime,
               proc[i].burstTime, proc[i].priority, wt[i], tat[i]);
    awt=awt+wt[i];
    atat=atat+tat[i];
        
    }
  printf("AWT=%f\t ATAT=%f",awt/n,atat/n);
    return 0;
}
Output:
Enter the number of processes: 5
Enter process details (arrival time, burst time, priority):
P1: 0 4 1
P2: 0 3 2
P3: 6 7 1
P4: 11 2 2
P5: 12 4 3

Process     Arrival Time    Burst Time      Priority        Waiting Time    Turnaround Time
        P1              0                   4                   1                   0                       4
        P2              0                   3                   2                   4                       7
        P3              6                   7                   1                   1                       8
        P4              11                  2                   2                   3                       5
        P5              12                  4                   3                   4                       8
AWT=2.400000     ATAT=6.400000

Comments

Post a Comment

Popular posts from this blog

CSL 204 OPERATING SYSTEM LAB KTU IV SEM CSE

About Me Syllabus Scheme Program List Linux Basics 1. Linux History and GNU 2. Linux Basic Features and Architecture 3. How to Install Linux 4. Install Linux Inside Windows using WSL 5. Free software 6. Linux Chronology 7 .Package Management 8 .Compile and install from source 9 .Important Directories 10. File Permissions 11. Special Permissions 12 .Shell 13. Bash shell in windows 10 14 .Basic Linux command for beginners 15. Input Output Redirection  16. Directory Commands 17. File Commands 18 .Communication Commands 19. Information Commands  20 .IO Commands   21 .Process Management Commands 22. Account Administration Commands 23. Pipes and Filters  24. Top 100 commands to learn. Shell Programming 1. Shell Script 2. Arithmetic Expressions 3. Special Shell Variables 4. Shell Script for getting important info 5. if and case statement 6. looping statements while,until,for 7. Menu driven Programs 8. GUI Menus 9. Functions in scripts 10. String Handling 11. Command line arguments in scripts
Read more

FCFS and SJF

Image
CPU Scheduling in Operating Systems: In the context of operating systems, CPU scheduling involves determining which process (or task) should be executed next by the central processing unit (CPU). The goal is to maximize CPU utilization, minimize waiting time, and ensure fair allocation of resources. Various scheduling algorithms are used to achieve these objectives. First-Come-First-Serve (FCFS) Scheduling: Definition: FCFS is the simplest CPU scheduling algorithm. It is non-preemptive, meaning once a process starts executing, it cannot be interrupted until completion. Processes are placed in a queue based on their arrival time. The process that arrives first gets executed first. Execution Order : Processes are executed in the order they arrive. The process at the front of the queue is selected for execution. Advantages: Easy to implement. Minimal overhead. Disadvantages: Often results in long waiting times. Leads to the convoy effect (where a long process holds up other processes). Sh
Read more

Shared Memory Inter-Process Communication ( IPC)

Shared memory Inter-Process Communication (IPC) in Linux allows processes to communicate by sharing a region of memory. This method is efficient because it avoids the overhead of copying data between processes. Here's how shared memory IPC is typically done in Linux: Create a Shared Memory Segment: To use shared memory IPC, you need to create a shared memory segment. This is done using the shmget() system call, which allocates a new shared memory segment or obtains the identifier of an existing one. You specify the size of the shared memory segment and some permissions. Attach the Shared Memory Segment: Once you have obtained the identifier for the shared memory segment, you need to attach it to the address space of your process. This is done using the shmat() system call. This call returns the address of the shared memory segment in your process's address space. Accessing the Shared Memory: After attaching the shared memory segment to your process's address space, you c
Read more