CS 111: Lecture 8

Scribe Notes for 10/19/10

Scheduling

Preemptive Schedulers

Preemptive scheduling is implemented using clock interrupts at regular intervals, called the quantum. At these intervals, the scheduler interrupts the currently running process and actively changes control to another process, if available. The following sub-sections describe two types of preemptive schedulers.

Priority Schedulers

The examples above are specific cases of a priority scheduler. A priority scheduler schedules the highest priority process first. These priorities can be attributed to different properties of the process. For example, a priority value that is attributed to shortest process size would be the same as a Shortest Job First scheduler. Priority values that are attributed to arrival time would be the definition of FCFS schedulers.

There is a terminalogy problem that arises when using the concept of priorities in a quantatative form. A higher priority has a smaller priority value. This fact can create some contradictions when writing the scheduler. To fix this problem, the developers of Linux, assign "niceness" values to processes rather than priority values. The contradiction does not exist for "niceness".

Priorites can be established by either user or the kernel. User implemented priorities are called External Priorities, while ones set by the kernel and system are called Internal Priorities

Real-time Schedulers

All the schedulers described thus far can be considered best-effort schedulers. In these implementations, there aren't much if any penalties for not completing a task within a time frame. While this implementation works well for most systems in the world, it would not work for time-dependent systems (such as, car braking systems or nuclear power plants). For such systems, a real-time scheduler is used.

Real-time schedulers emphasize the deadline over all other aspects. The systems can differing values of emphasis. Systems for where there are major penalties for missing a deadlies would use a hard real-time scheduler. Soft real-time schedulers are used for systems with minor penalties for missing deadlines.

The emphasis on deadlines does not always translate to a drive for performance. In fact, most real-time systems give up performance in favor of predictability. For example, if there are two algorithms with one of them being slightly slower but consistent in runtime and the other one being faster but more volatile, a real-time scheduler will prefer the slower algorithm. The predictabiltiy of the system allows the scheduler to allot deadlines that the process will not miss.

Scaling Concerns

There are problems with standard schedulers that don't become apparent until you are on a large scale. When there are thousands of threads trying to access one CPU, the scheduler becomes a bottleneck for the threads. In the case of multiple cores or CPUs, a scheduler that is multi-core aware and doesn't induce race conditions is difficult to implement. Even then, this approch doesn't work when there are hundreds of CPUs.

File Descriptors and Race Conditions

Race conditions are possible between two processes that are trying to access the same file. Consider the following examples.

Example 1: File removed by another process

//Process A
1   fd = open("/tmp/foo", O_RDONLY);
2   char buf[1000];
3   size_t n = read(fd, buf, sizeof(buf));

//Process B
1   unlink("/tmp/foo");

It is important to note that files are kept around in a program if either: (a) there is a hard link to it from some directory, or (b) a process has the file open. Additionally, processes can communicate with each other via files.

Consider two process, C and D, which both attempt to open the file /tmp/foo with read-write permissions at the same time. Here, race conditions are possible because it is uncertain which process will open the file with the both the write permission.

To help avoid this race condition, we can have processes secure file access with a lock. In practice, introducing file locks introduces additional issues. In particular, Unix considers file locks to be purely advisory; if a process 'rudely' opens a file without first requesting a lock, then that process will be allowed to do so. Thus, file locking is ineffective at preventing malicious side effects caused by an uncooperative process. If all processes are cooperative, they can avoid race conditions. Enforcing mandatory locks is also not ideal, since a process may acquire a lock and be set into an infinite loop, essentially deadlocking the file such that no other process can ever access it.

Example 2: Creating a temporary file

1   fd = open("/tmp/temp", O_RDWR|O_CREAT, 0666);
		//leaving out error code checks
2   char buf[1000];
3   read(fd, buf, sizeof(buf));  //assumption is that you can still 
								 //access file if you still have fd
4   write(fd, /*details omitted*/);
5   close(fd);