Changes between Version 5 and Version 6 of scheduler


Ignore:
Timestamp:
Aug 29, 2017, 3:14:08 PM (7 years ago)
Author:
alain
Comment:

--

Legend:

Unmodified
Added
Removed
Modified

  • scheduler

    v5 v6  
    11In this section, we describe the scheduling mechanisms used by ALMOS-MKH.
    22
    3 == A. Threads List ==
     3== A. General principles ==
    44
    5 There are two lists of threads in ALMOS-MKH: a list of ''user'' threads and a list of ''kernel''
    6 threads.
     5There is one private scheduler per core, and ALMOS-MKH does not support thread migration: threads are assigned to a given core at thread creation, and will never be executed by another core, until thread destruction.
     6ALMOS-MKH implement a preemptive policy for time sharing between all threads assigned to given core. The <cpu_context> and <fpu_context> fields in the thread descriptor define the storage required to save (or initialize) the core registers values when the thread is not running. A fixed number of TICK periods is allocated to a running thread. The value of the TICK period (in milli-second) is defined by the CONFIG_SCHED_TICK_MS_PERIOD parameter. The number of TICKS  is defined by the CONFIG_SCHED_TICK_MS_PERIOD configuration parameter.
     7Finally, the max number of threads assigned to a given core is defined by the CONFIG_SCHED_MAX_THREADS_NR configuration parameter.
    78
    8 == B. Context Switches ==
     9== B) Thread states ==
    910
    10 ALMOS-MKH supports switching context among threads only when they do not hold any kernel locks.
     11ALMOS-MKH defines two types of threads:
     12 * USER threads are POSIX compliant threads, defined in a given user process. A main thread is always created for an user process. Other threads are created by the pthread_create() syscall.
     13 * KERNEL threads implement kernels services, such as RPC threads executing the Remote Procedure Calls, the DEV threads implementing IO channels operations, or the IDLE thread that is a default (low-power) thread.
    1114
    12 Context switches have two causes:
    13  * The currently-executing thread explicitly asks to be rescheduled. When such a thing happens,
    14    it is guaranteed that the current thread does not hold any kernel locks.
    15  * A rescheduling interrupt (such as a tick) was received and it is decided that another thread
    16    needs to execute. The mechanism to ensure that the currently-executing thread does not hold
    17    any kernel locks is more complex, and described below.
     15From the scheduler point of view, any thread (KERNEL or USER) can be in three states:
     16 * RUNNING : the thread is running on the core. The scheduler <current> field contains a pointer on the running thread.
     17 * READY : the thread is ready to execute, but is not currently running.
     18 * BLOCKED : The thread is blocked on a given condition, and cannot be selected for execution.
    1819
    19 When a rescheduling interrupt is received, the interrupt routine that is called gives a look
    20 at the currently-executing thread. If this thread does not hold any kernel locks, the rescheduling
    21 is performed right away. Otherwise, the interrupt routine adds a flag in the thread's structure,
    22 to indicate that a rescheduling is necessary. The interrupt routine then returns to the original
    23 context.
     20The thread state is implemented as the <blocked> bit-vector field in the thread descriptor.
     21A thread generally enter in the BLOCKED state, when a given resource is not available, by calling the thread_block() function that set the relevant bit in the <blocked> bit-vector. It returns to the READY state when another thread releases the blocking resource, and call the thread_unblock() function, that reset the relevant bit. The thread_unblock() function can be called by any thread running in any cluster.
    2422
    25 The thread keeps executing, and at some point, will release its last lock. When this last release
    26 is performed, the thread will give a look at the rescheduling flag in its structure. If this flag
    27 is set, the thread performs the rescheduling itself: this behavior is the same as if it was the
    28 thread that had asked to be rescheduled in the first place. In this scenario, it is therefore
    29 guaranteed that no kernel locks are held.
     23This simple blocking / unblocking mechanism is well suited to the Multi-Kernel-Hybrid architecture, as it is uses simple remote_write accesses.
    3024
    31 == C. Kernel Mode Preemption ==
     25== C) Scheduling policy ==
    3226
    33 ALMOS-MKH supports descheduling a userland thread that is currently in kernel mode - as a result
    34 of a syscall for example.
     27Each scheduler maintains two separate, circular, lists of threads: one list of KERNEL threads, and one list of USER threads. A KERNEL threads have a higher priority than the USER threads, and each list is handled with a round-robin priority. When the sched_yield() function is called to perform a context switch for a given core, it implement the following policy:
     28 1. It scan the KERNEL list to find a READY thread. It executes this KERNEL thread if found.
     29 1. If no KERNEL thread is found, it scan the USER list to fin a READY thread. It executes this USER thread if found.
     30 1. If there is no KERNEL thread and no USER thread (other than the calling thread), the calling thread continues execution. if possible.
     31 1. If there is no READY thread, it executes the IDLE thread.
     32
     33The kernel has the possibility to force the selection of a given thread, identified by the sched_yield() function argument. This is used to reduce the latency of the RPCs.
     34
     35== D. Delayed Context Switches ==
     36
     37Context switches can have two causes:
     38The RUNNING thread can explicitly ask to be descheduled. When such a thing happens, it is guaranteed that the current thread does not hold any kernel locks.
     39But the scheduling policy being preemptive,  the RUNNING thread can hold one (or several) kernel lock(s) when receiving a TICK interrupt.
     40
     41In this situation, ALMOS-MKH implements the following delayed context switch mechanism:
     42 1. The RUNNING thread holding locks continues execution, but the THREAD_FLAG_SCHED is set in the running thread descriptor.
     43 2. All kernel functions used to release kernel locks check this THREAD_FLAG_SCHED. When this flag is set, and the last lock is released by the calling thread, the sched_yield() is immediately executed.
     44
     45More generally, ALMOS-MKH supports descheduling of an USER thread that is currently in kernel mode - as a result of a syscall. In other words, sys calls can be interrupted by interrupts signaling the completion of an I/O operations, or by the TICK interrupt, requiring a context switch.
     46
     47== E) Floating Point Unit ==
     48
     49To be Documented.