| 5 | | == A) Locks general principles == |
| 6 | | |
| 7 | | Most kernel data structures are shared: they can be concurrently accessed by several threads. These threads can be specialized kernel threads , such as the DEV threads or the RPC threads, or can be user threads, running in kernel mode after a syscall. |
| 8 | | |
| 9 | | There exist actually two levels of sharing: |
| 10 | | * some structures are locally shared: they can only be accessed by threads running in the cluster containing the shared structure. Examples are (i) the Schedulers (associated to the cores in a given cluster), or the Physical Pages Manager (PPM) allocator in a given cluster, or the Virtual Memory Manager (associated to a given process descriptor in a given cluster. |
| 11 | | * some structures are globally shared: they can be concurrently by any thread running in any cluster. Examples are the waiting queues associated to the Chdevs (channel devices, distributed on all clusters, or the kernel distributed Virtual File System, that is also distributed on all clusters. |
| 12 | | |
| 13 | | ALMOS-MKH defines three types of locks to implement exclusive access to these shared structures: ''busylocks'', ''queuelocks'', and ''rwlocks''. |
| 14 | | |
| 15 | | == B) busylocks & remote_busylocks == |
| 16 | | |
| 17 | | The '''busylock''' (local) and '''remote_busylock''' (global) are low-level locks implementing a busy-waiting policy for the calling threads. If the lock is already taken by another thread, the calling thread keep polling the lock until success. They are used to protect higher level synchronisation primitives (such as the ''queuelocks'' or ''rwlocks'' described below) , or ''simple'' data-structure where the locking time is small and can be bounded. |
| 18 | | |
| 19 | | A thread holding a busy lock cannot deschedule. To enforce this rule, the ''busylock_acquire()'' function enters a critical section before taking the lock, and saves the SR value in the busy lock descriptor. The thread holding the busy lock exit the critical section when it calls the ''busylock_release()'' function that releases the lock and restores the SR state. Each time a thread acquire a busylock, it increments a busylocks counter in the thread descriptor, and decrements it when it releases the lock. |
| 20 | | The scheduler makes a kernel panic if the current thread busylocks counter is not nul when it executes the ''sched_yield()'' function. |
| 21 | | |
| 22 | | To improve fairness, the ''busylock_acquire()'' function uses a ticket policy: the calling thread makes an atomic increment on a ''ticket'' allocator in lock descriptor, and keep polling the ''current'' value until ''current'' == ''ticket''. To release the lock, the ''busylock_release()'' function increments the "current" value in lock descriptor. |
| 23 | | |
| 24 | | == C) queuelock & remote_queuelock == |
| 25 | | |
| 26 | | The '''queuelock''' (local) and '''remote_queuelock''' (global) are higher level locks implementing a descheduling policy, with registration in a waiting queue. If the lock is already taken by another thread, the calling thread register in a (local or trans-cluster) waiting queue rooted in the queuelock, and deschedules. The first thread T registered in the waiting thread is re-activated by the thread T' holding the lock when T' release the lock. It is used to protect complex structures, where the access can require to get exclusive access to one (or more) other shared resources. |
| 27 | | |
| 28 | | The queue lock descriptor itself contains a busylock, that is used by the ''queuelock_acquire()'' and ''queue lock_release()'' functions to protect exclusive access to the |
| 29 | | queue lock state. |
| 30 | | |
| 31 | | A thread holding a queuelock can deschedule, and no special checking is done by the scheduler. |
| 32 | | |
| 33 | | == D) rwlocks & remote_rwlocks == |
| 34 | | |
| 35 | | The '''rwlock''' (local) and '''remote_rwlock''' (global) support several simultaneous read accesses, but only one write access to a given shared object. |
| 36 | | As for queue locks, both readers and writers take the associated busylock before accessing or updating the rwlock state, and releases the busylock after |
| 37 | | rwlock state update. |
| 38 | | * when a reader try to access the object, it increments the readers "count" when the lock is not "taken" by a writer. It registers in the "rd_root" waiting queue, blocks, and deschedules when the lock is taken. |
| 39 | | * when a writer try to take the rwlock, it check the "taken" field. If the lock is already taken, or if the number of readers is non zero, it registers in the "wr_root" waiting queue, blocks, and deschedules. It set "taken" otherwise. |
| 40 | | * when a reader completes its access, it decrement the readers "count", unblock the first waiting writer if there is no other readers, and unblock all waiting readers if there is no write request. |
| 41 | | * when a writer completes its access, it reset the "taken" field, releases the first waiting writer if queue non empty, or releases all waiting readers if no writer. |
| 42 | | |
| 43 | | == E) Locks debug infra-structure == |
| 44 | | |
| 45 | | When the DEBUG_BUSYLOCK parameter is set in the kernel_config.h file, an optional debug mechanism is activated, thanks to conditional compilation. |
| 46 | | |
| 47 | | Each thread contains - besides the ''busylocks'' counter - an optional ''busylocks_root'' field, that is the root of the embedded xlist of (local or remote) busylocks hold by a given thread at a given time. This list is implemented by an optional ''xlist'' field in the busy lock descriptor. It is dynamically updated by the ''busylock_acquire()'' and ''busylock_release()'' functions. The set of taken busylocks is printed in the error message, when the scheduler detects that a descheduling thread is holding one or several busylocks. This list can also be be printed through the ''idbg" interactive debugger, for any thread identified by its (pid,trdid). |
| 48 | | |
| 49 | | == F) Synchronisation barriers == |
| | 5 | == A) Synchronisation barriers == |
| | 16 | == B) Locks general principles == |
| | 17 | |
| | 18 | Most kernel data structures are shared: they can be concurrently accessed by several threads. These threads can be specialized kernel threads , such as the DEV threads or the RPC threads, or can be user threads, running in kernel mode after a syscall. |
| | 19 | |
| | 20 | There exist actually two levels of sharing: |
| | 21 | * some structures are locally shared: they can only be accessed by threads running in the cluster containing the shared structure. Examples are (i) the Schedulers (associated to the cores in a given cluster), or the Physical Pages Manager (PPM) allocator in a given cluster, or the Virtual Memory Manager (associated to a given process descriptor in a given cluster. |
| | 22 | * some structures are globally shared: they can be concurrently by any thread running in any cluster. Examples are the waiting queues associated to the Chdevs (channel devices, distributed on all clusters, or the kernel distributed Virtual File System, that is also distributed on all clusters. |
| | 23 | |
| | 24 | ALMOS-MKH defines three types of locks to implement exclusive access to these shared structures: ''busylocks'', ''queuelocks'', and ''rwlocks''. |
| | 25 | |
| | 26 | == C) busylocks & remote_busylocks == |
| | 27 | |
| | 28 | The '''busylock''' (local) and '''remote_busylock''' (global) are low-level locks implementing a busy-waiting policy for the calling threads. If the lock is already taken by another thread, the calling thread keep polling the lock until success. They are used to protect higher level synchronisation primitives (such as the ''queuelocks'' or ''rwlocks'' described below) , or ''simple'' data-structure where the locking time is small and can be bounded. |
| | 29 | |
| | 30 | A thread holding a busy lock cannot deschedule. To enforce this rule, the ''busylock_acquire()'' function enters a critical section before taking the lock, and saves the SR value in the busy lock descriptor. The thread holding the busy lock exit the critical section when it calls the ''busylock_release()'' function that releases the lock and restores the SR state. Each time a thread acquire a busylock, it increments a busylocks counter in the thread descriptor, and decrements it when it releases the lock. |
| | 31 | The scheduler makes a kernel panic if the current thread busylocks counter is not nul when it executes the ''sched_yield()'' function. |
| | 32 | |
| | 33 | To improve fairness, the ''busylock_acquire()'' function uses a ticket policy: the calling thread makes an atomic increment on a ''ticket'' allocator in lock descriptor, and keep polling the ''current'' value until ''current'' == ''ticket''. To release the lock, the ''busylock_release()'' function increments the "current" value in lock descriptor. |
| | 34 | |
| | 35 | == D) queuelock & remote_queuelock == |
| | 36 | |
| | 37 | The '''queuelock''' (local) and '''remote_queuelock''' (global) are higher level locks implementing a descheduling policy, with registration in a waiting queue. If the lock is already taken by another thread, the calling thread register in a (local or trans-cluster) waiting queue rooted in the queuelock, and deschedules. The first thread T registered in the waiting thread is re-activated by the thread T' holding the lock when T' release the lock. It is used to protect complex structures, where the access can require to get exclusive access to one (or more) other shared resources. |
| | 38 | |
| | 39 | The queue lock descriptor itself contains a busylock, that is used by the ''queuelock_acquire()'' and ''queue lock_release()'' functions to protect exclusive access to the |
| | 40 | queue lock state. |
| | 41 | |
| | 42 | A thread holding a queuelock can deschedule, and no special checking is done by the scheduler. |
| | 43 | |
| | 44 | == E) rwlocks & remote_rwlocks == |
| | 45 | |
| | 46 | The '''rwlock''' (local) and '''remote_rwlock''' (global) support several simultaneous read accesses, but only one write access to a given shared object. |
| | 47 | As for queue locks, both readers and writers take the associated busylock before accessing or updating the rwlock state, and releases the busylock after |
| | 48 | rwlock state update. |
| | 49 | * when a reader try to access the object, it increments the readers "count" when the lock is not "taken" by a writer. It registers in the "rd_root" waiting queue, blocks, and deschedules when the lock is taken. |
| | 50 | * when a writer try to take the rwlock, it check the "taken" field. If the lock is already taken, or if the number of readers is non zero, it registers in the "wr_root" waiting queue, blocks, and deschedules. It set "taken" otherwise. |
| | 51 | * when a reader completes its access, it decrement the readers "count", unblock the first waiting writer if there is no other readers, and unblock all waiting readers if there is no write request. |
| | 52 | * when a writer completes its access, it reset the "taken" field, releases the first waiting writer if queue non empty, or releases all waiting readers if no writer. |
| | 53 | |
| | 54 | == F) Locks debug == |
| | 55 | |
| | 56 | When the DEBUG_BUSYLOCK parameter is set in the kernel_config.h file, an optional debug mechanism is activated, thanks to conditional compilation. |
| | 57 | |
| | 58 | Each thread contains - besides the ''busylocks'' counter - an optional ''busylocks_root'' field, that is the root of the embedded xlist of (local or remote) busylocks hold by a given thread at a given time. This list is implemented by an optional ''xlist'' field in the busy lock descriptor. It is dynamically updated by the ''busylock_acquire()'' and ''busylock_release()'' functions. The set of taken busylocks is printed in the error message, when the scheduler detects that a descheduling thread is holding one or several busylocks. This list can also be be printed through the ''idbg'' interactive debugger, for any thread identified by its (pid,trdid). |
| | 59 | |
| | 60 | Moreover, when the DEBUG_BUSYLOCK is set, it is possible to trace all busylocck_acquire() / busylock_release() for one single thread identified by the DEBUG_BUSYLOCK_THREAD_XP parameter. |
| | 61 | |
