Table of Contents
FCFS
SJF
HPF
RR
FCFS
FCFS (First-Come, First-Served) scheduling algorithm is the simplest process scheduling algorithm, also known as first-come, first-served algorithm. In this algorithm, processes are executed in the order in which they arrive on the ready queue, that is, processes that arrive first are executed first, and processes that arrive later are queued to wait.
The basic principle is to assign processes to the CPU one by one in the order they arrive until all processes have been executed. This means that in the FCFS algorithm, the execution time or priority of the process is not considered, and it is only scheduled according to the order in which they enter the ready queue.
Although the FCFS algorithm is simple and easy to understand, it also has some shortcomings. One of the main problems is that the average wait time can be long, especially when some short processes arrive after some long processes. This can lead to inefficient use of CPU time, as longer processes can tie up the CPU for longer periods of time while other processes wait longer.
The FCFS algorithm is a non-preemptive scheduling algorithm because once a process begins execution, it will run until completion or until it is preempted by a higher priority process.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//Define process structure
typedef struct
{
char name[10];
int enter_time;
int running_time;
} Program;
//Define the ready queue structure
typedef struct
{
Program **programs;
int size;
int capacity;
} ProgramQueue;
//Initialize ready queue
void InitializeQueue(ProgramQueue *queue, int capacity)
{
queue->programs = (Program **)malloc(capacity * sizeof(Program *));
queue->size = 0;
queue->capacity = capacity;
}
//Add the process to the queue
void EnterQueue(ProgramQueue *queue, Program *program)
{
if (queue->size < queue->capacity)
{
queue->programs[queue->size] = program;
queue->size + + ;
}
}
// Remove the process from the queue
Program *PollQueue(ProgramQueue *queue)
{
if (queue->size > 0)
{
Program *program = queue->programs[0];
for (int i = 1; i < queue->size; i + + )
{
queue->programs[i - 1] = queue->programs[i];
}
queue->size--;
return program;
}
return NULL;
}
//Execute FCFS scheduling
void FCFS(Program pro[], int num)
{
printf("Process arrival time service time start time completion time turnaround time weighted turnaround time\\
");
// Sort by arrival time
ProgramQueue queue;
InitializeQueue( & amp;queue, num);
EnterQueue( & amp;queue, & amp;pro[0]);
int time = pro[0].enter_time;
int pronum = 1;
float sum_T_time = 0, sum_QT_time = 0;
while (queue.size > 0)
{
Program *curpro = PollQueue( & amp;queue);
if (time < curpro->enter_time)
{
time = curpro->enter_time;
}
int done_time = time + curpro->running_time;
int T_time = done_time - curpro->enter_time;
sum_T_time + = T_time;
float QT_time = (float)T_time / curpro->running_time;
sum_QT_time + = QT_time;
printf("%s\t%d\t%d\t%d\t%d\t%d\t%.2f\\
", curpro->name, curpro- >enter_time, curpro->running_time, time, done_time, T_time, QT_time);
time + = curpro->running_time;
// Process simulation execution process
while (pronum < num & amp; & amp; pro[pronum].enter_time <= done_time)
{
EnterQueue( & amp;queue, & amp;pro[pronum]);
pronum + + ;
}
}
printf("The average turnaround time is %.2f\tThe average weighted turnaround time is %.2f\\
", sum_T_time / num, sum_QT_time / num);
}
int main()
{
int num = 3; // Assume there are 3 processes
//Initialize process array
Program pro[num];
strcpy(pro[0].name, "P1");
pro[0].enter_time = 0;
pro[0].running_time = 5;
strcpy(pro[1].name, "P2");
pro[1].enter_time = 1;
pro[1].running_time = 3;
strcpy(pro[2].name, "P3");
pro[2].enter_time = 3;
pro[2].running_time = 6;
//Call FCFS function
FCFS(pro, num);
return 0;
}
SJF
SJF (Shortest Job First) is a process scheduling algorithm that selects the process with the shortest service time for execution to minimize the average waiting time. This is a non-preemptive scheduling algorithm, that is, once a process starts executing, it will be executed until it is completed, unless a shorter job enters the ready queue.
The main idea is to select the next process to execute by predicting the service time of the process to ensure the shortest job completion time overall. This improves system throughput and responsiveness.
SJF can be divided into two types:
1. Non-preemptive SJF: Once a process starts executing, it will not be interrupted until it completes. Only after the process is complete does the system select the next shortest job.
2. Preemptive SJF: Allows shorter jobs to be executed midway. If the service time of the new process is shorter than that of the currently executing process, the system will interrupt the current process and execute the new process instead.
When implementing the SJF scheduling algorithm, processes need to be sorted by service time so that the process with the shortest service time can be easily found when selecting the next process to be executed. This is usually achieved by using a sorting algorithm such as quick sort or insertion sort. It should be noted that a problem with the SJF algorithm is that it may cause other processes to wait for a long time for processes with long service times, which may lead to starvation.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//Define process structure
typedef struct
{
char name[10];
int enter_time;
int running_time;
} Program;
//Define the ready queue structure
typedef struct
{
Program **programs;
int size;
int capacity;
} ProgramQueue;
//Initialize ready queue
void InitializeQueue(ProgramQueue *queue, int capacity)
{
queue->programs = (Program **)malloc(capacity * sizeof(Program *));
queue->size = 0;
queue->capacity = capacity;
}
//Add the process to the queue
void EnterQueue(ProgramQueue *queue, Program *program)
{
if (queue->size < queue->capacity)
{
queue->programs[queue->size] = program;
queue->size + + ;
}
}
// Remove the process from the queue
Program *PollQueue(ProgramQueue *queue)
{
if (queue->size > 0)
{
Program *program = queue->programs[0];
for (int i = 1; i < queue->size; i + + )
{
queue->programs[i - 1] = queue->programs[i];
}
queue->size--;
return program;
}
return NULL;
}
// Comparison function sorted by service time
int CompareByRunningTime(const void *a, const void *b)
{
return ((Program *)a)->running_time - ((Program *)b)->running_time;
}
//Execute SJF scheduling
void SJF(Program pro[], int num)
{
printf("Process arrival time service time start time completion time turnaround time weighted turnaround time\\
");
// Sort by service time
qsort(pro, num, sizeof(Program), CompareByRunningTime);
ProgramQueue queue;
InitializeQueue( & amp;queue, num);
int time = 0;
int pronum = 0;
float sum_T_time = 0, sum_QT_time = 0;
while (pronum < num || queue.size > 0)
{
while (pronum < num & amp; & amp; pro[pronum].enter_time <= time)
{
EnterQueue( & amp;queue, & amp;pro[pronum]);
pronum + + ;
}
if (queue.size > 0)
{
Program *curpro = PollQueue( & amp;queue);
int done_time = time + curpro->running_time;
int T_time = done_time - curpro->enter_time;
sum_T_time + = T_time;
float QT_time = (float)T_time / curpro->running_time;
sum_QT_time + = QT_time;
printf("%s\t%d\t%d\t%d\t%d\t%d\t%.2f\\
", curpro->name, curpro- >enter_time, curpro->running_time, time, done_time, T_time, QT_time);
time + = curpro->running_time;
}
else
{
time = pro[pronum].enter_time;
}
}
printf("The average turnaround time is %.2f\tThe average weighted turnaround time is %.2f\\
", sum_T_time / num, sum_QT_time / num);
}
int main()
{
int num = 3; // Assume there are 3 processes
//Initialize process array
Program pro[num];
strcpy(pro[0].name, "P1");
pro[0].enter_time = 0;
pro[0].running_time = 5;
strcpy(pro[1].name, "P2");
pro[1].enter_time = 1;
pro[1].running_time = 3;
strcpy(pro[2].name, "P3");
pro[2].enter_time = 3;
pro[2].running_time = 6;
//Call SJF function
SJF(pro, num);
return 0;
}
HPF
The High Priority First (HPF) scheduling algorithm is a scheduling strategy based on process priority. This algorithm determines the next process to execute based on the priority of the process. Processes with higher priority will be executed first to ensure that more important or urgent tasks can be processed as quickly as possible.
Each process is assigned a priority value, usually an integer. Smaller priority values indicate higher priority, while larger values indicate lower priority. At each scheduling point, the system selects the ready process with the highest priority for execution. This ensures that tasks with higher priority get processed faster. The HPF scheduling algorithm can be preemptive or non-preemptive. Preemptive HPF allows an executing process to be interrupted by a higher priority process so that the higher priority task can be executed immediately. When a process arrives, it is inserted into the ready queue and sorted according to priority. Processes with higher priority will be at the front of the queue. At each time slice or event, the process with the highest priority in the ready queue is selected for execution. After execution, continue to select the next highest priority ready process.
It should be noted that over-reliance on high priority may cause low-priority tasks to wait for a long time, resulting in starvation. Therefore, when designing a scheduling algorithm, it is necessary to balance services for high-priority tasks and fairness for low-priority tasks.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//Define process structure
typedef struct
{
char name[10];
int enter_time;
int running_time;
int priority;
} Program;
//Define the ready queue structure
typedef struct
{
Program **programs;
int size;
int capacity;
}ProgramQueue;
//Initialize ready queue
void InitializeQueue(ProgramQueue *queue, int capacity)
{
queue->programs = (Program **)malloc(capacity * sizeof(Program *));
queue->size = 0;
queue->capacity = capacity;
}
//Add the process to the queue
void EnterQueue(ProgramQueue *queue, Program *program)
{
if (queue->size < queue->capacity)
{
queue->programs[queue->size] = program;
queue->size + + ;
}
}
// Remove the process from the queue
Program *PollQueue(ProgramQueue *queue)
{
if (queue->size > 0)
{
Program *program = queue->programs[0];
for (int i = 1; i < queue->size; i + + )
{
queue->programs[i - 1] = queue->programs[i];
}
queue->size--;
return program;
}
return NULL;
}
// Comparison function sorted by priority
int CompareByPriority(const void *a, const void *b)
{
return ((Program *)a)->priority - ((Program *)b)->priority;
}
//Execute HPF scheduling
void HPF(Program pro[], int num)
{
printf("Process arrival time service time priority start time completion time turnaround time weighted turnaround time\\
");
// Sort by priority
qsort(pro, num, sizeof(Program), CompareByPriority);
ProgramQueue queue;
InitializeQueue( & amp;queue, num);
int time = 0;
int pronum = 0;
float sum_T_time = 0, sum_QT_time = 0;
while (pronum < num || queue.size > 0)
{
while (pronum < num & amp; & amp; pro[pronum].enter_time <= time)
{
EnterQueue( & amp;queue, & amp;pro[pronum]);
pronum + + ;
}
if (queue.size > 0)
{
Program *curpro = PollQueue( & amp;queue);
int done_time = time + curpro->running_time;
int T_time = done_time - curpro->enter_time;
sum_T_time + = T_time;
float QT_time = (float)T_time / curpro->running_time;
sum_QT_time + = QT_time;
printf("%s\t%d\t%d\t%d\t%d\t%d\t%d\t%.2f\\
", curpro- >name, curpro->enter_time, curpro->running_time, curpro->priority, time, done_time, T_time, QT_time);
time + = curpro->running_time;
}
else
{
time = pro[pronum].enter_time;
}
}
printf("The average turnaround time is %.2f\tThe average weighted turnaround time is %.2f\\
", sum_T_time / num, sum_QT_time / num);
}
int main()
{
int num = 3; // Assume there are 3 processes
//Initialize process array
Program pro[num];
strcpy(pro[0].name, "P1");
pro[0].enter_time = 0;
pro[0].running_time = 5;
pro[0].priority = 3;
strcpy(pro[1].name, "P2");
pro[1].enter_time = 1;
pro[1].running_time = 3;
pro[1].priority = 1;
strcpy(pro[2].name, "P3");
pro[2].enter_time = 3;
pro[2].running_time = 6;
pro[2].priority = 2;
//Call HPF function
HPF(pro, num);
return 0;
}
RR
Round Robin Scheduling is one of the common operating system scheduling algorithms. It allocates a time slice (amount of time) to each process, and then executes each process in turn in a round-robin manner until it is completed or time The tablets are exhausted.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//Define process structure
typedef struct
{
char name[10];
int arrival_time;
int burst_time;
int remaining_time;
} Process;
//Define the ready queue structure
typedef struct
{
Process **processes;
int size;
int capacity;
} ProcessQueue;
//Initialize ready queue
void InitializeQueue(ProcessQueue *queue, int capacity)
{
queue->processes = (Process **)malloc(capacity * sizeof(Process *));
queue->size = 0;
queue->capacity = capacity;
}
//Add the process to the queue
void EnterQueue(ProcessQueue *queue, Process *process)
{
if (queue->size < queue->capacity)
{
queue->processes[queue->size] = process;
queue->size + + ;
}
}
// Remove the process from the queue
Process *PollQueue(ProcessQueue *queue)
{
if (queue->size > 0)
{
Process *process = queue->processes[0];
for (int i = 1; i < queue->size; i + + )
{
queue->processes[i - 1] = queue->processes[i];
}
queue->size--;
return process;
}
return NULL;
}
// Round robin scheduling function
void RoundRobin(Process processes[], int num_processes, int time_slice)
{
printf("Process arrival time service time start time completion time turnaround time weighted turnaround time\\
");
//Initialize ready queue
ProcessQueue queue;
InitializeQueue( & amp;queue, num_processes);
int time = 0;
int remaining_processes = num_processes;
while (remaining_processes > 0)
{
for (int i = 0; i < num_processes; + + i)
{
if (processes[i].arrival_time <= time & amp; & amp; processes[i].remaining_time > 0)
{
// Process is executable
EnterQueue( & amp;queue, & amp;processes[i]);
}
}
if (queue.size > 0)
{
Process *current_process = PollQueue( & amp;queue);
//Execute process
int execution_time = (current_process->remaining_time <= time_slice) ? current_process->remaining_time : time_slice;
printf("%s\t%d\t%d\t%d\t%d\t%d\t%.2f\\
", current_process->name, current_process- >arrival_time, current_process->burst_time,
time, time + execution_time, time + execution_time - current_process->arrival_time,
(float)(time + execution_time - current_process->arrival_time) / current_process->burst_time);
//Update process information
current_process->remaining_time -= execution_time;
time + = execution_time;
// Re-add the unfinished process to the queue
if (current_process->remaining_time > 0)
{
EnterQueue( & amp;queue, current_process);
}
else
{
--remaining_processes;
}
}
else
{
// Wait for the next process to arrive
time + + ;
}
}
printf("The round robin scheduling algorithm is completed.\\
");
}
int main()
{
int num_processes = 3;
int time_slice = 2;
//Initialize process array
Process processes[num_processes];
strcpy(processes[0].name, "P1");
processes[0].arrival_time = 0;
processes[0].burst_time = 5;
processes[0].remaining_time = processes[0].burst_time;
strcpy(processes[1].name, "P2");
processes[1].arrival_time = 1;
processes[1].burst_time = 3;
processes[1].remaining_time = processes[1].burst_time;
strcpy(processes[2].name, "P3");
processes[2].arrival_time = 3;
processes[2].burst_time = 6;
processes[2].remaining_time = processes[2].burst_time;
//Call the round robin scheduling function
RoundRobin(processes, num_processes, time_slice);
return 0;
}