What is CPU Scheduling

The processes entered into the computer system are put into the job queue. Similarly, the processes that are in main memory and are ready to execute are kept in a ready queue. In a multiprogramming and timesharing systems, multiple processes is used to determine which process to run first and how much times.  The method or procedure for switching the CPU among multiple processors is called CPU scheduling or process scheduling. The part of operating system which schedules the process is called the CPU scheduler.

In single precursors system one process can run at a time and other processes have wait. In multiprocessing system some processes may be running in this cases schedules the execution of processes on the CPU.

In multiprogramming system some processes may be running at all times. Similarly timesharing system must switch from one process to another so frequently that users can interact with their programs. The CPU scheduler plays the main role in multiprogramming and timesharing system.

CPU scheduling increase the CPU utilization.  Whenever CPU becomes idle the CPU scheduler selects a process from the ready queue and sends it to the CPU for execution.

Preemptive and None preemptive scheduling:

The earlier computer systems used the non preemptive scheduling. It means that a process retained control of the CPU until the process blocked or terminated. This approach was used in batch systems. In modern computer systems preemptive scheduling is used. The scheduler may preemptive a process before it blocks or terminated in order to allocate the CPU to another process.

For example, the non preemptive scheduling was used by Microsoft windows 3.x product. The preemptive scheduling was introduced in Windows 95 operating system. To day all operating systems used this method. Non preemptive scheduling is used only on certain hardware platform.

What is Thread

A thread is a sequence of instruction within a process. A thread also represents the sequential flow of execution of the task of a process. A process may consist of one of many threads. Therefore a thread is sometimes called a lightweight process. Each thread has its own information of program counter, CPU register and stack. In a process, threads are typically used for dividing a task in a web browser are divided into multiple threads such as,

• Task to download the images
• Task to download the text
• Task to display images and text etc

You have observed that downloading images take more time than text. In this case one thread remains busy for downloading images, while other threads download and display the text. It must be noted that each process occupies an independent address space in memory. But all threads of the process share the same address space. On the basis of process execution, the Operating System can be classified as,

1.      Single-Process single-thread

2.      Single-Process multiple-threads

3.      Multi-Process single-thread

4.      Multi-Process multi-threads

The simplest arrangement is single-process single-thread. Where only one task can be perform at a time. MS DOS is an example of a single-process single-thread operating system. For example in a word processor program only one process can execute at a time. The user cannot simultaneously type text and run the spell checker within the same process.

To day modern systems allow a process to have multiple threads per process. A Java run-time environment is an example of a system of one process with multiple threads.

The multiprogramming system allows the CPU to be shared by multiple processes, for example UNIX supports multiple users’ processes but each process has only one thread.

Some operating system allows multiple process and multiple threads per process like Windows, Linux and OS/2 etc.

User level and kernel level threads

The support for thread may be provided either at user level or by kernel level. Therefore threads may be divided into two categories.

1. User-level Threads
2. Kernel-level Threads

User-level Threads

In user level threads all work of threads management is done by the application without kernel support. Any application can be programmed to be multithreaded by using a threads library, which has a collection of routines that can be sued for user level threads management. For example threads library contains the routines for

• Creating and destroying threads
• Passing data between threads
• Scheduling threads
• Saving and restoring states of threads etc.

Once and application is loaded into user space, all the threads are created and managed within the user space of a process, by default an application begins with a single thread and continuously running in that thread. This application and its thread are managed by the Kernel. At any time the application may create many threads within the same process. A separate data structure for each thread also created. Some scheduling algorithm is also used to pass control to one thread to another within the process; when control is switched from one thread to another that state of the currently executed is saved and then restored which control returns back.

Kernel-level thread

In kernel level thread all work of threads management is done by the kernel of operating system. There is no thread management code in user space of the process. In this approach when control is switched form one thread to another within the same process then control also has to switch form user mode to kernel mode. So this approach affects the performance of the system. Scheduling by the kernel is done on a thread basis. Most of the operating system support kernel threads. These systems are windows XP, Linux and Solaris etc.

Multithreading Models

There must exist a relationship between user threads and kernel threads. These relationships can be established by using the following models.

1. Many to One model
2. One to One model
3. Many to Many model

Many to one model

In many to one model a user space is allocated to single process and multiply threads may be created and executed within that process. The application and its threads are managed by the kernel. The many to one model maps many user level threads to one kernel thread. Thread management is done by the thread library in user space. In this model the entire process will be block if a thread makes a blocking system call. Only one thread can access the kernel at a time so it is impossible to run multiple threads in parallel on multiprocessors system.

One to One model

The one to one model maps each user level thread to one kernel thread. This modl provides more concurrency than many to one model, because it allows another thread to run when a thread makes a blocking system call. This model also allows multiple threads to run in parallel on multiprocessors system.

Many to Many models

The Many to Many models multiplexes many user level threads to smaller equal number of kernel threads. The number of kernel threads may be specific to either a paruvullar application or a particular machine.