# Dynamic Round Robin CPU Scheduling Algorithm Based on K-Means Clustering Technique
## 1 Introduction
### CPU Scheduling  
The mechanism for allocating and de-allocating the CPU to a process is known as CPU scheduling [1; 2; 3]; the portion of the operating system that carries out these functions is called the _scheduler_. In multi-programming systems, the number of processes in the memory is restricted by the degree of multi-programming. There are several processes in the memory waiting to receive service from the CPU, the scheduler chooses the next process to assign the CPU, waits for its processing period, and de-allocates the CPU from that process. The scheduling mechanism is the order in which processes are selected for CPU processing. The scheduling scheme may be preemptive (i.e., the CPU is assigned to a process for a certain period) or non-preemptive (i.e., once the CPU has been assigned to a process, the process keeps the CPU until it liberates the CPU either by switching to another state or by terminating). Many different CPU scheduling algorithms have been suggested. Under First Come First Served (FCFS), non-preemptive CPU-scheduling, the process that arrives first, gets executed first. Shortest Job First (SJF), non-preemptive CPU-scheduling, selects the process with the shortest burst time. The preemptive version of SJF is called Shortest Remaining Time First (SRTF); processesare placed into the ready queue as they arrive, and the existing process is removed or preempted from execution as a process with short burst time arrives, and the shorter process is executed first. Under priority scheduling, preemptive CPU-scheduling, if a new process arrived has a higher priority than the currently running process, the processing of the current process is paused and the CPU is assigned to the incoming new process [4].  
RR scheduling is the most common of the preemptive scheduling algorithms [5], referred to hereafter as Standard RR (SRR), used in real-time operating systems and timesharing [6; 7]. In RR scheduling, the operating system is driven by a regular interrupt. Processes are selected in a fixed sequence for execution [8]. A process receiving CPU service is interrupted by the system timer after a short fixed interval called time slice which usually is much shorter than the CPU service period (or CPU burst) of the process [9; 10; 11]. After that interruption, the scheduler performs a context switch to the next process selected from the ready queue which is treated as a circular queue [12; 13]. Thus, all processes in the queue are given a chance to receive service for a short fixed period. This scheduling mechanism is basically used in timesharing systems [14; 15; 16]. The efficiency of RR algorithm depends on the time slice, if the time slice is small, overheads of more context switches will occur and if the time slice is large, RR behaves somewhat similar to FCFS with the possibility of starvation occurrence between processes. The scheduling algorithm performance depends upon the scheduling states of waiting time (i.e., total period the process spent waiting in the ready queue), turnaround time (i.e., total time between process submission and its completion), and number of context switches (NCS) [17; 18; 19].