Process and thread creation/destruction

The process is the internal representation of an user application. A process can be running as a single thread (called main thread), or can be multi-threaded. ALMOS-MKH supports the POSIX thread API. For a multi-threaded application, the number of threads can be very large, and the threads of a given process can be distributed on all cores available in the shared memory architecture, for maximal parallelism. Therefore, a single process can spread on all clusters. To avoid contention, the process descriptor of a P process, and the associated structures, such as the list of registered vsegs (VSL), the generic page table (GPT), or the file descriptors table (FDT) are (partially) replicated in all clusters containing at least one thread of P.

1) Process definition

The PID (Process Identifier) is coded on 32 bits. It is unique in the system, and has a fixed format: The 16 MSB (CXY) contain the owner cluster identifier. For any process, the owner cluster is the cluster where the process has been created. The 16 LSB bits (LPID) contain the local process index in the owner cluster.

Since there are several copies of the process descriptor, ALMOS-MKH defines a reference process descriptor, located in the reference cluster that contains the reference values for replicated structures such as the process VMM. The other copies are used as local caches, and ALMOS-MKH must guaranty the coherence between the reference and the copies.

Initially, the reference cluster is the owner cluster. But the reference cluster can be different from the owner cluster. The owner cluster cannot change (because the PID is fixed), but the reference cluster can change in case of process migration.

In each cluster K, the local cluster manager ( ​cluster_t type in ALMOS-MKH ) contains a process manager ( ​pmgr_t type in ALMOS-MKH ) that maintains three structures for all processes owned by K :

• The ​pref_tbl[lpid] is an array indexed by the local process index. Each entry contains an extended pointer on the reference process descriptor for each process owned by cluster K.
• The ​copies_root[lpid] array is also indexed by the local process index. Each entry contains the root of the global list of copies for each process owned by cluster K.
• The ​local_root is the local list of all process descriptors in cluster K. A process descriptor copy of P is present in K, as soon as P has a thread in cluster K.

A process can be in four termination states:

• RUNNING : the process is normally executing.
• STOPPED : the process received a SIGSTOP signal. It can return to RUNNING state by a SIGCONT signal.
• EXITED : the process terminated by an exit() syscall. It will be destroyed by the parent process executing a wait() syscall.
• KILLED : the process received a SIGKILL signal. It will be destroyed by the parent process executing a wait() sys call.

You can find below a partial list of information stored in a process descriptor ( ​process_t in ALMOS-MKH ):

• pid : proces identifier.
• parent_xp : extended pointer on the parent process.
• owner_xp : extended pointer on the owner process descriptor.
• ref_xp : extended pointer on the reference process descriptor.
• vmm.vsl : root of the local list of vsegs defining the process memory image.
• vmm.gpt : generic page table defining the mapping of the process vsegs.
• fd_array : open file descriptors table.
• th_tbl : local table of threads owned by this process in this cluster.
• local_list : member of local list of all process descriptors in same cluster.
• copies_list : member of global list of all descriptors of same process.
• children_list : member of global list of all children of same parent process.
• children_root : root of global list of children process.
• etc.

All elements of a local list are in the same cluster, so ALMOS-MKH uses local pointers. The elements of a global list can be distributed on all clusters, so ALMOS-MKH uses extended pointers.

2) Thread definition

ALMOS-MKH defines in ​thread_type_t four types of threads :

• one USR thread is created by a pthread_create() system call.
• one DEV thread is created by the kernel to execute all I/O operations for a given channel device.
• one RPC thread is activated by the kernel to execute pending RPC requests in the local RPC FIFO.
• the IDL thread is executed when there is no other thread to execute on a core.

From the point of view of scheduling, a thread can be in three states : RUNNING, RUNNABLE or BLOCKED.

In a given process, a thread is identified by a fixed format TRDID kernel identifier, coded on 32 bits : The 16 MSB bits (CXY) define the cluster K where the thread has been created. The 16 LSB bits (LTID) define the thread local index in the local ​TH_TBL[K,P] of a process descriptor P in a cluster K. This LTID index is allocated by the local process descriptor when the thread is created.

