HOME
« PREVIOUS |
| NEXT »
Top 10 List of Week 08
- CPU Scheduling
CPU Scheduling is a process of determining which process will own CPU for execution while another process is on hold. The main task of CPU scheduling is to make sure that whenever the CPU remains idle, the OS at least select one of the processes available in the ready queue for execution. The selection process will be carried out by the CPU scheduler. It selects one of the processes in memory that are ready for execution.
- CPU Scheduling Types
CPU scheduling can be divided into two categories, preemptive and non preemptive scheduling. In Preemptive Scheduling, the tasks are mostly assigned with their priorities. In Non-preemptive Scheduling, the CPU has been allocated to a specific process. To determine if scheduling is preemptive or non-preemptive, we need to consider these four parameters: 1) A process switches from the running to the waiting state; 2) Specific process switches from the running state to the ready state; 3) Specific process switches from the waiting state to the ready state; 4) Process finished its execution and terminated. If only conditions 1 and 4 apply, the scheduling is called non-preemptive. All other scheduling are preemptive.
- How CPU switch processes
The answer? using Dispatcher. A Dispatcher is a module that provides control of the CPU to the process. The Dispatcher should be fast so that it can run on every context switch. Dispatch latency is the amount of time needed by the CPU scheduler to stop one process and start another. Functions performed by Dispatcher are: Context Switching, Switching to user mode, and Moving to the correct location in the newly loaded program.
- How to Decide Which Process that Will be Run
There are various algorithms which are used by the Operating System to schedule the processes on the processor in an efficient way. The purpose of a scheduling algorithm is to get: Maximum CPU utilization, Fare allocation of CPU, Maximum throughput, Minimum turnaround time, Minimum waiting time, and Minimum response time. There are mainly six types of process scheduling algorithms: First Come First Serve (FCFS), Shortest-Job-First (SJF) Scheduling, Shortest Remaining Time, Priority Scheduling, Round Robin Scheduling, and Multilevel Queue Scheduling.
- First-Come Firts-Served Algorithm
First-Come First-Served Algorithm run the tasks in order that the tasks are submitted. It’s one of the simplest scheduling algorithm. It’s implemented using a FIFO(First-in first-out) data structure like a Queue.
- How Operating System Schedule Task in a Multiprocessor System
In the multiprocessor scheduling, there are multiple CPU’s which share the load so that various process run simultaneously. In general, the multiprocessor scheduling is complex as compared to single processor scheduling. In the multiprocessor scheduling, there are many processors and they are identical and we can run any process at any time. The multiple CPU’s in the system are in the close communication which shares a common bus, memory and other peripheral devices. So we can say that the system is a tightly coupled system. These systems are used when we want to process a bulk amount of data. These systems are mainly used in satellite, weather forecasting etc.
- Thread scheduling
We introduced threads to the process model, distinguishing between user-level and kernel-level threads. On operating systems that support them, it is kernel-level threads—not processes—that are being scheduled by the operating system. User-level threads are managed by a thread library, and the kernel is unaware of them. To run on a CPU, user-level threads must ultimately be mapped to an associated kernel-level thread, although this mapping may be indirect and may use a lightweight process (LWP).
- User and Kernel Level Thread
The two main types of threads are User-level threads and Kernel-level threads. User-level threads are implemented by users and the kernel is not aware of the existence of these threads. It handles them as if they were single-threaded processes. User-level threads are small and much faster than kernel level threads. Kernel-level threads are handled by the operating system directly and the thread management is done by the kernel. The context information for the process as well as the process threads is all managed by the kernel. Because of this, kernel-level threads are slower than user-level threads.
- CPU and I/O Bursts?
CPU/IO burst Characterizes process execution, which alternates between CPU and I/O activity. CPU times are usually shorter than the time of I/O. Almost all programs have some alternating cycle of CPU number crunching and waiting for I/O of some kind. In a simple system running a single process, the time spent waiting for I/O is wasted, and those CPU cycles are lost forever. A scheduling system allows one process to use the CPU while another is waiting for I/O, thereby making full use of otherwise lost CPU cycles. Almost all processes alternate between two states in a continuing cycle: A CPU burst of performing calculations, and an I/O burst, waiting for data transfer in or out of the system.
- How to Choose the Best Scheduling Algorithm
There are several different criteria to consider when trying to select the “best” scheduling algorithm for a particular situation and environment, including:
- CPU utilization - Ideally the CPU would be busy 100% of the time, so as to waste 0 CPU cycles. On a real system CPU usage should range from 40% ( lightly loaded ) to 90% ( heavily loaded. )
- Throughput - Number of processes completed per unit time. May range from 10 / second to 1 / hour depending on the specific processes.
- Turnaround time - Time required for a particular process to complete, from submission time to completion. ( Wall clock time. )
Waiting time - How much time processes spend in the ready queue waiting their turn to get on the CPU.
- Response time - The time taken in an interactive program from the issuance of a command to the commence of a response to that command.
In general we wants to optimize the average value of a criteria ( Maximize CPU utilization and throughput, and minimize all the others. ) However some times one wants to do something different, such as to minimize the maximum response time.
Sometimes it is most desirable to minimize the variance of a criteria than the actual value. I.e. users are more accepting of a consistent predictable system than an inconsistent one, even if it is a little bit slower.
-