The OKL4 microkernel provides a pre-emptive scheduler responsible for allocation processing time to user threads. The scheduler implements a pre-emptive rigid-priority round-robin scheduling algorithm.
(OKL4 마이크로커널은 사용자 Thread에게 프로세싱 시간 할당 의무를 가지는 선정형 스케줄러를 제공한다. 스케줄러는 선점형 엄격한 우선순위 라운드로빈 스케줄링 알고리듬을 구현한다.)
It is used by the OKL4 microkernel to enforce its fault isolation policy with regards to time-related misbehaviour(misbehavior 아닌감).
(이것(preemptive 쓰레드 스케줄링?)은 시간과 관계된 오동작에 대해서 이것의 fault 격리정책을 시행하기 위해서 OKL4 microkernel 에 의해서 사용되어진다.)
Preemptive scheduling allows the microkernel to forcibly revoke the processing time of a thread. This ensures that misbehaving threads do not affect the integrity of the remainder of the system.
(선점적인 스케줄링은 마이크로널이 강제로 쓰레드의 프로세싱 시간을 취소하는 것을 허용한다. 이것은 오동작하는 Thread가 시스템에 남아 있는 쓰레드들의 무결성에 영향을 주지 않도록 하는 것을 확신시킨다(안전하게 한다).)
Priorities can be used by the operating system to implement an array of scheduling policies including policies suitable for real-time applications.
(우선순위들은 OS에 의해서 실시간 어플리케이션에 적합한 정책을 포함한 스케줄링 정책의 배열을 구현하기 위해서 사용되어 질 수 있다.)
OKL4 allows the use of schedule inheritance to avoid unbounded priority inversion which occurs when a high-priority thread cannot run for an indefinite period of time because it is waiting on an object held by a low-priority thread prevented from executing by a medium priority thread.
(OKL4는 끝없는 우선순위 인버젼을 회포하기 위해서 스케줄 상속의 사용을 허용한다. - unbound priority inversion은 중간순위 Thread에 의해서 실행을 하지 못하게 된 낮은 순위 쓰레드가 잡은 object를 기다리는 높은 우선순위의 쓰레드가 정해지지 않은 기간동안(무기한) 동작할 수 없을 때 일어난다.)
OKL4 allows the user to enable or disable scheduling inheritance at compile time as required. Unless schedule inheritance is enable, the rigid nature of OKL4 priorities means that the microkernel never implicitly adjust the priorities of individual threads, giving the operating system personality complete control over management of thread priority levels.
(OKL4는 사용자에게 필요하다면 컴파일 시점에 스케줄링 상속의 활성화와 비활성화를 허용한다. 스케줄링 상속이 활성화가 아니면, OKL4 우선순위들의 엄격한 특징은 마이크로커널은 결코 개인적인 쓰레드들의 우선순위들을 맹목적으로 조절하지 않는다는 것을 말한다. 주어진 OS 특성은 쓰레드 우선순의 레벨들의 매니지먼트 전부를 완벽하게 제어한다.)
Note that a rigid priority system allows for the possibility of thread starvation. If this is unacceptable, the operating system personality should dynamically adjust thread priorities to prevent the starvation of lower-priority threads.
(엄격한 우선순위 시스템은 쓰레드 기아(starvation)의 가능성을 허용하는 것을 주의하세요. 만약 이것을 받아 들일 수 없다면, OS 특성은 우선순위가 낮은 쓰레드들의 기아를 막기 위해서 다이나믹하게 쓰레드 우선순위들을 조절해야한다.)
- thread starvation -> thread가 제어권을 제대로 받지 못해서 동작을 하지 못하는것.
Each user thread in the system is associated with the following scheduling parameters : priority level, allowed execution units, time slice and remaining time slice.
(각 시스템의 사용자 쓰레드는 우선순위 레벨, 허용된 실행 유닛, 타임 슬라이스 그리고 남은 타임 슬라이스, 쓰레드 파라메터들과 결합된다.)
The first thread parameters are configured using the Schedule system call, and remaining time slice parameter is maintained internally by the microkernel.
(첫번째 파마메터들은 Schedule 시스템 콜을 사용하여 구성되어지고, 남은 타임 슬라이스는 마이크로커널의 의해서 내부적으로 관리가 되어진다.)
Each parameter is described in the following section :
1. Priority Levels.
Each thread is associated with a priority level(or priority) which is used by the microkernel during the allocation of processing time to user threads. The priority level is a positive integer in the range 0-255.
(각 thread는 마이크로커널이 사용자 쓰레드에게 수행시간을 할당하는 동안 사용되는 우선순위와 함께 결합된다. 우선순위는 0-255 범위안의 양의 정수이다.)
A thread is said to have a higher priority than another thread if its priority level is numerically greater than that of the other thread.
(쓰레드의 우선수이가 다른 쓰레드보다 더 크다면 높은 우선순위를 가진다고 말한다.)
Upon initialization, the priority of the newly created thread is set to 0. It may be subsequently modified using the Schedule system call.
(초기화에, 새롭게 생성되는 쓰레드의 우선순위는 0으로 설정된다. 이것은 이어서 Schedule 시스템 콜을 사용하여 수정되어 진다.)
2. Allowed Execution Units
The set of execution units on which a thread may be allocated time is specified by its allowed execution units as specified by its hardware thread mask. The hardware thread is defined as an execution unit and is associated with a single domain which is a collection of one or more hardware thread.
( 해석 안함.. 젠장)
3. Time Slices
The time slice of a thread specifies the maximum period of time a thread may execute on a processor before being preempted.
(쓰레드의 타임슬라이스는 쓰레드가 점유되기전에 프로세스상에서 실행될 수 있는 시간의 최대 기간을 명세한다.)
Specifically, it defines the initial value of the remaining time slice. Upon initialization of a new thread, its time slice is set to a default value. This value may be subsequently modified using the Schedule system call. The time slice parameter can be set to an infinite value, effectively disabling pre-emption of the corresponding user thread.
(엄밀히 말하면, 이것은 남은 타임 슬라이스의 초기값을 정의한다. 새로운 쓰레드의 초기화에, 쓰레드의 타임 슬라이스는 기본값으로 설정된다. 이 값은 이어서 Schedule 시스템 콜을 사용하여 수정되어질지 모른다. 타임슬라이스 파라메터는 무한값(infinite value)로 설정될 수 있다.해당 쓰레드는 실제로 선점을 불가능하게 한다.)
4. The remaining time slice
Each user thread with a finite time slice parameter is associated with a remaining time slice parameter that is maintained internally by the microkernel. Upon initialization, the remaining time slice of a thread is set to a default value. The remaining time slice is reset to the time slice of the thread when the time slice parameter of the thread is modified.
(유한한 타임슬라이스 매개변수를 가진 각 사용자 쓰레드는 마이크로커널이 내부적으로 관리하는 남은 타임 슬라이스 매개변수와 결합된다. 초기화에 쓰레드의 남은 타임 슬라이스는 기본값으로 설정된다. 쓰레드의 타임슬라이스 파라메터가 변경될 때 남은 타임슬라이스는 쓰레드의 타임슬라이스로 재설정된다.)
The microkernel decrements the remaining time slice parameter one to one for every microsecond of processing time consumed by the thread unless parameter has been initialized to an infinite value.
(마이크로커널은 남은 타임 슬라이스 파라메터를 파라메터를 무한값으로 초기화하지 않은 쓰레드에 의해서 소모되는 모든 프로세싱 타임 1ms당 1씩 감소시킨다.)
When the remaining time slice reaches 0, the thread is pre-empted. The remaining time slice is reset back to its initial value as configured using the Schedule system call. The current value of a thread’s remaining time slice parameter may be obtained using the Schedule system call.
(남은 타임 슬라이스가 0에 도달할 때, 쓰레드는 점유된다(멈추는거죠~). 남은 타임 슬라이스는 Schedule 시스템 콜로 설정된 초기값으로 재설정된다. 쓰레드의 남은 타임 슬라이스의 현재값은 Schedule 시스템 콜을 사용하여 얻을 수 있다.)
5. Scheduling Queue.
The microkernel maintains one or more system scheduling queues which collectively contain all active threads in the system. Each queue maintains threads running on one or more processing units. Each processing unit can only be associated with one system scheduling queue. These queues are operated on by the thread selection algorithm.
(마이크로커널은 하나 또는 그 이상의 집합적으로 시스템상의 모든 활성 쓰레드를 담는 시스템 스케줄링 큐를 유지한다. 각 큐는 하나또는 그 이상의 Processing 유닛에서 실행되고 있는 쓰레드를 유지한다.)
In addition, it maintains an additional IPC queue for each initialized OKL4 thread in the system. These queues contain threads currently performing IPC send operations on the
corresponding thread
(추가적으로, 초기화된 시스템의 각 OKL4 thread를 위한 추가적인 IPC큐를 유지한다. 이 큐들은 해당 쓰레드에서 현재 IPC 전송 동작들을 실행되고 있는 쓰레드들을 담는다.)
Each queue is represented by a first in first out (FIFO) list of thread identifiers, with the first inserted thread located at the start of the queue. Threads are removed from a queue (dequeued) using the thread selection algorithm. When a new thread is added to a queue (enqueued), it is appended to the end of the queue. IPC queues are not priority sorted.
(각 큐는 큐의 시작에 위치한 첫번째 삽입된 쓰레드와 함께 쓰레드 식별자(identifiers)의 FIFO 리스트로 나타낸다. 쓰레들은 쓰레드 선택 알고리듬을 사용하여 큐에서 삭제된다. 새로운 쓰레드가 큐에 추가될 때, 이것은 큐의 끝에 붙는다. IPC큐는 우선순위로 정렬되지 않는다.)
6. Thread Execution and Selection Algorithm
Each processing unit in the system is associated with a current thread, which is the thread that is allocated processing time on that unit at the given point in time.
(각 시스템상의 프로세싱 유닛은 주어진 시점에 유닛상에서 프로세싱 시간을 할당받은 현재 쓰레드와 결합된다.)
The current thread can obtain the number of the processing unit from its ProcessingUnit register. The current thread releases its processing unit for use by another thread in the following situations:
(현재 쓰레드는 쓰레드의 ProcessingUnit 레지스터로부터 프로세싱 유닛의 수를 얻을 수 있다. 현재 쓰레드는 아래 상황안의 다른 쓰레드에 의한 사용을 위해서 프로세싱 유닛을 릴리즈한다.)
a. When its remaining time slice parameter reaches 0, the thread is preempted.
(쓰레드의 남은 타임 슬라이스 파라메터가 0에 도달할 때, 쓰레드는 선점된다.)
b. When a thread invokes the ThreadSwitch system call, it forfeits any remaining processing time allocation specified by the remaining time slice parameter and is immediately enqueued in the system scheduling queue.
(쓰레드가 ThreadSwitch 시스템 콜을 실행할 때, 남은 타임슬라이스 파라메터에 의해 명시되는 어떠한 남은 프로세싱 시간 할당도 잃어버리고, 즉각적으로 시스템 스케줄링 큐에 들어간다.)
c. When a thread performs an IPC send operation, or when the microkernel performs an IPC send sned operation on behalf of the thread. the thread immediately releases its remaining allocation of processing time and is added to the sender queue of the target thread.
(쓰레드가 IPC 전송 동작을 수행할 때, 또는 마이크로커널이 쓰레드를 대신해서 IPC 전송 동작을 수행할 때, 쓰레드는 즉각적으로 남은 프로세스 시간 할당을 놓고, 목적 쓰레드(IPC를 수신 받는 쓰레드)의 전송자 큐에 추가된다.)
* on behalf of ~ : ~ 대신하여
d. When a current thread is suspended using the ExchangeRegister system call, its allocation of processing time is released until it is subsequently resumed using the ExchangeRegister system call.
(현재 쓰레드는 ExchangeRegister 시스템콜을 사용하여 중지될 때, ExchangeRegister를 사용하여 이어서 재실행될 때까지 프로세스 시간 할당을을 놓는다.)
e. Lastly, when a current thread is deleted using the ThreadControl system call, its remaining allocation of processing time is released before entering the new state.
(마지막으로, 현재 쓰레다가 ThreadControl 시스템콜을 사용하여 삭제되어질 때, 남은 프로세싱 시간 할당을 new 상태로 진입하기 전까지 놓는다.)
In all situations, the microkernel selects the new current thread by searching the system scheduling queue for the first thread with the correct domain and corresponding hardware thread include in it allowed processing units.
(모든 상황에서, 마이크로커널은 올바른 도메인과 적합한 하드웨어 쓰레드 함께 첫번째 쓰레드를 위한 시스템 스케줄링 큐에서 찾아서 새로운 현재 쓰레드를 선택한다.)
The selected thread is then removed from the system scheduling queue and allocated the amount of processing time specified by its time slice parameter. The same algorithm is used to select a thread from the thread’s receiver and sender queues during the IPC operations.
(선택된 쓰레드는 그 다음에 시스템 스케줄링 큐에서 삭제되고, 타임 슬라이스 파라메터에 의해서 명세된 프로세싱 시간의 양을 할당받는다. 같은 알고리듬은 IPC 동작 동안에 쓰레드의 receiver 와 sender 큐에서 쓰레드를 선택하기 위해서 사용되어진다.)
7. Thread Pre-emption.
When a current thread is preempted by the microkernel, it immediately releases the corresponding processing unit for use by other threads. If the Signalled flag in the thread's PreemptionFlag register is set, the thread's Preemptedlp register is set to the current value of its InstructionPointer register, and the InstructionPointer is set to the value of the thread's PreemptCallbacklp register.
(현재 쓰레드가 마이크로커널에 의해서 점유될때, 다른 쓰레드의 사용을 위해서 쓰레드에 대응되는 프로세싱 유닛을 즉각적으로 잃어버린다. 만약 쓰레드의 PreemptionFlag 레지스터의 Singalled flagh가 셋되어 있다면, 쓰레드의 Preemptedlp 레지스터는 InstructionPointer 레지스터의 현재 값으로 설정되고, InstructionPointer 레지스터는 쓰레드의 PreemptCallbacklp 레지스터 값으로 설정된다.)
Irrespective of the value of the Signalled flag, the thread is then added to the system scheduling queue. This permits real-time threads to detect pre-emption events in order to maintain integrity of its data structures, timing invariants or real-time deadlines.
(쓰레드의 Signalled 플래그의 값과 상관없이, 그리고 쓰레드는 시스템의 스케줄링 큐에 추가된다. 이것은 실시간 쓰레드에게 쓰레드의 data 구조체의 무결성과 타이밍 불변 그리고 실시간 데드라인을 관리하기 위해서 선점 이벤트를 감지하는 것을 허용한다.)
8. Schedule Inheritance.
OKL4 allows the user to enable schedule inheritance at compile time to prevent priority inversion. Priority inversion occurs when a high-priority thread is forced to wait for a low-priority thread to finish an operation.
(OKL4는 컴파일 시점에 우선순위 인버전(반전)을 막기 위해서 스케줄 상속을 사용자에게 허용한다. 우선순위 반전은 높은 우선순위의 쓰레드가 낮은 순위의 쓰레드가 동작을 마치는 동안에 강제로 기다려질때 일어난다.)
In certain cases, a high-priority thread may be prevented from running for an indefinite period of time because a medium-priority thread prevents a low-priority thread from executing. This is known as an unbounded priority inversion
(어떤 상황에서는, 높은 우선순위의 쓰레드가 중간순위의 쓰레다가 낮은 순위의 쓰레드의 실행을 막기 때문에 일정하지 않는 기간동안 실행되는 것을 금지당할지도 모른다. 이것은 unbounded priority inversion으로 알려져 있다.)
A Priority inheritance protocol, where the scheduler automatically donates the priority of a thread blocked on a resource to the thread holding that resource, may be used to avoid unbounded priority inversion.
(스케줄러가 자동적으로 리소스가 차단된 쓰레드의 우선순위를 부여하는 곳에서 우선 순위 상속 규약은 무한 우선순위 반전을 피하는데 사용되어질 수 있다.)
OKL4 uses schedule inheritance, an implementation of priority inheritance to avoid unbounded priority inversion.
(OKL4는 무한 우선순위 반전을 피하기 위한 우선순위 상속의 구현, 스케줄 상속을 사용한다. )
OKL4 implements schedule inheritance in the following manner. Ordinarily, when a thread becomes dependent on another thread, it is removed from the scheduling queue.
(OKL4는 아래의 따라오는 방법으로 스케줄 상속을 구현한다. 보통, 쓰레드가 다른 쓰레드에 의존하게 될 때, 쓰레드는 스케줄링 큐에서 삭제된다.)
However, where a thread P, becomes dependent on another identifiable thread Q, the kernel notes the object that the thread is waiting on, but leaves thread P in the scheduling queue.
(그러나, 쓰레드 P가 다른 구분되는 쓰레드 Q에 의존하게 되는 것에서 커널은 쓰레드가 대기중이라는 object를 알려준다. 그러나 스케줄링 큐에서 쓰레드 P를 버린다.)
If thread P is selected by the scheduler, this information is then used to determine the thread to which thread P's schedule is donated to.
(만약 스케줄러가 쓰레드 P를 선택하면, 그러면 이 정보는 쓰레드의 스케줄을 기증하기로 결정하는데 사용된다.)
For example, if thread P that is currently dependent on thread Q is selected, the scheduler will donate thread P’s schedule to thread Q. Thread Q will then run until either thread P’s schedule is pre-empted or until thread Q changes state in such a way that thread P no longer depends on it.
(예를 들어, 현재 쓰레드 Q에 의존된 쓰레드 P가 선택되어지면, 스케줄러는 쓰레드 P의 스케줄을 쓰레드 Q에게 기증할것이다. 그러면, 쓰레드Q는 다른 쓰레드 P의 스케줄이 점유되거나 쓰레드Q가 쓰레드 P를 종속적이지 않는 상태로 변경할 때까지 동작할 것이다.)
If thread Q is in turn dependent on another identifiable thread, the scheduler will continue the process of following this dependency chain until either it finds a thread to which it can donate thread P’s schedule, or until it detects a deadlock.
(만약 이번에는 쓰레드 Q가 다른 식별 쓰레드에 종속적이면, 스케줄러는 쓰레드 P의 스케줄을 기증할 쓰레드를 찾거나 데드락을 찾을 때까지 디펜던시체인의 프로세스를 계속할 것이다.)
* in turn : 이번에는, 차례로, 번갈아
9 Deadlock Detection
Where schedule inheritance is enabled, it is possible for a chain of dependencies to form a loop. As a result, deadlock detection is required by the scheduler to ensure that it is able to determine when it should stop following a chain of dependencies.
(스케줄 상속이 가능한 곳에서, 디펜던시 체인을 위한 루프를 형성하는 것이 가능하다. 결과로써, 데드락검출은 스케줄러에 의해서 언제 디펜던시 체인을 따라가는 것을 멈춰야할지 결정하는 것을 가능하도록 보장하게 위해서 요구된다. )
The OKL4 kernel performs deadlock detection to ensure that the kernel does not deadlock during scheduling operations. Once detected, deadlocks are removed by halting all threads in the dependency chain.
(OKL4 커널은 커널이 스케줄링 동작동안 데드락이 되지 않도록 보장하기 위해서 데드락 검출을 수행한다. 한번 검출이 되면, 데드락은 디펜던시 체인안의 모든 쓰레드를 멈춤으로써 제거된다.)
댓글 없음:
댓글 쓰기