IC221: Systems Programming (SP15)


Home Policy Calendar

Lec 15: Process State and O.S. Scheduling

Table of Contents

1 Process State and Scheduling

The scheduler of the O.S. is the most fundamental and perhaps the most important component of the O.S. kernel. Its sole task is to decide which process will run next on the CPU, the heart of process management. This decisions cannot be made lightly. There are many contingent properties to consider when discussing the scheduler and process management; such as, ensuring that all process have a chance to run and that the cpu is being fully utilized.

To complicate the issue, not all process are ready to run. Process can be in many different states. Some are ready and can be run immediately, for sure, but others may be blocked or waiting for some other process to complete, like a shell, or for a hardware component to become available, like reading from disc. Some process are neither blocked nor waiting, but just sitting around wasting resources … zombies, and others loose their parents and are orphaned and adopted by other processes. It's a whole ecosystem.

In this lesson, we'll explore this ecosystem of varied process states and how this affect the O.S. resource of process management. We will look briefly at different ideas in scheduling algorithms and, in particular, how to interact with the Unix scheduler. We will also go over the various states of a process, both alive and undead.

2 The O.S. Scheduler

The scheduling of process or jobs is a large academic area. Depending upon the task at hand, different scheduling algorithms are used. For example, in real-time systems, like in a airplane auto-pilo, it is important to ensure that a computation occurs immediately so action can be taken. You may want to schedule tasks differently on a desktop computer where waiting a few milliseconds for a webpage to load isn't going to kill anyone.

We will begin the discussion by first overviewing a few different scheduling concepts. Next, we'll explore the Unix scheduling routine, and how you, the programmer, can interact with the schedule to change the priority of your processes.

2.1 O.S. Scheduling Ideas

A good scheduling algorithm must meet the following constraints:

  • CPU Utilization: The processor should be utilized at the highest possible level. If there exists a process that can run, it should be running.
  • Turnaround Time: How long does it take for a process to run once it is ready to run?
  • Fairness: All tasks, of equal priority, should have the same opportunity to run. Or, no process should be starved for resources, and unable to run.

Based on these concepts, we can come up with some fairly naive strategy for scheduling. Consider a situation where, you — the processor — are being tasked with completing some amount of work divided into jobs. Jobs arrive in some order, each takes some amount of time, and once you start a job, you don't stop until you finish it.

One strategy you could employ is just First-Come-First-Serve, like a queue. While this is effective at CPU Utilization and Fairness, it doesn't have good turnaround. A job at the end of the queue could end up waiting a long time before it actually gets to run, and that job could be the computation needed most of all.

Another strategy, we could employ is some kind of introspection scheduling routine. Suppose we knew how long it would take for a job to complete, then we could just always schedule the shortest job next. Or, perhaps we are facing a deadline, like we must compute a flight trajectory RIGHT NOW or this plane is going down, then we could schedule jobs based on a deadline, or deadline scheduling. These strategies work great if we know how long tasks take to complete; we do not have that luxury on most Unix systems — have you ever written an infinite loop?

2.2 Preemptive Scheduling

Unix systems, and most modern consumer Operatin Systems, use a form of preemptive scheduling, which means that a process gets scheduled for some amount of time, then it is preempted before it get's to finish and another process get's to run for some amount of time, which will get preempted, allowing another process to run, and so on. Returning to the scenario where you are the scheduler, now you don't have to fully complete the job before moving onto the next. We can again come up with a few reasonable strategies for how to schedule tasks.

One simple solution to scheduling is to just allow each task to run for a set amount of time, say 500 milliseconds, and then you swap it out with the next job, running for 500 milliseconds, and then the next, and etc. You move in this round robin fashion until all the jobs are complete, and, on its surface, this seems like a great strategy. The CPU is being utilized a lot, all jobs have the same turnaround, and it is the most fair way to divide time as possible.

But, there are other factors to consider. Maybe if you let a job run for a bit longer then your timeout, it would have completed, and would not have to rotate all the way around before finishing? Or, maybe a job is using the CPU but it is not doing any computation; instead, it is just waiting for the disc to return with data, which can take an eternity in CPU time. It doesn't seem like the CPU is being properly utilized in either of those situations.

2.3 Priority Queue Scheduling

Unix implements a hybrid strategy for scheduling that is a mix of round-robin scheduling and priority scheduling, where higher priority process go first. Essentially, there is a set of priority queues, from -20 to positive 19, and within each priority queue, process are run in a round robin fashion, but which queue executes is chosen based on priority preference. To avoid starvation, process can be moved from lower priority queues to higher priority queues when they have not run in awhile. This strategy is called multilevel queue scheduling and it is used in most Unix systems, and is very effective and highly efficient in the selection of next processes to run. It is also easily customized and adaptable for user needs, e.g., running tasks at the highest priority.

The gritty details of the Unix scheduler is a topic for your Operating Systems class, not systems programming, and instead we will concern ourselves with how we interact with the scheduler. There are two key questions to address:

  • Given a process, how do we understand its priority?
  • And, how do we change its priority?

