CPU 스케줄링

목차

CPU 스케줄링

• CPU 스케줄링은 운영 체제가 여러 프로세스 또는 스레드가 CPU를 공유하여 사용할 수 있도록 관리하는 메커니즘입니다. CPU 스케줄링의 목적은 CPU 사용률을 최대화하고, 시스템 또는 사용자의 요구 사항에 맞춰 작업 처리 시간을 최적화하는 것입니다.

CPU bound process , I/O bound process

• 일반적으로 프로세스는 CPU 작업과 I/O 작업을 반복하며 실행됩니다. 
  • CPU 버스트(burst) : CPU를 이용하는 작업
  • I/O 버스트(burst) : I/O를 기다리는 작업
• 각 프로그램마다 CPU 버스트와 I/O 버스트가 차지하는 비율이 균일하지 않습니다. 그중 한 부분의 비율이 유독 높은 프로세스를 CPU Bound process와 I/O bound process라고 합니다.
  • CPU bound process
    • I/O 작업을 거의 수행하지 않아 CPU 버스트가 길게 나타나는 프로세스
    • CPU Bound 예시
      • 수학적 계산 : 대규모 수학적 연산, 복잡한 수학 문제 해결 등
      • 데이터 압축 : 파일이나 데이터의 압축 및 압축 해제 과정은 CPU를 집중적으로 사용합니다.
  • I/O bound process
    • I/O 요청이 빈번해 CPU 버스트가 짧게 나타나는 프로세스
    • 사용자로부터 interaction을 계속 받아가며 프로그램을 수행시키는 대화형 프로그램(interactive program)이 대표적
    • 짧은 CPU 버스트를 많이 가지고 있습니다.
    • CPU 스케줄링을 할때 I/O 바운드 프로세스의 우선순위를 높여주는 것이 바람직합니다.
      • I/O 바운드 프로세스의 경우 CPU를 잠깐만 사용하여 I/O작업을 실행합니다.
      • 만약 CPU 바운드 프로세스에게 CPU를 먼저 할당하면 그 프로세스는 CPU를 다 사용할 때까지 I/O 바운드 프로세스는 응답시간이 길어질 뿐 아니라 해당 I/O 장치도 그 시간 동안 작업을 수행하지 않는 상태가 되어버려 비효율적입니다.
    • IO Bound 예시
      • 파일 시스템 작업 : 디스크에서 큰 파일을 읽거나 쓰는 작업
      • 데이터베이스 쿼리 : 대용량 데이터베이스에서 쿼리를 실행하는 것은 IO Bound 작업
      • 웹페이지 로딩 : 서버로부터 웹 페이지를 로드하는 것은 네트워크 IO에 의존하므로 IO Bound에 속합니다.
      • 스트리밍 데이터 처리 : 실시간으로 데이터를 스트리밍 하는 경우, 네트워크 속도에 의해 성능이 제한될 수 있습니다.

디스패처(Dispatcher)

• CPU 스케줄러가 어떤 프로세스에게 CPU를 할당할지 결정하고나면 선택된 프로세스에게 CPU를 이양하는 작업이 필요합니다. 이때 새롭게 선택된 프로세스가 CPU를 할당받고 작업을 수행할 수 있도록 환경설정을 하는 운영체제의 코드를 디스패처(dispatcher)라고 부릅니다.
• 디스패처 과정
  • 현재 수행 중이던 프로세스의 문맥(context)를 해당 프로세스의 PCB에 저장하고, 새롭게 선택된 프로세스의 문맥을 PCB로부터 복원한 후(Context Switching) 해당 프로세스에게 CPU를 넘기는 과정을 수행합니다.(dispatch)
  • 새로운 프로세스의 문맥을 복원시킨 후에는 시스템의 상태를 사용자 모드로 전환해 사용자 프로그램에게 CPU의 제어권을 넘기게 됩니다.
  • 그러면 사용자프로그램은 복원된 문맥 중 프로그램 카운터로부터 현재 수행할 주소를 찾아 다시 해당 부분부터 코드를 실행합니다.
