Scheduling algorithm

 

1. FCFS (First Come First Serve) Scheduling

Algorithm:

  1. Input n processes with Arrival Time (AT) and Burst Time (BT).

  2. Sort processes by Arrival Time.

  3. For the first process:

    • Completion Time (CT) = AT + BT

  4. For each next process:

    • CT = max(previous CT, current AT) + BT

  5. Calculate Turnaround Time (TAT) = CT - AT.

  6. Calculate Waiting Time (WT) = TAT - BT.

  7. Calculate average TAT and WT.

     

    Pseudo Code:

    text
    Start
  Input n
  For i = 1 to n
    Input AT[i], BT[i]
  Sort processes by AT

  CT[1] = AT[1] + BT[1]

  For i = 2 to n
    CT[i] = max(CT[i-1], AT[i]) + BT[i]
  EndFor

  For i = 1 to n
    TAT[i] = CT[i] - AT[i]
    WT[i] = TAT[i] - BT[i]
  EndFor

  Calculate average TAT and WT
  Print CT, TAT, WT, Average TAT, Average WT
End

    2. SJF (Shortest Job First) Non-preemptive Scheduling

    Algorithm:

  8. Input n processes with Arrival Time (AT) and Burst Time (BT).

  9. Initialize time = 0 and completed process count = 0.

  10. While all processes are not completed:

    • Select from arrived (AT ≤ time) and incomplete processes the one with smallest BT.

    • If none arrived yet, increment time.

    • Else schedule selected process:

      • CT = time + BT

      • Update time = CT

      • Calculate TAT and WT for process.

      • Mark the process as completed.

  11. Calculate average TAT and WT.

Pseudo Code:

text
Start
  Input n
  For i = 1 to n
    Input AT[i], BT[i], completed[i] = false

  time = 0, completedCount = 0

  While completedCount < n
    idx = process with min BT where AT[idx] <= time and not completed
    If idx == none
      time = time + 1
    Else
      CT[idx] = time + BT[idx]
      TAT[idx] = CT[idx] - AT[idx]
      WT[idx] = TAT[idx] - BT[idx]
      time = CT[idx]
      completed[idx] = true
      completedCount = completedCount + 1
    EndIf
  EndWhile

  Calculate average TAT and WT
  Print CT, TAT, WT, Average TAT, Average WT
End

3. Priority Scheduling Non-preemptive

Algorithm:

  1. Input n processes with Arrival Time (AT), Burst Time (BT), and Priority.

  2. Initialize time = 0 and completed count = 0.

  3. While some processes are incomplete:

    • Among arrived (AT ≤ time) and incomplete processes, select one with highest priority (lowest priority number).

    • If no processes arrived, increment time.

    • Otherwise, schedule the selected process:

      • CT = time + BT

      • Update time = CT

      • Calculate TAT = CT - AT, WT = TAT - BT

      • Mark the process completed.

  4. Calculate average TAT and WT.

Pseudo Code:

text
Start
  Input n
  For i = 1 to n
    Input AT[i], BT[i], Priority[i], completed[i] = false

  time = 0, completedCount = 0

  While completedCount < n
    idx = process with highest priority where AT[idx] <= time and not completed
    If idx == none
      time = time + 1
    Else
      CT[idx] = time + BT[idx]
      TAT[idx] = CT[idx] - AT[idx]
      WT[idx] = TAT[idx] - BT[idx]
      time = CT[idx]
      completed[idx] = true
      completedCount = completedCount + 1
    EndIf
  EndWhile

  Calculate average TAT and WT
  Print CT, TAT, WT, Average TAT, Average WT
End

4. SJF Preemptive (Shortest Remaining Job First / SRTF)

Algorithm:

  1. Input n processes with Arrival Time (AT) and Burst Time (BT).

  2. Set remaining time (RT) = BT for all processes.

  3. Initialize time = 0 and completed count = 0.

  4. While processes remain incomplete:

    • Among arrived (AT ≤ time) and incomplete, select process with smallest RT.

    • If none arrived, increase time.

    • Execute selected process for 1 unit time.

    • Decrease RT by 1.

    • If RT becomes zero, mark process completed, set CT = current time + 1.

    • Increase time by 1.

  5. Calculate TAT = CT - AT and WT = TAT - BT.

  6. Calculate average TAT and WT.

Pseudo Code:

