CS 111 - Operating Systems Principles

      Notes by Wade Norris

Lecture 19: Thursday, June 3, 2010

Topic: Scheduling and Cloud Computing

Textbook Reading: Sections 6.3 to 6.3.3

Outside Reading: Above the Clouds (PDF)

Scheduling

Introduction

Scheduling provides a solution to the the common problem of too much demand for computation with too little resources. If your computer cannot handle the number of processes currently running then the OS must decide which processes to run when. If many processes are asking for common resources how will we divide up access to these processes. When the kernel decide the order of execution of these many processes it will strive to do so in a fair way that enhances the preformance of the computer. In some situtions we may not want to even give access to the resources to some requests, making scheduling essentially a "glorified bouncer".

Types of Scheduling

• Long Term - Which processes are admitted to the system? If there is too much demand, then we may not even allow some processes to wait for access. In scheduling we must decide whether it is worth it to let something wait if demand is too high. What processes can we deny access to resources without causing problems?
• Medium Term - Which processes will reside in RAM? RAM space is much more limited than disk space, so while processes that don't have room to fit in RAM can be cached in virtual memory on the drive, it will be much slower to access. This means that process put on the disk will most likely be set aside for later execution, when they will be transferred back to RAM. The question in medium term scheduling is which processes will be set aside by caching them and which will reside in RAM.
• Short Term - Which processes will have a CPU currently? If we have many processing trying to gain CPU time and be executed, which ones will be executed when? We must consider which processes should or need to be executed sooner and which processes will take a very short time to execute. These considerations should cause us to bump up these processes on the execution order. If we have a multicore processor then we may be able to give multiple processes execution time concurrently. A vast majority of what we deal with in scheduling is short term.

Scheduling Metrics

Scheduling metrics are different methods of measuring the effectiveness of a scheduler at giving processes access to the CPU. There are multiple metrics used for measuring different aspects of the processes' execution timing. There different metrics all important for different things: some applications require a quick initial batch of execution while others are only concerned with how long it takes untill they complete execution. The following metrics are the ones we will use to analyze different scheduling algorithms.

Common Metrics

• Wait Time - The amount of time it takes for the process to first be run from when the process arrives.
• Response Time - The amount of time it takes for the first output to be completed from when the process first arrives.
• Turnaround Time or Latency - The amount of time it takes for the process to complete being executed from when the process first arrives.

Which metrics are important to certain applications?

• Payroll Application - Here we want the entire job to be completed as fast as possible. We don't car how long it takes for the first person's pay t be computed, we care when everyone's is completed. So in this case Turnaround Time is important.
• Wait Time - Here we can start working or reading once something has been outputed to the page. Due to this we are more concerned with how long it takes for the first substantial output to be generated and not as much how long it takes for the entire page to be loaded. Frequently the user will click a link at the top of the page, meaning the rest of the page does not even have to be loaded. Therefore we are not as concerned with Turnaround Time and rather we are more concerned with the Response Time.

Aggregate Statistics

• Utilization - This is the percentage of CPU time spend doing usefull work. By usefull work we generally mean execution of user code rather than time spent doing scheduling or context switching.
• Throughput - This is the rate of usefull work being done. Throughput is calculated as the sum of all runtime over total time.

Generally in scheduling the goal is to maximize utilization and throughput while minimizing wait time, response time, and turnaround time. Sometimes though these goals can conflict and great difficulties in optimizing scheduling. Frequently we will have to sacrifice one metric in order to benefit the other.

Common Scheduling Algorithms