• 디스패처가 하나의 프로세스를 정지시키고 다른 프로세스에게 CPU를 전달하기까지 걸리는 시간을 디스패치 지연시간(dispatch latency)이라고 합니다. 디스패치 지연시간의 대부분은 컨텍스트 스위칭 오버헤드에 해당합니다.

CPU 스케줄링 방식(선점, 비선점)

• CPU 스케줄링 방식
  • 선점형(preemptive) 방식
    • 프로세스가 CPU를 계속 사용하기를 원하더라도 강제로 빼앗을 수 있는 스케줄링 방법입니다.
    • 더 급한 프로세스가 언제든 끼어들어 사용할 수 있기 때문에 한 프로세스의 자원 독점을 막고 프로세스들에 골고루 자원을 배분할 수 있다는 장점이 있습니다. 하지만 그만큼 컨텍스트 스위칭 과정에서 오버헤드가 발생할 수 있습니다.
    • 운영체제가 선점해서 해당 CPU를 빼앗아버릴수 있는 방법이라고 암기!
  • 비선점형(nonpreemptive) 방식
    • 프로세스가 CPU를 사용하고 있다면 해당 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까지는 다른 프로세스가 끼어들 수 없는 스케줄링 방식입니다. 
    • 컨텍스트 스위칭 횟수가 선점형 스케줄링보다 적기 때문에 오버헤드가 작게 발생합니다. 하지만 하나의 프로세스가 자원을 사용 중이라면 무작정 기다려야 하기 때문에 모든 프로세스가 골고루 자원을 사용할 수 없다는 단점이 있습니다.

스케줄링의 성능 평가

• 시스템 관점의 지표
  • CPU 이용률(CPU utilization)
    • 전체 시간 중에서 CPU가 일을 한 시간의 비율
  • 처리량(throughput)
    • 주어진 시간동안 준비 큐에서 기다리고 있는 프로세스 중 완료되는 프로세스의 개수입니다. (CPU 버스트를 완료한 프로세스의 개수)
    • 처리량을 높이기 위해서는 CPU버스트가 짧은 프로세스에게 우선적으로 CPU를 할당하는 것이 유리합니다.
• 사용자 관점의 지표
  • 소요 시간(Turnaround Time)
    • 한 프로세스 안에서 한 CPU 버스트가 끝날 때까지 걸린 시간
    • 한 CPU버스트 작업의 총 준비큐 대기시간 + 총 CPU버스트 작업 시간
    • 프로그램이 시작해서 종료하기까지 CPU 버스트는 여러 차례 있을 수 있고, 하나의 프로세스라도 소요시간은 CPU 버스트의 수만큼 각각 별도로 측정됩니다.
  • 대기 시간(Waiting Time)
    • 한 CPU 버스트 기간 중 프로세스가 준비 큐에서 CPU를 얻기 위해 기다린 시간의 합
    • 한 CPU버스트 작업의 총 준비큐 대기시간
    • 시분할 시스템에서는 일반적으로 타이머를 사용해 CPU 사용시간을 제한하기 때문에 한 번의 CPU 버스트 중에도 준비큐에서 기다린 시간이 여러 번 발생할 수 있습니다. 
  • 응답 시간(Response Time)
    • 한 CPU 버스트가 준비 큐에 들어온 후 첫번째 CPU를 획득하기까지 기다린 시간
    • 사용자가 요청을 시작한 후 첫 번째 응답을 받기까지의 시간입니다. 특히 대화형 시스템에서 응답 시간을 최소화하는 것이 중요합니다.
• 식당 비유를 통한 성능 척도들의 의미
  • 식당 사장님(시스템 관점), 손님(사용자 관점), 식당요리사(CPU), 한 손님팀이 주문한 음식들(CPU Burst)
    • 한 손님팀이 식당에 들어서고 나가는 순간이 한 CPU Burst입니다. (음식을 여러 개 주문하든 하나를 주문하든 한 CPU Burst)
  • 식당 사장님(시스템 관점)
    • 이용률 : 전체 영업시간 중 식당요리사가 일한 시간
    • 처리량 : 주어진 시간동안 식당요리사가 몇 손님팀의 주문을 처리했는지
  • 손님 (사용자 관점)
    • 소요시간 : 한 손님팀이 주문한 모든 음식들을 다 먹고 나가기까지 소요된 총 시간
    • 대기시간 : 한 손님팀이 소요시간에서 음식을 먹은 시간을 제외하고 순수하게 기다린 시간을 의미(여러 음식이 조금씩 여러 번에 걸쳐 나왔다면 음식을 먹은 시간을 제외하고, 각각의 음식이 나오기까지 기다린 시간을 합한 것이 대기시간)
    • 응답시간 : 한 손님팀이 최초의 음식이 나오기까지 기다린 시간