text
Start
  Input n
  For i = 1 to n
    Input AT[i], BT[i]
    RT[i] = BT[i]
    completed[i] = false

  time = 0, completedCount = 0

  While completedCount < n
    idx = process with min RT where AT[idx] <= time and not completed
    If idx == none
      time = time + 1
      Continue
    EndIf

    Execute process idx for 1 unit
    RT[idx] = RT[idx] - 1
    time = time + 1

    If RT[idx] == 0
      completed[idx] = true
      completedCount = completedCount + 1
      CT[idx] = time
    EndIf
  EndWhile

  For i = 1 to n
    TAT[i] = CT[i] - AT[i]
    WT[i] = TAT[i] - BT[i]
  EndFor

  Calculate average TAT and WT
  Print CT, TAT, WT, Average TAT, Average WT
End



  1. code: fcfs

    #include <stdio.h>

    typedef struct {
        int pid; // Process ID
        int at;  // Arrival Time
        int bt;  // Burst Time
        int ct;  // Completion Time
        int tat; // Turnaround Time
        int wt;  // Waiting Time
    } Process;

    void sortByArrival(Process p[], int n) {
        for (int i = 0; i < n - 1; i++)
            for (int j = 0; j < n - i - 1; j++)
                if (p[j].at > p[j + 1].at) {
                    Process temp = p[j];
                    p[j] = p[j + 1];
                    p[j + 1] = temp;
                }
    }

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

        Process p[n];
        for (int i = 0; i < n; i++) {
            p[i].pid = i + 1;
            printf("Enter Arrival Time for P%d: ", i + 1);
            scanf("%d", &p[i].at);
            printf("Enter Burst Time for P%d: ", i + 1);
            scanf("%d", &p[i].bt);
        }

        sortByArrival(p, n);

        int time = 0;
        float sum_tat = 0, sum_wt = 0;
        printf("\nGantt Chart:\n| ");

        for (int i = 0; i < n; i++) {
            if (time < p[i].at)
                time = p[i].at;
            printf("P%d | ", p[i].pid);
            p[i].ct = time + p[i].bt;
            p[i].tat = p[i].ct - p[i].at;
            p[i].wt  = p[i].tat - p[i].bt;
            time = p[i].ct;
            sum_tat += p[i].tat;
            sum_wt += p[i].wt;
        }

        printf("\n\nPID\tAT\tBT\tCT\tTAT\tWT\n");
        for (int i = 0; i < n; i++)
            printf("P%d\t%d\t%d\t%d\t%d\t%d\n",
                    p[i].pid, p[i].at, p[i].bt, p[i].ct, p[i].tat, p[i].wt);

        printf("\nAverage Turnaround Time = %.2f", sum_tat / n);
        printf("\nAverage Waiting Time    = %.2f\n", sum_wt / n);

        return 0;
    }


    code : sjf


    #include <stdio.h>

    typedef struct {
        int pid; // Process ID
        int at;  // Arrival Time
        int bt;  // Burst Time
        int ct;  // Completion Time
        int tat; // Turnaround Time
        int wt;  // Waiting Time
        int completed; // Flag for completion
    } Process;

    int main() {
        int n, completed = 0, time = 0, prev = 0;
        float sum_tat = 0, sum_wt = 0;
        printf("Enter number of processes: ");
        scanf("%d", &n);

        Process p[n];
        for (int i = 0; i < n; i++) {
            p[i].pid = i + 1;
            printf("Enter Arrival Time for P%d: ", i + 1);
            scanf("%d", &p[i].at);
            printf("Enter Burst Time for P%d: ", i + 1);
            scanf("%d", &p[i].bt);
            p[i].completed = 0;
        }

        printf("\nGantt Chart:\n| ");

        while (completed < n) {
            int idx = -1, min_bt = 100000;
            for (int i = 0; i < n; i++) {
                if (p[i].at <= time && !p[i].completed && p[i].bt < min_bt) {
                    min_bt = p[i].bt;
                    idx = i;
                }
            }
            if (idx == -1) {
                time++;
                continue;
            }
            printf("P%d | ", p[idx].pid);
            p[idx].ct = time + p[idx].bt;
            p[idx].tat = p[idx].ct - p[idx].at;
            p[idx].wt  = p[idx].tat - p[idx].bt;
            time = p[idx].ct;
            p[idx].completed = 1;
            completed++;
            sum_tat += p[idx].tat;
            sum_wt += p[idx].wt;
        }

        printf("\n\nPID\tAT\tBT\tCT\tTAT\tWT\n");
        for (int i = 0; i < n; i++)
            printf("P%d\t%d\t%d\t%d\t%d\t%d\n",
                    p[i].pid, p[i].at, p[i].bt, p[i].ct, p[i].tat, p[i].wt);

        printf("\nAverage Turnaround Time = %.2f", sum_tat / n);
        printf("\nAverage Waiting Time    = %.2f\n", sum_wt / n);

        return 0;
    }


    code : srjf

     #include <stdio.h>
    #define MAX 100

    typedef struct {
        int pid; // Process id
        int at;  // Arrival Time
        int bt;  // Burst Time
        int rt;  // Remaining Time
        int ct;  // Completion Time
        int tat; // Turnaround Time
        int wt;  // Waiting Time
        int completed;
    } Process;

    int main() {
        int n, completed = 0, time = 0;
        float sum_tat = 0, sum_wt = 0;
        Process p[MAX];

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

        for (int i = 0; i < n; i++) {
            p[i].pid = i + 1;
            printf("Enter Arrival Time for P%d: ", i + 1);
            scanf("%d", &p[i].at);
            printf("Enter Burst Time for P%d: ", i + 1);
            scanf("%d", &p[i].bt);
            p[i].rt = p[i].bt;
            p[i].completed = 0;
        }

        printf("\nGantt Chart:\n| ");

        int last_idx = -1;
        while (completed < n) {
            int idx = -1, min_rt = 100000;
            for (int i = 0; i < n; i++) {
                if (p[i].at <= time && !p[i].completed && p[i].rt < min_rt && p[i].rt > 0) {
                    min_rt = p[i].rt;
                    idx = i;
                }
            }

            if (idx == -1) {
                time++;
                continue;
            }

            if (last_idx != idx) {
                printf("P%d | ", p[idx].pid);
                last_idx = idx;
            }

            p[idx].rt--;
            time++;

            if (p[idx].rt == 0) {
                p[idx].ct  = time;
                p[idx].tat = p[idx].ct - p[idx].at;
                p[idx].wt  = p[idx].tat - p[idx].bt;
                sum_tat += p[idx].tat;
                sum_wt  += p[idx].wt;
                p[idx].completed = 1;
                completed++;
            }
        }

        printf("\n\nPID\tAT\tBT\tCT\tTAT\tWT\n");
        for (int i = 0; i < n; i++)
            printf("P%d\t%d\t%d\t%d\t%d\t%d\n",
                    p[i].pid, p[i].at, p[i].bt, p[i].ct, p[i].tat, p[i].wt);

        printf("\nAverage Turnaround Time = %.2f", sum_tat / n);
        printf("\nAverage Waiting Time    = %.2f\n", sum_wt / n);

        return 0;
    }


    priority scheduling

    #include <stdio.h>
    #define MAX 100

    typedef struct {
        int pid; // Process ID
        int at;  // Arrival Time
        int bt;  // Burst Time
        int prio;// Priority (lower value = higher priority)
        int ct;  // Completion Time
        int tat; // Turnaround Time
        int wt;  // Waiting Time
        int completed;
    } Process;

    int main() {
        int n, completed = 0, time = 0;
        float sum_tat = 0, sum_wt = 0;
        Process p[MAX];

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

        for (int i = 0; i < n; i++) {
            p[i].pid = i + 1;
            printf("Enter Arrival Time for P%d: ", i+1);
            scanf("%d", &p[i].at);
            printf("Enter Burst Time for P%d: ", i+1);
            scanf("%d", &p[i].bt);
            printf("Enter Priority for P%d (lower value = higher priority): ", i+1);
            scanf("%d", &p[i].prio);
            p[i].completed = 0;
        }

        printf("\nGantt Chart:\n| ");

        while(completed < n) {
            int idx = -1, highest = 100000;
            for (int i = 0; i < n; i++) {
                if (p[i].at <= time && !p[i].completed && p[i].prio < highest) {
                    highest = p[i].prio;
                    idx = i;
                }
            }
            if (idx == -1) {
                time++;
                continue;
            }
            printf("P%d | ", p[idx].pid);
            p[idx].ct = time + p[idx].bt;
            p[idx].tat = p[idx].ct - p[idx].at;
            p[idx].wt = p[idx].tat - p[idx].bt;
            sum_tat += p[idx].tat;
            sum_wt  += p[idx].wt;
            time = p[idx].ct;
            p[idx].completed = 1;
            completed++;
        }

        printf("\n\nPID\tAT\tBT\tPrio\tCT\tTAT\tWT\n");
        for (int i = 0; i < n; i++)
            printf("P%d\t%d\t%d\t%d\t%d\t%d\t%d\n",
                    p[i].pid, p[i].at, p[i].bt, p[i].prio, p[i].ct, p[i].tat, p[i].wt);

        printf("\nAverage Turnaround Time = %.2f", sum_tat / n);
        printf("\nAverage Waiting Time    = %.2f\n", sum_wt / n);

        return 0;
    }
     

    code : rr

    #include <stdio.h>
    #define MAX 100

    typedef struct {
        int pid; // Process id
        int at;  // Arrival Time
        int bt;  // Burst Time
        int ct;  // Completion Time
        int tat; // Turnaround Time
        int wt;  // Waiting Time
        int rt;  // Remaining Time
        int completed;
    } Process;

    int main() {
        int n, tq, complete = 0, time = 0, queue[MAX], front = 0, rear = 0;
        float sum_tat = 0, sum_wt = 0;
        Process p[MAX];

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

        for (int i = 0; i < n; i++) {
            p[i].pid = i + 1;
            printf("Enter Arrival Time for P%d: ", i+1);
            scanf("%d", &p[i].at);
            printf("Enter Burst Time for P%d: ", i+1);
            scanf("%d", &p[i].bt);
            p[i].rt = p[i].bt;
            p[i].completed = 0;
        }

        printf("Enter Time Quantum: ");
        scanf("%d", &tq);

        printf("\nGantt Chart:\n| ");

        // Initialization: Put in all processes that have arrived at time=0
        for (int i = 0; i < n; i++)
            if (p[i].at == 0) queue[rear++] = i;

        int last_idx = -1;
        while (complete < n) {
            if (front == rear) { // No one is ready; time skips to next arrival
                int earliest = 100000;
                for (int i = 0; i < n; i++)
                    if (!p[i].completed && p[i].at < earliest)
                        earliest = p[i].at;
                time = earliest;
                for (int i = 0; i < n; i++)
                    if (p[i].at == time && !p[i].completed) queue[rear++] = i;
            }

            int idx = queue[front++];
            if (last_idx != idx) {
                printf("P%d | ", p[idx].pid);
                last_idx = idx;
            }

            int run_time = (p[idx].rt < tq) ? p[idx].rt : tq;
            time += run_time;
            p[idx].rt -= run_time;
            // Check for new arrivals during this timeslice
            for (int i = 0; i < n; i++)
                if (!p[i].completed && p[i].at > (time - run_time) && p[i].at <= time)
                    queue[rear++] = i;
            if (p[idx].rt == 0) {
                p[idx].ct = time;
                p[idx].tat = p[idx].ct - p[idx].at;
                p[idx].wt  = p[idx].tat - p[idx].bt;
                sum_tat += p[idx].tat;
                sum_wt  += p[idx].wt;
                p[idx].completed = 1;
                complete++;
            } else {
                queue[rear++] = idx; // Re-enqueue the process
            }
        }

        printf("\n\nPID\tAT\tBT\tCT\tTAT\tWT\n");
        for (int i = 0; i < n; i++)
            printf("P%d\t%d\t%d\t%d\t%d\t%d\n",
                p[i].pid, p[i].at, p[i].bt, p[i].ct, p[i].tat, p[i].wt);

        printf("\nAverage Turnaround Time = %.2f", sum_tat / n);
        printf("\nAverage Waiting Time    = %.2f\n", sum_wt / n);

        return 0;
    }
     














  

