Round Robin Scheduling Using Fork

Disclaimer: This implementation is not full-fledged code that uses round robin scheduling. Instead it takes the burst time of the parent process and executes the round robin algorithm by taking the burst time array (includes parent’s and child’s burst time) and quantum as inputs.

Concepts Used:

1. System Calls – Fork()
2. Inter Process Communication

CPU Scheduling

CPU Scheduling is a process which allows one process to use the CPU while execution of another process is on hold due to unavailability of resource like I/O etc. The aim of the CPU scheduling is to make the system efficient, fair and fast.

What are we trying to Optimize?

1. CPU Utilization
2. Throughput
3. Turnaround Time
4. Waiting Time
5. Response Time

Types of Scheduling

Preemptive	Non-preemptive
Used when a process switches from running state to ready state or from waiting state to ready state	Used when a process terminates or a process switches from running to waiting state
The CPU is allocated to the processes for the limited time	The CPU is allocated to the process till it terminates or switches to waiting state
The executing process is interrupted in the middle of execution	The executing process is not interrupted in the middle of execution.
Example: Round Robin, Shortest Time to Completion First	Example: First Come First Serve, Shortest Job First

Types of Schedulers

1. Long-Term Scheduler
2. Short-Term Scheduler
3. Medium-Term Scheduler

Comparison among Schedulers

S. No.	Long-Term Scheduler	Short-Term Scheduler	Medium-Term Scheduler
1	Job Scheduler	CPU Scheduler	Processes Swapping Scheduler
2	Speed is lesser that Short-Term Scheduler	Faster than other two Schedulers	Faster than Long-Term Scheduler
3	Controls the degree of Multiprogramming	Lesser Control over the degree of Multiprogramming	Reduces the degree of Multiprogramming
4	Almost Absent in time sharing system	Minimal in time sharing system	Part of time sharing system
5	Selects processes from pool	Selects processes which are ready	Re-introduce the process

Round Robin Scheduling

The round-robin (RR) scheduling algorithm is similar to FCFS scheduling, but preemption is added to enable the system to switch between processes. A small unit of time, called a time quantum or time slice, is defined. A time quantum is generally from 10 to 100 milliseconds in length. The ready queue is treated as a circular queue. The CPU scheduler goes around the ready queue, allocating the CPU to each process for a time interval of up to 1 time quantum.

The CPU scheduler picks the first process from the ready queue, sets a timer to interrupt after 1 time quantum, and dispatches the process.

One of two things will then happen. The process may have a CPU burst of less than 1 time quantum. In this case, the process itself will release the CPU voluntarily. The scheduler will then proceed to the next process in the ready queue. If the CPU burst of the currently running process is longer than 1 time quantum, the timer will go off and will cause an interrupt to the operating system. A context switch will be executed, and the process will be put at the tail of the ready queue. The CPU scheduler will then select the next process in the ready queue.

Although the time quantum should be large compared with the contexts witch time, it should not be too large. As we pointed out earlier, if the time quantum is too large, RR scheduling degenerates to an FCFS policy. A rule of thumb is that 80 percent of the CPU bursts should be shorter than the time quantum.

System Calls

A system call is the programmatic way in which a computer program requests a service from the kernel of the operating system on which it is being executed. We have used fork system call.

The purpose of fork() is to create a new process, which becomes the child process of the caller. fork() returns a positive value, the process ID of the child process, to the parent. 

Inter Process Communication

IPC or inter-process communication allows processes to communicate with each other and synchronize their actions. Pipe is used for this.

There are two types of pipes namely,

1. Ordinary Pipe
2. Named Pipe

Ordinary pipe is special type of file in UNIX and it can be accessed using read() and write() system calls. It allows communication in standard producer-consumer style where producer writes to one end and consumer reads from the other end. Ordinary pipes are unidirectional and requires parent-child relationship between communicating processes. For a two way communication, create two pipes. Windows call these pipes as anonymous pipes.

Named pipes are more powerful than ordinary pipes and communication is bidirectional. No parent-child relationship is necessary between the communicating processes. Several processes can use the named pipe for communication which is provided on both UNIX and windows systems. It is also referred to as FIFO (First In First Out) in UNIX.

We Have Used Ordinary Pipes Instead Of Named Pipes

Implementation

The implementation is done in python in Linux operating system. We can’t use fork() in a Windows environment because it is is only present in the standard libraries on Unix or Linux based operating systems.

Code

Round Robin Scheduling Algorithm Function

 

Execution Using Fork

Summary on How It Works: The parent process write the pipe with the burst time which was manually delayed by sleep and in the child process we read the pipe and append the burst time of parent into burst array. Similarly we calculate the child process burst time and append the same into burst time array. Then the burst time array and quantum time (which was taken from user using input() function) are given as inputs to the round_robin function which returns the waiting time and turnaround time.

Output

I will try to upload an another blog on implementation of scheduling algorithms using named pipes as soon as possible.

Hope this blog is helpful and Feel free to send feedbacks or comment on my blogs for my further improvements in the future.

Get contents delivered to your mail ID by entering you mail ID in the HOME page.

Thank you