스케줄링 큐

• CPU를 사용하고 싶은 프로세스들 / 메모리에 적재되고 싶은 프로세스들 / 특정 입출력장치를 사용하고 싶은 프로세스들을 모두 스케줄링 큐로 관리합니다.
  • 운영체제가 관리하는 대부분의 자원은 큐로 관리됩니다.
• 큐의 종류
  • 준비 큐(ready queue)
    • CPU를 이용하고 싶은 프로세스들이 서는 줄
    • 준비 상태에 있는 프로세스들의 PCB는 준비 큐의 마지막에 삽입되어 CPU를 사용할 차례를 기다립니다.
      • 운영체제는 PCB들이 큐에 삽입된 순서대로 프로세스를 하니씩 거내어 실행하되, 그중 우선순위가 높은 프로세스를 먼저 실행합니다. 
  • 대기 큐(wating queue)
    • 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄
    • 같은 장치를 요구한 프로세스들은 같은 대기 큐에서 기다립니다. 
      • 하드 디스크 사용을 요구한 프로세스는 하드 디스크 큐에서 입출력 작업이 완료되기를 기다리고, 프린터 사용을 요구한 프로세스는 프린터 대기 큐에서 입출력 작업이 완료되기를 기다립니다.
      • 입출력이 완료되어 완료 인터럽트가 발생하면 운영체제는 대기 큐에서 작업이 완료된 PCB를 찾고, 이 PCB를 준비 상태로 변경한 뒤 대기 큐에서 제거합니다. 해당 PCB는 준비 큐로 이동합니다.
• 

CPU 스케줄링 알고리즘

선입선출 스케줄링(First-Come First-Served : FCFS)

• 프로세스가 준비 큐에 도착한 시간 순서대로 CPU를 할당하는 방식
• 비선점형 방식
  • 해당 프로세스가 CPU를 할당받으면 다른 누가 대기큐에 오더라도 CPU를 자진반납하기 전까지 CPU를 뺏기지 않습니다.
• 비효율적
  • CPU 버스트가 긴 프로세스 하나가 CPU 버스트가 짧은 프로세스 여러 개보다 먼저 도착했을 경우, CPU 버스트가 긴 프로세스가 끝나야지만 나머지 작업들이 처리 가능
    • 이런 현상을 콘보이 현상(Convoy effect)이라고 합니다. 
    • FCFS의 대표적인 단점
  • CPU 버스트가 긴 프로세스가 먼저 도착 → 평균 대기시간 길어짐
  • CPU 버스트가 짧은 프로세스가 먼저 도착 → 평균 대기시간 짧아짐
• 

최단작업 우선 스케줄링(Shortest-Job First : SJF)

• CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식
  • 평균 대기시간을 가장 짧게 하는 최적 알고리즘입니다.
  • FCFS에서 CPU 버스트 시간이 짧은 프로세스를 먼저 할당할 경우 평균 대기시간이 감소하였습니다. → SJF
• SJF는 비선점형, 선점형 두 가지 방식으로 구현됩니다.
  • 비선점형
    • 해당 프로세스가 CPU를 할당받으면 다른 누가 대기큐에 오더라도 CPU를 자진반납하기 전까지 CPU를 뺏기지 않습니다.
  • 선점형 
    • 선점형 방식의 SJF는 SRTF(Shortest Remaining Time First)라고 합니다.
    • 준비 큐에서 CPU 버스트가 더 짧은 프로세스가 도착할 경우 CPU를 빼앗아 더 짧은 프로세스에게 부여하는 방식입니다.
  • 
• SJF 방식의 가장 큰 어려운 부분은 프로세스의 CPU 버스트 시간을 미리 알 수 없습니다. 
  • 과거 CPU 버스트 시간을 통해 구한 예측 시간을 이용해야 합니다.
