CS401: Operating Systems

4a. Discuss CPU scheduling and its relevance to operating systems

• Define scheduling and the concept of fair scheduling.
• What is a computing cycle?
• Define a bus.

Scheduling refers to how the CPU decides which tasks it should retrieve first from the Ready queue. Fair scheduling refers to how the user understands scheduling, in terms of the context of their particular computing situation.

Fair scheduling does not imply moral reasoning, which may be confusing to someone who is unfamiliar with the terminology of computer science. Rather, it applies to the optimal use of resources and computer performance.

According to fair scheduling, should it take a long time for the CPU to perform an action (i.e. a long computation time), with a short wait time for the user? Or should there be short CPU computation time and long user wait time? The answer is: it should be short on user time and long on computation time.

Most users would probably argue that CPU scheduling tasks should prioritize the user, regardless of the length of time it takes to perform a computation. We do not want to annoy users by making them wait! 

However, some would consider prioritizing the user unfair because it violates fairness in terms of CPU scheduling. Minimizing average user response time violates "fairness" in terms of CPU scheduling. Let's be practical and make them wait!

The computer cycle refers to the entire cycle the bus takes to complete one iteration around the computer. As we discussed in section 3a on synchronization, the bus is a scheduling paradigm similar to a subway line which has different stops (computing resources, I/O) that must be placed on the bus and taken to the resource intended to be manipulated. Results are put back on the bus to the computing resource intended, such as I/O, memory, screen, etc.

Computer engineers strive to develop the most efficient and reliable techniques for organizing and preventing conflict among different operations and their resources, which are always limited in the real world. Whether it is vehicle traffic, queueing theory of any kind, or making sure operating systems perform robustly and efficiently, these challenges remain standard.

While the conditions and parameters of computing have changed over the years, the lessons learned from doing things well persist into the modern age, in addition to the benefits.

Review this material in Thread Scheduling (the first from 54:00 to the end and the second until 31:00) and CPU Scheduling.

 

4b. Explain the general goals of CPU scheduling

• Why is fair scheduling an important concept in operating systems?
• What does it mean to maximize throughput?
• Define overhead. Name two parts of maximizing overhead.

Fair scheduling refers to CPU scheduling controlled by the OS, which optimizes the use of computing time and resources according to the goals intended for the job.

Maximizing throughput means completing the most important meaningful work in the shortest amount of time. Two parts of maximizing throughput include 1. minimizing overhead and 2. optimizing the efficient use of computing resources, often by minimizing response time.

Programming errors are the primary cause of overhead in CPU scheduling. Minimizing overhead usually means eliminating useless or unnecessary computing cycles that are unnecessary and create little, if any, benefit. We reduce overhead cost by promoting brilliant programming, which tends to incorporate practices that are less than intuitive.

Goals for minimizing overhead include: 

1. Minimize context switching.
2. Minimize accessing CPU.
3. Minimize accessing memory.
4. Minimize accessing I/O.

The second main goal of CPU scheduling is to minimize response time. Unfortunately, our two goals – minimizing overhead and response time – are often at loggerheads. Short user requests are easy to handle, but maximizing throughput may preclude user activity. Meanwhile, computational cycles tend to be long but improve throughput.

The concept of fair scheduling originated as a way to balance limited and expensive resources. But even today, when resources are much cheaper, the multiplying effect of modern computing has demonstrated the wisdom of these techniques which have minimized overhead and maximized throughput.

So, maximizing throughput means achieving the most useful "bits" in the shortest amount of time, transmitting the greatest percentage of data possible. Computing will always involve limited data transmission, even though its magnitude has grown significantly. Brilliant software engineers have created computing functions that perform more efficiently, achieving more benefit and speeding processing along with fewer lines of code and less total data transmission.

Review this material in Thread Scheduling (the first from 54:00 to the end and the second until 31:00), CPU Scheduling, and CPU Scheduling.

 

4c. Describe the differences between preemptive and non-preemptive scheduling

• Describe a preemptive and a non-preemptive CPU scheduling technique.
• What is a computing preemptive resource and a computing non-preemptive service?

Here's another analogy that is similar to computing. Let's say, you work in a call center and your job is to respond to inquiries from users. Should you respond to each call, first come, first serve, which means you could get bogged down responding to one question that requires an hour of research? Or is it better to respond to 20 inquiries that are easy to answer first, so you can make 20 people happy and deal with the one long response later?

