CPU Scheduling OS Assignment

1. Explain the difference between preemptive and nonpreemptive scheduling.

Answer: Preemptive scheduling allows a process to be interrupted in the midst of its execution, taking the CPU away and allocating it to another process. Non preemptive scheduling, once the CPU has been allocated to a process, the process keeps the CPU until it releases the CPU either by terminating or by switching to the waiting state.

2. Which of the following scheduling algorithms could result in starvation?

a. First-come, first-served

b. Shortest job first

c. Round robin

d. Priority

Answer: Shortest job first and priority-based scheduling algorithms could result in starvation.

3. CPU scheduling such as SJF (shortest job first) is based on the precise prediction of CPU burst times. One of the algorithm is exponential averaging. Check out the following implementation and answer to questions (20 points)

float absolute(float n){

    if (n < 0) return -n;

    return n;

}

float eval_error(float *pred, float *actual, int size){

    float err = 0;

    int i;

    for (i=0;i<size;i++){

         // add each error value

          err += absolute(pred[i] - actual[i]);

    }  

    return err;

}

int main() {

    float predicted_burst[100];

    float actual_burst[]={20, 8, 7};

    float alpha = 0.2;

    int num_burst = 3;

    int i;

    predicted_burst[0] = 10;

    for(i=0; i<num_burst; i++){

        predicted_burst[i+1] = alpha * predicted_burst[i] + (1-alpha) * actual_burst[i];

        printf("%f ", predicted_burst[i+1]);    // Line P

    }

    printf("error = %f\n", eval_error(predicted_burst, actual_burst, num_burst));   // Line X

}

(a) What output will be displayed to the screen by Line P?
Put down all three values in order.

Answer: 18.000000 10.000000 7.600000 

(b) What output will be displayed to the screen by Line X?

      Answer: error = 23.000000

4. Consider the following four processes of varying arrival times and CPU burst times.

* Assumptions

-       When there are multiple processes that arrive at the same time, the process with smaller index goes first to the ready queue.

-       If a process goes back to the ready queue after running when new processes arrive, new processes go first to the ready queue.

Process	Arrival Time	CPU Burst Time
P1	0	6
P2	1	5
P3	3	2
P4	6	7

(a) Draw a Gantt chart that illustrates the execution of these processes using preemptive SJF (or shortest-remaining-time-first) scheduling algorithms. Calculate its average turnaround time, waiting time, and average response time. When a new process has the same remaining time with the running process, the running process keeps running.  When there are multiple processes with the same remaining time in the ready queue, the one that comes first in the ready queue is selected.

(b) Draw a Gantt chart that illustrates the execution of these processes using RR (quantum = 3) scheduling algorithms.  Calculate its average turnaround time, waiting time, and average response time.

5. Check out the following real time CPU scheduling information and answer to each question.

There are two processes P1. P2.  The periods for P1 and P2 are 50 and 80. The processing times are t1 = 30 for P1 and t2 = 25 for P2. The deadline for each process requires that it complete its CPU burst by the start of its next period.

(a) Draw a Gantt chart when rate-monotonic scheduling is used. Does this algorithm satisfy all the deadlines? Yes/No

No, Rate monotonic Scheduling algorithm doesn’t satisfy the deadlines

(b) Draw a Gantt chart when earliest-deadline-first-scheduling is used. Does this algorithm satisfy all the deadlines? Yes/No

Yes, earliest-deadline-first-scheduling algorithm satisfies all the deadlines