• SJF 알고리즘이 평균 대기시간을 최소화하는 알고리즘이지만, 이 방식에는 심각한 문제점이 있습니다. (기아 현상(starvation))
  • CPU 버스트가 짧은 프로세스에게만 CPU를 할당할 경우, CPU 버스트가 긴 프로세스는 준비 큐에 줄 서서 무한정 기다려야 하는 문제가 발생할 수 있습니다. (기아 현상(starvation)) (SJF 알고리즘의 심각한 문제점)
  • 예시
    • 프로세스 A의 CPU 버스트 시간이 1000인데 현재 준비 큐에 CPU 버스트가 10,20,30인 프로세스가 있습니다.
    • 그러면 프로세스 A는 위 세 프로세스가 모두 CPU를 사용한 후에 CPU를 할당받을 수 있습니다.
    • 하지만 CPU 버스트 30인 프로세스의 수행이 끝나기 직전 CPU 버스트가 100,200,300인 프로세스가 차례로 도착하게 되면 프로세스 A는 또 대기를 해야 합니다.
    • 이런 식으로 프로세스 A는 영원히 CPU를 할당받지 못할 수도 있습니다.
    • 이러한 현상을 기아 현상(starvation)이라고 하며 이는 SJF 알고리즘의 심각한 문제점입니다.

우선순위 스케줄링(Priority)

• 우선순위 스케줄링은 준비 큐에서 대기 중인 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식입니다.
  • 우선순위를 결정하는 방식에는 여러 가지가 있을 수 있습니다. (priority number이 작을수록 높은 우선순위)
  • CPU 버스트 시간을 우선순위 값으로 정의하면 SJF 알고리즘과 동일한 의미를 가지게 됩니다.
• 우선순위 스케줄링도 비선점형, 선점형 두 가지 방식으로 구현됩니다.
  • 비선점형
    • 해당 프로세스가 CPU를 할당받으면 다른 누가 대기큐에 오더라도 CPU를 자진반납하기 전까지 CPU를 뺏기지 않습니다.
  • 선점형
    • 현재 CPU에서 수행 중인 프로세스보다 우선순위가 높은 프로세스가 대기 큐에 도착하면 해당 프로세스가 CPU를 빼앗을 수 있습니다.
• 우선순위 스케줄링 역시 SJF와 마찬가지로 기아현상이 발생할 수 있습니다. (우선순위가 높은 프로세스가 계속해서 도착하여 우선순위가 낮은 프로세스는 계속해서 CPU를 얻지 못할 수 있습니다.)
  • 이러한 현상을 해결하기 위해 노화(aging) 기법을 사용할 수 있습니다.
    • 에이징 기법은 기다리는 시간이 길어지면 우선순위를 조금씩 높여, 언젠가는 가장 높은 우선순위가 되어 CPU를 할당받을 수 있게 해주는 방법입니다.
    • 나이가 드신 분에게 자리를 양보하는 것이라고 생각하면 됩니다.

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

• 라운드 로빈 스케줄링은 각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간을 특정시간으로 제한하는 방식입니다.
  • CPU를 할당받은 프로세스가 정해진 시간이 경과하면 CPU를 회수해 다음 프로세스에게 할당하고 기존 프로세스는 준비큐에 다시 넣어줍니다.
  • 만약 CPU 버스트 시간이 할당시간보다 짧으면 CPU를 자신의 버스트 시간만큼만 사용한 후 스스로 반납합니다.
• 각 프로세스마다 한 번에 CPU를 연속적으로 사용할 수 있는 최대시간을 할당시간(time quantum)이라고 합니다.
  • 할당시간이 너무 길면 결국에는 FCFS가 됩니다. (할당 시간이 없는 RR = FCFS)
  • 반면 할당시간이 너무 짧으면 프로세스를 너무 빈번하게 교환해 컨텍스트스위칭의 오버헤드가 커지게 됩니다.
  • 적당한 시간설정이 중요합니다.
  • 할당시간이 만료되어 CPU를 회수하는 방법은 타이머 인터럽트를 사용합니다.
