KR19990057122A - 실시간 시스템을 위한 사용자 레벨 다중 쓰레딩 방법 - Google Patents

Abstract

본 발명은 실시간 시스템을 위한 사용자 레벨 다중 쓰레딩 방법을 제공한다. 사용자 레벨 쓰레드가 동시성을 표현하고 응용 프로그램을 구조화하는데 필수적인 방법을 제공하지만, 시그널 처리나 쓰레드 스케쥴링의 어려움으로 인하여 실시간 프로그램에는 널리 사용되지 못하였다. 본 발명은 이러한 문제에 대한 해결책을 제시한다. 본 발명에서는 첫째, 커널에서 블록된 쓰레드가 프로세스 전체를 블록할 수 없도록 동적 스택 바인딩 기법을 제안한다. 둘째, 응용 프로그램이 원하는 방식에 따라 쓰레드 스케쥴링을 할 수 있도록 커널의 이벤트를 효율적으로 사용자 스케쥴러에 전달하기 위한 방법으로서 스케쥴링 이벤크 업콜 방식을 제안한다.

스케쥴링 이벤트 업콜을 받아서 수행되는 사용자 스케쥴러는 쓰레드와 독립적으로 수행되는 쓰레드로 볼 수 있다. 사용자 스케쥴러는 쓰레드 스케쥴링을 수행하는 라이브러리와 자료 구조를 공유한다. 쓰레드 라이브러리가 공유 자료 구조에 안전하게 접근하기 위하여 사용자 스케쥴러를 블록하여야 한다. 본 발명에 의하면, 시스템 콜을 통하지 않고 사용자 스케쥴러와 라이브러리 코드가 공유 자료 구조를 안전하게 접근할 수 있다.

Description

실시간 시스템을 위한 사용자 레벨 다중 쓰레딩 방법

본 발명은 컴퓨터 운영 체계에 관한 것으로서, 더욱 특별하게는 실시간 시스템을 위한 사용자 레벨 다중 쓰레딩 방법에 관한 것이다.

쓰레드(thread)는 프로세스(process) 또는 태스크(task)보다 더 작은 작업 단위로서, 동시성 관리와 자원 관리를 효과적으로 표현할 수 있고, 비동기적 이벤트들을 효율적으로 처리할 수 있다. 쓰레드의 이러한 특성은 제한된 시간에 빠른 문맥 교환을 요구하는 실시간 시스템을 구현하는데 적합하다.

쓰레드는 구현 방법에 따라서 커널 레벨 쓰레드와 사용자 레벨 쓰레드로 나눌 수 있다. 커널 레벨 쓰레드는 모든 응용 프로그램이 커널이 제공하는 하나의 모델만을 사용하여야 하기 때문에 응용 프로그램에 맞는 쓰레드 모델을 적용하기가 어렵고 쓰레드에 대한 연산을 수행할 때마다 커널로 들어가야 하는 오버헤드가 있기 때문에, 일반적인 프로그래밍에서는 사용자 레벨 쓰레드를 사용하여 왔다.

그러나, 실시간 프로그래밍에서는 실시간 처리에 있어서 중요한 부분인 쓰레드 스케쥴링과 시그널 처리를 쉽게 할 수 있기 때문에, 사용자 레벨 쓰레드보다는 커널 레벨 쓰레드를 사용한다. 사용자 레벨 쓰레드는 커널의 지원이 없이는 쓰레드의 커널내에서의 블록과 시그널의 전달을 처리할 수 없다. 따라서 사용자 레벨 쓰레드가 시스템 호출에 의하여 커널내에서 블록되었다면 사용자 레벨에서 수행할 수 있는 다른 쓰레드가 해당 프로세스에 있어도 프로세스 전체가 블록되게 된다.

그러나, 커널 레벨 쓰레드만으로 실시간 프로그램을 구성하면 응용 프로그램이 매우 제한되게 된다. 모든 응용 프로그램내의 실시간 쓰레드들에 대하여 하나의 스케쥴링 정책만을 사용하여야 하기 때문에 각 프로세스마다 응용 프로그램의 특성에 맞는 스케쥴링 정책을 적용하기 힘들다. 즉, 커널 스케쥴러를 각 응용 프로그램의 요구에 맞도록 고치지 않고서는 다른 스케쥴링 정책을 지원할 수 없다. 따라서 실시간 쓰레드에 다양한 스케쥴링 정책을 적용시키기 위하여 커널 레벨 쓰레드와 사용자 레벨 쓰레드를 절충한 새로운 쓰레딩 방법이 필요하다.

