Figure 3.7 Configuring a message queue

Operating System Fundamentals
47 Process Scheduling Algorithms In this section we will describe the common algorithms that are used for scheduling processes and threads. Here the word scheduling will refer to the task of deciding which processor thread should be selected from the process table and put into the Run state. Most current operating systems actually implement thread scheduling so that it does not matter if the two threads are in the same processor different processes. In this section we will try to use only the term ―process scheduling.‖ However, if the term thread is mentioned it really does mean the same thing.


Scheduler and the Process Table
The scheduler is apiece of software code (it is generally a function) that is included as part of the operating system. The scheduler is often tied to the periodic clock interrupt and to most of the operating system calls. By connecting to both a clock and the IO, it means that processes can be scheduled each time there is a clock tick and they can be scheduled each time that the process talks to the OS (such as when it asks to take a semaphore, asks to sleep, or performs an IO operation. Each time that the scheduler code is executed, the code will examine the process table and make a decision (based on what it reads from the process table) about which process should be run next. Over the next few sections we may realize that some additional items are required to be added to the process table to help the scheduler.
Round-Robin Scheduling
If a computer has four processes currently running, it would seem logical that one of the fairest ways to divide the CPU time is to give each process a turn in a certain order and continue to use that order. For example if the processes are called ABC, and D then the order could be ABC, DAB, CD, AB, etc. This type of scheduling is called round-robin scheduling. Most modern operating systems provide this type of scheduling algorithms and it is one of the easiest algorithms to understand. A common way of showing the algorithm is to create a small table that looks like this Process T T T T T T T T TAB CD The labels T, T, etc. refer to small units of time called time slices or quantums. The actual number of seconds (or more likely milliseconds) is dependent on the operating system but can sometimes be configured. Typical values for the time slices are in the order of ms.

Operating System Fundamentals
48 Each process is given a number of milliseconds to execute and then interrupted, and the scheduling algorithm will pick the next process in the list. However, if the process blocks (waits fora semaphore or sleeps) the scheduler would wake up early and schedule the next process. While a process is in the blocked state it will be not considered until it gets back into the ready state. The size of the time slice is quite important. If you pick a really large time slice (say ten seconds, then it means that each process gets to execute for up to ten seconds. If Windows used a ten second time slice, then it means when you click on the start menu (part of the Explorer process) you might have to wait up to ten seconds for Word to finish what it is doing before seeing the menu appear. On the other extreme, if you set the time slice to a really small value (such as 1 ms) then it means that the scheduler is executing 1,000 times per second. When the scheduler code is busy selecting a process it means that no other process can be running. The result is an inefficient system that spends more time trying to decide what to do than actually doing something.

Download 2.34 Mb.

Share with your friends: