CISC2005 Exercise 05

1. Prerequisites

1. Successful installation of *nix terminal (e.g., WSL, cygwin) or a *nix operating system (e.g., Linux, Mac).
   

For Windows system, I recommend you to install WSL. https://learn.microsoft.com/en-us/windows/wsl/install

1. Successful installation of a C compiler, GCC is recommended.
   
2. Successful installation of a text editor, VIM or Emacs is recommended.
   

1. Tasks

In this section, students are required to complete the following codes to implement several basic operating system scheduling algorithms. For each program, students should capture a screenshot of the successful execution with provided sample input, verify that the output is the same as sample output. In the submission file, please attach the added code and execution screenshot in sequence.

Q1: Complete the code at the blank underline to implements the First-Come First-Served (FCFS) scheduling algorithm. The program reads in a set of processes, each of which includes a Process ID, an Arrival Time(at) and a Service Time(st). The program should schedule the processes on a first-come, first-served basis based on arrival time and calculate the Wait Time(wt) and Turnaround Time(tt) for each process.

Input format.

The first line includes a positive integer n, indicating the number of processes. Each of the next n lines includes three positive integers indicating the process ID, arrival time, and service time, respectively.

Output format.

Outputs the wait time and turnaround time of each process in ascending order of process ID.

Sample input	Sample output
3
1 0 3	1 0 3
2 2 6	2 1 7
3 4 4	3 5 9

Tips.

• Turnaround time = completion time - arrival time.
• You can uncheck the "numbering" of the setting in Word to eliminate line numbers of codes and then copy codes to your text editor.

1. #include <stdio.h>  
2. #include <stdlib.h>  
3.   
4. struct process {  
5.     int pid;    // Process ID  
6.     int arrive; // Arrival Time  
7.     int service;    // Service Time  
8. };  
9.   
10. // Sort in ascending order of arrival time
11. int cmp(const void *a, const void *b) {  
12.     struct process *p1 = (struct process *) a;  
13.     struct process *p2 = (struct process *) b;  
14.     return p1->arrive - p2->arrive;  
15. }  
16.   
17. int main() {  
18.     int n, i;  
19.     printf("please enter the number of processes：");  
20.     scanf("%d", &n);  
21.     struct process *proc = malloc(sizeof(struct process) * n);  
22.     int *wait_time = malloc(sizeof(int) * n);  
23.     int *turnaround_time = malloc(sizeof(int) * n);  
24.     int current_time = 0;  
25.   
26.     printf("please enter the info for each process, with three numbers on each line representing the process ID, arrival time, and service time(separated by Space).：\n");  
27.     for (i = 0; i < n; i++) {  
28.         scanf("%d %d %d", &proc[i].pid, &proc[i].arrive, &proc[i].service);  
29.     }  
30.   
31.     // Sort in ascending order of arrival time  
32.     qsort(proc, n, sizeof(struct process), cmp);  
33.   
34.     for (i = 0; i < n; i++) {  
35.         if (current_time < proc[i].arrive) {  
36.             current_time = proc[i].arrive;  
37.         }  
38.         wait_time[i] = _______________________;  
39.         current_time += ______________________;  
40.         turnaround_time[i] = ________________________;  
41.     }  
42.   
43.     printf("The wait time and turnaround time for each process are as follows ：\n"); 
44. double avg_wait_time = 0;   
45.     for (i = 0; i < n; i++) {   
46.         avg_wait_time += wait_time[i];   
47.         printf("%d %d %d\n", proc[i].pid, wait_time[i], turnaround_time[i]);    
48.     }
49. printf("avg. Wait Time:%f\n", avg_wait_time);    
50.     avg_wait_time /= n
51.     free(proc);  
52.     free(wait_time);  
53.     free(turnaround_time);  
54.     return 0;  
55. }  

Q2: Complete the code at the blank underline to implements the Shortest Job First (SJF) scheduling algorithm and answer a questions. The program reads in a set of processes, each of which includes a Process ID, an Arrival Time and a Service Time. The program should schedule the processes on a Shortest Job First basis based on service time (arrival time should also be considered) and calculate the Wait Time and Turnaround Time for each process.