• First Come First Serve (FCFS) - In first come first serve each process will be executed in it's entirety in the order in which the process comes in.
• Shortest Job First (SJF) - In shortest job first we execute processes in their entirety but when switching to the next process we select the shortest process. In this case we would assume there is some method of measuring execution time, maybe the process will specify how long it will take when it asks to be executed. If it takes longer it will be cut off and told to try again. The important part though is that when processes are placed in waiting for execution they are pulled out not based on when they were put in, but based on some measurement of how long they will take. In this manner the long CPU hogs will have to wait longer for a chance to execute.
• SJF + Preemption - Preemption means that processes will not neccesarily be executed in their entirity as before. Now we may interupt processes mid execution to context switch to another process. In shortest job first if a process comes in that has less work to do than the current process executing has left, then it will interrupt the currently executing process and context switch over to the shorter one. In this way the shortest task waiting for execution will get execution time immediately.
• FCFS Round Robin Preemption - This case is slightly more complex. Now rather than picking one process to execute based on a single criteria, we will rotate through all of the processes giving each a chance for one unit of execution. The order in which they will be rotated through depends on when they arrived.
• Priorities - Priority based scheduling requires a level of priority that will be supplied either by the user or the system. If we use a system where we have high, medium, and low priority then all high priority processes will be executed before medium and low and all medium processes will be executed before low processses.

Example Process Set

For this example of each type of scheduling algorithm lets say we have 4 processes. Process A, B, C, and D will be attempting to get access to the CPU. The arrival times will 0, 1, 2, and 3 and the run times will be 5, 2, 9, and 4 respectively. We will now go through different algorithms and in what order they will be executed. A letter in the execution order will represent one time unit of execution. The letter Y will represent the time of a context switch between processes.

First Come First Serve
Execution Order: Y A A A A A Y B B Y C C C C C C C C C Y D D D D
Process A Wait Time: 0 + Y
Process B Wait Time: 4 + 2Y
Process C Wait Time: 5 + 3Y
Process D Wait Time: 13 + 4Y
Utilization: Almost 1
Average Wait Time: 5.5 + 2.5Y
Average Turnaround Time: 10.5 + 2.5Y

Shortest Job First
Execution Order: Y A A A A A Y B B Y D D D D Y C C C C C C C C C
Process A Wait Time: 0 + Y
Process B Wait Time: 4 + 2Y
Process C Wait Time: 9 + 4Y
Process D Wait Time: 4 + 3Y
Utilization: Almost 1
Average Wait Time: 4.25 + 2.5Y
Average Turnaround Time is the same as before.

SJF + Preemption
Execution Order: Y A Y B B Y D D D D Y A A A A Y C C C C C C C C C
Process A Wait Time: 0 + Y
Process B Wait Time: 1 + 2Y
Process C Wait Time: 9 + 5Y
Process D Wait Time: 3 + 3Y
Utilization: Almost 1 (but slightly lower with 1 more Y)
Average Wait Time: 3.25 + 2.75Y
Average Turnaround Time is higher.

Starvation

Starvation occurs when a process is caused to not get access to the CPU due to a schedueling algorithm that lets it constantly get cut of for other processes. When there is high demand of resources starvation can occur very easily. FCFS and Round-Robin algorithms will no cause starvation because they will either rotate in serving all processes or they will solve processes based on the order in which they came in, and no process will sit around without ever getting served. On the other hand SJF algorithms will interject shorter processes in front of longer processes without considering how long the other processes have been sitting around. This could cause some processes to sit around indefinitely if there is enough demand.

Realtime Scheduling

In realtime scheduling there are limitations that we do not normally have. In realtime scheduling there are time constraints that must be met or the there will be adverse reactions or the work will be wasted because it will no longer be usable.

• Hard Realtime
- If time constraints are not met there there will be adverse reactions. For example bakes in a car or a nuclear reactor. If timelines are not met there could be very bad results, not just a slow down of preformance.
• Soft Realtime
- If the deadline there are not terrible results but the work will be useless so the task should just be dropped. For example in video streaming if you cannot process a frame in time it will just be dropped, or if you know ahead of time you will not meet that deadline, the task should be preemtively dropped.

Once big problem with priority scheduling is priority inversion. In priority inversion some high level process is waiting to get a lock on something where a low level process already has the lock. In the midst of waiting on the low level process to give up the lock a mid level process starts running. Now the high level process will keep giving up controll because it is waiting for the low level process to give up the lock, but the low level process never gets to run because the medium level process has priority. This is what caused the loss of the mars rover. How do we solve this problem? When a higher level process is waiting on a lower level process, we lend the priority level of a higher level process to the lower level process untill it gives up the lock. This prevents the problem of priority inversion.

