운영체제 및 보안 - Lecture 5. cpu scheduling

세종대학교 - 운영체제 및 보안 수업

Process Scheduling

• Basic Concepts
• Scheduling Criteria
• Scheduling Algorithms
• Thread Scheduling
• Multiple-Processor Scheduling
• Real-Time CPU Scheduling

Objectives

• 멀티 프로그램 운영체제를 기반으로한 CPU 스케줄링 설명
• 다양한 CPU-스케줄링 알고리즘 설명
• 특정 시스템을 위한 CPU-스케줄링 알고리즘을 선택하는 평가 기준 설명
• 몇 몇 운영체제의 스케줄링 알고리즘 검사

기본 개념 (5.1.)

• 다중 프로그래밍의 목적 : CPU 이용률을 최대화

• CPU-I/O 버스트 사이클 (5.1.2.)

  • 프로세스 실행 : CPU 실행과 I/O 대기의 사이클로 구성

    

• CPU 버스트는 I/O 버스트를 따라감

• CPU 버스트의 분배가 주목표

CPU 스케줄러 (5.1.2.)

• short-term 스케줄러는 준비 큐에 있는 프로세스를 선택하여 cpu를 그 중 하나에 할당
  • (long-term과 구분)
  • 큐는 다양한 방법으로 정렬되어 있음 (PCB의 나열임)
• cpu 스케줄러의 결정은 프로세스가 아래와 같은 상태일 때 발생
  1. from running to waiting state → 실행 상태에서 입출력 대기 상태로 전환 (wait호출)
  2. from running to ready state → 실행 상태에서 준비 상태로 전환 (인터럽트 발생-타이밍 인터럽트 등)
  3. from wating to ready → 입출력 대기 상태에서 준비 상태
  4. terminate → 프로세스 종료할 때
• 스케줄링 1과 4는 선택의 여지가 없음 → 비선점 (nonpreemptive)
• 다른 스케줄링은 선점적 (preemptive)
  • 문제 (프로세스가 선점적으로 교체 될 때 문제 발생)
    • 공유된 데이터 접근 고려
    • 커널 모드일 때 선점성 고려
    • 중요 운영체제 활동 동안 발생한 인터럽트 고려

디스패쳐 (5.1.4.)

• 디스패쳐 모듈은 short-term 스케줄러에 의해 선택된 프로세스에 대한 cpu의 제어를 줌

  • 문맥 교환
  • 사용자 모드로 전환
  • 프로그램 재시작을 위해 사용자 프로그램의 적절한 위치로 이동(jump)

• 디스패치 지연 시간(latency)

  • (프로세스 교체 시간)
  • 하나의 프로세스를 정지하고 다른 하나의 실행을 시작하는데 디스패쳐가 소요되는 시간

스케줄링 기준 (5.2.)

• (cpu 스케줄링 알고리즘을 평가할 때 사용하는 기준)
• cpu 이용률
  • cpu를 가능한 바쁘게 유지하기
• Throughput (처리량)
  • 단위 시간 당 완료된 프로세스 개수
• Turnaround Time (총 처리 시간)
  • 특정 프로세스를 실행하는데 걸린 시간량
• 대기 시간
  • 준비큐에서 프로세스가 기다린 시간
• 응답 시간
  • 결과가 아니라 처음 요청을 받고 첫 응답까지 걸린 시간
  • (time-sharing 환경)

스케줄링 알고리즘 최적화 기준

• (아래 수치가 어떻게 되어야 좋은 스케줄링인지)
• cpu 이용률 최대화
• 처리량 극대화
• 총 처리 시간 최소화
• 대기 시간 최소화
• 응답 시간 최소화

First-Come First-Served (FCFS) 스케줄링 (5.3.1.)

• (선입 선출 스케줄링)

