More Scheduling Algorithms

In the previous lecture, we examined two simple scheduling algorithms, First-Come-First-Serve (FCFS) and Shortest-Job-First (SJF). We continue in this lecture with three more scheduling algorithms.

Round-Robin Scheduling

In round-robin scheduling, the scheduler gives equal priority to all processes. A queue is used to keep track of which process the scheduler should allow to run. It will allow a process to run for a given period of time (quantum). Then it will interrupt the process and place it at the end of the queue. The next process in the queue will then be run. Processes are added to the queue as soon as they arrive. In other words, round-robin scheduling is equivalent to FCFS plus preemption.

Consider the following scenario where four different jobs (A, B, C, D) need to be scheduled:

Process Arrive Time Run Time
A 0 3
B 1 1
C 2 7
D 3 4

Using round-robin scheduling with a quantum of 2 (jobs will run for a time of 2 before a switch occurs), the processes will be ordered like the following:

AA`B`CC`DD`A`CC`DD`CC`C (` = context switch)

How are the wait times and turnaround times?

Process Arrive Time Run Time Wait Time Turnaround Time
A 0 3 0 8+4k
B 1 1 1+k 2+k
C 2 7 1+2k 13+8k
D 3 4 2+3k 9+6k
Average 1+1.5k 8+4.75k
* k is the time it takes to perform a context switch.

We can see that the average wait time for this scheduling algorithm is better compared to a FCFS or SJF scheduler. However, the average turnaround time is worse since it has to continuously shuffle between the jobs that it has on its queue.

Because round-robin scheduling gives and equal opportunity for each process, processes will never face the problem of starvation. Starvation is when a process never gets a chance to run.

Question: Does it make any sense to have SJF with preemption?

After the scheduler lets a process run for a certain amount of time, it will look at the list of processes wanting to run and pick the one with the shortest amount of run time left. However, because the process that it was just running was the shortest task at the time (by definition), it will pick that task again unless there is a new task that has an even shorter run time. This means that shorter processes will starve out the longer ones.

Priority Scheduling

In priority scheduling, each job is given a priority number, and the scheduler will choose jobs to run based off of this number. Typically, lower priority numbers go first. For example, jobs with a priority number of 1 will run before jobs with a priority number of 2. A job's overall priority is influenced by two priority types: external and internal.

External Priorities

External priorities are set and modified by the user. For example, UNIX users can modify a program's priority before executing it.

Internal Priorities

Internal priorities are set and modified by the system (OS/scheduler). Generally, well-behaved programs will be given higher priority numbers, meaning that their execution can be delayed to a slightly later time. By using the yield() function, developers can influence the system into assigning their programs with higher priority numbers.

For a FCFS scheduler, the priorities are set based on the process' arrival time. For a SJF scheduler, it is based on the process' expected run time. For a round-robin scheduler, it is based on how much time has passed since a process last had the CPU.

Side-note: "Niceness" (The Confusion With Priority Numbers)

You might have noticed the concept of priority numbers (lowest number means highest priority) seems strange from a mathematical point of view.

UNIX tries to address this confusion by replacing priority numbers with "niceness" numbers. The idea is that if a process has a high "niceness" value, they are more willing to yield to other processes. Conversely, a mean process (one with a low "niceness" value) is less likely to yield.

Niceness values range from -19 (rudest) to 19 (nicest). The default value of process is 0. A user can actually influence this number through the nice command. By prepending a command with the nice command and a value, a user can make the process nicer or meaner. Note that by default, users can only make a process nicer. The only user who can make processes meaner is root.

Example

$ nice +10 make // make is run with a niceness boost of 10
$ nice -10 make // this can only be done by root

Niceness values are not the only determining factor in priority in UNIX. Other factors such as time spent waiting, resources, and expected run-time are considered.

Real-Time Scheduling

Real-time scheduling is applicable in situations where the execution time of a job is important. Deadlines are essential and the system must guarantee that a job will start and finish at a designated time. This type of scheduling has two distinct categories: hard and soft.

Hard Real-Time Scheduling

In a hard real-time scheduling system, deadlines for a process can not be missed. If a process needs to end at time t, it has to adhere to that rule with no exceptions. Predictability takes precedence over performance, and many aspects of its implementation reflect that. Caches are often disabled during testing because cache hits and misses affect the runtime of a process. Traps and interrupts are not used. Instead, the kernel utilizes polling, giving the kernel consistent behavior.

Question: Where would a hard real-time scheduling algorithm be used in?

It is appropriate for control software for time-critical systems such as braking systems and nuclear power plants. There are no second chances or room for delay when it comes to slowing down a car or preventing a nuclear meltdown.

Soft Real-Time Scheduling

In soft real-time scheduling, deadlines are still important, but it's okay to miss it. Low priority jobs can be skipped when necessary.

Question: Where would a soft real-time scheduling algorithm be used in?

Media players are a good place to use soft real-time scheduling. Ideally the application would render all the frames at the designated time (creating a smooth video to the user). However, it may run past the deadlines. In these situations, frames will be skipped and the user will notice, but the application can still continue on.

The following are some scheduling algorithms that a soft real-time scheduler might use:

Earliest Deadline First (EDF)

Whenever the scheduler needs to pick a task to run, it will choose the one with a deadline that's closest to the current time (analogy: I have CS111 homework due today and CS131 homework due tomorrow. I'll do CS111 first.).

Rate-Monotonic

Frequently run jobs are assigned a higher priority.

Scaling and Scheduling

If the number of threads increase into the millions or billions, it will not be manageable on a single CPU. We can attempt to address this problem by using multiple CPUs and cores, but this requires a scheduler that can run in parallel.

Grid computing introduces additional problems with regards to data transmission between nodes. This is an open problem in the computer science community. Amazon Elastic Compute Cloud (Amazon EC2) is a well known grid computing network.

Consistency

What can go wrong with file descriptors?

Consider the following code executed by two processes.

process_1
fd=open("/tmp/foo", O_RDONLY);
charbuf[1000];
ssize_t n=(fd, buf, sizeof(buf));
process_2

unlink("tmp/foo");

In this situation, process 2 will unlink the file after process 1 opens it, but before it gets to read from it. Will the file disappear, creating an error on process 1's read?

In this case it's important to know when a file is actually deleted. Files are kept around if there is a hard link to it from some directory or if it has been opened up by a process. This means that despite process 2 unlinking the file, because process 1 had already opened the file, it would still be able to read from it.

What about another scenario where two processes open the same file and one reads from it while the other is writing to it? If they're working with different sections of the file, then there are no problems. But if they attempt to access a common area, then a race condition will occur and they will step on each other's work.

What can be done?

Locks can be used to control access to file descriptors. A useful function to help facilitate locking is fcntl():

int fcntl(int fildes, int cmd, struct flock *p...)

p points to a struct that describes the type (l_type), starting offset (l_whence), relative offset (l_start), size (l_len) and process ID (l_pid) of the segment of the file that is to be affected by this fuction call.

cmd can be set to to the following:

F_SETLK - Set or clear a file segment lock according to the description in p.
F_SETLKW - This is the same as F_SETLK except that it will wait until a lock is obtained.
F_GETLK - Get the first lock which blocks the lock description in p.

It is very important to note that the locks are not mandatory in UNIX, meaning that a process can completely ignore locking. Processes cooperate to avoid race conditions.

Question: So why don't we just enforce mandatory locking?

You could, and there are operating systems that do that. In theory it sounds like a good idea, but practically speaking, deadlocking becomes a major issue. In UNIX systems, because locks are not mandatory, race conditions become the major problem while deadlocks are not.

Temporary Files

Suppose we have a function that creates a temporary file to do something:

fd = open("/tmp/temp", O_RDWR | O_CREAT, 0666);
unlink("/tmp/temp");
read(fd, ...);
write(fd, ...);
close(fd);

It's probably easy to see how multiple processes running something like this would eventually step on each other's work. What can we do to fix this?

We could append a process ID and thread ID to the end of the temporary file name, reducing the collisions. We can even take it a step further and generate a random string R to use as the file name. We can then utilize the O_EXCL flag in open() to set the open to fail if the file exists:

while(fd = open("/tmp/R", O_CREAT | O_RDWR | O_EXCL, 0666) < 0 &&errno = EEXIT)

Side-note: Wouldn't This Be Fun...

Another interesting situation can occur with temporary files. Suppose we have a runaway process that creates a temporary file that becomes extremely large. The user might notice that something is taking a lot of disk space. He/she looks into the temporary files directory and sees nothing there because the process unlinked the file. Now what? This user is now in a difficult situation, but there is a powerful program that can be used to help him/her out: lsof.

lsof along with the -p flag and a process id number can list all open file descriptors for a particular process. Temporary files that were hidden from the user can be seen with this method.

... Or, you can just take the easy way out and reboot.

GNU Zip (gzip)

Let's consider some cases when the kill command (control-c) is invoked while gzip is doing its work.

0) Before anything is done
^c -> Exit, and there is nothing to worry about.

1) Creates an empty file foo
^c -> Unlink foo.gz since nothing is written on it.

Now we are entering a critical section, so read and write operations are considered to be inseparable.

2) Reads from foo, write to foo
^c -> Unlink foo.gz, since we cannot guarantee the integrity of the data.

3) Close foo.gz
^c -> At this point we prefer to unlink foo, but it's okay to unlink foo.gz

4) Unlink foo
^c -> Don't stop me now! I'm having such a good time!

To prevent guarantee that file is always unlinked, we can include a signal handler that will unlink the file before terminating:

main() {
  signal(SIGINT, handler_int());
  signal(SIGINT, SIG_DFL);
  close (output_fd);
  unlink (ouput_file);
}
void handle_int (int sig) {
  unlink (output_file);
}