본 발명의 목적은 사용자 레벨 쓰레드를 지원할 수 있는 신규한 실시간 커널 구조에 의한 사용자 레벨 스레딩 방법을 제공하는데 있다.

본 발명의 목적은 커널에서 블록된 쓰레드가 프로세스 전체를 블록할 수 없도록 하는 실시간 시스템을 위한 사용자 레벨 다중 쓰레딩 방법을 제공하는데 있다.

본 발명의 또 다른 목적은 응용 프로그램이 원하는 방식에 따라서 쓰레드를 스케쥴링할 수 있도록 커널의 이벤트를 효율적으로 사용자 스케쥴러에게 전달하는 실시간 시스템을 위한 사용자 레벨 다중 쓰레딩 방법을 제공하는데 있다.

도1은 본 발명에 의한 사용자 레벨 다중 쓰레딩 방법을 설명하는 도면;

도2는 본 발명에 의한 사용자 레벨의 다중 쓰레딩 방법에서 쓰레딩의 수행 환경을 설명하는 도면;

도3은 본 발명에 의한 방법에서 사용자 스케쥴러의 기준 모델에 따른 고정 우선순위 스케쥴러의 예.

상기한 바와 같은 목적을 달성하기 위하여, 본 발명에 의한 쓰레딩 방법은, 프로세스를 스케쥴링하는 커널 모드와 쓰레드를 스케쥴링하는 사용자 모드를 포함하는 쓰레딩 방법에 있어서, 쓰레드가 커널을 블록킹하는 경우 커널은 새로운 커널 스택을 생성하는 단계; 및 업콜을 유발하는 이벤트들을 특정하고, 이러한 특정된 이벤트들에 의한 스케쥴링 이벤트 업콜에 의하여 커널의 이벤트를 사용자 스케쥴러에게 전달하는 단계를 포함하는 것임을 특징으로 한다.

이하에서 첨부된 도면을 참조하면서 본 발명의 바람직한 일실시예를 상세하게 설명한다.

도1은 본 발명에 의한 사용자 레벨 다중 쓰레딩 방법을 설명하는 도면이다.

본 발명에 의한 사용자 레벨 다중 쓰레딩 방법에서 '프로세스'와 '쓰레드'의 개념은 일반적인 다른 다중 쓰레딩 시스템에서 사용되는 개념과 동일하다. 본 발명에 의한 실시간 시스템을 위한 사용자 레벨 다중 쓰레딩 방법의 작동을 도1에 도시된 바와 같이, 커널 모드와 사용자 모드로 구분하여 설명한다.

쓰레드는 사용자 레벨의 스케쥴링 객체이므로 커널은 쓰레드의 존재를 알지 못하고, 커널에서의 스케쥴링 객체는 프로세스이다. 결과적으로 커널은 프로세스를, 프로세스는 쓰레드를 스케쥴링하는 두 단계의 스케쥴링이 발생하게 된다.

본 발명에 의한 사용자 레벨 다중 쓰레딩 방법의 특징은 첫 번째로, '동적 스택 바인딩(dynamic stack binding)'에 있다. 커널은 쓰레드의 존재를 알 수 없으므로 프로세스에 하나의 커널 스택만을 할당하는 것이 일반적이다. 이러한 커널 스택은 여러 쓰레드들이 공동으로 사용하기 때문에 공유 데이터 영역이 된다. 따라서 만약 한 쓰레드가 커널에서 서비스를 받는 도중에 블록을 하게 되면 다른 쓰레드는 커널 서비스를 받을 수 없게 된다.

본 발명에 의한 사용자 레벨 다중 쓰레딩 방법에서는 이러한 문제를 해결하기 위하여 쓰레드가 커널에서 블록킹하는 경우 커널은 새로운 커널 스택을 생성하여 다른 쓰레드가 불필요하게 볼록킹을 당하는 상황을 발생하지 않도록 하는 동적 스택 바이딩 방식을 사용한다. 도1에 커널 모드에 생성된 커널 스택들이 도시되어 있다.