• 예시 : Process(Burst time)

  • P1(24), P2(3), P3(3)

  • P1, P2, P3 순으로 들어왔다면 아래와 같이 실행

    

  • 대기 시간 : P1 = 0, P2 = 24, P3 = 27

    • (할당된 시간 기준)

  • 평균 대기 시간 : (0 + 24 + 27 )/3 = 17

  • 만약 순서 바꿔서 들어왔으면

  • P2, P3, P1 순서

    

  • 대기 시간 : P1 = 6, P2 = 0, P3 = 3

  • 평균 대기 시간 : (6 + 0 + 3) / 3 = 3

  • 이전 보다 결과 좋음

  • convoy effect (호위 효과)

    • 긴 프로세스 뒤에 짧은 프로세스 → 총 대기 시간 길어짐
    • cpu-bound와 I/O-bound 프로세스 고려

Shortest-Job-First (SJF) 스케줄링 (5.3.2.)

• 다음 cpu burst 시간의 길이 (프로세스 총 길이가 아님)에 따라 프로세스 연관

  • 이 길이는 가장 짧은 시간을 가진 프로세스를 스케줄링 할 때 사용

• SJF 알고리즘이 최적이긴 함

  • 주어진 프로세스들 집합의 평균 대기 시간을 최소화
    • 다음 cpu burst 시간 길이 알기 쉽지 않음
      • (추가적인 정보 필요 → 스케줄러에 task 추가하는거랑 같음)
    • 사용자에게 물어볼 수 있음

• 예시

  • Process(Burst Time)

  • p1(6), p2(8), p3(7), p4(3)

    

  • 평균 대기 시간 = (3 + 16 + 9 + 0) / 4 = 7

다음 CPU Burst 길이 설정

• 길이 측정은 이전 것과 비슷하다고 생각

  • 그러면 가장 짧게 예측된 프로세스 선택

• 이전 cpu burst 길이를 사용할 수 있다면 지수적 평균 계산

  1. t(n) = n번째 cpu burst의 실제 길이
  2. τ(n+1) = 예측될 다음 cpu burst
  3. 𝛼, 0 ≤ 𝛼 ≤ 1 (가중치)
  4. Define : τ(n+1) = 𝛼 * t(n) + (1 - 𝛼) * τ(n)

• 보통 가중치는 1/2로 설정

• 선점적 방식은 shortest-remaining-time-first (SRTF)로 불림 ↔ SJF (non-preemtive)

Shortest-remaining-time-first (SRTF)

• 선점형 방식 적용 → 계속 현재 프로세스 burst 길이와 비교

• 예시

  • process(arrival time)(burst time)

  • p1(0)(8), p2(1)(4), p3(2)(9), p4(3)(5)

    

    → p2가 도착했을 때 burst time 4, p1 남은 burst time 7 따라서 뺏김

  • 평균 대기 시간 = [(10-1)+(1-1)+(17-2)+(5-3)]/4 = 6.5msec

    • ↔ 비선점형 SJF는 평균 대기시간 7.75mec

우선순위 스케줄링 (5.3.4.)

• 우선순위 숫자가 프로세스별로 포함

• 높은 우선순위 기준으로 프로세스 cpu에 할당 (작은 숫자 == 높은 우선순위)

  • 선점형
  • 비선점형

• SJF는 다음 cpu burst time을 예측한 값을 우선순위로 선정한 방식

• 기아 상태 (starvation)

  • 낮은 우선순위 프로세스 실행 안 될 수도 있는 문제점 발생

• 노화 (aging)

  • 시간 지날수록 우선순위 부여

• 예시

  • process(burst time)(priority)

  • p1(10)(3), p2(1)(1), p3(2)(4), p4(1)(5), p5(5)(2)

    

  • 평균 대기 시간 = 8.2 mesc

Round Robin (RR) (5.3.3.)

• 각 프로세스는 cpu 시간 할당량의 작은 단위(time quantum q)을 가짐. (대게 10-100 msec)

• 시간 지나면 프로세스가 선점적으로 레디큐의 끝에 더해짐

• n개의 프로세스, q는 time quantum, q타임을 유닛당 한번씩 갖게됨

• 어떤 프로세스도 (n-1) * q 시간 만큼 기다리지 않음.

• timer interrupt가 매 퀀텀마다 발생 (다음 프로세스 스케줄링을 위해)