• 선점형 방식
• FCFS vs RR
  
  • CPU 버스트 시간이 10인 프로세스 10개에 대해서 FCFS와 RR방식을 비교하겠습니다. (모든 프로세스는 시각 0에 대기 큐에 딱 도착한 상태)
  • FCFS
    • 소요시간
      • P1 : 10 / P2 : 20 / P3 : 30 / P4 :40 / ... / P10 : 100
      • 평균 : 55
    • 대기시간
      • P1 : 0 / P2 : 10 / P3 : 20 / P4 :30 / ... / P10 : 90
      • 평균 : 45
    • 응답시간
      • P1 : 0 / P2 : 10 / P3 : 20 / P4 :30 / ... / P10 : 90
      • 평균 : 45
  • RR
    • 소요시간
      • P1 : 100 / P2 : 100 / P3 : 100 / P4 :100 / ... / P10 : 100
      • 평균 : 100
    • 대기시간
      • P1 : 90 / P2 : 90 / P3 : 90 / P4 :90 / ... / P10 : 90
      • 평균 : 90
    • 응답시간
      • P1 : 0 / P2 : 할당시간*1 / P3 : 할당시간*2 / P4 : 할당시간*3 / ... / P10 : 할당시간*9
      • 평균 : 할당시간*4.5
      • 할당시간은 거의 수십 밀리초로 매우 작으므로 응답시간은 대부분 0에 가까울 것입니다.
      • 대부분의 프로그램이 동시에 작동하는 것처럼 보일 것입니다.
  • 응답시간이 중요하다면(예를 들면 대화형 작업) Round Robin 방식을 사용하고, 계산 시간이 중요하다면 FCFS방식을 사용합니다. (라운드 로빈 방식은 컨텍스트 스위칭 비용으로 인해 다소 느려질 수 있습니다.)

멀티레벨 큐(Multilevel Queue : MQ)

• 준비 큐를 여러 개로 분할해 관리하는 방식입니다.
  • 즉, 프로세스들이 CPU를 기다리기 위해 한 줄로 서는 것이 아니라 여러 줄로 서는 것입니다.
  • 하지만 이러한 방식은 추가적으로 고려해야 할 문제가 생깁니다.
    • CPU는 하나밖에 없으므로, 이 경우 어떤 줄에 서있는 프로세스를 우선적으로 스케줄링할 것인가 하는 추가적인 문제가 발생합니다.
    • 또한, 프로세스가 도착했을 때 어느 줄에 세워야 할지도 정해줘야 합니다.
• 일반적으로 멀티레벨 큐에서 준비 큐는 대화형 작업을 담기 위한 전위 큐(foreground queue)와 계산 위주의 작업을 담기 위한 후위 큐(background queue)로 분할하여 운영됩니다.
  • 전위 큐(foreground queue)
    • 전위 큐에서는 응답시간을 짧게 하기 위해 라운드 로빈 스케줄링을 사용
  • 후위 큐(background queue)
    • 계산 위주의 작업을 위한 후위 큐에서는 응답시간이 큰 의미를 가지지 않기 때문에 FCFS 스케줄링 기법을 사용해 문맥교환 오버헤드를 줄이도록 함
  • 
• 어느 줄에 세워야 할지는 정했지만, 어떤 줄에 서있는 프로세스를 우선적으로 스케줄링할지는 정해지지 않았습니다. 전위 큐, 후위 큐 멀티 레벨 큐에서는 보통 고정 우선순위 방식과 타임 슬라이스 방식을 적용합니다.
  • 후위 큐에 있는 프로세스 보다 전위 큐에 있는 프로세스에게 우선적으로 CPU를 할당합니다. (대화형 작업에서는 응답시간이 중요하기 때문입니다.) [고정 우선순위 방식]
  • 그러나 이렇게만 할 경우 기아문제가 발생해 후위 큐는 작업이 진행되지 않을 수가 있습니다. 따라서 타임 슬라이스 방식으로 각 큐에 CPU 시간을 적절한 비율로 배치합니다. 예를 들면 전체 CPU 시간 중 전위 큐에 80%, 후위 큐에 20%를 할당해 스케줄링을 해줄 수 있습니다. [타임 슬라이스 방식]