본 발명에 의한 사용자 레벨 다중 쓰레딩 방법의 두 번째 특징은 '스케쥴링 이벤트 업콜(scheduling event upcall)' 방식에 있다. 사용자 레벨 쓰레드만으로 실시간 쓰레드를 스케쥴링하는데 가장 어려운 문제는 쓰레드 스케쥴링에 영향을 미치는 스케쥴링 이벤트를 처리하는 방법이 없다는 것이다.

본 발명에서는 커널의 이벤트를 사용자 스케쥴러에게 효율적으로 전달하기 위하여 스케쥴링 이벤트 업콜 기법을 사용한다. '업콜'은 일반적으로 사용자가 커널의 서비스를 받기 위하여 수행하는 '시스템 콜'과는 반대되는 개념으로서, 커널에서 사용자로 콜을 발생하는 것을 의미한다. 이러한 업콜은 추가적인 오버헤드를 발생하게 되고, 프로세스가 수행되는 동안 수많은 업콜을 처리하여야 하기 때문에, 비용을 줄이는 것이 필요하다.

이를 위하여, 본 발명에서는 업콜을 유발하는 이벤트를 특정하고, 특정된 이벤트에 한하여 사용자 스케쥴러에게 이벤트의 발생을 알려줌으로써 불필요하게 발생하는 오버 헤드를 줄인다.

본 발명에서 스케쥴링 이벤트 업콜을 유발하는 특정된 이벤트들은 다음과 같다.

- 블록(BLOCK) 이벤트 -

쓰레드가 커널에서 블록을 할 때, 커널은 블록 이벤트를 사용자 스케쥴러에게 보내어 쓰레드가 블록을 했음을 알린다. 이때 블록된 쓰레드의 커널 스택 번호가 함께 전달된다.

- 웨이크업(WAKEUP) 이벤트 -

블록된 쓰레드가 커널에서 깨어날 때, 커널은 웨이크업 이벤트를 보낸다. 이 이벤트 역시 깨어난 쓰레드의 커널 스택 번호가 함께 전달된다.

- 타이머(TIMER) 이벤트 -

사용자 스케쥴러가 설정한 시간이 끝나면 커널은 사용자 스케쥴러에게 타이머 이벤트를 보낸다. 사용자 스케쥴러는 타이머 이벤트를 받을 때, 현재 수행중인 쓰레드를 선점하고, 새로운 쓰레드를 수행시킨다. 커널은 사용자 스케쥴러가 다음의 재스케쥴링 시점을 기록할 수 있도록 한다. 이러한 재스케쥴링 시점은 우선 순위에 기초한 스케쥴러의 경우 주기적인 쓰레드의 다음 시작 시간이 될 수 있으며, 환형 수행 스케쥴러(cyclic executive scheduling)의 경우, 다음 마이너 사이클의 시작 시간이 될 수 있다. 이렇게 설정된 재스케쥴링 시점이 될 때만 커널이 타이머 업콜을 처리한다. 이러한 예약 방식은 매번 클럭 인터럽트가 발생할 때마다 업콜을 하는 것에 비하여 스케쥴링 업콜의 횟수를 획기적으로 줄일 수 있다. 이 타이머 업콜은 실시간 시스템을 구현하기 위한 본 발명에 의한 방법의 중요한 특징이다.

본 발명에서는 또한 '이벤트 큐'를 사용하여 커널이 사용자 스케쥴러에게 이벤트의 발생을 알림에 의하여, 사용자 스케쥴러가 이벤트를 처리하고 있는 동안에 새로운 이벤트가 발생할 때 커널이 겪는 대기 시간(blocking time)을 줄인다.

도1에 도시된 바와 같이, 커널과 사용자 스케쥴러가 정보를 교환하기 위하여, 사용자 주소 공간에 매핑되어 있는 스케쥴링 제어 블록을 사용한다. 이러한 스케쥴링 제어 블록은 사용자의 정보 교환 채널로 이용되며, 현재 시스템 시간; 다음 타이머 업콜 시간; 업콜이 발생한 시점의 쓰레드 문맥과 플래그; 이벤트 큐; 이벤트 큐와 큐의 머리/꼬리 인덱스; 스케쥴러의 록(lock) 플래그 등의 정보가 들어 있다.