A preemptive scheduling technique is one that processes shorter computer processing jobs first, preempting longer CPU processing jobs. Preemptive scheduling is determined by the priority of the process as determined by the OS.

• Shortest Remaining Job First (SRJF) is an example of a preemptive scheduling technique. Note that Shortest Remaining Time First (SRTF) is simply another way of saying Shortest Remaining Job First.

A non-preemptive scheduling technique is one that processes computing jobs as they are presented, i.e. it does not consider the length of time the job will take before it begins working on what is next in the queue. Non-preemptive doesn't care about length. It just runs to completion whatever is presented to it. No interruptions.

• Shortest Job First is an example of a non-preemptive scheduling technique.

Shortest Remaining Time First (SRTF), which is the same as Shortest Remaining Job First (SRJF), requires a type of psychic ability to judge which job is actually going to be the shortest remaining job to finish first, since the OS only schedules, it does not read or investigate prior to scheduling.

There are several possible techniques for simulating this psychic ability.

Estimating SRTF requires:

1. Adaptive scheduling – changing scheduling policy based on past behavior of certain scheduling jobs and functions.
2. Estimator function – taking the average of past job length times.
3. Exponential averaging – is similar to taking an average, but can vary over time-based on past time requirements for that particular type of job.
4. Multi-level feedback scheduler – requires multiple ready queues that provide feedback to each other.

Every ready queue has a distinct and hierarchical priority. No two queues may have the same priority and each queue has a particular scheduling algorithm. Each higher-level, ready queue has a smaller time clock.

As jobs exceed the time clock of higher-level queues they descend to lower-level ready queues until the time to run the job does not exceed the clock of that level queue, regardless of priority. If a job does not expire the time clock of a ready queue, it will push the next job up to the next higher-level ready queue.

You can take a computing preemptive resource away from a thread without suffering any severe consequences. Taking a computing non-preemptive resource away from a thread, on the other hand, would have noticeable consequences.

Preemption is an attractive proposition for scheduling. Preemption considers the length of time each operation needs to execute. Since most user interface operations are preemptive, many programmers believe it is the solution for every scheduling problem. However, that would be foolish. One simple solution for all scheduling issues does not exist, otherwise, the issue of scheduling would be trivial and we would not spend any time or research discussing or learning about it.

Review this material in Thread Scheduling (first from 54:00 to the end, second until 31:00) and Scheduling.

 

4d. Discuss four CPU scheduling algorithms

• What are four CPU scheduling algorithms?
• Describe a negative aspect of FIFO and Round Robin.

Let's look at four CPU scheduling algorithms:

1. First In First Out (FIFO) – the first item in the docket is done until completion, followed by the second, third, and so on.
2. Round Robin – a clock controls access to the CPU. The clock goes off, you obtain access to the CPU for a small, specified period of time. If the job is not finished, you have to wait until your next turn is up to continue.
3. Shortest Job First – the CPU processes whatever job is smallest.
4. Shortest Remaining Time First – the CPU processes whatever job is closest to completion first.

A negative aspect of FIFO is that users become annoyed when they have to wait for the CPU to finish a longer job that arrived into the docket before theirs. A negative aspect of Round Robin is that so much overhead is continually switching. The average response time is much worse than the other options!!

As with all queue theory, classical approaches are available. However, each option has its own drawbacks. You should not implement them without considering the positive and negative consequences. Also, each option, even when implemented correctly, may have unintended consequences. Considering all of the scenarios that may occur, and the consequences that may result, is a critical part of robust and best-practice software design.

The most robust software is typically the simplest. But, an application, particularly involving interfacing with humans (involving a user experience, UX, and user interface, UI), usually requires more complex software to provide a graphical user interface (GUI) today's user expects. Simplicity is often lost and challenges that need to be resolved often ensue. 

Review this material in Thread Scheduling (first from 54:00 to the end and second until 31:00) and the first seven slides of CPU Scheduling.

 

Unit 4 Vocabulary

• Computer bus
• Computing cycles
• CPU bus
• CPU overhead
• CPU scheduling
• CPU scheduling
• Fair Scheduling
• FIFO (first in, first out)
• Maximize throughput
• Minimize overhead
• Non-preemptive resource
• Non-preemptive scheduling technique
• Preemptive resource
• Preemptive scheduling technique
• Ready queue
• Round Robin