4BSD nice
MLFQ에 대한 설명
다단계 큐 스케줄링과 비슷하게 동작하지만, 프로세스들이 큐 사이를 이동할 수 있는 차이 존재
새롭게 진입하는 프로세스는 먼저 우선순위가 가장 높은 우선순위 큐에 삽입되고, 타임 슬라이스 동안 실행
•
해당 큐에서 프로세스의 실행이 끝나지 않으면 다음 우선순위 큐에 삽입되어 실행
•
결국 오래 CPU를 사용해야 하는 프로세스의 우선순위는 점차 낮아짐
◦
CPU 집중 프로세스들의 우선순위는 낮아짐(CPU 사용시간이 길기 때문)
◦
입출력 집중 프로세스들의 우선순위는 높아짐
•
아사 현상 예방을 위해 우선순위 큐에서 오래 기다리고 있는 프로세스들을 높은 우선순위 큐로 이동시키는 에이징 기법을 적용 가능
◦
Feedback : 스레드가 CPU를 얼마나 썼는지, 얼마나 I/O 대기를 했는지 등의 실행 패턴을 기반으로 우선순위를 동적으로 조정하는 것
4BSD 스케줄러
•
PintOS의 MLFQS는 4BSD 스케줄러(UNIX에서 쓰던 CPU 스케줄링 알고리즘)를 모델로 함
•
4BSD에서는 CPU 사용량(recent_cpu)과 프로세스의 nice 값(유저가 지정하는 힌트)을 기반으로 우선순위를 조정
◦
결과 : CPU를 너무 많이 쓰는 스레드는 priority가 점점 낮아지고, I/O 위주로 대기 시간이 많은 스레드는 priority가 높아져서 CPU를 더 빨리 얻을 수 있게됨
결론 : 4BSD 스케줄러를 기반으로 만들어진 MLFQS는, 피드백을 통해 우선순위를 동적으로 조정하며 이 결과에 대한 문제를 해소했다
nice 값
유닉스 계열 시스템에서 nice 값은, “내 우선순위를 좀 낮춰줄게”라는 힌트를 의미
•
값 범위 : -20 ~ +20
•
nice값이 클수록 우선순위가 낮아짐 → CPU 양보(yield)
•
nice값이 작을수록 우선순위가 높아짐 → CPU 선점
결론 : nice값과 CPU 사용량, 부하를 반영해서 priority를 계속 조정 → 최대한 시스템 전체가 공정하게 CPU를 나눠쓰도록 설계
예시 코드
// MLFQS(Multi-Level Feedback Queue Scheduler)
#include <stdio.h>
#include <stdlib.h>
#define QUEUE_NUMS 4
#define TIME_SLICE 1
typedef struct thread_t
{
int id;
int priority; // 0(최고) ~ 3(최저)
int cpu_burst; // 남은 CPU 점유 시간
int nice; // 우선순위 결정에 영향을 미치는 값
struct thread_t* next;
} thread_t;
thread_t* queues[QUEUE_NUMS]; // 준비 큐 : 우선순위 별로 4개의 큐
// ---------------------------------------------------------------
void enqueue(thread_t** queue, thread_t* thread);
thread_t* dequeue(thread_t** queue);
thread_t* schedule();
void recalculate_priority(thread_t* thread);
// ---------------------------------------------------------------
void enqueue(thread_t** queue, thread_t* thread)
{
thread->next = NULL;
// 큐가 비어있는 경우
if(*queue == NULL)
{
*queue = thread;
}
// 큐가 비어있지 않은 경우
else
{
thread_t* temp = *queue;
while(temp->next != NULL)
{
temp = temp->next;
}
// 큐의 마지막에 삽입
temp->next = thread;
}
}
thread_t* dequeue(thread_t** queue)
{
if(*queue == NULL)
{
return NULL;
}
thread_t* t = *queue; // 제거할 스레드(헤드)
*queue = (*queue)->next; // 다음 스레드를 앞으로 당기기(헤드로 설정)
return t;
}
thread_t* schedule()
{
for(int i=0; i<QUEUE_NUMS; i++)
{
if(queues[i] != NULL)
{
// 가장 높은 우선순위 큐에서 스레드 선택 : 해당 큐에서 빼낸 스레드 반환
return dequeue(&queues[i]);
}
}
// 모든 큐가 비어있는 경우
return NULL;
}
// 단순화된 버전의 "우선순위 재계산" 함수
void recalculate_priority(thread_t* thread)
{
/*
<우선순위 재계산 공식 (예시)> : 공식은 자유롭게 변경 가능
1. nice값이 클수록 우선순위 낮아짐
2. cpu_burst가 클수록(CPU 집중 프로세스일수록 = CPU 사용량이 많을수록) 우선순위 낮아짐
*/
int new_priority = 2 - (thread->nice) - (thread->cpu_burst / 4);
if(new_priority < 0)
{
new_priority = 0;
}
else if(new_priority > 3)
{
new_priority = 3;
}
// 새로운 우선순위로 업데이트
thread->priority = new_priority;
}
// ---------------------------------------------------------------
int main()
{
// 스레드 3개 생성 : id, priority, cpu_burst, nice
thread_t t1 = {1, 0, 5, 0, NULL};
thread_t t2 = {2, 1, 3, 1, NULL};
thread_t t3 = {3, 2, 8, 0, NULL};
thread_t* threads[] = {&t1, &t2, &t3};
// 초기 우선순위 계산 & 준비 큐에 삽입
for(int i=0; i<3; i++)
{
recalculate_priority(threads[i]);
enqueue(&queues[threads[i]->priority], threads[i]); // 우선순위에 맞는 큐에 삽입
}
printf("MLFQS Scheduling 시작!\n");
thread_t* current_thread;
while((current_thread = schedule()))
{
printf("스레드 %d 실행 (우선순위: %d, 남은 CPU 점유 시간: %d)\n",
current_thread->id,
current_thread->priority,
current_thread->cpu_burst
);
current_thread->cpu_burst -= TIME_SLICE; // CPU 점유 시간 감소
if(current_thread->cpu_burst > 0)
{
recalculate_priority(current_thread); // 우선순위 재계산
enqueue(&queues[current_thread->priority], current_thread); // 다시 준비 큐에
}
}
printf("모든 스레드가 완료되었습니다!\n");
return 0;
}
C
복사
