Ⅰ. 스케줄러와 리스트

1 . 스케줄러의 역할과 종류

스케줄러(Scheduler)
- 태스크를 특정 기준에 따라, 정렬하여 실행 순서를 결정한다.
- 시스템의 성능 향상을 위해, 스케줄러로 태스크를 정렬한다.
라운드 로빈(Round-Robin) 알고리즘
- 태스크를 일정 시간마다 돌아가며 공평하게 실행하는 방법이다.
- 장점: 구현하기 쉽고, 태스크가 많지 않다면 어느정도 만족할만한 성능을 보장한다.
- 단점: 태스크가 많아질수록, 대기 시간이 길어져 모든 태스크의 성능이 같이 저하된다.
라운드 로빈의 단점 극복
- 태스크에 우선 순위를 부여하고, 우선순위별로 라운드 로빈 알고리즘을 적용한다.
라운드 로빈에 우선순위를 부여한 대표적인 기법
- 멀티레벨 큐(Multilevel Queue), 멀티레벨 피드백 큐(Multilevel Feedback Queue)
MINT64 OS 최종 목표
- 태스크의 우선순위를 3단계로 나누어, 각 레벨별로 라운드 로빈을 수행하는 멀티레벨 큐 스케줄러를 구현하는 것이다.

2. 스케줄러와 자료구조

리스트를 구성하는 자료구조들

// 데이터를 연결하는 자료구조
// 반드시 데이터의 가장 앞부분에 위치해야 함
typedef struct kListLinkStruct
{
		// 다음 데이터의 어드레스와 데이터를 구분하기 위한 ID
		void* pvNext;
		QWORD qwID;
} LISTLINK;

// 리스트를 관리하는 자료구조
typedef struct kListManagerStruct
{
		// 리스트 데이터의 수
		int iItemCount;
		// 리스트의 첫번째와 마지막 데이터의 어드레스
		void* pvHeader;
		void* pvTail;
} LIST;

리스트에 사용할 데이터를 정의하는 예

// 리스트에 사용할 데이터를 정의하는 예
// 반드시 가장 앞부분은 LISTLINK로 시작해야함
struct kListItemExampleStruct
{
		// 리스트를 연결하는 자료구조
		LISTLINK stLink;

		// 데이터들
		int iData1;
		char cData2;
};

리스트에 데이터를 추가하고 삭제하는 코드

// 리스트에 데이터를 더함
void kAddListToTail( LIST* pstList, void* pvItem )
{
    LISTLINK* pstLink;

    // 다음 데이터의 어드레스를 없음(NULL)으로 설정
    pstLink = (LISTLINK*) pvItem;
    pstLink->pvNext = NULL;

    // 리스트가 빈 상태이면, Header와 Tail을 추가한 데이터로 설정
    if( pstList->pvHeader == NULL)
    {
        pstList->pvHeader = pvItem;
        pstList->pvTail = pvItem;
        pstList->iItemCount = 1;

        return ;
    }

    // 마지막 데이터의 LISTLINK의 위치를 구하여, 다음 데이터를 추가한 데이터로 설정
    pstLink = (LISTLINK*) pstList->pvTail;
    pstLink->pvNext = pvItem;

    // 리스트의 마지막 데이터를 추가한 데이터로 변경
    pstList->pvTail = pvItem;
    pstList->iItemCount++;
}

// 리스트의 첫 부분에 데이터를 더함
void kAddListToHeader( LIST* pstList, void* pvItem )
{
    LISTLINK* pstLink;
    
    // 다음 데이터의 어드레스를 Header로 설정
    pstLink = ( LISTLINK* ) pvItem;
    pstLink->pvNext = pstList->pvHeader;

    // 리스트가 빈 상태이면 HEader와 Tail을 추가한 데이터로 설정
    if( pstList->pvHeader == NULL){
        pstList->pvHeader = pvItem;
        pstList->pvTail = pvItem;
        pstList->iItemCount = 1;

        return ;
    }

    // 리스트의 첫 번째 데이터를 추가한 데이터로 변경
    pstList->pvHeader = pvItem;
    pstList->iItemCount++;
}

// 리스트에서 데이터를 제거한 후, 데이터의 포인터를 반환
void* kRemoveList( LIST* pstList, QWORD qwID ){
    LISTLINK* pstLink;
    LISTLINK* pstPreviousLink;

    pstPReviousLink = ( LISTLINK* ) pstLink->pvHeader;
    for( pstLink = pstPreviousLink; pstLink !=NULL; pstLink = pstLink -> pvNext){
        // 일치하는 ID가 있다면 제거
        if(pstLink->qwID == qwID){
            // 만약 데이터가 하나밖에 없다면, 리스트 초기화
            if((pstLink == pstLink -> pvHeader) && 
                (pstLink == pstLink -> pvTail))
            {
                    pstList->pvHeader = NULL;
                    pstList->pvTail = NULL;
            }
            // 만약 리스트의 첫 번째 데이터면, Header를 두번째 데이터로 변경
            else if( pstLink == pstLink->pvHeader )
            {
                pstLink->pvHeader = pstLink->pvNext;
            }
            // 만약 리스트의 마지막 데이터면, Tail을 마지막 이전의 데이터로 변경
            else if( pstLink == pstList->pvTail ){
                pstList->pvTail = pstPreviousLink;
            }
            else
            {
                pstPreviousLink->pvNext = pstLink->pvNext;
            }

            pstList->iItemCount--;
            return pstLink;
        }
        pstPreviousLink = pstLink;
    }
    return NULL;
}

