리눅스 커널의 이해 중에서 10장. 프로세스 스케줄링 이명수 시스템 소프트웨어 실험실

목 차 Part I : 스케줄링 정책 Part II : 스케줄링 알고리즘 Part III : 스케줄링과 관련한 시스템 콜 Part IV : Q & A

Part I : 스케줄링 정책

스케줄링 정책 스케줄링 정책(I) 정의 특징 다음에 실행할 프로세스를 선택하기 위한 과정 시분할 기법 사용 동적 우선순위가 높은 프로세스를 먼저 사용하도록 허용(preemptive) 우선권을 기반으로 스케줄러 알고리즘 수행

스케줄링 정책 스케줄링 정책(II) 제약 조건 공정성 효율성 빠른 응답 시간 짧은 프로세스 반응 시간 무한정 대기하는 프로세스의 보살핌 낮은 우선순위와 높은 우선순위 프로세스 사이의 중재 역할

스케줄링 정책 스케줄링 종류 방법에 따른 분류 선점 스케줄링 비선점 스케줄링 우선 순위가 높은 프로세스 실행 빠른 응답시간을 요구하는 시분할 시스템에 유용 문맥 교환의 횟수가 많음 높은 우선순위 프로세스들이 들어오는 경우 오버헤드를 초래 비선점 스케줄링 현재 실행 중인 프로세스를 선점하지 못함 모든 프로세스들에 있어 CPU사용기회를 동등하게 할당 문맥 교환의 횟수가 적음

스케줄링 정책 스케줄링 종류 스케줄링 알고리즘별 분류 우선순위 스케줄링 FIFO 스케줄링 다단계 피드백 큐 스케줄링 프로세스에게 우선순위를 부여 정적 우선순위 방법, 동적 우선순위 방법 FIFO 스케줄링 대기큐에 도착한 프로세스 순서대로 CPU 할당 짧은 작업시간의 프로세스가 오래 기다릴 위험 존재 중요한 작업이 중요하지 않은 작업때문에 기다릴 위험 존재 다단계 피드백 큐 스케줄링 입출력/CPU 위주의 프로세스의 특성에 따라 서로 다른 CPU 사용시간 부여 짧은 작업에 유리 입출력 위주의 작업에 우선권을 줌 SJT, SRT 스케줄링

스케줄링 정책 프로세스의 종류 입출력 위주의 프로세스 CPU 위주의 프로세스 상호 작용 프로세스 일괄 작업 프로세스 입출력 장치를 많이 이용하는 프로세스 CPU 위주의 프로세스 CPU를 많이 이용하는 프로세스 상호 작용 프로세스 사용자와의 인터페이스가 많은 프로세스 일괄 작업 프로세스 사용자와의 인터페이스를 필요로 하지 않은 프로세스 실시간 프로세스 지연시간이 없이 즉각적으로 수행되는 프로세스

스케줄링 정책 프로세스 선점 정의 선점된 프로세스 한 프로세스가 CPU사용도중 더 높은 우선순위의 프로세스에 의해 CPU의 사용권한을 자신의 의지에 상관없이 빼앗기는 일 프로세스 사용시간의 초과, 우선순위가 더 높은 프로세스 도착 선점된 프로세스 프로세스의 상태는 TASK_RUNNING 상태를 유지 단지 CPU를 사용하지 않을 뿐

스케줄링 정책 적절한 퀀텀의 지속 시간 짧은 지속 시간 긴 지속 시간 빈번한 작업 전환 작업 전환에 걸리는 시간이 많이 발생 다중 프로세스의 의미가 줄어 듬 시스템의 반응속도가 떨어짐

Part II : 스케줄링 알고리즘