이 중에서 '시스템 시간'은 클럭 인터럽트가 발생할 때마다 커널이 기록하며, '다음 타이머 업콜 시간'은 사용자 스케쥴러가 타이머 이벤트를 받고 싶은 시간을 기록한다. 커널은 이 값을 보고 타이머 이벤트가 발생하면 사용자 스케쥴러를 호출한다. 또한 커널이 타이머 이벤트를 보낼 때, 이 값을 '0'으로 세트하여 타이머 업콜이 불필요하게 중복되는 것을 방지한다. 사용자 스케쥴러는 타이머 이벤트를 받을 때, 다음에 받아야 할 시간을 새로 설정해주어야 한다.

'이벤트 큐의 머리와 꼬리 인덱스'는 사용자 스케쥴러가 이벤트를 꺼내고, 커널이 이벤트를 추가할 때 각각 변경된다. 이벤트 큐는 환형 큐이며 머리와 꼬리 값이 같으면 큐가 비어 있는 것이며, (꼬리+1)이 머리와 같으면 큐가 꽉 찬 것이 된다.

이벤트 큐의 크기는 스케쥴러를 등록할 때 사용자가 지정할 수 있다. 큐가 꽉차게 되는 상황은 사용자 스케쥴러가 큐를 비우고 있을 때, 타이머와 웨이크업을 유발하는 인터럽트들이 동시에 발생하여 사용자 스케쥴러가 큐를 비울 기회를 얻지 못할 때나 사용자 스케쥴러를 호출하지 못하도록 쓰레드가 록(lock)을 갖고 있는 기간이 긴 경우에 발생한다.

큐의 크기는 (블록될 수 있는 쓰레드의 개수 + 4)가 되며, 이는 본 명세서의 후반에서 설명하기로 한다. 따라서, 큐의 크기는 응용의 특성에 영향을 받게 되고, 사용자가 적절하게 설정하여 주어야 한다.

쓰레드 문맥은 업콜이 발생할 때의 쓰레드의 문맥 정보를 담고 있다. 사용자 모드에서 업콜이 발생하면 쓰레드의 문맥인 레지스터들의 값이 복사된다. 반면, 커널 모드에서 업콜이 발생하면 커널 쓰레드의 문맥을 담고 있는 스택의 번호가 들어간다. 쓰레드의 문맥의 상태를 나타내는 플래그가 있는데, 이것은 문맥이 사용자 모드의 것인지 커널 모드의 것인지를 나타내며, 또한 문맥이 유효한가를 나타낸다.

록(lock) 플래그는 사용자 라이브러리와 사용자 스케쥴러 사이의 동기화를 위하여 사용하는 정보이다. 즉, 라이브러리 함수에서 임계 영역을 보호하기 위하여 사용하는 변수이다.

도2는 본 발명에 의한 사용자 레벨의 다중 쓰레딩 방법에서 쓰레딩의 수행 환경을 설명하는 도면이다. 도2는 쓰레드들, 사용자 스케쥴러 및 라이브러리 함수들이 어떠한 관계를 가지고 수행되는가를 보여준다.

도2에 도시된 바와 같이, 모든 쓰레드들은 자신이 할당된 개별적인 스택 위에서 수행된다. 사용자 스케쥴러 역시 스케쥴링 제어 블록에 위치한 독립적인 스택 위에서 수행된다. 그러므로, 사용자 스케쥴러를 하나의 쓰레드로 생각할 수 있다. 쓰레드가 라이브러리 함수의 코드를 호출하면, 라이브러리 함수는 호출한 쓰레드의 스택 위에서 작업을 처리한다. 즉, 스케쥴링 작업을 처리하면서 사용자 스케쥴러와는 서로 다른 스택 위에서 수행되는 것이다. 도2에서 볼 수 있는 바와 같이, 한 쓰레드에서 다른 쓰레드로의 문맥 교환은 커널의 업콜에 의하여 호출 사용자 스케쥴러와 라이브러리 함수에 의하여 발생한다. 라이브러리 함수에 의해서는 동기적으로 스케쥴링이 발생하며, 사용자 스케쥴러에 의하여는 비동기적으로 스케쥴링이 발생한다.

