Long description

The first figure (a) shows a vertical block labeled Per CPU run queue in the Linux O(1) scheduler which is divided into six parts. The first part is labeled Flags, CPU, Static_prio, and <>. The second part is labeled Active. The third part is labeled Expired. The fourth part is labeled <..>. The fifth part is labeled Priority 0, Array[0], and Priority 139. The sixth part is labeled Priority 0, Array[1], and Priority 139. An arrow is pointing from the second layer to the sixth layer. Another arrow is pointing from the third layer to the fifth layer. Figure (b) shows a tree labeled Per CPU red-black tree in the CFS scheduler. The tree diagram starts with the number 35. This block is connected to two blocks labeled 26 and 47. 26 is connected to two blocks labeled 10 and 30 and 47 is connected to two blocks labeled 38 and 62. 10 is connected to two blocks labeled 3 and NIL and 30 is connected to two blocks labeled 27 and NIL 38 is connected to two blocks 45 and NIL and 62 is connected to two blocks labeled 86 and NIL. 3 is connected to two blocks labeled NIL and NIL and 27 is connected to two blocks labeled NIL and NIL. 45 is connected to two blocks labeled NIL and NIL. 86 is connected to two blocks labeled NIL and NIL.