스케줄링 알고리즘 타임 퀀텀 기본 타임 퀀텀 서로 다른 퀀텀 지속 시간 기본 타임 퀀텀값 프로세스마다 기본적으로 할당되는 CPU 사용시간 사용자는 자신이 실행시킨 프로세스의 기본 타임 퀀텀을 바꿀 수 있음 서로 다른 퀀텀 지속 시간 프로세스의 CPU사용시간에 따라 퀀텀 지속 시간을 다르게 할당 프로세스는 퀀텀 시간이 남아 있는 조건하에 스케줄러에 의해 여러 번 선택되어 실행될 수 있음 퀀텀시간을 모두 사용하였다면 타임 퀀텀을 재 설정 기본 타임 퀀텀값 #define DEF_PRIORITY (20*hz/100)

스케줄링 알고리즘 리눅스의 우선순위(Priority) 정적 우선 순위 동적 우선 순위 실시간 프로세스에게만 부여되는 값 스케줄러로 바꿀 수 없다. 동적 우선 순위 스케줄러가 각각의 프로세스에 지정한 우선순위 값 프로세스가 실행될 때 프로세스가 실행될 수 있는 시간

스케줄링 알고리즘 스케줄러가 사용하는 자료구조(I) 프로세스 디스크립터 스케줄링과 관련된 프로세스 디스크립터 필드(I) 프로세스의 현재 상태를 저장하고 있는 자료구조 스케줄링과 관련된 프로세스 디스크립터 필드(I) state 프로세스의 상태를 저장하는 플래그 TASK_RUNNING, TASK_STOPPED, TASK_ZOMBIE TASK_INTERRUPTIBLE, TASK_UNINTERRUPTIBLE need_resched 스케줄러 함수에 의해 다시 스케줄 할 필요성이 있는지를 저장하는 플래그 0과 0이 아닌 값 policy 해당 프로세스에 적용될 스케줄링 정책을 저장하는 플래그 SCHED_FIFO, SCHED_RR, SCHED_OTHER, SCHED_YIELD

스케줄링 알고리즘 스케줄러가 사용하는 자료구조(II) 스케줄링과 관련된 프로세스 디스크립터 필드(II) rt_priority 실시간 프로세스의 정적 우선순위를 저장하는 플래그 시스템 콜을 이용하여 변경이 가능 priority 일반 프로세스의 기본 타임 퀀텀을 저장하는 플래그 counter 프로세스의 퀀텀이 끝날 때 까지의 프로세스에 남은 CPU 사용 틱의 횟수 저장 부모로부터 새로운 프로세스 생성시 부모의 counter값을 반으로 나눈 후 자식에게 나누어 줌 mm 프로세스가 사용하던 메모리 디스크립터를 가리키는 플래그

스케줄링 알고리즘 schedule()(I) 호출되는 시기(I) 직접적인 호출 현재 프로세스를 블록 시켜야 할 경우 과정 현재 프로세스를 대기큐에 저장 프로세스 디시크립터의 state 클래그값을 TASK_INTERRUPTIBLE 또는 TASK_UNINTERRUPTIBLE 상태로 설정 Schedule()함수 호출 자원을 사용할 수 있으면 대기큐에서 제거, 아니면 자원을 사용할 수 있는지 검사

스케줄링 알고리즘 schedule()(II) 호출되는 시기(II) 우호적인 호출 현재 프로세스에서 재 스케줄링 해야 할 필요성이 있을 때( need_resched = !0 ) 현재 프로세스가 사용시간을 다 사용했을 때 Sleep상태의 프로세스가 깨어났는데, 현재 프로세스의 우선순위보다 우선순위가 높을때 시스템 콜을 호출했을 때( sched_setscheduler(), sched_yield() )

스케줄링 알고리즘 schedule()(II) 수행 과정(I) Prev = current Need_resched = 0 Prev->counter == 0 && Prev->policy == SCHED_RR YES Prev->state != TASK_RUNNING Prev->counter = prev->priority 실행큐의 가장뒤에 추가 NO Prev->state == TASK_INTERRUPTIBLE&& 필요한 자원을 기다리고 있는 상태인가? 실행큐에서 prev제거 YES 현재 프로세스의 우수성 검사 Prev->state = TASK_RUNNING

