cpuanddiskschedulingalgorithms-文庫吧資料
2024-10-07 21:50本頁面
【正文】 ed. It runs on the idea of giving the task with the “gravest need” to the CPU ? This method uses what is called a red black tree instead of queues. The Red Black Tree This is a type of Binary Search Tree. With a few differences. ? First, a node is either black or red. ? Second, the root is black. ?Third, all leaves are black ?Fourth, both children of every node are black ?Fifth, Every simple path from a given node to any of its descendant leaves contains the same number of black nodes. So what does this all mean? ? No path can have two red nodes in a row. ? The shortest possible path has all black nodes, and the longest possible path alternates between red and black nodes. ? Since all maximal paths have the same number of black nodes, this shows that no path is more than twice as long as any other path. ? This means that even in the worst case scenario it can still be considered efficient. More on how it works ? The old method used heuristics. ? This new method ignores sleep time and time slices, so instead what it does is: ? As a process waits for the CPU, the scheduler tracks the amount of time it would have used on the processor. ? This time is calculated by dividing the wait time (in nanoseconds) by the total number of processes waiting. ? The resulting value is the amount of CPU time the process is entitled to, and is used to rank processes for scheduling and to determine the amount of time the process is allowed to execute before being preempted. CFS and Red Black Tree ? A tasks wait_runtime value gets incremented by an amount depending on the number of proce
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1