멀티레벨 피드백 큐(Multilevel Feedback Queue : MFQ)

• 멀티레벨 피드백 큐는 CPU를 기다리는 프로세스를 여러 큐에 세운다는 측면에서 멀티레벨 큐와 동일하나, 프로세스가 하나의 큐에서 다른 큐로 이동 가능하다는 점이 다릅니다.
  • 예를 들어 우선순위 스케줄링에서 기아 현상을 해결하기 위해 등장했던 에이징 기법을 멀티레벨 피드백 큐 방식으로 구현할 수 있습니다.
• 멀티레벨 피드백 큐를 정의하는 요소들
  • 큐의 수
  • 각 큐의 스케줄링 알고리즘
  • 프로세스를 상위 큐로 승격시키는 기준
  • 프로세스를 하위 큐로 강등시키는 기준
  • 프로세스가 도착했을 때 들어갈 큐를 결정하는 기준
• 멀티레벨 피드백 큐의 대표적인 방식
  • 
  • 상위에 있는 큐일수록 우선순위가 높습니다.
  • 순서
    • 가장 먼저 프로세스가 준비 큐에 도착하면 우선순위가 가장 높은 큐에 줄을 섭니다. 이럴 경우 CPU 사용시간이 짧은 대화형 프로세스들은 우선순위가 가장 높은 큐에서 빨리 서비스받고 작업을 완료할 수 있습니다. 
    • CPU 버스트 시간이 긴 프로세스들은 5만큼의 시간 동안 CPU를 사용하고도 작업을 완료할 수 없기 때문에 할당시간이 10인 하위 큐로 내려가서 줄을 서게 됩니다.
    • 이후 하위 큐에서 본인 차례가 되면 할당시간 10을 추가로 사용하여 진행합니다. 여기서도 작업이 완료되지 않으면 해당 작업은 CPU를 오래 사용하는 계산 위주의 프로세스로 간주하여 최하위 큐로 이동하게 되고 FCFS 스케줄링을 적용받게 됩니다.
    • 큐에 대한 스케줄링 방식으로는 최상위 큐가 우선적으로 CPU를 배당받고, 상위 큐가 비었을 때만 하위 큐에 있는 프로세스들이 CPU를 할당받을 수 있게 됩니다.
    • 이러한 방식은 라운드 로빈 스케줄링을 한층 더 발전시켜, 프로세스의 CPU 작업 시간을 다단계로 분류함으로써 작업시간이 짧은 프로세스일수록 더욱 빠른 서비스가 가능하도록 하고, 작업시간이 긴 프로세스에 대해서는 문맥교환 없이 CPU 작업만 열중할 수 있는 FCFS 방식을 채택할 수 있습니다.

다중처리기 스케줄링(Multi-processor system)

• CPU가 여러 개인 시스템을 다중처리기 시스템(multi-processor system)이라고 부릅니다. 
• CPU가 여러 개이기 때문에 CPU가 한 개인 시스템에서보다 복잡합니다.
  • 먼저, 그냥 단순히 모든 프로세스를 준비 큐에 한 줄로 세워서 각 CPU가 알아서 다음 프로세스를 꺼내가는 방식이 있습니다. (은행창구에서 번호표를 통해 번호 순서대로 고객을 부르는 방식)
    • 공유하는 준비 큐에서 경쟁 상태(Race Condition)가 생길 수 있습니다. 
  • 다른 방식으로는 각 CPU별로 줄을 세우는 경우입니다. (미용실에서 특정 헤어디자이너만을 원하는 손님들이 있을 수 있습니다. 이럴 경우 헤어디자이너별로 예약을 받습니다.)
    • 이럴 경우 문제는 일부 CPU에 작업이 편중되는 현상이 발생할 수 있습니다. (인기 많은 헤어디자이너만 예약이 엄청 많아짐)
    • 이런 현상을 방지하기 위한 각 CPU별 부하가 적절히 분산되도록 하는 부하균형(Load Balancing) 메커니즘을 필요로 합니다.
