Skip to content

Instantly share code, notes, and snippets.

@zeerorg

zeerorg/file_os.md

Last active March 30, 2017 14:16
Show Gist options
  • Save zeerorg/a7cfb4202296a452491220b8894e1934 to your computer and use it in GitHub Desktop.
Save zeerorg/a7cfb4202296a452491220b8894e1934 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
file_os.md

Process.h

#include <iostream>
#define MAX 100

using namespace std;

struct Process {
    int pid;
    int arrival;
    int burst;
    int start;          // Time executed = current time - start (if this process is executing)
    int waiting;
    int turnaround;
    int completed;
    int priority;       // 1(highest) to 7(lowest)

    Process () {
        pid = arrival = burst = waiting = turnaround = completed = priority = 0;
        start = -1;  // Not started
    }
};

struct ProcessQueue {
    Process q[MAX];
    int front;
    int rear;

    ProcessQueue() {
        front = rear = -1;
    }

    void insertQ(Process p) {
        if(front == -1) {
            front = 0;
            rear = 0;
        } else {
            rear++;
        }
        q[rear] = p;
    }

    Process delQ() {
        Process temp = q[front];
        if(front == -1) {
            throw "Queue Empty";
        }
        if (front == rear) {
            front = rear = -1;
        } else {
            front++;
        }
        return temp;
    }

    bool isEmpty() {
        return front == -1;
    }

    Process* first(){
        return &q[front];
    }

    int getSize() {
        return rear-front;
    }
};
# Practical 1.a #### AIM Implement First Come First Serve process scheduling algorithm ___

Code

#include <iostream>
#include "Process.h"

using namespace std;

int main() {
    Process p;
    ProcessQueue processes;
    int n;
    cout << "Enter Number of Processes: ";
    cin >> n;
    cout << endl;
    for(int i=1; i<=n; i++) {
        Process temp;
        temp.pid = 1000 + i;
        cout << "Enter burst time for P[" << temp.pid << "] : ";
        cin >> temp.burst;
        processes.insertQ(temp);
        cout << endl;
    }

    int time = 0;
    processes.first()->start = 0;
    cout << "0:P[1001]\n";
    while(!processes.isEmpty()) {
        Process *top = processes.first();
        if(top->start + top->burst == time) {
            processes.delQ();
            if (!processes.isEmpty()) {
                top = processes.first();
                cout << time << ":P[" << top->pid << "]\n";
                top->start = time;
            } else {
                cout << time << ":finish\n";
            }
        }

        time ++;
    }

    return 0;
}
#### Output ![FCFS output](/home/rishabh/Documents/Os/fcfs.png)
# Practical 1.b #### AIM Implement First Come First Serve process scheduling algorithm ___

Code

#include <iostream>
#include "Process.h"

using namespace std;

int main() {
    Process p;
    ProcessQueue processes;
    ProcessQueue readyQ;
    int n;
    cout << "Enter Number of Processes: ";
    cin >> n;
    cout << endl;
    for(int i=1; i<=n; i++) {
        Process temp;
        temp.pid = 1000 + i;
        cout << "Enter burst time for P[" << temp.pid << "] : ";
        cin >> temp.burst;
        cout << "Enter Arrival time for P[" << temp.pid << "] : ";
        cin >> temp.arrival;
        processes.insertQ(temp);
        cout << endl;
    }

    int time = 0;
    readyQ.insertQ(processes.delQ());
    readyQ.first()->start = 0;
    cout << "0:P[1001]\n";
    while(!(processes.isEmpty() && readyQ.isEmpty())) {
        if (!processes.isEmpty() && processes.first()->arrival == time) {
            Process ptemp = processes.delQ();
            ptemp.start = time;
            if(readyQ.isEmpty()) {
                cout << time << ":P[" << ptemp.pid << "]\n";
            }
            readyQ.insertQ(ptemp);
            continue;
        }


        Process *top = readyQ.first();
        if(top->start + top->burst == time) {
            top = NULL;
            readyQ.delQ();
            if (!readyQ.isEmpty()) {
                top = readyQ.first();
                cout << time << ":P[" << top->pid << "]\n";
                top->start = time;
            } else {
                cout << time << ":stopped\n";
            }
        }

        time ++;
    }

    return 0;
}

Output

FCFS output

# Practical 2 #### AIM Implement Shortest Job First process scheduling algorithm ___

Code

#include <iostream>
#include "Process.h"

