운영체제 8주차

---

 

• Starvation: 낮은 우선순위를 가진 프로세스가 계속 실행되지 못함 → why? 우선 순위가 낮기 때문에 계속 대기 상태로 있었는데, ready queue에 우선 순위가 높은 프로스스가 계속 들어오면 starvation이 된다. 그래서 오랫동안 준비 큐에 대기하는 프로세스를 우선 순위를 점차적으로 증가시킨다.(Aging)

 

라운드 로빈(Round Robin, RR) 스케줄링

• 시분할(time sharing) 시스템을 위해 만들어졌다.

• 각 프로세스는 시간량(또는 시간 할당량, time slice, time quantum ← 이 용어도 알아둘 것) 동안 CPU를 할당받는다(보통 10~100 ms). 이 시간이 지나면 프로세스는 CPU를 빼았기고 Ready Queue에 들어간다.

• Ready Queue는 선입선출(FCFS) 방식의 큐.
  • 새로운 프로세스는 Ready Queue 끝에 들어간다.
  • 스케줄러는 큐의 맨 앞의 프로세스를 선택하여 CPU 할당

• OS는 타이머 인터럽트를 설정하여 주기적으로 인터럽트를 발생시킴. 인터럽트가 발생하면, OS가 실행되고 이때 스케줄러가 실행된다.

 

RR Example 1

라운드 로빈은 응답시간이 좋다? → 사용자가 프로그램 아이콘을 클릭하면 바로 웬만하면 바로 실행이 된다. 대화형 시스템에서는 응답시간이 중요하기 때문에, 대부분의 대화 시스템 OS에서는 라운드 로빈에 기반한 스케줄링을 채택하고 있다.

 

RR Example 2

• 프로세스가 도착하면 현재 준비큐에 맨 뒤에 가서 실행을 기다린다. 준비 큐에 들어가면 우선순위는 가장 마지막이다.

• 위 템플릿에서는 기본 CPU 할당 시간은 2초이며, 2초 이전에 프로세스가 종료되면, Ready Queue에 있는 최상위 우선순위에 있는 프로세스를 실행시킨다.

 

라운드 로비(RR) 스케줄링에서 시간 할당량을 어떻게 정할 것인가?

• 시간 할당량(time slice)가 크면 FCFS(선착순) 스케줄링 알고리즘이랑 거의 유사해진다. → Convoy effect(소요시간이 긴 프로세스가 먼저 도달하여 시간을 잡아먹고 있는 부정적인 현상)

• 시간 할당량이 적다면, 문맥 교환 부담이 증가한다.

• 연구 결과에 의하면, 대체적으로 CPU time slice를 10~100 ms 하면 적당하다고 밝혀졌고 대체적으로 CPU 버스트(실행시간)의 80%가 시간 할당량보다 짧은 것이 좋다.

 

 

• 프로세스의 실행은 CPU 실행과 입출력 대기가 반복되는 사이클이다. 즉, 프로세스의 실행은 CPU 버스트로 시작하고, 입출력 버스트가 발생되고, 다시 CPU 버스트가 발생하는 사이클 반복

• 대화식 시스템의 경우(대화식 시스템은 대부분 위 템플릿의 흐름대로 실행됨), 프로세스들의 CPU 버스트 시간 측정 결과
  • 짧은 CPU 버스트가 대부분
  • CPU를 매우 짧게 사용하고, 사용자와의 대화를 위한 입출력을 많이 하는 패턴

 

위 템플릿을 보면 알 수 있듯이 대부분의 CPU 버스트는 매우 짧다. 대부분 8ms보다 짧다. 그래서 CPU time slice 크기를 10ms 정도로 하면 대부분 프로세스는 CPU 시간이 짧기 때문에 그 전에 CPU를 내놓는다. (10ms 큰 프로세스들은 CPU를 빼앗기겠지만 몇 개 안 되므로 Context Switching 부담이 많이 줄어든다). 즉, 대부분의 프로세스는 CPU 버스트 시간이 10ms보다 작으므로 time slice 시간을 10ms로 설정한다. ⇒

연구 결과에 의하면, 대체적으로 CPU time slice를 10~100 ms 하면 적당하다고 밝혀졌고 대체적으로 CPU 버스트(실행시간)의 80%가 시간 할당량보다 짧은 것이 좋다.

 

 

다단계 큐(Multilevel Queue) 스케줄링: 여러 개의 큐

• 준비 큐를 여러 개의 큐로 나눈다
  • 지금까지 공부한 스케줄링은 모두 하나의 준비 큐를 가졌지만 다단계 큐 스케줄링은 큐가 여러 개로 나뉘어서 각 큐를 특정 목적에 맞게 사용한다.
  • 전면 작업(foreground job, 대화식): 빠른 응답시간을 요구함
  • 후면 작업(background job, 일괄처리(batch)): 응답시간은 상대적으로 중요도가 떨어지고, 순차적으로 처리만 되면 된다.

• 각 큐는 각자의 스케줄링 알고리즘을 가짐
  • foregroud: Round Robin 스케줄링
  • backgroud: FCFS

 

bactch process나 student process느 상대적으로 덜 중요하므로 FCFS 스케줄링으로 처리하고