스케줄링 알고리즘 schedule()(II) 수행 과정(II) Prev->state == TASK_RUNNING NO YES Next = prev Prev->polich에 SCHED_YIELD 값이 포함되어 있는가? NO YES C = goodness(prev, prev) SCHED_YIELD값 제거 C = 0 C = -1000 Next = &init_task 다음에 실행할 프로세스 선택

Weight = goodness(prev, p) 스케줄링 알고리즘 schedule()(II) 수행 과정(II) P = init_task.next_run 실행큐에 있는 프로세스를 모두 검사 했는가? YES NO Weight = goodness(prev, p) Weight > c NO YES 문맥 교환 C = weight Next = p P = p->next_run

스케줄링 알고리즘 schedule()(II) 수행 과정(II) !C NO YES 모든 프로세스의 counter값 재 설정 이전에 실행된 프로세스와 실행될 프로세스가 같은가? NO 문맥 교환

스케줄링 알고리즘 goodness() 기능 반환값의 의미(I) 이전에 실행된 프로세스의 디스크립터와 평가하려는 프로세스의 디스크립터의 주소값을 인지로 받아서 평가하려는 프로세스의 우수성을 측정하여 반환 반환값의 의미(I) 반환되는 값이 클수록 다음에 실행될 확률이 높음 c = -1000 평가하려는 프로세스를 선택하지 않도록 함 실행큐에 스와퍼만 있을 때 반환됨 c = 0 평가하려는 프로세스는 자신에게 주어진 수행시간을 다 소비했음

스케줄링 알고리즘 goodness() 반환값의 의미(II) 0 < c = 1000 C >= 1000 평가하려는 프로세스는 아직 자신에게 주어진 시간을 다 소비하지 않았음 일반 프로세스가 이 범위에 속함 C >= 1000 평가하려는 프로세스는 실시간 프로세스이다. 다음에 실행될 확률이 높다. [그림 4-3] 인터럽트 핸들링(Page. 196)

스케줄링 알고리즘 goodness() 실행 과정 만일 실시간 프로세스이면 실행시간을 다 소비 했다면 1000 + 프로세스의 정적 우선 순위값 반환 실행시간을 다 소비 했다면 0값 반환 이전에 실행될 프로세스와 동일한 메모리 디스크립터를 가리킨다면 Counter + priority + 1(advantate value) 반환 위의 조건에 만족하지 않으면 Counter + priority 반환

스케줄링 알고리즘 리눅스/ SMP 스케줄러(I) 이상적인 프로세서 선택 자료구조(I) 현재 실행되는 프로세스가 이전에 실행되었던 프로세스이면서 CPU도 똑같은 프로세서이면 가장 이상적 캐시 실패의 횟수를 줄여줌 자료구조(I) Struct schedule_data{ struct task_struch* curr; unsigned long last_schedule; } Curr 현재 특정 CPU에서 실행되는 프로세스의 디스크립터를 가리킵 Last_schedule 스케줄러가 curr이 가리키는 프로세스를 실행할 프로세스로 선택한 시점

스케줄링 알고리즘 리눅스/ SMP 스케줄러(II) 자료구조(II) Cacheflush_time 이전에 실행된 프로세스가 다음에 다시 실행될 때 이전에 사용했던 CPU에서 사용할 지를 결정짓는 변수 현재 실행중인 프로세스의 평균 타임 슬라이드보다 크면 자신을 마지막으로 실행한 프로세스에서 다시 수행한다.

스케줄링 알고리즘 리눅스/ SMP 스케줄러(III) 스케줄링 특징 각각의 프로세서는 독립적으로 스케쥴러를 수행 각각의 프로세서마다 idle 프로세스가 존재 각 프로세스의 디스크립터에는 자신이 현재 실행되고 있는 프로세서 번호와 마지막으로 실행하였던 프로세서 번호를 저장 실행가능한 프로세스를 특정한 프로세서에서만 사용할 수 있도록 제한이 가능 스케줄러는 프로세스 디스크립터를 보고 특정한 프로세서에 프로세스를 할당할 수 있음