Comments

Post a Comment

Popular posts from this blog

alter table

 The ALTER TABLE command in Oracle Database is used to modify the structure of an existing table . You can use it to add, modify, or drop columns, constraints, or even rename the table itself. 1. Syntax of ALTER TABLE ALTER TABLE table_name [ADD column_definition] [MODIFY column_definition] [DROP COLUMN column_name] [RENAME COLUMN old_column_name TO new_column_name] [ADD CONSTRAINT constraint_definition] [DROP CONSTRAINT constraint_name] [RENAME TO new_table_name]; 2. Key Use Cases of ALTER TABLE A. Adding a Column You can add one or more columns to an existing table. Syntax: ALTER TABLE table_name ADD column_name datatype [constraint]; Example: ALTER TABLE EMP1 ADD phone_number VARCHAR2(15); B. Modifying a Column You can modify the data type, size, or constraints of an existing column. Syntax: ALTER TABLE table_name MODIFY column_name new_datatype [constraint]; Example: ALTER TABLE EMP1 MODIFY NAME VARCHAR2(30) NOT NULL; C. Dropping a Column You...
Read more

DROP command

 The DROP command in Oracle Database is used to permanently delete database objects , such as tables, views, indexes, or even the entire database schema. Once a table or other object is dropped, it is removed from the database and cannot be recovered (unless you have enabled features like Oracle's Recycle Bin). 1. Purpose of DROP Command Completely removes the specified object from the database. Deletes the structure and data of the object. Drops dependent objects like constraints, indexes, and triggers associated with the table. 2. Syntax DROP TABLE table_name [CASCADE CONSTRAINTS] [PURGE]; 3. Parameters table_name : Specifies the name of the table to drop. CASCADE CONSTRAINTS : Drops the table along with all constraints (e.g., foreign key constraints) referencing it. PURGE : Removes the table from the Oracle Recycle Bin, making it unrecoverable. 4. Examples A. Basic Drop Table Deletes the table and all its data. DROP TABLE EMP1; B. Drop Ta...
Read more