Scheduling Threads

We have alluded to scheduling in the previous sections. As a subject, scheduling is complex and is often the topic of an entire chapter or more in an operating systems text. Understanding the Linux Kernel provides an excellent in-depth presentation of Linux scheduling. Essentially, scheduling is used to determine which ready-to-run task the CPU will execute next . A check of any good operating systems text will reveal a variety of scheduling policies, some of the more common of which are

• First come, first served first to request service is processed first (also called a FIFO arrangement).
• Shortest job first the task requiring least amount of processing is done first.
• Priority-based tasks with higher priority are done first.
• Round- robin each task gets a small time slice; tasks reside in a circular queue until they are finished.

Furthermore, many of these strategies can be implemented as nonpreemptive (once the task begins, it goes to completion) or as preemptive (the task can be removed by a task of a higher priority). In current operating systems preemption is the norm. Keep in mind, as noted in Chapter 1, processes can be in user mode or kernel mode. Traditionally, a process running on a single processor system is nonpreemptive when it is in kernel mode.

Similar to processes, threads can be in one of several states. A very simplified thread state diagram is shown in Figure 11.4. As shown, a thread can be ready to run (able to run if selected); running (active); or blocked (waiting on some other event, say I/O or a wake-up, to occur).

Figure 11.4. High-level thread state diagram.

In Linux the scheduling of a POSIX thread is determined by two factors: priority and scheduling policy.

The system uses the static priority value of a thread to assign it to a ready-to-run list. The static priority values for a Linux system range from 0 to 99, with 0 being the lowest priority. When dealing with a POSIX thread, higher priority threads are scheduled before those with a lower priority. Usually, the priority of a thread is inherited from its creating thread. However, the priority of a thread can be set at creation time by modifying the thread attribute object before the thread is created. Conceptually, the system maintains a separate list for each static priority value. The library calls sched_get_priority_max and sched_get_priority_min can be used to determine the actual priority limits for a specific scheduling policy.

POSIX specifies three scheduling policies for threads. The first policy, SCHED_OTHER, is used for normal (conventional) processes. The remaining two policies, SCHED_FIFO and SCHED_RR, are for real-time (time-dependent) applications. Implementation-wise, as all scheduling is basically preemptive, these policies are used by the system to determine where threads are inserted in a list and how they move within the list.

• SCHED_OTHER the system default. This is a time-sharing policy where competing threads with the same static priority (0) are multiplexed (each receiving a time slice) according to their dynamic priority. A thread's dynamic priority is based on its nice level, which is established at runtime. The nice level can be changed using the setpriority system call. The thread's dynamic priority is increased each time it is ready to run but is denied access to the CPU.
• SCHED_FIFO a first in, first out scheduling policy. SCHED_FIFO threads have a static priority greater than 0. The highest priority, longest waiting thread becomes the next thread to execute. The thread will execute until it finishes, is blocked (such as by an I/O request), is preempted, or yields (calls sched_yield ). Initially, ready-to-run SCHED_FIFO scheduled threads are placed at the end of their list. If a SCHED_FIFO thread is preempted, it remains at the head of its list and resumes its execution when all higher priority threads have finished or blocked. A SCHED_FIFO thread that yields the processor is placed at the end of its list.
• SCHED_RR Round-robin scheduling. This is similar to SCHED_FIFO with a time slicing factor (quantum) added in. When a thread has run for a period of time equal to it quantum (and has not finished) it is placed at the end of its list. If a SCHED_RR scheduled process is preempted, as with SCHED_FIFO, it stays at the head of its list, but when recalled, only gets to complete the remaining portion of its quantum.

A scheduling policy and priority of a thread that already exists can be set with the pthread_setschedparam library function, detailed in Table 11.8.

Table 11.8. The pthread_setschedparam Library Function.

Include File(s)			Manual Section	3
Summary	int pthread_setschedparam( pthread_t target_thread, int policy, const struct sched_param *param );
Return	Success	Failure	Sets errno
		Nonzero

The first argument of pthread_setschedparam is a valid thread ID. The second argument should be one of the following defined constants: SCHED_OTHER, SCHED_FIFO, or SCHED_RR (see previous discussion). The third argument for this call is a reference to a sched_param structure (examine the include file for definition details).