using namespace std;

struct ShortestJobHeap {
    Process q[MAX];
    int length;
    ShortestJobHeap() {
        length = 0;
    } 

    void insertHeap(Process p, int time) {
        q[length] = p;
        if(isEmpty()) {
            q[0].start = 0;
            cout << time << ":P[" << q[0].pid << "]\n";
        } else {
            int parent = (length-1)/2;
            int child = length;
            while(parent>0) {
                if(q[child].burst < q[parent].burst) {
                    Process temp = q[child];
                    q[child] = q[parent];
                    q[parent] = temp;
                    child = parent;
                    parent  = (child-1)/2;
                } else {
                    break;
                }
            }
            if(parent == 0) {
                if(q[child].burst < (q[0].burst - (time - q[0].start))) {
                    q[0].burst = q[0].burst - (time - q[0].start);
                    q[0].start = -1;
                    Process temp = q[child];
                    q[child] = q[0];
                    q[0] = temp;
                    q[0].start = time;
                    cout << time << ":P[" << q[0].pid << "]\n";
                }
            }
        }
        length++;
    }
    
    Process deleteHeap(int time) {
        Process p = q[0];
        q[0] = q[length-1];

        int parent = 0;
        int left, right;
        while(true) {
            left = parent*2 + 1;
            right = parent*2 + 2;
            if(left < length && q[left].burst < q[parent].burst)
                parent = left;
            if(right < length && q[right].burst < q[parent].burst)
                parent = right;
            if(parent == (right-1)/2)
                break;
            else {
                int t = (right-1)/2;
                Process temp = q[parent];
                q[parent] = q[t];
                q[t] = temp;
            }
        }
        q[0].start = time;
        length--;
        return p;
    }
    
    Process* getTop() {
        return &q[0];
    }

    bool isEmpty() {
        return length <= 0;
    }
};


int main() {
    Process p;
    ProcessQueue processes;
    ShortestJobHeap ready;
    int n;
    cout << "Enter Number of Processes: ";
    cin >> n;
    cout << endl;
    for(int i=1; i<=n; i++) {
        Process temp;
        temp.pid = 1000 + i;
        cout << "Enter burst time for P[" << temp.pid << "] : ";
        cin >> temp.burst;
        cout << "Enter Arrival time for P[" << temp.pid << "] : ";
        cin >> temp.arrival;
        cout << endl;
        processes.insertQ(temp);
    }

    int time = 0;
    cout << endl;
    while(!(processes.isEmpty() && ready.isEmpty())) {

        if (!processes.isEmpty() && processes.first()->arrival == time) {
            Process ptemp = processes.delQ();
            if(ready.isEmpty() && time > 0) {
                cout << time << ":P[" << ptemp.pid << "]\n";
            }
            ready.insertHeap(ptemp, time);
            continue;
        }
        Process *top = ready.getTop();
        if(time == 0) {
            top->start = 0;

        }

        if(top->start + top->burst == time) {
            top = NULL;
            ready.deleteHeap(time);
            if (!ready.isEmpty()) {
                top = ready.getTop();
                cout << time << ":P[" << top->pid << "]\n";
            } else {
                cout << time << ":stopped\n";
            }
        }

        time ++;
    }
    cout << endl;

    return 0;
}

Output

FCFS output

# Practical 3 #### AIM Implement **Priority** based process scheduling algorithm ___

Code

#include <iostream>
#include "Process.h"

using namespace std;

struct ProcessHeap {
    Process q[MAX];
    int length;
    ProcessHeap() {
        length = 0;
    }

    void insertHeap(Process p, int time) {
        q[length] = p;
        if(isEmpty()) {
            q[0].start = 0;
            cout << time << ":P[" << q[0].pid << "]\n";
        } else {
            int parent = (length-1)/2;
            int child = length;
            while(parent>0) {
                if(q[child].priority < q[parent].priority) {
                    Process temp = q[child];
                    q[child] = q[parent];
                    q[parent] = temp;
                    child = parent;
                    parent  = (child-1)/2;
                } else {
                    break;
                }
            }
            if(parent == 0) {
                if(q[child].priority < q[parent].priority) {
                    q[0].burst = q[0].burst - (time - q[0].start);
                    q[0].start = -1;
                    Process temp = q[child];
                    q[child] = q[0];
                    q[0] = temp;
                    q[0].start = time;
                    cout << time << ":P[" << q[0].pid << "]\n";
                }
            }
        }
        length++;
    }