Therefore, the TH_TBL(K,P) thread table for a given process in a given cluster contains only the threads of P placed in cluster K. The set of all threads of a given process is defined by the union of all TH_TBL(K,P) for all active clusters K. To scan the set of all threads of a process P, ALMOS-MKH traverses the COPIES_LIST of all process_descriptors associated to P process.

This implementation of ALMOS-MKH does not support thread migration: a thread is pinned on a given core in a given cluster. In the future process migration mechanism, all threads of a process in a given cluster can migrate to another cluster for load balancing. This mechanism is not implemented yet (february 2018), and will require to distinguish the kernel thread identifier (TRDID, that will be modified by a migration), and the user thread identifier (THREAD, that is modified by a migration). In the current implementation, the user identifier (returned by the pthread_create() sys call) is identical to the kernel identifier.

You can find below a partial list of information stored in a thread descriptor (​thread_t in ALMOS-MKH):

• trdid : thread identifier
• type : KERNEL / USER / IDLE / RPC
• flags : bit_vector of thread attributes.
• blocked : bit_vector of blocking causes.
• process : pointer on the local process descriptor
• parent : extended pointer on the parent thread descriptor.
• sched : pointer on the scheduler in charge of this thread.
• core : pointer on the owner core descriptor.
• cpu_context : save the CPU registers when descheduled.
• fpu_context : save the FPU registers when descheduled.
• wait_xlist : member of a global list of threads waiting on the same resource.
• wait_list : member of a local list of threads waiting on the same resource.
• sched_list : member of the local list of threads running on the same core.
• etc.

3) Process creation

The process creation in a remote cluster implements the POSIX fork() / exec() mechanism. When a parent process P executes the fork() system call, a new child process C is created. The new C process inherits (from the parent process P) the open files (FDT), and the memory image (VSL and GPT). These structures must be replicated in the new process descriptor. After a fork(), the C process can execute an exec() system call, that allocates a new memory image to the C process, but the new process can also continue to execute with the inherited memory image. For load balancing, ALMOS-MKH uses the DQDT to create the child process C on a different cluster from the parent cluster P, but the user application can also use the non-standard place_fork() system call to specify the target cluster.

3.1) fork()

See ​sys_fork.c.

The fork() system call is the only method to create a new process. A thread of parent process P, running in a cluster X, executes the fork() system call to create a child process C on a remote cluster Y, that will become both the owner and the reference cluster for the C process. A new process descriptor and a new thread descriptor are created and initialized in target cluster Y for the child process. The calling thread can run in any cluster. If the target cluster Y is different from the calling thread cluster X, the calling thread uses a RPC to ask the target cluster Y to do the work.

Regarding the process descriptor, a new PID is allocated in cluster Y. The child process C inherits the vsegs registered in the parent process reference VSL, but the ALMOS-MKH replication policy depends on the vseg type:

• for the DATA, ANON, REMOTE vsegs (containing shared, non replicated data), all vsegs registered in the parent reference VSL(Z,P) are registered in the child reference VSL(Y,C), and all valid GPT entries in the reference parent GPT(Z,P) are copied in the child reference GPT(Y,C). For all pages, the WRITABLE flag is reset and the COW flag is set, in both (parent and child) GPTs. This requires to update all corresponding entries in the parent GPT copies (in clusters other than the reference).
• for the STACK vsegs (that are private), only one vseg is registered in the child reference VSL(Y,C). This vseg contains the user stack of the parent thread requesting the fork, running in cluster X. All valid GPT entries in the parent GPT(X,P) are copied in the child GPT(Y,C). For all pages, the WRITABLE flag is reset and the COW flag is set, in both (parent and child) GPTs.
• for the CODE vsegs (that must be replicated in all clusters containing a thread), all vsegs registered in the reference parent VSL(Z,P) are registered in the child reference VSL(Y,C), but the reference child GPT(Y,C) is not updated by the fork: It will be dynamically updated on demand in cases of page fault.
• for the FILE vsegs (containing shared memory mapped files), all vsegs registered in the reference parent VSL(Z,P) are registered in the child reference VSL(Y,C), and all valid entries registered in the reference parent GPT(Z,P) are copied in the reference child GPT(Y,C). The COW flag is not set for these shared data.

Regarding the thread descriptor, a new TRDID is allocated in cluster Y, and the calling parent thread context (current values stored in the CPU and FPU registers) is saved in the child thread CPU and FPU contexts, to be restored when the child thread will be selected for execution. Three CPU context slots are not simple copies of the parent value:

• the thread pointer register contains a pointer the currently running thread descriptor. This thread pointer register cannot have the same value for parent and child.
• the stack pointer register contains the current pointer on the kernel stack. ALMOS-MKH uses a specific kernel stack when a user thread enters the kernel, and this kernel stack is implemented in the thread descriptor. As parent and child cannot use the same kernel stack, the parent kernel stack content is copied to the child kernel stack, and the stack pointer register cannot have the same value for parent and child.
• the page table pointer register contains the physical base address of the current generic page table. As the child GPT is a copy of the parent GPT in the child cluster, this page table register cannot have the same value for parent and child.

At the end of the fork(), cluster Y is both the owner cluster and the reference cluster for the new C process, that contains one single thread running in the Y cluster. All pages of DATA, REMOTE, and ANON vsegs are marked Copy On Write in the child C process GPT (cluster Y), and in all copies of the parent P process GPT (all clusters containing a copy of P).

3.2) exec()

See ​sys_exec.c

After a fork() system call, any thread of a process P can execute an exec() system call. This system call forces the P process to execute a new application, while keeping the same PID, the same parent process, the same open file descriptors, and the same environment variables. The existing process descriptor will be cleaned up (both the reference and the copies) and all user threads will be deleted. A new main thread descriptor is created in the reference cluster from values contained in the .elf file defining the new application. The calling thread can run in any cluster. If the reference cluster Z for process P is different from the calling thread cluster X, the calling thread must use a RPC to ask the reference cluster Z to do the work.

At the end of the exec() system call, the cluster Z is both the owner and the reference cluster for process C, the latter of which contains one single thread in cluster Z.

4) Thread creation

See ​sys_thread_create.c

Any user thread T of any process P, running in any cluster K, can create a new thread NT in any cluster K'. This creation is initiated by the pthread_create system call.

• The target cluster K' can be specified by the user application, using the CXY field of the ​pthread_attr_t argument. If the CXY is not defined by the user, the target cluster K' is selected by the kernel K, using the DQDT.
• The target core in cluster K' can be specified by the user application, using the CORE_LID field of the pthread_attr_t argument. If the CORE_LID is not defined by the user, the target core is selected by the target kernel K'.

If the target cluster K' is different from the client cluster K, the cluster K sends a RPC_THREAD_USER_CREATE request to cluster K'. The argument is a complete structure pthread_attr_t, containing the PID, the function to execute and its arguments, and optionally, the target cluster and target core. This RPC should return the thread TRDID.

• If the target cluster K' does not contain a copy of the P process descriptor, the kernel K' creates a process descriptor copy from the reference P process descriptor, using a remote_memcpy(), and using the ​cluster_get_reference_process_from_pid() to get the extended pointer on reference cluster. It allocates memory for the associated structures GPT(M,P), VSL(M,P), FDT(M,P). These structures, being used as read-only caches, will be dynamically filled by the page faults. This new process descriptor is registered in the COPIES_LIST and in the LOCAL_LIST.
• When the local process descriptor is set, the kernel K' select the core that will execute the new thread, allocates a TRDID to this thread, creates the thread descriptor, and registers it in the local process descriptor, and in the selected core scheduler.

5) Thread destruction

The destruction of a target thread T can be caused by another thread K, executing the ​pthread_cancel() syscall requesting the target thread T to stop execution. It can be caused by the thread T itself, executing the ​pthread_exit() syscall to suicide. Finally, it can be caused by the ​exit() or ​kill() syscalls requesting the destruction of all threads of a given process.

The unique method to destroy a thread is to call the ​thread_delete() function, that sets the THREAD_FLAG_REQ_DELETE bit in the flags field of the target thread descriptor. The thread will be asynchronously deleted by the scheduler at the next scheduling point. The scheduler calls the ​thread_destroy() function that detaches the thread from the scheduler, detaches the thread from the local process descriptor, and releases the memory allocated to the thread descriptor.