Disk Scheduling

There are many differences between scheduling for the disk and scheduling for the CPU. The disk takes a lot longer for accesing so we want to attempt to limit the number of times we access it in any way possible. Also since there are physical arms that must position the head to read from physical locations the idea of scheduling for the disk must be much more complex and take into consideration how long it will take to position for the reads requested.

How do we solve this problem? Abstraction. The simplest and most common abstraction is stretching the entire disk into one long line of data in which the cost of access is just the distance from the read head to the location of the data.

• FCFS - This algorithm follows the same principle as the CPU version, the jobs requested of the disk will be completed in the order they came in. This causes lots of seeking, but prevents and starvation.
• SCTF - Shortest Seek Time First is like SJF except instead of execution time it is based on seek time. This minimizes seek time and maximizes throughput, but causes possible starvation. It also takes more CPU time, but this time is negligible because the CPU is so much faster than the disk.
• FCFS + SCTF - A comination of the two can be done where requests are grouped into batches. Within these batches requests will be ordered by the shortest seek time first, but the batches will be done in the order they came in. This prevents starvation while still gaining some of the benefit of shortest seek time first.
• Elevator Scheduling - Elevator scheduling implements a shortest seek time first algorithm, but only in one direction. In this way the seek head essentially scans the entire disk cyclically and completes any jobs along the way. The head can either bounce and seek back in the opposite direction doing jobs on the way back as well, or it can skip over to the beggining again. The benefit of skipping over is that the entire disk will get equal average response times, but at the same time the delay of skipping over without reading causes some loss of utilization. This algorithm prevents starvation while also gaining some of the benifit of shortest seek time first.
• Anticipatory Scheduling - Anticipatory scheduling takes advantage of the fact that there is a high likelyhood of subsequent reads being in a certain location. By guessing the location of later reads we can attempt to speed up the next read by prepositioning the read head. The advantages of this are minimizing access by anticipating certain reads and possibly combining them and also accelerating those reads by prepositioning the read head. This means the disk can take advantage of the benefits of dallying. The drawback to this however is that if we guess wrong the seek may be much slower and unneccesary work will have been done.

Cloud Computing

Introduction

In cloud computing large amounts of high power computing technology can be packed into a certain remote area that can be accessed over the internet. In this manner the computer technology can be placed in a location where power is cheap and the cost of running these systems is very inexpensive. With fast internet connections now users don't actually have to own fast systems, they can just rent these systems from these technology headquarters. This has many advantages as opposed to simply buying your own computing systems. There are large shared resources with much less down time. In this system the economy can scale very well. The customers don't have to make a large time commitment, they can rent the systems for varying amounts of time and can grow as needed instantly.

Problems with Cloud Computing

• Payment - We must have some method of measuring how much usage the user has done that is very accurate and can charge the user accurately. The measurement of how much the user has used must be done in a way that both the user and the supplier trust. If there is any chance that either person can tamper with the results then it would create a problem since it is hard to know how much you actually owe or how much is actually owed.
• Resource Management - If there is a sudden increase in demand of the systems then we must figure out how to allocate the resources. If people expect to be able to use the systems for work they may be very disappointed if they are paying for this service and they are denied access to the resources. Therefore we must have a very good method of resource management or there could be problems.
• Security - There must be a strong security system because if data confidentiality is corrupted then people will not want to put their data on your servers. The other question is who should put their data on cloud computers. When systems are on the internet, there is allways the possibility of data being accessed by unwanted users. With intelectual property becoming increasingly valuable then you must really trust the cloud computing system's security. If you data is comprimised, then the value of everything is lost. All connections to the cloud and data stored on the cloud should be encrypted. Still the biggest concern is people fear of the security of cloud computing.
• Data Transfer Bottlenecks - The usage of these systems can be limited by the transfer of data from where the systems are stored to where the user is. If the transfer rate is limited then the user may not be able to take advantage of the power of the systems.