상기한 바와 같은 쓰레드의 수행 환경에서는 두가지 문제가 발생한다. 첫 번째는 라이브러리 함수와 스케쥴러 사이에 경쟁 관계가 발생하여 공유 데이터의 일관성이 깨지게 된다는 것이다. 그러므로, 라이브러리 함수가 공유 데이터를 접근하는 동안에는 사용자 스케쥴러가 호출되지 못하도록 하여야 한다. 즉, 업콜이 블록되어야 한다. 그러나, 업콜을 블록시키기 위하여 시스템 콜을 사용하게 되면 사용자 레벨 쓰레드의 장점들을 완전히 잃어버리게 되므로 이를 효과적으로 처리할 수 있는 방법이 필요하다.

두 번째 문제는 사용자 스케쥴러에 하나의 스택만이 할당되어 있기 때문에 발생하는 문제이다. 즉, 이벤트에 의하여 업콜이 발생하여 사용자 스케쥴러가 수행되고 있는 동안 새로운 이벤트가 발생할 때 커널은 또 다른 사용자 스케쥴러를 수행시킬 수 없게 된다. 이 경우 또 다시 이벤트가 발생하게 되면 이벤트를 잃어버리게 되는 일이 발생할 수 있는데, 이러한 문제는 앞에서 설명한 이벤트 큐에 의하여 일부분 해결될 수 있다.

본 발명에서는 이러한 문제점들을 효율적으로 해결하기 위하여, 스케쥴러의 록-프리(lock-free) 구현 기법을 제안한다. 본 발명에서 제안하는 스케쥴러의 록-프리(lock-free) 기법에서는 커널의 도움을 받아 최소의 오버헤드로 라이브러리 함수와 사용자 스케쥴러 사이의 동기화 문제를 해결하고, 또한 이벤트가 중첩되어 발생할 때 효율적으로 처리할 수 있다.

이하에서는 본 발명에서 제시하는 록-프리(lock-free) 기법을 설명한다.

본 발명에서 제시하는 록-프리(lock-free) 기법은 모든 사용자 스케쥴러가 커널이 제시하는 기준 모델에 따라서 작성되어야 한다는 제약을 두고 있다. 도3은 본 발명에 의한 방법에서 사용자 스케쥴러의 기준 모델에 따른 고정 우선순위 스케쥴러의 예이다.

도3에 도시된 스케쥴러의 기준 모델에서는 스케쥴러가 두 개의 섹션으로 나뉘어져 있다. 첫 번째 섹션에서는 쓰레드의 문맥을 저장하고, 이벤트 큐가 빌 때까지 이벤트를 꺼내서 우선순위 조정과 같은 스케쥴링 정책에 연관된 작업을 처리한다. 두 번째 섹션에서는 다음에 수행되어야 하는 쓰레드를 선택하여 수행시키는 작업(dispatching)을 한다.

이러한 기준 모델에 따라서 사용자 스케쥴러를 작성할 때, 앞에서 설명한 스케쥴링 제어 블록을 이용하여 커널과 사용자 스케쥴러가 정보를 효율적으로 교환함으로써 상기한 두가지 문제를 해결할 수 있다.

본 발명에서 제시하는 록-프리(lock-free) 기법은 다음의 관찰에 입각하여 설계되었다.

- 커널과 사용자 스케쥴러는 서로 다른 인덱스 값을 변경한다.

- 사용자 스케쥴러는 이벤트 큐에서 이벤트를 꺼내기만 한다.

- 사용자 스케쥴러의 디스팻칭 작업은 이벤트가 발생할 때마다 처리되므로, 새로운 이벤트가 발생하면 이전의 디스팻칭 작업은 무시될 수 있다.

- 쓰레드는 업콜에 의해서만 그 수행이 선점(preemption)될 수 있다.

- 스케쥴링 제어 블록에 록 변수를 통하여 커널은 사용자 스케쥴러와 라이브러리 함수 사이의 동기화를 조율할 수 있다.

상기한 관찰을 바탕으로 본 발명에 의한 방법에서, 커널과 사용자 스케쥴러는 다음과 같은 규칙에 따라서 동작한다.

제1 규칙 : 이벤트의 삽입

이벤트가 발생하면 커널은 꼬리 인덱스가 가리키는 곳에 이벤트를 기록하고 꼬리 인덱스를 증가시킨다.

제2 규칙 : 사용자 스케쥴러의 호출

커널은, 큐가 비어 있는 상태에서 이벤트가 발생하는 경우와 스케쥴링 제어 블록의 록 변수의 값이 '0'인 경우의 두 가지 상황이 만족되어야만 사용자 스케쥴러를 호출한다. 이외의 상황에서는 단순히 큐에 발생한 이벤트를 기록하고 바로 이전에 수행되던 곳으로 되돌아간다.

제3 규칙 : 사용자 스케쥴러의 블록

라이브러리 함수가 임계 영역에 들어가기 전에 록 변수를 '1'로 세트한다.

제4 규칙 : 사용자 스케쥴러의 언블럭

라이브러리 함수가 임계 영역을 빠져 나올 때 록 변수를 '0'으로 리셋한다. 그리고, 이벤트 큐를 조사하여 이벤트 큐가 비어있지 않다면 사용자 스케쥴러로 문맥 교환을 한다.

제5 규칙 : 쓰레드의 문맥

이벤트에 수반되는 쓰레드의 문맥은, 사용자 스케쥴러가 수행되고 있는 동안 이벤트가 발생하는 경우와 스케쥴링 제어 블록의 록 변수가 '1'인 동안 이벤트가 발생하는 경우에는 유효하지 않다. 이러한 두 경우를 제외하면 사용자 스케쥴러가 저장하여야 할 문맥은 오직 한 경우이다. 즉, 쓰레드가 스케쥴러를 록하지 않고 수행중일 때 사용자 스케쥴러가 호출되는 경우이다.

제6 규칙 : 사용자 스케쥴러의 문맥 처리

사용자 스케쥴러는 쓰레드의 문맥이 유효한 경우에만 쓰레드 제어 블록에 문맥을 저장한다.

상기한 바와 같은 제1 내지 6 규칙에 따르는 동작에 의하면, 커널과 사용자 스케쥴러는 서로 다른 큐의 인덱스를 변경하기 때문에, 이벤트 삽입시 커널은 사용자 스케쥴러와 무관하게 큐에 이벤트를 넣을 수 있다(제1 규칙).

또한, 사용자 스케쥴러가 호출되면 큐에 존재하는 이벤트를 모두 처리하기 때문에 새로운 이벤트가 발생하였을 때 큐가 비어있지 않다면, 스케쥴러가 이미 수행되고 있다는 것을 의미한다. 만약, 큐가 비어 있지 않은 경우 커널이 사용자 스케쥴러를 호출하면 동일한 이벤트가 중복되어 처리되면서 자료 구조의 일관성이 깨질 수 있다. 그러나, 큐를 모두 비우고 디스팻칭 작업을 할 때는 디스팻칭 작업이 끝나기를 기다리지 않고 바로 새로운 사용자 스케쥴러를 호출하여 디스팻칭 작업의 중복을 최대한 피한다. 그러므로 이벤트 큐를 이용하고 상기한 제2 규칙에 따라서 사용자 스케쥴러를 호출하면 상기한 두 번째 문제를 해결할 수 있다.

상기 제2 규칙의 후반부, 제3 규칙, 제4 규칙은 사용자 스케쥴러와 라이브러리 함수 사이의 경쟁 관계 발생을 방지하기 위한 것이다. 이를 상세하게 설명하면 다음과 같다. 록 변수가 커널이 접근할 수 있는 스케쥴링 제어 블록에 있으므로, 록이 걸려 있는 동안에는 이벤트가 발생하여도 커널은 사용자 스케쥴러를 호출하지 않는다(제2 규칙의 후반부). 즉, 비동기적으로 호출되는 사용자 스케쥴러는 블록되게 된다. 이 이벤트는 후에 쓰레드가 언블록을 할 때 사용자 스케쥴러를 호출하여 반드시 이벤트를 처리하도록 하여야 한다(제4 규칙). 이러한 방식으로 첫 번째 문제인 사용자 스케쥴러와 라이브러리 함수 사이의 경쟁 관계 발생 문제를 해결할 수 있다.