• 성능

  • q가 크면 → FIFO
  • q가 작으면 → 문맥 전환 비용 증가

• 예시

  • p1(24), p2(3), p3(3)

    

  • SJF보다 전형적으로 높은 평균 처리량 가짐, 그러나 더 나은 응답

    • q는 문맥 전환 시간과 비교해서 커야함
    • q는 10에서 100msec, 문맥 전환은 10 usec보다 작음

time quantum과 문맥 전환 시간 (그림 5.5)

time quantum에 따른 처리 시간 (그림 5.6)

멀티레벨 큐

• 준비 큐는 foreground (interactvie)와 background (batch)로 나눠질 수 있다.
• 프로세스는 영구적으로 주어진 큐만 쓴다.
• 각 큐는 각 스케줄링 알고리즘을 가짐
  • foreground - RR
  • background - FCFS
• 스케줄링은 큐 사이에 반드시 수행
  • 고정된 우선순위 스케줄링 (foreground만 실행 가능) → starvation 발생 가능
  • 시간 쪼개기
    • 각 준비 큐는 확실한 cpu 시간을 할당 받아야함
      • 80% foreground, 20% background 식

멀티레벨 큐 스케줄링 (5.3.5.)

멀티레벨 피드백 큐 (5.3.6.)

• 프로세스는 다양한 큐 사이에서 움직일 수 있음 (↔ 멀티 레벨 큐는 다른 큐로 못 움직였음)

  • 예를 들어 aging 같은 경우 기아 상태 방지

• 멀티레벨-피드백-큐 스케줄러는 다음 매개변수에 의해 정의됨

  • 큐의 개수
  • 각 큐를 위한 스케줄링 알고리즘
  • 프로세스를 높은 우선순위 큐로 업그레이드하는 시기 결정하는 방법
  • 프로세스를 낮은 우선순위 큐로 강등시키는 (demote) 시기 결정하는 방법
  • 프로세스에 서비스가 필요해질 때 프로세스가 어떤 큐에 들어가야되는지 결정하는 방법

• 예시

  • Q0 - RR with time quantum 8 msec

  • Q1 - RR with time quantum 16 msec

  • Q2 - FCFS

  • 새로운 job이 FSFC인 Q0에 들어간다.

    • cpu를 얻으면, job은 8msec만큼 받는다.
    • 8msec안에 안 끝나면 Q에 들어간다.

  • Q1에서 job은 FSFC로 제공받고 16 msec만큼 받는다

    • 아직 안 끝나면 선제적이 되고 Q2로 간다.

    

• → 요약하면 처음에 높은 우선순위 큐에서 있던 job이 만약에 해당 cpu quantum 시간에 다 안 끝나면 다른 우선순위 낮은 큐들도 실행하기 위해 낮은 우선순위 큐로 이동시키는 방법(FSFC방식으로)
  • 멀티레벨 큐 : 한번 정한 큐에서만 계속 프로세스 준비
  • 멀티레벨 피드백 큐 : 다른 준비 큐의 실행을 위해 마무리 못한 프로세스는 다음 우선순위 준비 큐로 이동

스레드 스케줄링 (5.4.)

• 사용자 레벨과 커널 레벨 스레드로 구별
• 스케줄 되는 대상은 프로세스가 아니라 커널 수준 스레드 (최신 운영체제)
• 다대일, 다대다 모델, 스레드 라이브러리는 LWP에 스레드가 작동하도록 스케줄함
  • process-contention scope(PCS) (프로세스 경쟁 범위)로 알려짐
    • 프로세스 간 스케줄링 경쟁 때문에
  • 전형적으로 프로그래머에 의해 우선순위 가짐
• 사용 가능한 cpu에 스케줄된 커널 스레드는 system-contention scope (SCS)이다.
  • 시스템 내 모든 스레드간 경쟁

Pthread 스케줄링 (5.4.2.)