1. #include <stdio.h>  
2.   
3. struct process {  
4.     int id;  
5.     int arrival_time;  
6.     int service_time;  
7.     int wait_time;  
8.     int turnaround_time;  
9.     int service_save;  
10. };  
11.   
12. void calculate_times(struct process *p, int n) {  
13.     int i, j;  
14.     int current_time = 0;  
15.   
16.     for (i = 0; i < n; i++) {  
17.         // Find the process with the shortest execution time among all processes whose arrival time is less than or equal to the current time  
18.         int shortest_index = -1;  
19.         int shortest_time = -1;  
20.         for (j = 0; j < n; j++) {  
21.             if (p[j].arrival_time <= ____________ && p[j].service_time _______) {  
22.                 if (shortest_time == -1 || p[j].service_time < shortest_time) {  
23.                     shortest_index = j;  
24.                     shortest_time = p[j].service_time;  
25.                 }  
26.             }  
27.         }  
28.   
29.         if (shortest_index == -1) {  
30.             current_time++;  
31.             i--;  
32.             continue;  
33.         }   
34.   
35.         // Update the wait time and current time  
36.         p[shortest_index].wait_time = ____________ - ______________________;  
37.         current_time += ______________________;  
38.         p[shortest_index].turnaround_time = current_time - p[shortest_index].arrival_time; 
39.         p[shortest_index].service_time = 0; //   
40.     }  
41. }  
42.   
43. int main() {  
44.     int i, n;  
45.     printf("please enter the number of processes:");  
46.     scanf("%d", &n);  
47.     struct process p[n];  
48.   
49.     // Input process information  
50.     for (i = 0; i < n; i++) {  
51.         printf("Please enter the arrival time and service time of process %d: ", i + 1);  
52.         scanf("%d%d", &p[i].arrival_time, &p[i].service_time);  
53.         p[i].service_save = p[i].service_time;  
54.         p[i].id = i + 1;  
55.         p[i].wait_time = 0;  
56.         p[i].turnaround_time = 0;}     
57.   
58.     calculate_times(p, n);  
59.   
60.     // calculate average wait time.  
61.       
62.     double avg_wait_time = 0;  
63.     for (i = 0; i < n; i++) {  
64.         avg_wait_time += p[i].wait_time;  
65.     }  
66. avg_wait_time /= n;  
67.   
68.     // Ouput results  
69.     printf("Process\tArrival Time\tService Time\tWait Time\tTurnaround Time\n");  
70.     for (i = 0; i < n; i++) {  
71.         printf("P%d\t%d\t\t%d\t\t%d\t\t%d\n", p[i].id, p[i].arrival_time, p[i].service_save, p[i].wait_time, p[i].turnaround_time);  
72.     }  
73.     printf("avg. Wait Time:%f\n", avg_wait_time);  
74.     return 0;
75. }  

Sample input1(at and st)	Sample output1(wt and tt)
3
0 3	0 3
2 6	5 11
3 4	0 4

Question: Comment out lines 29 to 33 of the code, run the program, and enter sample input2. What happens? Explain why.

Sample input2(at and st)

3

2 3

0 1

2 2

Q3: I have provided the code for Preemptive Shortest Job First(PSJF) below. You can run the programs for non-preemptive and preemptive SJF with the same inputs several times and compare the average waiting times of the two algorithms. If you're interested, you can study the code in detail.

Input(at and st)	Avg.Wait_time(SJF)	Avg.Wait_time(PSJF)
[0 1, 2 7, 3 4]	2	1.33

#include <stdio.h>

#include <stdlib.h>

struct process {

    int id;

    int arrival_time;

    int service_time;

    int wait_time;

    int turnaround_time;

};

void calculate_times(struct process *p, int n) {

    int i, j, time = 0, completed = 0;

    int *remaining_time = (int*)malloc(n * sizeof(int));

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

        remaining_time[i] = p[i].service_time;

    }

    while (completed != n) {

        int shortest_index = -1;

        int shortest_time = -1;

        for (j = 0; j < n; j++) {

            if (p[j].arrival_time <= time && remaining_time[j] > 0) {

                if (shortest_time == -1 || remaining_time[j] < shortest_time) {

                    shortest_index = j;

                    shortest_time = remaining_time[j];

                }

            }

        }

        if (shortest_index == -1) {

            time++;

            continue;

        }

        remaining_time[shortest_index]--;

        if (remaining_time[shortest_index] == 0) {

            completed++;

            int k = shortest_index;

            p[k].wait_time = time - p[k].arrival_time - p[k].service_time + 1;

            if (p[k].wait_time < 0) {

                p[k].wait_time = 0;

            }

            p[k].turnaround_time = time - p[k].arrival_time;

        }

        time++;

    }

    free(remaining_time);

}

int main() {

    int i, n;

    printf("please enter the number of processes:");

    scanf("%d", &n);

    struct process p[n];

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

        printf("Please enter the arrival time and execution time of process %d: ", i + 1);

        scanf("%d%d", &p[i].arrival_time, &p[i].service_time);

        p[i].id = i + 1;

        p[i].wait_time = 0;

        p[i].turnaround_time = 0;

    }

    calculate_times(p, n);

    printf("Process\tArrival Time\tService Time\tWait Time\tTurnaround Time\n");

    int total_wait_time = 0;

    int total_turnaround_time = 0;

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

        printf("P%d\t%d\t\t%d\t\t%d\t\t%d\n", p[i].id, p[i].arrival_time, p[i].service_time, p[i].wait_time, p[i].turnaround_time);

        total_wait_time += p[i].wait_time;

        total_turnaround_time += p[i].turnaround_time;

    }

    printf("avg. Wait Time:%.2f\n", (float)total_wait_time/n);

    printf("avg. Turnaround Time:%.2f\n", (float)total_turnaround_time/n);

    return 0;

}