대화식 프로세스와 시스템 프로세스는 Round Robin 스케줄링으로 처리하되, 큐에도 우선순위가 있다. 위 우선순위는 고정돼 있다. 즉, system process queue에 프로세스가 있을 때는 system process를 최우선으로 실행시키고, system process queue에 대기 중인 프로세스가 없을 때 그 하위인 interactive process를 실행시킨다. 또한, 만약에 3번째 큐의 interactive editing process가 실행되고 있는데 가장 우선순위가 높은 system processes queue에 시스템 프로세스가 새로 queuing 된다면 기존에 실행되던 프로세스는 CPU를 빼았기고, 시스템 프로세스에게 CPU를 할당한다 → 선점식(Preeempt)

• 고정된 우선순위의 선점식 스케줄링
  • 각 큐는 낮은 우선순위의 큐보다 절대적인 우선순위를 가진다.
    • 위의 큐가 비어야 아래 큐의 프로세스가 실행될 수 있고, 아래 큐의 프로세스가 실행되는 도중에 위의 큐에 프로세스가 들어오면 선점된다.
    • 문제점: 기아 상태(Starvation state)
  • 기아 상태의 해결: 각 큐는 CPU의 일정량의 받는다.
    • foregroud task는 CPU의 80%를 받고, background task는 CPU의 20%를 받음.

그런데 다단계 큐 스케줄링을 사용하려면 우선 프로세스를 어떤 큐에 배정할지를 미리 알아야 하지 않을까? 즉, 시스템 프로세스의 경우 시스템 프로세스 큐에 집어넣어야 할 테지만, 실제로 해당 프로세스가 시스템 프로세스인지 배치 프로세스인지 사전에 어떻게 알 수 있을까? → 다단계 피드백 큐 스케줄링

 

다단계 피드백 큐 스케줄링(Multilevel Feedback Queue)

• 다단계 큐 스케줄링에서는 프로세스들이 특정 큐에 배정되면 큐 사이를 이동하지는 않는다.
  • 다단계 피드백 큐 스케줄링은 프로세스가 큐 사이를 이동한다.
    • CPU를 많이 사용하는 프로스세는 낮은 우선순위 큐로 이동시킴 (CPU를 많이 사용하는 프로세스는 대화식 프로세스는 아니고, 계산이 많이 사용되는 일괄식 처리 프로세스)
    • 입출력 중심의 프로세스와 대화식 프로세스들을 높은 우선순위의 큐에 이동시킴(빠른 응답시간 제공)
    • 낮은 우선순위의 큐에서 오래 대기하는 프로세스들을 높은 우선순위 큐로 이동(기아 상태 예방, 에이징)
  • 가변식 우선순위 선점식 스케줄링
    • 프로세스가 큐를 이동하게 되면 우선순위가 변동됨
    • 위의 큐가 비어야 아래 큐의 프로세스가 실행될 수 있고, 아래 큐의 프로세스가 실행되는 도중에 위의 큐에 프로세스가 들어오면 선점된다. 즉, CPU를 빼앗긴다.

 

Queue 0, Queue 1: Round Robin

Queue1: FCFS

 

(부연) 각 큐에는 프로세스의 PCB가 연결되어 대기하고 있고, Queue 0에 제일 먼저 있는 프로세스가 CPU를 할당받아서 실행이 되면, time quantum이 8ms이므로 8ms가 끝나면 CPU를 빼았길 것이다. 여기서는 두 가지 상황이 발생할 수 있다. 해당 프로세스의 CPU 버스트가 8보다 클 경우 해당 프로세스의 PCB1은 아래 큐인 Queue 1로 이동할 것이고, 반대로 해당 프로세스의 CPU 버스트가 8초보다 작아서 CPU를 빼앗기기 전에 입출력이 발생해서 스스로 CPU를 반납하면 해당 프로세스의 PCB는 다시 Queue 0 마지막에 가서 위치한다. 즉 CPU 버스트 시간이 많을수록 실행될 때마다 우선순위가 낮은 하위 큐로 이동하게 되고, 하위 큐로 갈 때마다 CPU time quntum이 증가하는 것을 알 수 있다. 다시 말하면, 하위 큐에 있는 프로세스들은 CPU 실행시간이 많은 프로세스들이며, 제일 하위의 큐에 있는 프로세스들은 time quntum 제한을 두지 않고 그냥 선착순으로 프로세스를 실행시킨다.

다단계 큐 스케줄링은 사전에 프로세스들의 특성을 알아야 해서 많은 제한사항이 있었지만, 다단계 피드백 큐 스케줄링은 프로세스들의 특성을 사전에 아는 게 많은 제한사항이 따른다는 것을 인정하고 프로세스들이 실행될 때마다 프로세스의 특성별로 적절한 큐 자리로 찾아간다. 상위 큐(입출력을 많이 하는 큐), 하위 큐(CPU 파워를 많이 사용하는 큐)

⇒

가변식 우선순위 선점식

• 프로세스가 큐를 이동하게 되면 우선순위가 변동됨

• 위의 큐가 비어야 아래 큐의 프로세스가 실행될 수 있고, 아래 큐의 프로세스가 실행되는 도중에 위의 큐에 프로세스가 들어오면, 선점된다.(CPU를 빼앗긴다)

 

 

HRN(Highest Response-rate Next) 알고리즘

• SJF의 약점인 긴 프로세스와 짧은 프로세스의 불평들을 보안

• 가변적 우선순위의 비선점식 스케줄링
  • 우선순위가 높은 프로세스에게 CPU를 할당

    

• CPU burst가 짧을수록 우선순위가 높고, 오래 대기할수록 우선순위가 높다