제5 규칙 및 제6 규칙은, 이벤트가 발생하였을 때의 쓰레드의 문맥과 그 처리에 관한 것이다. 사용자 스케쥴러는 쓰레드 제어 블록을 갖지 않는 쓰레드로 생각할 수 있으므로 사용자 스케쥴러의 문맥은 저장될 곳이 없다. 즉, 사용자 스케쥴러의 문맥은 커널에 의하여 소실된 후, 재시작되어도 지장이 없는 문맥이다. 록 변수가 '1'로 세트되어 있는 동안에는 사용자 스케쥴러가 호출되지 않고, 커널에 의하여 바로 복구되는 문맥이므로 사용자 스케쥴러가 호출되어 이벤트를 처리할 때는 오래된 문맥(stable context)이 된다. 이러한 경우 커널은 문맥이 유효하지 않다는 플래그를 세트하여 주며, 상기한 제6 규칙에 따라서 사용자 스케쥴러는 플래그를 보고 문맥이 유효한 경우에만 문맥을 저장한다.

이상에서 설명한 바와 같은 본 발명에 의한 사용자 레벨 다중 쓰레딩 방법에 의하면, 이벤트 큐의 크기가 (블록된 쓰레드 갯수 + 4)로 제한될 수 있다. 일반적으로 이벤트가 다발적으로 발생하는 경우가 있기 때문에 이벤트 큐의 크기에 제한을 줄 수 없으리라고 생각한다. 본 발명에 의한 방법에서는 이벤트 큐의 크기를 커널에서 블록할 수 있는 쓰레드의 개수의 함수로 제한할 수 있다.

이를 상세하게 설명하면, 다음과 같다.

먼저, 상기한 바와 같은 본 발명에 의한 방법에 따른 다음의 세가지 정리를 살펴본다.

제1 정리: 이벤트 큐에 쌓일 수 있는 타이머 이벤트의 개수는 최대 2이다.

사용자 스케쥴러가 호출되기 전에 최대 1개의 이벤트가 쌓일 수 있고, 이러한 상황에서 사용자 스케쥴러가 타이머(TIMER)를 처리하면서 다음 타이머를 갱신하는 경우에만 새로운 타이머가 발생할 수 있다. 그러므로, 이러한 경우에만 2개의 타이머가 큐에 존재할 수 있다. 따라서, 이벤트 큐에 쌓일 수 있는 타이머 이벤트의 개수는 최대 2이다.

제2 정리: 블록 이벤트에 의하여 사용자 스케쥴러가 호출되는 경우에는 최대 1개의 타이머 이벤트가 큐에 존재할 수 있다.

블록 이벤트에 의하여 사용자 스케쥴러가 호출되는 경우에는 라이브러리 함수를 거치지 않고, 사용자 스케쥴러가 바로 호출되기 때문에 최대 1개의 타이머 이벤트가 큐에 존재할 수 있다.

제3 정리: 이벤트 큐에 쌓일 수 있는 웨이크업 이벤트의 개수는 프로세스에 존재하는 쓰레드의 개수를 넘지 못한다.

이는 쓰레드가 커널에서 블록한 경우에만 웨이크업 이벤트가 발생할 수 있기 때문에 자명한 것이다.

상기한 제1 내지 제3 정리에 따라서, 이벤트 큐에 존재할 수 있는 이벤트의 개수는 최대 (쓰레드 개수+3)이 된다. 이벤트 큐에 존재하는 이벤트의 수가 (쓰레드 개수+3)으로 최대가 되는 것은 블록 이벤트가 발생한 경우, 타이머 이벤트가 두 번 발생하고, 블록된 모든 쓰레드들이 모두 웨이크업 하는 경우이다. 환형 큐의 특성에 따르면, (큐의 크기-1)개의 엔트리만 존재할 수 있으므로, 큐의 크기는 (블록된 쓰레드 개수+4)가 되면 된다.

이상에서 설명한 바와 같이, 본 발명은 실시간 시스템을 위한 사용자 레벨 다중 쓰레딩 방법을 제안한다. 본 발명에서는 이를 위하여 동적 스택 바인딩 기법과 스케쥴링 이벤트 업콜 방식을 사용한다. 동적 스택 바인딩 기법에 의하여 한 스레드가 커널에서 블록하였을 때 다른 쓰레드들이 블록되는 것을 방지한다. 스케쥴링 이벤트 업콜은 스케쥴링 이벤트가 발생할 때, 비동기적으로 사용자 스케쥴러를 호출한다. 업콜의 오버헤드를 줄이기 위하여 사용자 스케쥴러를 록-프리하도록 구현하는 기법을 제안하였다.