• api는 스레드 생성동안 PCS 또는 SCS 특징화함
  • PTHREAD_SCOPE_PROCESS는 PCS 스케줄링을 사용하면서 스레드를 스케줄한다.
  • PTHREAD_SCOPE_SYSTEM는 SCS 스케쥴링을 사용면서 스레드를 스케줄한다.
• 운영체제에 의해 제한 될 수 있다.
  • Linux와 Mac OS X는 PTHREAD_SCOPE_SYSTEM만 허용한다.

Pthread Scheduling API (그림 5.10)

#include <pthread.h>
#include <stdio.h>
#define NUM-THREADS 5

int main(int argc, char * argv []){
    int i, scope;
    pthread.t tid [NUM_THREADS];
    pthread_attr_t attr;

    / * get the default attributes * /
    pthread_attr_init (feattr);

    / * first inquire on the current scope * /
    if (pthread_attr_getscope(&attr, fescope) > = 0)
        fprintf(stderr, "Unable to get scheduling scope\n");
    else {
        if (scope == PTHREAD_SCOPE_PROCESS)
            printf ("PTHREAD_SCOPE_PROCESS");
        else if (scope == PTHREAD.SCOPE_SYSTEM)
            printf ( "PTHREAD_SCOPE_SYSTEM");
        else
            fprintf(stderr, "Illegal scope value.\n");
    }

    / * set the scheduling algorithm to PCS or SCS * /
    pthread_attr_setscope (feattr, PTHREAD_SCOPE_SYSTEM);

    / * create the threads * /
    for (i = 0; i < NUM-THREADS; i++)
        pthread.create(fetid[i],feattr,runner,NULL);
    / * now join on each thread * /
    for (i = 0; i < NUM-THREADS; i++)
        pthread-join(tid[i], NULL);
}

/ * Each thread will begin control in this function * /
void *runner(void * param){
    / * do some work ... * /
    pthread_exit(0);
}

다중 프로세서 스케줄링 (5.5.)

• cpu 스케줄링은 다중 cpu가 사용 가능할 때 더 복잡하다.
• 다중 프로세서 내의 Homogeneous processors
• asymmetric multiprocessing (비대칭 다중 처리기)
  • 하나의 프로세서가 시스템 데이터 구조체에 접근, 데이터 공유의 필요성을 배제
• symmetric multiprocessing (SMP) (대칭 다중 처리기)
  • 각 프로세서는 셀프 스케줄링할 수 있음
  • 각 프로세서의 스케줄러가 준비 큐를 검사, 실행할 스레드 선택하여 스케줄링 진행
    1. 모든 프로세스들은 공통 준비 큐에 존재
    2. 준비 프로세스에 각 개인적인 큐를 가짐
    • 대부분 공통 큐
• processor affinity (선호도) (5.5.4.)
  • 프로세스는 현재 작동하고 있는 프로세서에 대한 선호도를 가짐 (캐시 무효화 및 다시 채우는 비용 때문에)
    • soft 선호도
    • hard 선호도
    • 프로세서 집합을 포함한 다양성

NUMA와 cpu 스케줄링 (그림 5.16)

• Non-Uniform Memory Access
• 메모리 할당 알고리즘이 선호도 또한 고려

다중-프로세서 스케줄링 - Load Balancing (5.5.3.)

• SMP면, 모든 cpu들을 효율적으로 적재하는 것을 유지할 필요 있음
• Load balancing은 작업 적재를 공평하게 분산시키는 것을 시도한다.
• Push migration
  • 기한 있는 작업물은 각 프로세서의 적재를 확인한다.
  • 더 넘게 적재된 cpu에서 다른 cpu로 작업을 푸시하는 것을 찾는다.
• pull migration
  • idle 프로세서는 바쁜 프로세서에서 기다리고 있는 작업을 가져온다.

멀티 코어 프로세서 (5.5.2.)

• 최근 트랜드는 다중 프로세서 코어들을 같은 물리적 칩에 놓는 것이다.
• 빠르고 파워를 적게 씀
• 코어 당 다중 스레드들은 또한 자란다.
  • 메모리 검색이 수행되는 동안 메모리 스톨을 활용하여 다른 스레드에서 진행