    Process deleteHeap(int time) {
        Process p = q[0];
        q[0] = q[length-1];

        int parent = 0;
        int left, right;
        while(true) {
            left = parent*2 + 1;
            right = parent*2 + 2;
            if(left < length && q[left].priority < q[parent].priority)
                parent = left;
            if(right < length && q[right].priority < q[parent].priority)
                parent = right;
            if(parent == (right-1)/2)
                break;
            else {
                int t = (right-1)/2;
                Process temp = q[parent];
                q[parent] = q[t];
                q[t] = temp;
            }
        }
        q[0].start = time;
        length--;
        return p;
    }

    Process* getTop() {
        return &q[0];
    }

    bool isEmpty() {
        return length <= 0;
    }
};

int main() {
    int slice;
    Process p;
    ProcessQueue processes;
    ProcessHeap ready;
    int n;
    cout << "Enter Number of Processes: ";
    cin >> n;
    cout << endl;
    for(int i=1; i<=n; i++) {
        Process temp;
        temp.pid = 1000 + i;
        cout << "Enter burst time for P[" << temp.pid << "] : ";
        cin >> temp.burst;
        cout << "Enter Arrival time for P[" << temp.pid << "] : ";
        cin >> temp.arrival;
        cout << "Enter Priority for P[" << temp.pid << "] : ";
        cin >> temp.priority;
        processes.insertQ(temp);
        cout << endl;
    }

    int time = 0;
    cout << endl;
    while(!(processes.isEmpty() && ready.isEmpty())) {

        if (!processes.isEmpty() && processes.first()->arrival == time) {
            Process ptemp = processes.delQ();
            if(ready.isEmpty() && time > 0) {
                cout << time << ":P[" << ptemp.pid << "]\n";
            }
            ready.insertHeap(ptemp, time);
            continue;
        }
        Process *top = ready.getTop();
        if(time == 0) {
            top->start = 0;

        }

        if(top->start + top->burst == time) {
            top = NULL;
            ready.deleteHeap(time);
            if (!ready.isEmpty()) {
                top = ready.getTop();
                cout << time << ":P[" << top->pid << "]\n";
            } else {
                cout << time << ":stopped\n";
            }
        }

        time ++;
    }

    return 0;
}

Output

FCFS output

# Practical 4 #### AIM Implement **Round Robin** process scheduling algorithm ___

Code

#include <iostream>
#include "Process.h"

using namespace std;

int main() {
    int slice;
    Process p;
    ProcessQueue processes;
    ProcessQueue readyQ;
    int n;
    cout << "Enter Number of Processes: ";
    cin >> n;
    cout << "Enter time slice: ";
    cin >> slice;
    cout << endl;
    for(int i=1; i<=n; i++) {
        Process temp;
        temp.pid = 1000 + i;
        cout << "Enter burst time for P[" << temp.pid << "] : ";
        cin >> temp.burst;
        cout << "Enter Arrival time for P[" << temp.pid << "] : ";
        cin >> temp.arrival;
        processes.insertQ(temp);
        cout << endl;
    }

    int time = 0;
    readyQ.insertQ(processes.delQ());
    readyQ.first()->start = 0;
    cout << "0:P[1001]\n";
    while(!(processes.isEmpty() && readyQ.isEmpty())) {
        if (!processes.isEmpty() && processes.first()->arrival == time) {
            Process ptemp = processes.delQ();
            ptemp.start = time;
            if(readyQ.isEmpty()) {
                cout << time << ":P[" << ptemp.pid << "]\n";
            }
            readyQ.insertQ(ptemp);
            continue;
        }

        Process *top = readyQ.first();
        if(top->start + top->burst == time) {
            top = NULL;
            readyQ.delQ();
            if (!readyQ.isEmpty()) {
                top = readyQ.first();
                cout << time << ":P[" << top->pid << "]\n";
                top->start = time;
            } else {
                cout << time << ":stopped\n";
            }
        }
        if(time % slice == 0 && time != 0 && readyQ.getSize() > 1) {
            Process temp = readyQ.delQ();
            temp.burst -= time - temp.start;
            temp.start = -1;
            readyQ.insertQ(temp);
            readyQ.first()->start = time;
            cout << time << ":P[" << readyQ.first()->pid << "]\n";
        }

        time ++;
    }

    return 0;
}

Output

FCFS output

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment