Re: 2.6 Scheduler of O(1)

From: Nix (nix-razor-pit_at_esperi.org.uk)
Date: 02/09/05

  • Next message: Tauno Voipio: "Re: Linux Device drivers" 
    Date: Wed, 09 Feb 2005 15:57:04 +0000

    On 9 Feb 2005, Milind Dumbare uttered the following:
    > fabiano.ramos@gmail.com (Fabiano) wrote in message news:<5afb2c65.0502081517.60b96d12@posting.google.com>...
    >> - each runqueue has 2 priority arrays, the active and the expired.
    >> The active array stores the processes that still have some time slice.
    >> Once this time finished, they go to the expired array.
    >> Each array has 140 entries (queues), one for each privilege level.
    >are they sorted if yes who sort them ( it can (must )not be scheduler()
    >because it would cause one more overhead

    Each entry in the array corresponds directly to a single priority, and
    the task's priority is already known. Within the task, tasks are
    added to the end of the list and removed from the beginning.

    There is a bitmap showing which arrays have anything in them at all:
    most CPUs (notably the Intel ones) have CPU instructions to search
    bitmaps for first-set-bit very fast, and it's bounded in any case
    as the number of priority levels is fixed. All O(1).

    >>> So, picking a process to run is as simple as picking the first
    >> process of the first non-empty queue. As the number of queue
    >> is fixed (140) and independent of the number of processes running,
    >> the scheduler is O(1).
    > if its that much easy then what was the problem to not to implemented in earlier
    > versions

    Er, because nobody thought of it? It's one of those designs that's only
    obvious in hindsight; it's like an ordinary scheduler's data structures
    turned inside out. :)

    >> Why don't you try Love's Linux Kernel Development?
    > please give me some URL or should I search on gooooooogle for above line

    It's a book.

    Ingo's original post is pretty informative, and the scheduler still
    works in pretty much the same way it did back then:
    <http://www.uwsg.iu.edu/hypermail/linux/kernel/0201.0/0810.html>. 

    -- 
Synapsids unite! You have nothing to lose but your eggshells!
  • Next message: Tauno Voipio: "Re: Linux Device drivers"

    Relevant Pages

    • [PATCH] V-3.0 Single Priority Array O(1) CPU Scheduler Evaluation
      ... Version 3 of the various single priority array scheduler patches for ... single array and an Opromotion mechanism plus scheduling statistics: ... Priority based Oscheduler with active/expired arrays replaced by ...
      (Linux-Kernel)
    • [PATCH] V-5.0 Single Priority Array O(1) CPU Scheduler Evaluation
      ... Version 5.0 of the various single priority array scheduler patches for ... This version adds NEW FEATURES to ZAPHOD and HYDRA schedulers. ... My proposed replacement scheduler which offers runtime ... selectable choice between a priority based or entitlement based O ...
      (Linux-Kernel)
    • [PATCH] V-4.1 Single Priority Array O(1) CPU Scheduler Evaluation
      ... Version 4.1 of the various single priority array scheduler patches for ... update of the staircase scheduler code to match Con's 7.I version. ... selectable choice between a priority based or entitlement based O ... interactive bonus mechanism and throughput bonus mechanism: ...
      (Linux-Kernel)
    • Re: [ANNOUNCE][RFC] PlugSched-6.3.1 for 2.6.16-rc5
      ... But anyway, based on the evidence, I think the problem is caused by the fact that the eatm tasks are running to completion in less than one time slice without sleeping and this means that they never have their priorities reassessed. ... The reason that it does this is that it gives newly forked processes a fairly high priority and if they're left to run for a full 120 msecs at that high priority they can hose the system. ... Having a shorter first time slice gives the scheduler a chance to reassess the task's priority before it does much damage. ...
      (Linux-Kernel)
    • Re: [ANNOUNCE][RFC] PlugSched-6.3.1 for 2.6.16-rc5
      ... problem is that it uses a smaller time slice for the first time slice ... full 120 msecs at that high priority they can hose the system. ... shorter first time slice gives the scheduler a chance to reassess the ... This is supposed to represent the task with the highest CPU usage rate per share and is used to determine how fairly CPU is being distributed among the currently active tasks. ...
      (Linux-Kernel)