If the target thread is running in attached mode, the ​thread_delete() function synchronizes with the joining thread, waiting the actual execution of the ​pthread_join() syscall before marking the target thread for delete.

If the target thread is the main thread (i.e. the thread 0 in the process owner cluster) the ​thread_delete() function does not mark the target thread for delete, because this must be done by the parent process main thread executing the ​wait() syscall (see section [6] below).

5.1) Thread running in DETACHED mode

The scenario is rather simple when the target thread T is not running in ATTACHED mode. The killer thread (that can be the target thread itself for an exit) calls the thread_delete() function that does the following actions:

• the killer thread sets the ​THREAD_BLOCKED_GLOBAL bit in the target thread blocked field,
• the killer thread sets the ​THREAD_FLAG_REQ_DELETE bit in the target thread flags field,
• the killer thread returns without waiting the actual deletion.

5.2) Thread running in ATTACHED mode

The thread destruction is more complex if the target thread T is running in ATTACHED mode, because another joining thread J must be informed of the termination of thread T. As the thread_delete() function (executed by the killer thread K) and the sys_thread_join() function (executed by the joining thread J) can be executed in any order, this requires a "rendez-vous": The first arrived thread blocks and deschedules. It will be unblocked by the other thread.

The destruction mechanism can therefore involve three threads: the target thread T, the killer thread K, and the joining thread J.

It uses three specific fields in the thread descriptor:

• the join_lock field (in target thread) is a remote_spin_lock.
• the join_xp field contains an extended pointer on the first arrived thread.
• the exit_status field is used to transmit the global pointer returned by the terminating thread T to the joining thread T.

It uses also two specific ​THREAD_FLAG_JOIN_DONE and ​THREAD_FLAG_KILL_DONE flags in the target thread descriptor flags field, and one specific blocking bit ​THREAD_BLOCKED_JOIN, in the blocked field.

• Both the killer thread K, (executing the thread_kill() or the thread_exit() function), and the joining thread J (executing the sys_thread_join() function), try to take the join_lock implemented in the T thread descriptor (the join_lock in the J thread is not used).
• After taking the lock, the K thread test the FLAG_JOIN_DONE in the T thread descriptor:
  • If the FLAG_JOIN_DONE is set, the J thread arrived first and is blocked on the BLOCKED_JOIN condition: the K thread copies the exit_status from the the T thread to the J thread exit_status field (because the T thread can be deleted before the J thread resumes), unblocks the J thread from the BLOCKED_JOIN condition (using the join_xp field in the T thread), reset the JOIN_DONE flag in T thread, releases the join_lock in T thread, and finally completes the T thread destruction as described in the detached case.
  • If the FLAG_JOIN_DONE is not set, the K thread arrived first: the K thread blocks the K thread on the BLOCKED_JOIN condition, sets the FLAG_KILL_DONE in the T thread, registers the killer thread extended pointer in the T thread join_xp field, releases the join_lock in the T thread, and deschedules. It completes the T thread destruction as described in the detached case when it is unblocked by the J thread.
• After taking the lock, the J thread tests the FLAG_KILL_DONE in the T thread descriptor:
  • If the FLAG_KILL_DONE is set, the K thread arrived first and is blocked on the BLOCKED_JOIN condition: the J thread get the exit_status from the T thread to the J thread descriptor, unblocks the K thread, resets the FLAG_KILL_DONE in the T thread, releases the "join_lock" in T thread, and returns the exit_value from the T thread descriptor.
  • If the FLAG_KILL_DONE is not set, the J thread arrived first: the J thread registers its extended pointer in the T thread "join_xp" field, set the FLAG_JOIN_DONE in the T thread, sets the BLOCKED_EXIT bit in the J thread, releases the "join_lock" in the T thread, and deschedules. It returns the exit_status from its own J thread descriptor when it is unblocked by the K thread.

6) Process destruction

The destruction of a process P can be caused by a ​sys_exit() system call executed by any thread of the process P itself, or by another process executing the ​sys_kill(SIGKILL) system call. It can also be caused by a CtrlC signal typed on the process terminal. In all cases, the work must be done for all process copies in all clusters, using the list of copies rooted in the owner cluster.

6.1) Parent / children synchronization

The process descriptors copies (other than the process descriptor in owner cluster) are simply deleted by the scheduler when the last thread of a given process in a given cluster is deleted. The process descriptor copy is removed from the list of copies in the owner process cluster descriptor, and the process copy disappears.

The process destruction in the owner cluster is more complex, because the child process destruction must be reported to the parent process when the main thread of the parent process executes the blocking ​sys_wait() system call (in the parent owner cluster). Therefore, the child process in owner cluster cannot be destroyed before the parent calls the sys_wait() function. As the sys_wait() and the sys_kill() (or sys_exit()) functions are executed by different threads running in different clusters, this requires a parent/child synchronization. To keep a process descriptor in zombie state after a sys_kill() or sys_exit(), the main thread (i.e. thread 0 in process owner cluster) is not deleted until the sys_wait() syscall is executed by the parent process main thread. This synchronization uses the term_state field in process descriptor, that contains the following information :

• The ​PROCESS_TERM_KILL indicates that a KILL request has been received by the child;
• The ​PROCESS_TERM_EXIT indicates that an EXIT request has been made by the child;
• The ​PROCESS_TERM_BLOCK indicates that a SIGSTOP signal has been received by the child;
• The ​PROCESS_TERM_WAIT flag indicates that a WAIT request from parent has been received by the child.
• Moreover, for an exit(), the exit() argument value is registered in this ​term_state field.

The actual deletion of the child owner process descriptor and child main thread are done by the sys_wait() function, executed by the parent main thread (i.e. thread 0 in parent owner cluster). This sys_wait() function executes an infinite loop. At each iteration, the parent main thread scans all children owner descriptors. When it detects that one child terminated, it sets the PROCESS_FLAG_WAIT in child owner process descriptor, sets the ​THREAD_FLAG_REQ_DELETE in the child main thread, and returns to report the child termination state to parent process. It is the responsibility of the parent process to re-enter the sys_wait() syscall for the other children. When the parent process does not detect a terminated child at the end of an iteration, it deschedules without blocking.

6.2) Detailed exit scenario

This section describes the termination of a process caused by a sys_exit().

1. The sys_exit() syscall can be executed by any thread running in any cluster.
2. The sys_exit() function calls the process_sigaction() function that send a multicast, parallel and non blocking RPC to all clusters containing at least one thread of the calling process, to mark for delete all process threads, but the main thread and the calling thread. This function returns only when all target threads are blocked and marked for delete.
3. These marked threads will be actually destroyed by the scheduler at the next scheduling point. The remote process descriptor copies are also destroyed by the scheduler when the last thread in remote cluster is destroyed.
4. The sys_exit() function blocks and marks for delete the calling thread itself, when it is different from the main thread.
5. The sys_exit() function blocks the main thread, and sets the PROCESS_TERM_EXIT flag in owner process descriptor to ask the parent process (sys_wait function) to mark this main thread for delete, and deschedules. The calling thread will be destroyed at the next scheduling point.
6. The main thread, and the owner process descriptor on one hand, the calling thread and the associated process will be destroyed by the scheduler at the next scheduling point.

6.3) Detailed kill scenario

This section describes the termination of a target process caused by a sys_kill( SIGKILL ).

1. The sys_kill() syscall must be executed by the main thread of the target process, OR by any thread of another process than the target process.
2. The sys_kill() function calls the process_sigaction() function that sends a multicast, parallel and non blocking RPC to all clusters containing at least one thread of the target process, to block all process threads, except for the main thread. This function returns only when all threads (but the main) are blocked and descheduled.
3. The sys_kill() function calls again the process_sigaction() function that sends another multicast, parallel and non blocking RPC to the same clusters, to mark for delete all process threads, but the main thread. The marked threads will be actually destroyed by the scheduler at the next scheduling point. The target process descriptor copies are actually destroyed by the scheduler when the last thread in remote cluster is destroyed.
4. The sys_kill() function sets the PROCESS_TERM_KILL flag in the target process descriptor in owner cluster to ask synchronize with its parent process, and returns.
5. The target process main thread, and the target process descriptor in owner cluster will be actually destroyed by the scheduler when the parent process sys_wait() function marks this main thread for delete.