2.3.1 How nice a program is its priority

In Unix, the concept of priority is described as how nice a process is to another process. The nicer a process is, the more willing it is for another process to run in its stead. Thus, nicer processes have lower priority and meaner processes have higher priority.

The nice-ness scale is between -20, very mean, to 19, very nice. By default, all programs are born with niceness 0: just plain ambivalent. Some programs must then become less nice, such as interactive process that must meet some deadline. For example, you want your computer to play sound when you click on something, or, for that matter, your mouse to move when you move it. Those process shouldn't be scheduled with a low priority because it would degrade the user experience.

There are also other process running where being nice is fine. For example, many daemons, programs constantly running the background, do not need a lot of priority. They are not interactive, and not being scheduled right away is not going to upset any users.

2.3.2 Viewing Process State with ps

One way to view the nice level of a process is using the shell command ps, short for process state. The ps command is an amazing tool for inspecting the state of process, and below, we use it to show the nice-ness of the process running on a typical Linux system in the lab.

#> ps axo nice,comm,pid --sort nice
 NI COMMAND           PID
-20 cpuset             36
-20 khelper            37
-20 netns              39
-20 kintegrityd        43
-20 kblockd            44
-20 ata_sff            45
-20 md                 47
-20 crypto             56
-20 kthrotld           65
-20 binder             69
-20 deferwq            88
-20 charger_manager    89
-20 devfreq_wq         90
-20 ext4-dio-unwrit   282
-20 rpciod            448
-20 nfsiod            455
-20 kpsmoused         549
-20 kvm-irqfd-clean   887
-20 iprt             1224
-20 hd-audio0        1353
-11 pulseaudio       1735
-10 krfcommd          639
  0 init                1
(...)

These commands, with negative nice values, are vital to the execution of the computer. For example, cpuset is a process that assists with loading of memory and process for execution, the pulseaudio systems is used for audio output, and the various k* commands are kernel process. Those really need to be run with high priority.

In the middle, you'll find many process with priority 0.

(...)
  0 ntpd             2040
  0 sshd            13782
  0 sshd            13789
  0 bash            13790
  0 emacs           14453
  0 emacs           14712
  0 emacs           15219
  0 emacs           15273
  0 emacs           15304
  0 emacs           18917
  0 kworker/7:0     21860
  0 emacs           27417
  0 crontab         28380
  0 sh              28381
  0 sensible-editor 28382
  0 emacs23         28390
  0 sshd            29814
  0 sshd            29821
  0 bash            29822
  0 crontab         29894
  0 sh              29895
(...)

These process are user-level process. I have a number of emacs sessions open, which all have equal priority. The shell, bash, is also running with priority 0. Finally, at the bottom, are the nicest of processes:

(...)
  1 rtkit-daemon     1737
  5 ksmd               52
 19 khugepaged         53

The rtkit-daemon is a process for realtime scheduling, but it doesn't need to run that often, in relation to the process it is scheduling. Thus, its just a bit nice. While khugepaged is a process that manages large memory pages, collapsing them whenever necessary, but this operation doesn't have to occur for the system to function properly, it's just nice when it does. Thus, the priority of this process is quite low, being very nice.

2.3.3 Programming Priority with getpriority() and nice()

When programming, we can inspect the current priority level of a process using the getpriority() system call, which has the following function declaration:

#include <sys/time.h>
#include <sys/resource.h>

int getpriority(int which, int who);

The which is for which kind of priority we are interested in. The Unix system has multiple priority indicators, but we are only concerned with the process level priority, or PRIO_PROCESS. The who is to query the priority of a given process (or other identity) by id. Using the value 0 for who refers to the current process.

Here's a program that will print the current nice value for the process:

#include <stdlib.h>
#include <stdio.h>
#include <sys/types.h>
#include <sys/resource.h>

int main(){

  int prio;

  prio = getpriority(PRIO_PROCESS, 0); //get the priority of this process

  printf("Priority: %d\n",prio);
  return 0;

}

Of course, since the default priority of any process is 0, the output of this program is:

#> ./getpriority
Priority: 0

We can change the priority of a process using the nice command, which exists as both a command line tool and system call. It's purpose is to make programs more nice or less nice. For example, on the command line, we can run the getpriority with a nice value of 10.

#> nice -n 10 ./getpriority
Priority: 10

The output now indicates that the priority of the program is 10; it is more nice, more willing to let other programs with lower priority values run. We can try and set a negative priority value with nice:

#>nice -n -10 ./getpriority
nice: setpriority: Permission denied
Priority: 0

This will fail because only the privileged user can set a negative nice value; however, sudo can make this sandwich.

#> sudo nice -n -10 ./getpriority
Password:
Priority: -10

The sudo command says, run this command as the privilege super user … you do not have sudo privilege on the lab machines.

In code, we can do the same thing using the nice() system call:

#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/resource.h>


int main(){

  int prio;

  prio = getpriority(PRIO_PROCESS, 0); //get the priority of this process
  printf("Priority: %d\n",prio);


  if( nice(10) != 10){ //error checking is different
    perror("nice");
    return 1;
  }

  prio = getpriority(PRIO_PROCESS, 0); //get the priority of this process
  printf("Priority: %d\n",prio);

  return 0;
}

One thing to note about nice() is that it returns the new priority value, which may be negative. To error check, you must compare the output of nice() with the value you expect.

3 Process States

Now that we have a decent understanding about how process are scheduled and how to interact with the O.S. to affect the priority of scheduling, let us turn our attention to the different states of a process. This is an important discussion because a scheduler must consider both the priority of a process and if it ready to run in order to maximize the utilization of the CPU. It turns out that not all processes are ready to run, and that a process can be in a number of different states.

3.1 Running, Waiting, Blocked, and Undead

There are three main states of a process. It may be running, which means it is currently running on the CPU; it may be ready and waiting, which menas that it is ready to run immediately if selected; and, it may be blocked and waiting, which means that it is not ready to run because some other information is needed by the process before it can proceed. A scheduler will consider both the priority of the process as well as it's current state

A process can be blocked for a number of reasons. Perhaps the most common cause of a process being blocked is I/O, such as reading and writing from a device. Consider that a read/write is a system call, which means that a context switch must occur where the process stops running and the kernel starts running to complete the action. Conceptually, we'd like to think that the context switch occurs immediately, the process swaps out, the kernel swaps in, performs the action, and the kernel swaps out, and the process swaps back in and continues on — but it doesn't work that way.

Instead, once the system call is initiated, the process is blocked and waiting for the system call to complete. At this point, the process is no longer eligible to be run, i.e., it is not ready, and the scheduler can schedule another process to run. The next process may be the kernel, which could complete the system call and return the result and unblock the process, or it could just be another user process, in which case the blocked process remains so.

Another way to think about how I/O blocks a process is to consider the shell. The shell prompts a user for input by reading from stdin, but it cannot continue until the user actually typed something into the terminal and hits "enter." That could take an eternity in compute cycles, and instead, the shell is blocking on I/O waiting for user input. In the meanwhile, other processes can run, and this is how the scheduler ensures high utilization.

Beyond I/O, a process can block for other reasons. For example, a call to wait() is a blocking system call. The parent process is designated to block and will not proceed until the kernel recognizes a state change in the child, which will unblock the parent.

3.2 Undead processes: Zombies

To understand the idea behind undead process, you must first think about how the system call wait() functions. When a parent is calling wait() it is specifically blocking until the child process has terminated (or changed state). That means, there is some period of time between when the process actually terminates and when the parent process becomes unblocked. The child process still exists during that short window, but is not alive … it is undead, or a zombie!

A zombie is a process that has terminated but has not been wait()'ed on by its parent. For example, consider the following program:

int main(){
  int i;
  for(i=0; i<10;i++){

   if(fork() == 0){ //create a child
      _exit(0); // and exit
   }

  }

  while(1); //run forever
}

The parent process will fork 10 children, who all just _exit() immediately, but the parent does not call wait() and instead spin's in a while loop. The child processes have terminated and are now in limbo, not running but waiting to be wait()'ed on by the parent. They are zombies! And we can see this state by looking at the ps output:

#> ps -o pid,comm,state
  PID COMMAND       STATE
 2362 bash            S
 2463 zombies         R
 2464 zombi <defunct> Z
 2465 zombi <defunct> Z
 2466 zombi <defunct> Z
 2467 zombi <defunct> Z
 2468 zombi <defunct> Z
 2469 zombi <defunct> Z
 2470 zombi <defunct> Z
 2471 zombi <defunct> Z
 2472 zombi <defunct> Z
 2473 zombi <defunct> Z
 2475 ps              R

"Z" is for Zombie, while "R" is for running. The additional "<defunct>" indicator is what the UNIX system uses to indicate that the process is now a zombie.

The big problem with zombie processes is in long running services. If you have zombie leak, these process can stick around for the entirety of the parent program. This wastes resources, and eventually, a zombie apocalypse will occur, and you're kernel will crash as it slowly runs out of resources.

3.3 Orphan Process, init, and daemons

At this point you may be wondering, what happens if the parent dies before the children? Won't the children become zombies forever if there is no parent to ever call wait()?

The answer is no. If a parent dies before the children, those children are now designated as orphans. The special process init inherits all orphans and will call wait() on them once the children complete.

It is sometimes desirable for a process to become an orphan and be inherited by init, such as long running process that always execute in the background. In Unix terms, such process are called daemons, and if you look at all the processes running on your unix computer, these are processes with names that end in "d." A daemon is usually formed by having a process fork a child, which executes the logic of the daemon, while the parent dies. The daemon is now an orphan, which is inherited by init, and the daemon continues running happily in the background.