[FreeBSD] Context Switching

 

 

 

4.3 Context Switching

The kernel switches among threads in an effort to share the CPU effectively; this activity is called context switching. When a thread executes for the duration of its time slice or when it blocks because it requires a resource that is currently unavailable, the kernel finds another thread to run and context switches to it. The system can also interrupt the currently executing thread to run a thread triggered by an asynchronous event, such as a device interrupt.

 

Although both scenarios involve switching the execution context of the CPU, switching between threads occurs synchronously (동기적으로) with respect to the currently executing thread, whereas servicing interrupts occurs asynchronously with respect to the current thread.

 

In addition, interprocess context switches are classified as voluntary or involuntary. A voluntary context switch occurs when a thread blocks because it requires a resource that is unavailable. An involuntary context switch takes place when a thread executes for the duration of its time slice or when the system identifies a higher-priority thread to run.

 

Each type of context switching is done through a different interface. Voluntary context switching is initiated with a call to the sleep() routine, whereas an involuntary context switch is forced by direct invocation of the low-level context-switching mechanism embodied in the mi_switch() and setrunnable() routines. Asynchronous event handling is triggered by the underlying hardware and is effectively transparent to the system.

 

 

 

Thread State

Context switching between threads requires that both the kernel- and user-mode context be changed. To simplify this change, the system ensures that all of a thread’s user-mode state is located in the thread structure while most kernel state is kept elsewhere.

 

The following conventions apply to this localization:

• Kernel-mode hardware-execution state: Context switching can take place in only kernel mode. The kernel’s hardware-execution state is defined by the contents of the TSB that is located in the thread structure.

• User-mode hardware-execution state: When execution is in kernel mode, the user-mode state of a thread (such as copies of the program counter, stack pointer, and general registers) always resides on the kernel’s execution stack that is located in the thread structure. The kernel ensures this location of user-mode state by requiring that the system-call and trap handlers save the contents of the user-mode execution context each time that the kernel is entered.

• The process structure: The process structure always remains resident in memory.

• Memory resources: Memory resources of a process are effectively described by the contents of the memory-management registers located in the TSB and by the values present in the process and thread structures. As long as the process remains in memory, these values will remain valid and context switches can be done without the associated page tables being saved and restored. However, these values need to be recalculated when the process returns to main memory after being swapped to secondary storage.

 

 

 

Low-Level Context Switching

The localization of a process’s context in that process’s thread structure permits the kernel to perform context switching simply by changing the notion of the current thread structure and (if necessary) process structure, and restoring the context described by the TSB within the thread structure (including the mapping of the virtual address space). Whenever a context switch is required, a call to the mi_switch() routine causes the highest-priority thread to run. (우선 순위에 따라 실행) The mi_switch() routine first selects the appropriate thread from the scheduling queues, and then resumes the selected thread by loading its context from its TSB.

 

 

 

Voluntary Context Switching

A voluntary context switch occurs whenever a thread must await the availability of a resource or the arrival of an event. (비동기 처리 관련) Voluntary context switches happen frequently in normal system operation. In FreeBSD, voluntary context switches are initiated through a request to obtain a lock that is already held by another thread (다른 스레드가 가진 락을 기다리며) or by a call to the sleep() routine.

When a thread no longer needs the CPU, it is suspended, awaiting the resource described by a wait channel, and is given a scheduling priority that should be assigned to the thread when that thread is awakened. This priority does not affect the user-level scheduling priority.

 

When blocking on a lock, the wait channel is usually the address of the lock. When blocking for a resource or an event, the wait channel is typically the address of some data structure that identifies the resource or event for which the thread is waiting. For example, the address of a disk buffer is used while the thread is waiting for the buffer to be filled. (버퍼가 채워지길 기다릴 때, 해당 디스크 버퍼의 주소가 wait channel로 활용됨) When the buffer is filled, threads sleeping on that wait channel will be awakened.

 

In addition to the resource addresses that are used as wait channels,
there are some addresses that are used for special purposes: (다양한 목적으로 활용되는 주소들) 

• When a parent process does a wait system call to collect the termination status of its children, it must wait for one of those children to exit. Since it cannot know which of its children will exit first, and since it can sleep on only a single wait channel, there is a quandary about how to wait for the next of multiple events. The solution is to have the parent sleep on its own process structure. When a child exits, it awakens its parent’s process-structure address rather than its own. Thus, the parent doing the wait will awaken independently of which child process is the first to exit. Once running, it must scan its list of children to determine which one exited.

• When a thread does a sigsuspend system call, it does not want to run until it receives a signal. Thus, it needs to do an interruptible sleep on a wait channel that will never be awakened. By convention, the address of the signal-actions structure is given as the wait channel. 

 

A thread may block for a short, medium, or long period of time depending on the reason that it needs to wait.

• A short wait occurs when a thread needs to wait for access to a lock that protects a data structure.
• A medium wait occurs while a thread waits for an event that is expected to occur quickly such as waiting for data to be read from a disk.
• A long wait occurs when a thread is waiting for an event that will happen at an indeterminate time in the future such as input from a user. (기다리는 시간이 확실하지 않은 동작)

 

Short-term waits arise only from a lock request. Short-term locks include mutexes, read-writer locks, and read-mostly locks. Details on these locks are given later in this section. A requirement of short-term locks is that they may not be held while blocking for an event as is done for medium - and long-term locks. The only reason that a thread holding a short-term lock is not running is that it has been preempted by a higher-priority thread. It is always possible to get a short-term lock released by running the thread that holds it and any threads that block the thread that holds it.

 

A short-term lock is managed by a turnstile data structure. The turnstile tracks the current owner of the lock and the list of threads waiting for access to the lock. Figure 4.3 shows how turnstiles are used to track blocked threads. Across the top of the figure is a set of hash headers that allow a quick lookup to find a lock with waiting threads. If a turnstile is found, it provides a pointer to the thread that currently owns the lock and lists of the threads that are waiting for exclusive and shared access. The most important use of the turnstile is to quickly find the threads that need to be awakened when a lock is released. In Figure 4.3, Lock 18 is owned by thread 1 and has threads 2 and 3 waiting for exclusive access to it. The turnstile in this example also shows that thread 1 holds contested Lock 15.

 

 

 

Turnstile structures for blocked threads.