Claims (4)

1. 프로세스를 스케쥴링하는 커널 모드와 쓰레드를 스케쥴링하는 사용자 모드를 포함하는 쓰레딩 방법에 있어서,

   쓰레드가 커널을 블록킹하는 경우 커널은 새로운 커널 스택을 생성하는 단계; 및

   업콜을 유발하는 이벤트들을 특정하고, 이러한 특정된 이벤트들에 의한 스케쥴링 이벤트 업콜에 의하여 커널의 이벤트를 사용자 스케쥴러에게 전달하는 단계를 포함하는 것임을 특징으로 하는 실시간 시스템을 위한 사용자 레벨 다중 쓰레딩 방법.
2. 제1항에 있어서, 상기 방법에서 커널이 사용자 스케쥴러에게 이벤트의 발생을 알리기 위하여 이벤트 큐를 사용하는 것임을 특징으로 하는 실시간 시스템을 위한 사용자 레벨 다중 쓰레딩 방법.
3. 제2항에 있어서, 상기 업콜을 유발하는 특정된 이벤트들은,

   쓰레드가 커널에서 블록을 한 블록 이벤트;

   블록된 쓰레드가 커널에서 깨어난 웨이크업 이벤트; 및

   사용자 스케쥴러가 설정한 시간이 끝난 타이머 이벤트를 포함하는 것임을 특징으로 하는 실시간 시스템을 위한 사용자 레벨 다중 쓰레딩 방법.
4. 제3항에 있어서, 상기 방법은 업콜의 오버레드를 줄이기 위하여 사용자 스케쥴러가 첫 번째 섹션에서는 쓰레드의 문맥을 저장하고, 이벤트 큐가 빌 때까지 이벤트를 꺼내서 우선순위 조정과 같은 스케쥴링 정책에 연관된 작업을 처리하고, 두 번째 섹션에서는 다음에 수행되어야 하는 쓰레드를 선택하여 수행시키는 작업을 하는 그러한 기준 모델에 따르고, 다음과 같은 제1 내지 제6 규칙들에 의하여 사용자 스케쥴러를 록-프리하는 것임을 특징으로 하는 실시간 시스템을 위한 사용자 레벨 다중 쓰레딩 방법;

   제1 규칙 : 이벤트의 삽입

   이벤트가 발생하면 커널은 꼬리 인덱스가 가르키는 곳에 이벤트를 기록하고 꼬리 인덱스를 증가시킨다.

   제2 규칙 : 사용자 스케쥴러의 호출

   커널은, 큐가 비어 있는 상태에서 이벤트가 발생하는 경우와 스케쥴링 제어 블록의 록 변수의 값이 '0'인 경우의 두 가지 상황이 만족되어야만 사용자 스케쥴러를 호출한다. 이외의 상황에서는 단순히 큐에 발생한 이벤트를 기록하고 바로 이전에 수행되던 곳으로 되돌아간다.

   제3 규칙 : 사용자 스케쥴러의 블록

   라이브러리 함수가 임계 영역에 들어가기 전에 록 변수를 '1'로 세트한다.

   제4 규칙 : 사용자 스케쥴러의 언블럭

   라이브러리 함수가 임계 영역을 빠져 나올 때 록 변수를 '0'으로 리셋한다. 그리고, 이벤트 큐를 조사하여 이벤트 큐가 비어있지 않다면 사용자 스케쥴러로 문맥 교환을 한다.

   제5 규칙 : 쓰레드의 문맥

   이벤트에 수반되는 쓰레드의 문맥은, 사용자 스케쥴러가 수행되고 있는 동안 이벤트가 발생하는 경우와 스케쥴링 제어 블록의 록 변수가 '1'인 동안 이벤트가 발생하는 경우에는 유효하지 않다. 이러한 두 경우를 제외하면 사용자 스케쥴러가 저장하여야 할 문맥은 오직 한 경우이다. 즉, 쓰레드가 스케쥴러를 록하지 않고 술행중일 때 사용자 스케쥴러가 호출되는 경우이다.

   제6 규칙 : 사용자 스케쥴러의 문맥 처리

   사용자 스케쥴러는 쓰레드의 문맥이 유효한 경우에만 쓰레드 제어 블록에 문맥을 저장한다.