• 다중처리기 스케줄링을 위한 몇 가지 기법
  • 대칭형 멀티프로세싱(SMP, Symmetric Multiprocessing)
    • 모든 CPU 코어가 동일한 작업 큐에 접근하여 작업을 가져갑니다. 
    • 구현이 간단하지만, 모든 코어가 하나의 작업 큐에 접근해야 하기 때문에 큐에 대한 접근을 동기화하는 데 있어 오버헤드가 발생할 수 있습니다.
    • 사용 예시
      • 웹 서버: 대규모의 동시 요청을 처리해야 하는 웹 서버는 SMP 모델을 통해 모든 코어가 요청 처리에 참여하게 할 수 있습니다. 이렇게 하면 요청 처리 속도를 극대화할 수 있습니다.
      • 데이터베이스 시스템: 동시에 많은 쿼리를 처리해야 하는 데이터베이스 시스템에서도 SMP 방식이 유용합니다. 모든 코어가 쿼리 처리에 참여함으로써, 전체 시스템의 처리량을 증가시킬 수 있습니다.
  • 비대칭형 멀티프로세싱(AMP, Asymmetric Multiprocessing)
    • 한 CPU 코어(또는 소수의 코어)가 시스템 전체를 관리하고 스케줄링을 담당하는 방식입니다.
    • 이 방식은 관리가 간단하지만, 관리 코어에 병목 현상이 발생할 수 있습니다.
    • 사용 예시
      • 임베디드 시스템: 특정 임베디드 시스템에서는 한 코어가 시스템 관리와 통제를 담당하고, 나머지 코어가 실시간 데이터 처리 같은 특정 작업을 전담하는 AMP 방식을 사용할 수 있습니다.
      • 게임 서버: 게임 서버에서 한 코어가 네트워크 통신과 세션 관리를 담당하고, 다른 코어가 게임 로직 처리나 물리 계산을 담당하는 경우 AMP 방식을 적용할 수 있습니다.
  • 캐시 친화성(Cache Affinity)
    • 프로세스가 이전에 실행되었던 같은 CPU 코어에 다시 할당되도록 합니다.
    • 이 방식은 캐시 재사용을 극대화하여 성능을 향상시킬 수 있지만, 부하 균형을 해치는 원인이 될 수 있습니다.
    • 사용 예시
      • 반복적인 큰 데이터세트 처리 : 반복적으로 큰 데이터 세트를 처리할 때 이전에 실행했던 코어에 다시 할당함으로써 캐시의 재사용률을 높이고, 전체 실행 시간을 단축할 수 있습니다.
  • 작업 도둑질(Work Stealing)
    • 유후 상태의 코어가 다른 코어의 작업 큐에서 작업을 "도둑질"하여 수행하는 기법입니다.
    • 이 방식은 부하 균형을 유지하면서도 유휴 상태의 코어를 최소화할 수 있습니다.
    • 사용 예시
      • 병렬 프로그래밍 프레임워크: Java의 Fork/Join 프레임워크는 내부적으로 작업 도둑질 알고리즘을 사용하여, 가용한 모든 코어가 효율적으로 작업을 처리할 수 있도록 합니다. 이를 통해 유휴 상태의 코어 없이, 모든 작업을 효율적으로 분산시키고 처리할 수 있습니다.
        
        • 포크/조인 프레임워크의 처리 방식
          • 포크/조인 프레임워크는 병렬화할 수 있는 작업을 재귀적으로 작은 작업으로 분할한 다음에 서브태스크 각각의 결과를 합쳐서 전체 결과를 만들도록 설계
            1. Fork(분할): 큰 태스크가 시작될 때, 그것을 처리할 수 있는 더 작은 단위의 서브태스크로 나눕니다. 이 분할은 태스크가 충분히 작아질 때까지 재귀적으로 발생할 수 있습니다.
            2. 작업 실행: 분할된 각 서브태스크는 병렬로 실행됩니다. 이때 Java의 Fork/Join 프레임워크는 내부적으로 '작업 도둑질(Work Stealing)' 알고리즘을 사용하여, 유휴 상태인 스레드가 다른 스레드의 작업 큐에서 대기 중인 태스크를 가져와 실행하게 함으로써, 모든 CPU 코어가 효율적으로 활용되도록 합니다.
            3. Join(결합): 분할된 태스크의 실행이 완료되면, 그 결과는 다시 합쳐집니다. 이렇게 하여 최종적으로 원래 태스크의 결과가 도출됩니다.

