1 |
1
시스템에서 수행되는 N개의 태스크를 스케쥴링하는 장치에 있어서, 상기 N개의 태스크 각각에 대해, 상기 태스크의 단독 수행의 활성화 지터 및 종단간 지연시간을 산출하는 산출부; 상기 N개의 태스크를 상기 시스템에 포함된 M개의 프로세서로 분배하는 분배부; 상기 분배된 상기 N개의 태스크의 위상을 설정하는 위상 설정부;를 포함하되, 상기 위상 설정부는 상기 N개의 태스크의 순서에 따라 위상을 설정하되, 상기 N개의 태스크 중 i번째 태스크에 대해, 기설정된 시간 간격에 따라 시간을 앞당기면서 충돌여부 검사를 수행하되, 상기 충돌이 발생한 최초의 시간이 검출되는 경우 상기 검출된 최초의 시간의 이전 시간을 상기 i번째 태스크의 위상으로 설정하고, 상기 충돌여부 검사는 상기 단독 수행의 활성화 지터 및 종단간 지연시간과, 상기 N개의 태스크 모두를 수행할 때의 태스크 수행의 활성화 지터 및 종단간 지연시간을 이용하여 수행되며, 상기 태스크의 수행은 상기 태스크에 대한 메인 프로세스를 실행하는 제1 과정, 상기 실행된 메인 프로세스에 대한 I/O 메시지를 송수신하는 제2 과정 및 상기 실행된 메인 프로세스의 사후 프로세스를 실행하는 제3 과정을 포함하는 것을 특징으로 하는 태스크 스케쥴링 장치
|
2 |
2
제1항에 있어서, 상기 위상 설정부는, 상기 N개의 태스크 모두를 수행할 때의 태스크 수행의 활성화 지터가 상기 단독 수행의 활성화 지터의 확률값 중 임계 확률값 이상이고, 상기 N개의 태스크 모두를 수행할 때의 태스크 수행의 종단간 지연시간이 상기 단독 수행의 종단간 지연시간 확률값 중 임계 확률값 이상인 경우 상기 충돌이 발생된 것으로 판단하는 것을 특징으로 하는 태스크 스케쥴링 장치
|
3 |
3
삭제
|
4 |
4
제1항에 있어서, 상기 시스템은 하나의 추가 프로세서 및 하나의 시스템 버스를 포함하고, 상기 제1 과정은 상기 M개의 프로세서에서 수행되고, 상기 제2 과정은 상기 시스템 버스에서 수행되고, 상기 제3 과정은 상기 추가 프로세서에서 수행되고, 상기 제1 과정 이후 상기 제2 과정이 수행되고, 상기 제2 과정 이후 상기 제3 과정이 수행되고,상기 활성화 지터는 상기 제1 과정의 예상 시작시간과 실제 시작시간과의 차이값이고, 상기 종단간 지연시간은 상기 제1 과정의 시작시간과 상기 제3 과정의 종료시간의 차이값인 것을 특징으로 하는 태스크 스케쥴링 장치
|
5 |
5
제4항에 있어서, 상기 산출부는 상기 제1 과정의 수행시간, 상기 제2 과정의 수행시간 및 상기 제3 과정의 수행시간을 더 산출하되, 상기 활성화 지터, 상기 종단간 지연시간 및 상기 제1 과정의 수행시간은 시스템 함수에 의한 경과 시간의 측정을 통해 산출되고, 상기 제3 과정의 수행시간은, 수행시간을 알고 있는 더미 과정을 상기 제3 과정의 전후에 추가하여 더미 태스크를 생성하고, 상기 더미 태스크의 수행시간을 측정하며, 상기 측정된 더미 태스크의 수행시간에서 상기 전후의 더미 과정의 수행시간을 뺄셈 연산하여 산출되고, 상기 제2 과정의 수행시간은 상기 종단간 지연시간에서 상기 제1 과정의 수행시간 및 상기 제3 과정의 수행시간을 뺄셈 연산하여 산출되는 것을 특징으로 하는 태스크 스케쥴링 장치
|
6 |
6
제1항에 있어서, 상기 M개의 프로세서 각각에는 하나 이상의 태스크가 분배되고, 상기 분배부는 K번의 분배 과정을 통해 태스크를 분배하되, 상기 K번의 분배 과정 중 j번째 태스크 분배 과정의 경우 상기 제1 과정의 수행시간을 크기를 기준으로 오름차순에 따라 태스크를 분배하고, 상기 K번의 분배 과정 중 j+1번째 태스크 분배 과정의 경우 상기 제1 과정의 수행시간을 크기를 기준으로 내림차순에 따라 태스크를 분배하고, 상기 j번째 태스크 분배 과정에서의 상기 제1 과정의 수행시간의 최대값은 상기 j+1번째 태스크 분배 과정에서의 상기 제1 과정의 수행시간의 최소값보다 큰 것을 특징으로 하는 태스크 스케쥴링 장치
|
7 |
7
제1항에 있어서,상기 위상 설정부는 상기 N개의 태스크의 초기 위상을 설정하고, 상기 초기 위상을 기설정된 시간 간격에 따라 시간을 앞당기면서 충돌여부 검사를 수행하되,i-1번째 태스크의 위상, 상기 i-1번째 태스크의 단독 수행의 종단간 지연시간의 최대값 및 기 설정된 시간값을 덧셈 연산하여 상기 i번째 태스크의 초기 위상을 설정하는 것을 특징으로 하는 태스크 스케쥴링 장치
|
8 |
8
제1항에 있어서,상기 i번째 태스크에 대한 위상 설정 시 i+1 번째 태스크부터 N번째 태스크까지 N-(i+1)개의 태스크가 함께 위상이 앞당겨지는 것을 특징으로 하는 태스크 스케쥴링 장치
|
9 |
9
제1항에 있어서,상기 N개의 태스크의 주기를 설정하는 주기 설정부;를 더 포함하되, 상기 주기 설정부는 상기 N개의 태스크의 위상이 모두 설정된 경우 상기 위상이 설정된 N개의 태스크를 포함하는 제1 태스크 집합을 생성하고, 상기 태스크 집합을 이후 시간 영역에 복사(replica)하여 제2 태스크 집합을 생성하고, 상기 제1 태스크 집합과 상기 제2 태스크 집합 사이의 주기를 설정하는 것을 특징으로 하는 태스크 스케쥴링 장치
|
10 |
10
M개의 프로세서, 하나의 추가 프로세서 및 하나의 시스템 버스를 포함하는 시스템에서 수행되는 N개의 태스크를 스케쥴링하는 방법에 있어서, 상기 N개의 태스크 각각에 대해, 상기 태스크의 단독 수행의 활성화 지터의 확률값 및 종단간 지연시간의 확률값을 산출하는 단계; 상기 N개의 태스크를 상기 M개의 프로세서로 분배하는 단계; 상기 분배된 상기 N개의 태스크의 위상을 설정하는 단계;를 포함하되, 상기 위상을 설정하는 단계는 상기 N개의 태스크의 순서에 따라 위상을 설정하되, 상기 N개의 태스크 중 i번째 태스크에 대해, 기설정된 시간 간격에 따라 시간을 앞당기면서 충돌여부 검사를 수행하되, 상기 충돌이 발생한 최초의 시간이 검출되는 경우 상기 검출된 최초의 시간의 이전 시간을 상기 i번째 태스크의 위상으로 설정하고,상기 충돌여부 검사는 상기 단독 수행의 활성화 지터의 확률값 및 종단간 지연시간의 확률값과, 상기 N개의 태스크 모두를 수행할 때의 태스크 수행의 활성화 지터 및 종단간 지연시간을 이용하여 수행되며, 상기 태스크의 수행은 상기 M개의 프로세서에서 수행되며 상기 태스크에 대한 메인 프로세스를 실행하는 제1 과정, 상기 시스템 버스에서 상기 실행된 메인 프로세스에 대한 I/O 메시지를 송수신하는 제2 과정 및 상기 추가 프로세서에서 수행되며 상기 실행된 메인 프로세스의 사후 프로세스를 실행하는 제3 과정을 포함하는 것을 특징으로 하는 태스크 스케쥴링 방법
|
11 |
11
제10항에 있어서, 상기 위상을 설정하는 단계는 상기 N개의 태스크 모두를 수행할 때의 태스크 수행의 활성화 지터가 상기 단독 수행의 활성화 지터의 확률값 중 임계 확률값 이상이고, 상기 N개의 태스크 모두를 수행할 때의 태스크 수행의 종단간 지연시간이 상기 단독 수행의 종단간 지연시간 확률값 중 임계 확률값 이상인 경우 상기 충돌이 발생된 것으로 판단하는 것을 특징으로 하는 태스크 스케쥴링 방법
|
12 |
12
제10항에 있어서, 상기 시스템은 하나의 추가 프로세서 및 하나의 시스템 버스를 포함하고, 상기 산출하는 단계는 상기 제1 과정의 수행시간, 상기 제2 과정의 수행시간 및 상기 제3 과정의 수행시간을 더 산출하되, 상기 활성화 지터, 상기 종단간 지연시간 및 상기 제1 과정의 수행시간은 시스템 함수에 의한 경과 시간의 측정을 통해 산출되고, 상기 제3 과정의 수행시간은, 수행시간을 알고 있는 더미 과정을 상기 제3 과정의 전후에 추가하여 더미 태스크를 생성하고 상기 더미 태스크의 실행시간을 측정함으로써 산출되고, 상기 제2 과정의 수행시간은 상기 종단간 지연시간에서 상기 제1 과정의 수행시간 및 상기 제3 과정의 수행시간을 뺄셈 연산하여 산출되는 것을 특징으로 하는 태스크 스케쥴링 방법
|
13 |
13
제10항 내지 제11항 중 어느 한 항의 방법을 수행하는 프로그램을 기록한 컴퓨터 판독 가능 기록 매체
|