If successful, the pthread_setschedparam library returns a 0; otherwise , it returns one of the following values: EPERM (1), the calling process does not have superuser privileges; ESRCH (3), the specified thread does not exist; EFAULT (14), param references an illegal address; or EINVAL (22), invalid policy or param value or priority value is inconsistent with scheduling policy. Again, it is important to note that only the superuser can specify SCHED_FIFO or SCHED_RR scheduling (and thus change a thread's static priority to something other than 0); others are left with the system default SCHED_FIFO with a static priority of 0.

Program 11.2 demonstrates the use of the pthread_setschedparam , pthread_getschedparam , sched_get_priority_max , and sched_ get_priority_min functions. In main a scheduling policy is specified and the system's maximum and minimum priority values for the policy are displayed. The policy and an arbitrarily calculated priority are assigned to a parameter structure, which is passed to the threadfunc function. When a new thread is created, the threadfunc function calls pthread_setschedparam to set the scheduling policy and priority. To confirm the changes have actually been made, the pthread_getschedparam library function is used to retrieve the current scheduling and thread priority settings. The returned results are displayed.

Program 11.2 Manipulating scheduling parameters.

File : p11.2.cxx
 /*
 Changing scheduling parameters.
 */
 #define _GNU_SOURCE
 + #define _REENTRANT
 #include 
 #include 
 #include 
 #include 
 10 #include 
 #include 
 using namespace std;
 char *p[] = {"OTHER ","FIFO ","RR "};
 struct parameter { // data to pass
 + int policy; // new policy
 int priority; // new priority
 };
 void *threadfunc( void *);
 int
 20 main( ) {
 pthread_t t_id;
 struct parameter parm;
 int status;
 setvbuf(stdout, (char *)NULL, _IONBF, 0); // non-buffered output
 + for( int i=0; i < 3; ++i ){ // display limits
 cout << "Policy SCHED_" << p[i] << "	 MAX = "
 << sched_get_priority_max(i);
 cout << " MIN = " << sched_get_priority_min(i) << endl;
 parm.policy = i; // assign data to pass
 30 parm.priority= (i+1) * 2; // make up a priority
 status=pthread_create( &t_id, NULL, threadfunc, (void *)&parm );
 sleep(1);
 }
 return 0;
 + }
 void *
 threadfunc( void *d ) {
 struct sched_param param; // local to this function
 int policy;
 40 parameter *p_ptr=(parameter *)d; // cast to access
 param.sched_priority = p_ptr->priority; // passed data value
 // set new scheduling
 pthread_setschedparam(pthread_self(), p_ptr->policy, ¶m );
 memset(¶m, 0, sizeof(param)); // clear
 + // retrieve
 pthread_getschedparam(pthread_self(), &policy, ¶m );
 cout << "In thread with policy = SCHED_" << p[policy]
 << " 	priority = " << (param.sched_priority)
 << " effective ID = " << geteuid() << endl;
 50 return NULL;
 }

Figure 11.5 shows two runs of Program 11.2. In the first the effective ID of the user is 0 (that of the superuser). As a result, the requested scheduling changes are implemented. In the second run the effective ID of the user is 500. The requested changes are not made in the thread and default remains in effect.

Figure 11.5 Running Program 11.2 as root and as a regular user.

linux# p11.2
Policy SCHED_OTHER MAX = 0 MIN = 0
In thread with policy = SCHED_OTHER priority = 0 effective ID = 0

<-- 1

Policy SCHED_FIFO MAX = 99 MIN = 1
In thread with policy = SCHED_FIFO priority = 4 effective ID = 0
Policy SCHED_RR MAX = 99 MIN = 1
In thread with policy = SCHED_RR priority = 6 effective ID = 0
.
.
.
linux$ p11.2
Policy SCHED_OTHER MAX = 0 MIN = 0
In thread with policy = SCHED_OTHER priority = 0 effective ID = 500

<-- 2

Policy SCHED_FIFO MAX = 99 MIN = 1
In thread with policy = SCHED_OTHER priority = 0 effective ID = 500
Policy SCHED_RR MAX = 99 MIN = 1
In thread with policy = SCHED_OTHER priority = 0 effective ID = 500

(1) Run program as root ( eid = 0)requested changes are implemented.

(2) Run program as regular userrequested changes are not implemented.

By now I am sure you have noticed the similarities between the pthread_setschedparam library call and the pthread_attr_ setschedpolicy and pthread_attr_setschedparam library calls. The pthread_setschedparam call combines the functionality of the attribute-based calls and allows the user to modify scheduling policy and priority on the fly for an existing thread.

EXERCISE

Find the file sched.h that is part of the source code for your version of Linux. Its location is somewhat system-specific. The command

linux$ find /usr/src -name sched.h -print

should reveal its location. On our system this file resides in the /usr/src/linux-2.4.18-3/include/linux directory. Examine the sched.h file and find the INIT_TASK(tsk) macro that is used to establish a variety of scheduling parameters. What starting value is assigned to each of the following: dynamic priority, static priority, scheduling policy, and time slice?