실시간 시스템 스케줄링(Real-time system)

• 일반적으로 시분할 시스템에서 특정 시간 이내에 처리를 하지 못했다고 심각한 상황이 발생하지는 않습니다.(작업에 데드라인이 존재하지 않습니다.) 하지만 실시간 시스템(Real-time system)에서는 각 작업마다 주어진 데드라인이 있어 정해진 데드라인 안에 반드시 작업을 처리해야 합니다.
• 실시간 시스템은 hard real-time system과 soft real-time system으로 나눌 수 있습니다.
  • hard real-time system
    • hard real-time system은 미사일 발사, 원자로 제어 등 시간을 정확히 지켜야 하는 시스템을 말합니다.
    • 이러한 시스템에서는 정해진 시간 안에 반드시 작업이 완료되도록 스케줄링해야 합니다.
  • soft real time system
    • 데드라인이 존재하기는 하지만 데드라인을 지키지 못했다고 해서 위험한 상황이 발생하지는 않습니다.
    • 멀티미디어 스트리밍 시스템이 soft real time system의 대표적인 예
    • VOD 방식으로 영화를 볼 경우 시간당 정해진 프레임 수만큼의 서비스가 이루어지지 않으면 화면이 중간에 끊기는 현상이 발생하는 것입니다.
    • 그러나 데드라인이 지켜지지 않았다고 해서 시스템이 붕괴되거나 치명적인 결과를 초래하지는 않습니다.
• 실시간 환경에서의 스케줄링은 빠른 서비스도 중요하지만 반드시 데드라인을 지키는 서비스가 더욱 중요합니다.
  • 따라서 실시간 환경에서 먼저 온요청을 먼저 처리하기보다는 데드라인이 얼마 남지 않은 요청을 먼저 처리하는 EDF(Earlist Deadline First) 스케줄링을 널리 사용합니다.
  • 일반작업과 VOD 작업(soft real-time system) 등이 혼합된 환경에서는 VOD 등 데드라인이 존재하는 프로세스에게 일반 프로세스보다 높은 우선순위를 할당하는 방식도 사용되고 있습니다.

스케줄링 알고리즘의 평가

• 스케줄링 알고리즘의 성능을 평가하는 방법으로는 큐잉모델(queueing model), 구현 및 실측(implementation & measurement) , 시뮬레이션(simulation) 방식이 있습니다.
  • 큐잉 모델
    • 주로 이론가들이 수행하는 방식으로 확률분포를 통해 프로세스들의 도착률과 CPU의 처리율을 입력값으로 주면 복잡한 수학적 계산을 통해 각종 성능지표(performance index)인 CPU의 처리량, 프로세스의 평균 대기시간 등을 구하게 됩니다.
  • 구현 및 실측
    • 이론가와 정반대인 구현가들이 수행할 수 있는 방식으로, 운영체제 커널의 소스 코드 중 CPU 스케줄링을 수행하는 코드를 수정해서 커널을 컴파일한 후 시스템에 설치하는 과정을 필요로 합니다.
    • 그런 다음 동일한 프로그램을 원래 커널과 CPU 스케줄러를 수정한 커널에서 수행시켜 보고 실행시간을 측정하여 알고리즘의 성능을 평가합니다.
  • 시뮬레이션
    • 실제 시스템에 구현해 수행시켜 보는 것이 아니라 가상으로 CPU스케줄링 프로그램을 작성한 후 프로그램의 CPU 요청을 입력값으로 넣어 어떠한 결과가 나오는지를 확인하는 방법입니다.
    • 입력값은 가상으로 생성할 수도 있고 실제 시스템에서의 CPU 요청 내역을 추출해 사용할 수 도 있습니다.
      • 이때 실제 시스템에서 추출한 입력값을 트레이스(trace)라고 부릅니다.
      • 트레이스는 몇 초에 어떤 프로세스가 도착하고, 각각 CPU 버스트 시간을 얼마로 하는지에 대한 정보를 시간 순서대로 적어놓은 파일을 말합니다.

출처

• 혼자 공부하는 컴퓨터 구조+운영체제