Multithreaded Multicore System (그림 5.12) (그림 5.13)

Real-Time cpu 스케줄링 (5.6.)

• 명확한 도전 과제 제시 가능

• soft real-time 시스템

  • 중요한 실시간 프로세스가 예약 시점에 대한 보장 없음

• hard real-time 시스템

  • 마감시간 안에 무조건 작업이 수행되어야함

• 두 종류의 지연 시간이 성능에 영향을 줌

  1. 인터럽트 지연 시간

     • cpu에 인터럽트가 발생한 시점부터 인터럽트 처리 루틴이 시작하기까지의 시간

     • (cpu에 인터럽트 발생 → 인터럽트 종류 확인 → 문맥 교환 → 인터럽트 처리 루틴 시작)

       

  2. 디스패치 지연 시간

     • 현재 수행 중인 프로세스를 멈추고 다른 것으로 전환하는데 걸리는 시간

     

• 디스패치 지연시간의 구간 충돌

  1. 커널 모드에서 작동 중인 프로세스에 대한 선점
  2. 높은 우선순위 프로세스가 필요한 리소스를 낮은 프로세스가 방출

우선순위 기반 스케줄링 (5.6.2.)

• real-time 스케줄링을 위해, 스케줄러는 선점성과 우선순위 기반 스케줄링을 지원해야한다.

  • soft real-time만 보장한다.

• hard real-time은 반드시 마감시한을 만족하는 가능성을 제공해야함

• 프로세스는 새로운 특성을 가짐 : 일정한 간격으로 cpu를 필요로 하는 주기적인 프로세스

  • time t, deadline d, period p

  • 0 ≤ t ≤ d ≤ p

  • 주기적인 작업의 비율은 1/p

    

가상화와 스케줄링

• 가상화 소프트웨어는 cpu에 의해 다중 게스트로 스케줄된다.
• 각 게스트는 각각의 스케줄링을 수행
  • cpu를 소유하지 않은 것을 알지 못함
  • 부족한 응답 시간 결과
  • 게스트의 시간대 시계에 영향을 미칠 수 있다.
• 게스트의 좋은 스케쥴링 알고리즘 노력을 수행하지 않을 수 있다.

Rate Monotonic 스케줄링 (5.6.3.)

• 우선순위는 주기에 기반을 둔다.

• 짧은 주기 = 높은 우선순위, 주기 = 낮은 우선순위 (→ 더 자주 필요한 애 우선순위 부여)

• p1 은 p2보다 높은 우선순위 (아래와 같이 수행 하면 p1이 주기 안에 안 끝남)

  

• 아래와 같이 수행해야함

  

Rate Monotonic 스케쥴링에서 주기 놓침

Earliest Deadline First 스케줄링 (EDF) (5.6.4.)

• 우선순위가 마감 기한에 의해 정해짐

• 마감 기한이 빠를수록 우선순위 올라감

• 프로세스는 준비 상태가 되면 미리 마감시간을 알려야함

  

  • 주기마냥 다음 마감기한 증가

Proportional Share 스케줄링 (일정 비율 몫) (5.6.5.)

• 시스템의 모든 프로세스에 T개의 시간 몫이 할당됨
• 응용은 N개의 공유를 받음 (N < T)
• 각 응용이 전체 프로세서 시간의 N/T만큼을 받는 것을 보장
  • 지금까지 받은 몫이 총 몫보다 작아야하고 나중에 이걸 넘는 애가 들어오려고 하면 거부

POSIX Real-Time 스케줄링 (5.6.6.)

• POSIX.1b 확장 제공
• API는 real-time 스레드들 관리를 위한 함수 제공
• real-time 스레드를 위한 두가지 스케줄링 클래스를 정의
  • SCHED_FIFO
    • 스레드는 FIFO 큐에 FCFS 전략을 사용하며 스케줄됨
  • SCHED_RR
    • 위 클래스랑 비슷하지만 time-slicing이 발생 (동일 우선순위의 스레들 위해)