// 리스트의 첫번째 데이터를 제거하여 반환
void* kRemoveListFromHeader( LIST* pstList )
{
    LISTLINK* pstLink;

    if( pstLink->iItemCount == 0 )
    {
        return NULL;
    }

    // 헤더를 제거하고 반환
    pstLink = ( LISTLINK* ) pstList->pvHeader;
    return kRemoveList( pstList, pstLink->qwID );
}

// 리스트의 마지막 데이터를 제거하여 반환
void* kRemoveListFromTail( LIST* pstList )
{
    LISTLINK* pstLink;

    if(pstLink->iItemCount == 0)
    {
        return NULL;
    }

    // 테일을 제거하고, 반환
    pstLink = (LISTLINK*) pstList->pvTail;
    return kRemoveList( pstList, pstLink->qwID );
}

Ⅱ. 태스크 풀과 스케줄러

1. 태스크 풀과 스택 풀 설계

태스크 풀(Task Pool) : 태스크 자료구조를 모아놓는 공간 (태스크를 생성하거나 삭제할 때 사용할 TCB가 모여있는 특정 메모리 영역)

태스크 풀 관리용 자료구조

typedef struct kTCBPoolManagerStruct
{
		// 태스크 풀에 대한 정보
		TCB* pstStartAddress;
		int iMaxCount;
		int iUseCount;

		// TCB가 할당된 횟수
		int iAllocatedCount;
} TCBPOOLMANAGER;

2. 태스크 풀과 스택 풀 구현

태스크 풀은 초기화 함수, TCB 할당과 해제 함수로 구성된다.

태스크 풀을 관리하는 자료구조를 생성한 후, 초기화하는 코드

// 매크로
#define TASK_TCBPOOLADDRESS  0x800000 
#define TASK_MAXCOUNT        1024

// 태스크 풀을 관리하는 자료구조
static TCBPOOLMANAGER gs_stTCBPoolManager;

void kInitializeTCBPool( void )
{
		int i;

		kMemSet( &( gs_stTCBPoolManager ), 0, sizeof( gs_stTCBPoolManager ) );
		
		// 태스크 풀의 어드레스를 지정하고 초기화
		gs_stTCBPoolManager.pstStartAddress = ( TCB* ) TASK_TCBPOOLADDRESS;
		kMemSet( TASK_TCBPOOLADDRESS, 0, sizeof( TCB ) * TASK_MAXCOUNT );

		// TCB에 ID 할당
		for( i = 0; i<TASK_MAXCOUNT; i++ )
		{
				gs_stTCBPoolManager.pstStartAddress[ i ].stLink.qwID = i;
		}
		
		// TCB의 최대 개수와 할당된 횟수를 초기화
		gs_stTCBPoolManager.iMaxCount = TASK_MAXCOUNT;
		gs_stTCBPoolManager.iAllocatedCount = 1;
}

TCB 할당 및 해제 함수의 코드

TCB* kAllocateTCB( void )
{
		TCB* pstEmptyTCB;
		int i;

		if( gs_stTCBPoolManager.iUseCount == gs_stTCBPoolManager.iMaxCount )
		{
				return NULL;
		}

		for( i = 0; i< gs_stTCBPoolManager.iMaxCount; i++ ) 
		{
				// ID의 상위 32비트가 0이면 할당되지 않은 TCB
				if( ( gs_stTCBPoolManager.pstStartAddress[ i ].stLink.qwID >> 32 ) == 0 )
				{
						pstEmptyTCB = &( gs_stTCBPoolManager.pstStartAddress[ i ] );
						break;
				}
		}

		// 상위 32비트를 0이 아닌 값으로 설정해서, 할당된 TCB로 설정
		pstEmptyTCB -> stLink.qwID = ( (QWORD) gs_stTCBPoolManager.iAllocatedCount << 32 ) | i;
		gs_stTCBPoolManager.iUseCount++;
		gs_stTCBPoolManager.iAllocatedCount++;
		if( gs_stTCBPoolManager.iAllocatedCount == 0 )
		{
				gs_stTCBPoolManager.iAllocatedCount = 1;
		}

		return pstEmptyTCB;
}

void kFreeTCB( QWORD qwID )
{
		int i;

		// 태스크 ID의 하위 32비트가 인덱스 역할을 함
		i = qwID & 0xFFFFFFFF;

		// TCB를 초기화하고 ID 설정
		kMemSet( &( gs_stTCBPoolManager.pstStartAddress[ i ].stContext ), 0, sizeof( CONTEXT ));
		gs_stTCPoolManager.pstStartAddress[ i ].stLink.qwID = i;

		gs_stTCBPoolManager.iUseCount--;
}

Ⅰ. 스케줄러와 리스트

1 . 스케줄러의 역할과 종류

2. 스케줄러와 자료구조

Ⅱ. 태스크 풀과 스케줄러

1. 태스크 풀과 스택 풀 설계

2. 태스크 풀과 스택 풀 구현

3. 라운드 로빈 스케줄러 설계