Jason Lee Lecture Notes from Wednesday, January 26 It is thought that the goal of a scheduler is to be fair for all the incoming jobs, but really this is not the goal. This is because fairness is not objective. It is a psychological constant and could mean any number of things -"First come, first serve", for example, is fair, but not an ideali scheduling algorithm The real goal of a scheduler is to keep the maximum amount of users happy while minimizing complaints and keeping satisfaction high. -Typically we try to get "minimum flow time" -This means, we want to reduce the time from submission of job to completion of job to as low as possible -"service time" is the amount of time that the job itself requires to get done -We alsoe want to minimize the variance of flow time divided by service time (flow of i'th job/service of i'th job, or f(i)/s(i)) Many constraints occur against a scheduling algorithm -Fixed priorities: these are determined administratively or by purchase -Fixed fraction of machine: perhaps you are only given 25% of the computer's processing power to work with -Realtime, not CPU clock: these are constraints that have to do with real-life time, not processing time (ie, an incoming missile) It is easy to analyze some simple cases in scheduling algorithms, but a real computer system is a complex thing. Many different outside factors can affect the system. Open and Closed systems: -some terms: -Lambda: arrival rate -Mu: service rate -Ro: offered load, lambda/mu -Throughput: number of jobs completed per second -Open Systems are systems in which the arrival rate of customers is unaffected by the amount of customers already in the queue -No matter what scheduling algorithm is used, as long as ro < 1, every job will evetually finish in an open system -The throughput of an open system is the arrival rate. -If ro > 1, more work is arriving than the system can handle. However, everything will still ultimately get through. -Closed Systems are systems in which arrival rate of customers IS affected by the number of customers in the queue -The total number of customers is constant, so the more that are in the system waiting to be processed, the fewer that can be arriving. -A bad scheduling algorithm will affect throughput severely -An analogy: The DMV is like an open system, as people wait in line and eventually all are serviced. -Another analogy: Waiting for a commaned on a computer to return before inputting another command is an example of a closed system. Open system: (Mu) (lambda)-------> System ----------------> -arrival rate is invariant Closed System: -----world <--------- | | | | | | | | ------>system-------- Characteristics of Users: -Users are willing to wait for about as long as they expect the command to take -If users believe that a process will take a long time, their willingness to wait for the process to finish is relatively long. The opposite is also true. -Users like predictability. -A user at a terminal can become impatient. The scheduling problem is to decide which ready process actually gets to run. We attempt to solve this through scheduling algorithms The simplests scheduling algorithm is FIFO: first in, first out -alternatively known as FCFS: first come, first serve -In the simplest case, this means uniprogramming -Finished means "blocked", one process uses CPU while another waits on a semaphore. -When the process if ready, it goes to the back of the run queue -Pros: the process is "fair", it is simple, there is low overhead, no task switching, and it has the lowest variance of overall waiting time -Cons: one process might hog all the CPU (monopolize CPU), short jobsend up waiting for long jobs ahead of them to finish before being run -Also, minimal resource sharing: if we gave priority ot jobs that needed other resources, they'd finish with the CPU quickly and do something else -This algorithm provides high variance of f(i)/s(i), but low variance of f(i) Characteristics of Jobs -Jobs are usually highly skewed -There are lots of short jobs and few long jobs. -r(t): run time distribution -The expected time for a job to finish is an increasing function of the time it has already run -The longer a job takes to finish, the longer we expect that it will take to finish -Jobs that run for an hour are usually long jobs, so it will probably take longer to finish than a job that's only been running for a minute -Example: if your roommate is supposed to buy milk, after 5 days of not buying milk, we expect it to be a while before he actually buys milk -Example: if your landlord goes 2 weeks without fixing something he said he would, we expect it to be even longer before he actually does it -The expected time to next I/O is an increasing function of time since last I/O -The expected time to a page fault is an increasing function of time since the last page faulr -The expected time to a trap is an increasing function of time since the last trap -etc. | | | | | \ | \ Problem | \ | \ | \ | \ | \ | \ | ------------ ----------------------------- run time (r(t)) | | | | | | | | | | expected | | time | / until | / completion | / | _/ | _/ | _/ |------ / | ------------------------------ time so far One of the problems with FIFO is that long processes can monopolize the CPU. WE can fix this by limiting the amont of time a proces can run without a context switch. We call this scheduling algorithm, a "round robin" -time slice: amount of time that a process is allowed to run before switching to another process -Each process gets run for the amount of time in the slice, then is moved to the bakc of the queue. -Each process gets an equal share of CPU -Most existing systems use some version of round robin. -Pros: allows short jobs to get through fairly quickly, it is "fair", it has low variance of f(i)/s(i), no starvation, and is relatively simple -Cons: the overhead is high, and if job service times are not skewed, the round robin doesn't work so well. - Also, if time slice isn't chosen carefully, a process could still monopolize CPU (time slice too long) or time can be wasted on process switches (time slice too small) -Example: If ten processes require 100 time slices, they wouldn't begin to finish until after 1000 time slices. This is far too slow. -The original UNIX has one second time slices, modern systems have less than .5 seconds of time slice -Round robin works well for heavily skewed run times The goal of a good scheduling algorithm is to minimize flow time of processes, or minimize the amount of users in the system at any given time -Little's Formula: N = lambda * F -N: mean number of users in the system -F: mean flow time -lambda: arrival rate of users -1/lambda: mean time between arrivals -Little's Formula assumes that ro < 1; that the system is not overloaded -Alternatively, L = lambda * W -W: waiting time (flow time - service time) -L: customers in the queue A good scheduling algorithm lets the little guys go first. Shortest Job First: runts the job which has the shortest processing time first. -In Little's Formula, Shortest Job First will reduce N -Pros: minimum average flow time if no preemption, no knowledge of future arrivals -Cons: requires knowledge of future (how long a job will take to process), long jobs will have to wait -If a short job arrives while a long job is running, we have to wait for the longer job to finish before we acknolwedge the shorter job -Also, we can do better if we use preemption Shortest Remaining Processing Time: this is similar to Shortest Job First, except we also use preemption (interruption when something occurs) -If a shorter job arrivs, we interrupt whatever job is running in favor of the shorter job. -Pros: minimizes average flow time -Cons: requires knowledge of the future, there will be overhead due to preemption, which could get out of hand, high variance of flow time -However, you will never have more preemptions than jobs Shortest Elapsed Time: Run the job that has been running the shortest amount of time so far (shortest running processes are expected to end sooner) -For processes that have run for an equally long time, we run one process for a time slice before switching to the other one. -Pros: short jobs get out fast, variance of f(i)/s(i) is reasonably low -Cons: high overhead, must limit how often you switch -Also, if run times aren't skewed, this is a terrible algorithm. If all jobs have the same elapsed/run time, they all wait for each other. -Essentially, it has similar problems to round robin. At this point in the lecture, the professor had to leave about ten minutes later. Representatives from ResComp came to talk about positions that were open and handed out flyers for those who were interested.