The runtime of each task is known.<\/li>\n<\/ol>\nScheduler Metrics<\/h3>\n \n In addition to some assumptions about the load, we also need a tool to compare different scheduling policies: scheduler metrics. A metric is simply a measure of something. There are several metrics that can be used to compare schedulers.<\/p>\n
For example, we will use a metric called turnaround time<\/b> Turnaround time for a task is defined as the difference between the completion time of the task and the time the task arrived in the system.<\/p>\n
Tturnaround=Tcompletion\u2212Tarrival<\/u><\/p>\n
Since we assumed that all tasks arrived at the same time, then Ta=0 and thus Tt=Tc. This value will naturally change when we alter the assumptions mentioned above.<\/p>\n
Another metric is fairness. Performance and fairness are often opposing characteristics in scheduling. For example, a scheduler may optimize for performance at the cost of delaying other tasks, thereby reducing fairness.<\/b> FIRST IN FIRST OUT (FIFO)<\/p>\nThe simplest algorithm we can implement is called FIFO or<\/h3>\n
\n The most basic algorithm we can implement is called FIFO or first come (in), first served (out)<\/b>. This algorithm has several advantages: it is very simple to implement and fits all our assumptions, performing the task quite well.<\/p>\n
Let's consider a simple example. Suppose 3 tasks were set simultaneously. But let's assume task A arrived slightly earlier than the others, so it will be listed before the others, just as task B will be in relation to task C. Let's assume each of them will take 10 seconds to complete. What would be the average completion time of these tasks in this case?<\/p>\n
As it turns out, different execution times for tasks have a very negative impact on the productivity of the FIFO algorithm. Suppose task A takes 100 seconds, while tasks B and C still take 10 seconds each.<\/p>\n
the convoy effect<\/b>, where some short-term consumers of a resource will line up behind a heavy user. It's like waiting in line at a grocery store when there\u2019s a customer in front of you with a full cart. The best solution to the problem is to try to switch lines or just relax and take deep breaths.<\/p>\nShortest Job First<\/h3>\n
\n Is there a way to resolve such a situation with heavyweight processes? Of course. Another type of scheduling is calledShortest Job First<\/b> (SJF). Its algorithm is also quite primitive \u2014 as the name suggests, the shortest tasks will be executed first, one after another.<\/p>\n
50 instead of 110<\/b>, which is almost 2 times better.<\/p>\n
Thus, under the given assumption that all tasks arrive at the same time, the SJF algorithm seems to be the most optimal one. However, our assumptions still do not appear realistic. This time, let's modify assumption 2 and assume that tasks can arrive at any time, rather than all at once. What problems could this lead to?<\/p>\n
Shortest Time-to-Completion First (STCF)<\/h3>\n \n To improve the situation, let's drop assumption 3 that the program runs and works until completion. In addition, we will need hardware support and, as you might guess, we will use a timer<\/b> to interrupt the running task and context switching<\/b>. This way, the scheduler can take action at the moment tasks B and C arrive\u2014stop executing task A, process tasks B and C, and after they finish, continue executing process A. Such a scheduler is called STCF<\/b>or Preemptive Job First<\/b>.<\/p>\n
Response Time Metric<\/h3>\n \n Thus, if we know the execution times of the tasks and that these tasks only use the CPU, STCF will be the best solution. And at one time, these algorithms worked quite well. However, now users spend most of their time at the terminal and expect productive interactive responses from it. Thus, a new metric was born\u2014 response time<\/b> .<\/p>\n
Response time is calculated as follows:<\/p>\n
Tresponse=Tfirstrun\u2212Tarrival<\/u><\/p>\n
Thus, for the previous example, the response times will be: A=0, B=0, C=10 (abg=3.33).<\/p>\n
It turns out that the STCF algorithm is not very effective in situations where three tasks arrive simultaneously \u2014 it has to wait until the smaller tasks have fully completed. Thus, the algorithm is good for turnaround time metrics, but poor for interactivity metrics. Imagine sitting at a terminal trying to type characters in an editor and having to wait more than 10 seconds because another task is occupying the CPU. That's not very pleasant.<\/p>\n
Round Robin<\/h3>\n \n To solve this problem, an algorithm was developed Round Robin<\/b> (RR). The main idea is quite simple: instead of running tasks to completion, we will run a task for a certain amount of time (called a time quantum) and then switch to another task in the queue. The algorithm continues to work until all tasks are completed. Additionally, the runtime should be a multiple of the time after which the timer interrupts the process. For example, if the timer interrupts the process every x = 10ms, then the execution window size must be a multiple of 10 and can be 10, 20, or x*10.<\/p>\n
Consider an example: Tasks A, B, and C arrive simultaneously in the system, and each wants to run for 5 seconds. The SJF algorithm would execute each task to completion before starting another. In contrast, the RR algorithm with a time slot of 1s would progress through the tasks as follows (see Fig. 4.3):<\/p>\n
The average response time for the RR algorithm is (0+1+2)\/3=1, whereas for SJF it is (0+5+10)\/3=5.<\/p>\n
It is logical to assume that the time slice is a very important parameter for RR; the shorter it is, the higher the response time. However, it should not be too small, as the context-switching time also plays a role in overall performance. Thus, the choice of execution time slice is set by the OS architect and depends on the tasks that are planned to be executed in it. Context switching is not the only overhead that consumes time \u2014 a running program also operates on various caches, and with each switch, it is necessary to save and restore this environment, which can also take a considerable amount of time.<\/p>\n
RR is an excellent scheduler if we're only talking about response time metrics. But how will the turnaround time metric behave with this algorithm? Let's consider the example above, where tasks A, B, and C each run for 5 seconds and arrive at the same time. Task A will finish at 13 seconds, B at 14 seconds, and C at 15 seconds, resulting in an average turnaround time of 14 seconds. Therefore, RR is the worst-performing algorithm for turnaround time metrics.<\/p>\n
In general terms, any RR-type algorithm is fair; it divides CPU time equally among all processes. Thus, these metrics constantly conflict with each other.<\/p>\n
Consequently, we have several opposing algorithms and still several assumptions remain \u2014 that the task time is known and that the task only uses the CPU.<\/p>\n
Mixing with I\/O<\/h3>\n \n First, let\u2019s remove assumption 4, which states that the process only uses the CPU; this is naturally not the case, as processes can also interact with other hardware.<\/p>\n
At the moment when a process requests an I\/O operation, it transitions to a blocked state, waiting for the completion of the I\/O. If the I\/O is sent to a hard disk, such an operation may take several milliseconds or longer, and during this time, the CPU will be idle. The scheduler can then assign the CPU to any other process. The next decision the scheduler must make is when the process will finish its I\/O. When this happens, an interrupt will occur, and the OS will transition the I\/O-requesting process to a ready state.<\/p>\n
Let's consider an example with several tasks. Each of them requires 50ms of CPU time. However, the first task will access I\/O every 10ms (which will also be executed in 10ms). Meanwhile, process B simply uses 50ms of CPU time without any I\/O.<\/p>\n
The oracle is gone.<\/h3>\n \n Now let's try to eliminate the assumption that the execution time of a task is known. This is overall the worst and most unrealistic assumption on the list. In fact, in average operating systems, the OS usually knows very little about task execution times, so how can one build a scheduler without knowing how long a task will run? Perhaps we could use some principles of RR to address this issue?<\/p>\n
Summary<\/h3>\n \n We have looked at the basic ideas of task scheduling and examined two families of schedulers. The first runs the shortest task first, thereby improving turnaround time, while the second evenly splits time among all tasks, improving response time. Both algorithms perform poorly in situations where the algorithms from the other family excel. We also considered how parallel use of CPU and I\/O can enhance performance, but we still did not solve the problem of OS foresight. In the next session, we will explore a scheduler that looks into the near past and tries to predict the future, called the multi-level feedback queue.habr.com<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"\u0412\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0435 \u0441\u0438\u0441\u0442\u0435\u043c\u044b \u041f\u0440\u0438\u0432\u0435\u0442, \u0425\u0430\u0431\u0440! \u0425\u043e\u0447\u0443 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0432\u0430\u0448\u0435\u043c\u0443 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u044e \u0441\u0435\u0440\u0438\u044e \u0441\u0442\u0430\u0442\u0435\u0439-\u043f\u0435\u0440\u0435\u0432\u043e\u0434\u043e\u0432 \u043e\u0434\u043d\u043e\u0439 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u0439 \u043d\u0430 \u043c\u043e\u0439 \u0432\u0437\u0433\u043b\u044f\u0434 \u043b\u0438\u0442\u0435\u0440\u0430\u0442\u0443\u0440\u044b \u2014 OSTEP. \u0412 \u044d\u0442\u043e\u043c \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u0435 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0433\u043b\u0443\u0431\u043e\u043a\u043e \u0440\u0430\u0431\u043e\u0442\u0430 unix-\u043f\u043e\u0434\u043e\u0431\u043d\u044b\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0445 \u0441\u0438\u0441\u0442\u0435\u043c, \u0430 \u0438\u043c\u0435\u043d\u043d\u043e \u2014 \u0440\u0430\u0431\u043e\u0442\u0430 \u0441 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0430\u043c\u0438, \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u043c\u0438 \u043f\u043b\u0430\u043d\u0438\u0440\u043e\u0432\u0449\u0438\u043a\u0430\u043c\u0438, \u043f\u0430\u043c\u044f\u0442\u044c\u044e \u0438 \u043f\u0440\u043e\u0447\u0438\u0438\u043c\u0438 \u043f\u043e\u0434\u043e\u0431\u043d\u044b\u043c\u0438 \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442\u0430\u043c\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0442 \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u0443\u044e \u041e\u0421. \u041e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0432\u0441\u0435\u0445 \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u043e\u0432 \u0432\u044b \u043c\u043e\u0436\u0435\u0442\u0435 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u0432\u043e\u0442 \u0442\u0443\u0442. […]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":23990,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[688],"tags":[],"class_list":["post-32158","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-administrirovanie"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t