스케줄링 알고리즘 스케줄링 알고리즘 성능 단점 프로세스가 많아지면 원하는 성능을 기대하기 어려움 고성능 시스템에서는 타임 퀀텀값이 크게 느껴짐 입출력 위주의 프로세스 수행전략이 최선은 아님 실시간 응용프로그램 지원이 취약함

Part III : 스케줄링과 관련한 시스템 콜

시스템 콜 nice()(I) 프로세스 자신의 기본 우선 순위를 변경하는 시스템 콜 sys_nice() 서비스 루틴이 실행(I) 음수값 우선 순위를 높임 관리자 권한이 있을 때만 사용이 가능 양수값 우선 순위를 낮춤 일반 사용자 사용이 가능 절대값이 40을 넘으면 40이 되도록 조정

시스템 콜 nice()(II) sys_nice() 서비스 루틴이 실행(II) Increase = 0 Newprio = increment Increment < 0 YES 관리자 권한이 있는가? NO 무시 YES Newprio = -increment Increase = 1

시스템 콜 nice()(II) sys_nice() 서비스 루틴이 실행(II) NO Newprio > 40 YES (newprio*DEF_PRIORITY+10)/20 Newprio = 40 Increment = newprio Increment != 0 YES Increment = -increment

시스템 콜 nice()(III) sys_nice() 서비스 루틴이 실행(III) 변경한 우선순위값이 1보다 작은가? NO 변경한 우선순위값이 40보다큰가? NO YES YES Priority = 1 Priority = 40 Priority -= increment

시스템 콜 getpriority() setpriority() 일반 프로세스 그룹의 최대우선순위 값을 얻음 가장 높을 우선순위값에서 20을 더한 후 반환 Sys_getpriority()서비스 루틴 실행 setpriority() 일반 프로세스 그룹의 우선순위를 설정한다. Sys_setpriority()서비스 루틴 실행

시스템 콜 매개변수 Which Who Niceval 어떤 그룹에 속한 프로세스인지를 결정해줌 PRIO_PROCESS 프로세스 ID와 일치하는 프로세스 선택 PRIO_PGRP 그룹 ID와 일치하는 프로세스 선택 PRIO_USER 사용자 ID와 일치하는 프로세스 선택 Who 어떤 프로세스인지 결정해줌 0이면 현재 프로세스의 필드로 설정 Niceval 우선순위 값이 들어감

시스템 콜 Sched_getscheduler() Sched_setscheduler() 프로세스 스케줄링 정책을 얻는 함수 관리자 권한이 필요함 Pid 가 0이면 함수를 호출한 프로세스의 정책을 반환 Sched_setscheduler() 프로세스 스케줄링 정책과 우선순위를 설정한다. Pid가 0이면 함수를 호출한 프로세스에 정책을 설정

시스템 콜 Sched_getparam() Sched_setparam() 프로세스 스케줄링 우선순위를 얻는 함수 Pid가 0이면 현재 프로세스의 우선순위를 얻음 Sched_setparam() 함수를 사용해도 프로세스에 우선순위가 바뀌지 않음

시스템 콜 Sched_yield() Sched_rr_get_interval() 프로세스의 CPU사용을 반납 프로세스의 상태는 유지됨(TASK_RUNNING) CPU를 반납한 프로세스는 실행큐의 가장 뒤로 보내짐 Sched_rr_get_interval() 라운드 로빈 정책에서 타임 퀀텀을 얻는 함수 150ms라는 일정한 값을 반환함

시스템 콜 Sched_get_priority_min() Sched_get_priority_max() 스케줄링 정책에서 사용할 수 있는 실시간 정적 우선순위 최소값을 반환 현재 프로세스가 실시간이면 1을, 아니면 0을 반환 Sched_get_priority_max() 최대값을 반환 현재 프로세스가 실시간이면 99를, 아니면 0을 반환

Part IV : Q & A