• 스케줄링 정책을 가져오고 정의하기 위해 두 가지 함수 정의
  • pthread attr getsched policy(pthread attr t *attr, int *porlicy)
  • pthread attr setsched policy(pthread attr t *attr, int *porlicy)

POSIX Real-Time 스케줄링 API (그림 5.25)

#include <pthread.h>
#include <stdio.h>

#define NUM-THREADS 5

int main(int argc, char * argv []){
    int i, policy;
    pthread.t tid [NUM_THREADS];
    pthread_attr_t attr;
    / * get the default attributes * /
    pthread_attr_init(feattr);
    / * get the current scheduling policy * /
    if (pthread_attr_getschedpolicy(&attr, fepolicy) ! = 0)
        fprintf(stderr, "Unable to get policy.\n");
    else {
        if (policy == SCHED_OTHER)
            printf("SCHED_0THER\n");
        else if (policy == SCHED.RR)
            printf ("SCHED_RR\n");
        else if (policy == SCHED_FIFO)
            printf ("SCHED_FIF0\n");
        }

    / * set the scheduling policy - FIFO, RR, or OTHER * /
    if (pthread_attr_setschedpolicy(&attr, SCHED-FIFO) ! = 0)
        fprintf(stderr, "Unable to set policy.\n");

    / * create the threads * /
    for (i = 0; i < NUM_THREADS; i++)
        pthread_create(fetid[i],feattr,runner,NULL);

    / * now join on each thread * /
    for (i = 0; i < NUM一THREADS; i++)
        pthread.join(tid[i], NULL);
}

/ * Each thread will begin control in this function * /
void * runner(void * param){
    / * do some work ... * /
    pthread_exit(0);
}

알고리즘 평가 (5.8.)

• 운영체제를 위한 cpu-스케줄링 알고리즘을 어떻게 선택할 것인가?

• 기준 설정, 그리고 알고리즘 평가

• 결정론적 모델링

  • 분석적 평가 종류
  • 미리 정해진 특정작업량을 사용하고 해당 작업량을 위한 각 알고리즘의 성능을 정의

• 5개의 프로세스가 시간 0에 도착했다고 고려

  • p1(10), p2(29), p3(3), p4(7), p5(12)

• 각 알고리즘에서 최소 평군 대기 시간 게산하기

• 간단하고 빠르고, 대신 정확한 숫자 요구되어야하고, 여기 있는 입력값만 적용

  

Queueing Modles (5.8.2.)

• 프로세스의 도착과 CPU 및 I/O 버스트를 확률적으로 설명합니다
  • 일반적으로 지수적이며 평균으로 설명됩니다
  • 평균 처리량, 활용도, 대기 시간 등을 계산합니다
• 대기 프로세스의 대기열이 있는 서버 네트워크로 기술되는 컴퓨터 시스템
  • 도착률 및 서비스 기준 파악하기
  • 사용률, 평균 대기열 길이, 평균 대기 시간 등을 계산합니다

Little’s Formula

• n = 평균 큐 길이
• W = 평균 큐 대기 시간
• 𝜆 = 평균 큐 도착 비율
• Little’s 법칙
  • 꾸준한 상태, 큐를 떠난 프로세스는 반드시 동일 프로세스 도착, n = 𝜆 * W
    • 모든 스케줄링 알고리즘 및 도착 배포에 유효
• 예시
  • 평균 7 프로세스가 초당 도착, 보통 14 프로세스가 큐에 있음, 평균 대기시간은 2초

simulations (5.8.3.)

• queueing model은 한계가 있음
• 모의 실험이 더 정확
  • 컴퓨터 시스템의 설계된 모델
  • clock은 변수
  • 알고리즘 성능을 가르키는 통계를 가짐
• 다음을 통해 수집된 시뮬레이션을 구동하기 위한 데이터
  • 확률에 따른 난수 생성기
  • 수학적 또는 경험적으로 정의된 분포
  • 추적 파일은 실제 시스템에서 실제 사건의 시퀀스를 기록

시뮬레이션에 의한 CPU 스케줄러 평가 (그림 5.31)