박시은

(❁´◡`❁)

4 분 소요


1. Thread 스케줄링

1.1 쓰레드

  • 쓰레드는 유저 레벨과 커널 레벨로 구분한다.
  • 시스템에서 쓰레드를 지원할 경우, 프로세스가 아닌 쓰레드를 스케줄링한다.
  • 쓰레드에 자세히 알고 싶다면?


1.2 쓰레드 스케줄링 경쟁 범위

PCS와 SCS는 프로세스가 경쟁하는 범위의 차이로 구분한다.

  • PCS (Process-Contention Scope)
    • 프로세스 내에서 쓰레드끼리 경쟁한다.
  • SCS (System-Contention Scope)
    • 전체 시스템 내에서 쓰레드끼리 경쟁한다.



2. 다중 프로세서 스케줄링

2.1 다중 프로세서 스케줄링의 종류

비대칭 다중처리

  • master 프로세서 혼자 모든 자료구조를 관리한다. (병목현상이 발생)
  • master 프로세서(대장)이 죽으면 다 죽음!!!


대칭 다중처리 (SMP)


2.2 SMP Queue 구조

모든 프로세스가 하나의 Ready Queue에 들어가 있는 방식

하나의 Queue에서 여러 개의 core 중 뭐를 가지고 와서 서빙을 할지 경쟁하고 있는 상황


Per - Queue : 프로세스가 각 코어의 독립된 큐에 들어가 있는 방식


Per-Core Queue 특징

  • ① Affinity(친화성)
    • 특정 Core에서만 Task가 수행되도록 하는 것이다. (이 task는 core랑 친하다!)
    • Load Balancing을 하지 않는다. (메모리 멈춤 현상 방지책)
    • Affinity 기능을 통해, Cache Hit 확률을 높일 수 있다.
    • 따라서, Affinity 적용시 메모리 멈춤 현상을 최소화할 수 있다.

  • ② Load Balancing (부하 균등)
    • Core 당 할당된 Task 개수가 같게끔 맞추는 것을 말한다. (균형을 맞춘다.)
    • 특정한 CPU만이 많이 일하거나, 특정한 CPU가 놀지 않는 경우가 없도록 한다.
    • 부하 균등의 문제점
      • 부하 균등을 하고자 Task를 다른 Core로 옮기면 ⇒ Cache Miss 가 높아진다.
      • Cache Miss가 발생하면, 메모리 멈춤 현상 (Memory Stalling) 이 발생한다.
        • 메모리 멈춤 현상: 데이터를 가져오느라 프로세서가 idle상태에 놓이는 것
    • 부하 균등의 방식
      • 푸시 이주 (Push Migration)
        • 개별 프로세서에 대한 부하를 주기적으로 확인한다.
        • 특별히 많은 부하가 걸린 CPU가 있으면 다른 CPU로 부하를 분산한다.
        • 😠팀장이 열받으면 일 너가해!! 하고 push
      • 풀 이주 (Pull Migration)
        • 놀고 있는(Idle 상태의) CPU들이 바쁜 프로세서들의 Task를 가지고 온다.
        • 🥹팀장이 일 다 하고있어. 그럼 일 가져오는거



3. 멀티코어 프로세서

하나의 쓰레드가 메모리 탐색을 위해 Stall (메모리 멈춤) 되었을 때, 다른 쓰레드가 일하게 만들어서 효율을 더 올릴 수 있다

  • 단일 쓰레드일 때

  • 다중 쓰레드일 때

    • stall 될 때마다, 다른 쓰레드의 연산을 수행한다.



4. Real-Time CPU Scheduling

4.1 실시간 CPU 스케줄링이란?

Real-Time CPU Scheduling (실시간 CPU 스케줄링)

Deadline안에 task를 완수해야하는 시스템에 사용되는 스케줄링 방식이다.


4.2 실시간 시스템의 종류

연성 실시간 시스템 (Soft real-time systems)

  • 비교적 엄격하지 않은 조건
  • 경우에 따라, Task 처리 데드라인에 못 맞출 수도 있다.
  • 📞조금 처리가 부족해서 안녕하세요! 라고 출력되야 하는 것이 안냐세여 라고 출력
  • e.g., 이동 통신 시스템 (LTE)


강성 실시간 시스템 (Hard real-time systems)

  • 매우 엄격한 조건
  • 무조건 Task 처리 데드라인에 맞추는 것을 목표로 한다.
  • e.g., 미사일 시스템, 자율주행 자동차


4.3 실시간 시스템의 주요 개념

Interrupt Latency

인터럽트 발생부터 ISR 실행까지의 시간을 말한다.


Dispatch Latency

  • 디스패처가 수행되는데 걸리는 시간을 말한다.
  • conflicts 와 dispatch 시간의 합을 말한다.



5. Rate Montonic 스케줄링

선점형 정적 우선순위 스케줄링을 이용하는 스케줄링 방법이다.

  • 주기가 짧은 Task = 높은 우선순위
  • 주기가 긴 Task = 낮은 우선순위


  • 1년에 연봉을 1번만 받는 상황과, 한달의 한 번씩 월급을 받아야 하는 상황이면 전자가 낮은 우선순위
  • 가끔 해줘야 하는 애들은 우선순위가 낮다는 것임



6. EDF 스케줄링

Earliest Deadline First Scheduling (EDF)

  • Deadline이 바로 앞에있는 아이부터 스케줄링 해주는 기법이다.
  • 실시간 스케줄링에서 주로 사용하는 방식이다.
  • Deadline이 많이 남아 있으면 우선 순위를 낮춰서 처리해줘도 된다.



7. Proportional Share 스케줄링

Proportional Share Scheduling (비례 배분 스케줄링)이란, 전체 CPU실행시간을 Time share라는 단위로 쪼갠 뒤, 각 프로세스에게 일정 퍼센트만큼 할당해주는 방법이다.

  • 전체 Time share을 T라고 했을 때, 각 프로세스는 N만큼의 시간을 할당받는다. (N < T)

  • e.g 1.,

    • 기지국은 50명의 사람들을 한 번씩 서비스 해줘서 넷플릭스를 볼 수 있게 해야한다.
    • 이때, 신호가 제일 좋은 사람들 위주로 서비스를 하는데, 그럼 신호가 안좋은 사람들은 서비스를 못 받으니까 신호가 좋은 사람들의 우선순위는 점점 낮아지고, 신호가 좋지 않아 서비스를 받지 못한 사람들의 우선순위를 올려 서비스를 받게 한다. (에이징 기법!!!!🌟)

  • e.g 2.,

    • A프로세스와 B프로세스를 3:2의 비율로 Time share를 할당해준다고 하자.
    • 만약 B프로세스가 한타임 실행되면, 3:1이 되고, A프로세스가 한타임 실행되면 2:1이 되는 식이다.



8. CPU 스케줄링 알고리즘 평가

8.1 분석적 평가

어떤 스케줄링 알고리즘을 써야할까? 평가해보자!

  • 분석적 평가(결정론적 모델링)
    • 미리 결정되어 있는 매개변수(input)를 통해 성능 평가를 수행한다.
    • 결과를 정확히 알 수 있다.
    • 하지만, 실시간 스케줄링의 경우, 모든 input을 미리 알 수 없기 때문에 평가에 어려움이 있다.
    • 아래와 같은 정보들(Burst Time, …)

  • 시뮬레이션
    • 분석적 평가를 하기 힘든, 실시간 스케줄링을 평가하는 방법이다.


8.2 분석적 평가 예시

  • 모든 input을 알 때, 각 스케줄링 알고리즘에 대해 최소 평균 대기 시간을 구하자. (도착시간은 모두 0으로 같다.)

    Process Burst Time
    P1 10
    P2 29
    P3 3
    P4 7
    P5 12


  • FCRS
    • 최소 평균 대기 시간: (0+10+39+42+49) / 5 = 28(ms)


  • 비선점형 SJF (Shortest Job First)
    • 최소 평균 대기 시간: (0+3+10+20+32) / 5 = 13(ms)


  • RR (Round Robin)
    • q = 10 일때
    • 최소 평균 대기 시간: (0+(10+20+2)+20+23+(30+10)) / 5 = 23(ms)


=> 즉, 평균 대기 시간이 가장 작은 스케줄링 기법은 “비선점형 SJF”이다!



9. Little’s law

Little’s law (리틀의 법칙)

  • L = λW
    • L: 큐(queue) 안의 평균 사람 수
    • λ: 평균 도착 속도 (얼마나 자주 사람들이 오는가?)
    • W: 평균 대기 시간


e.g 1., 4시간 동안 300명의 손님이 다녀간 식당이 있다. 평균적으로 식사 시간은 10분이다. 식당 안의 손님들의 “평균” 숫자는 얼마일까?

  • λ = 300명/4시간 = 75명/시간
  • W = 1/6시간
  • L= 75/6 = 12.5명
  • 즉, 이에 맞는 규모로 테이블 갯수 등 식당 설비를 갖출 수 있다.


e.g 2., 한 식당에서는 고객이 평균 14명이 대기하고 있고, 시간당 평균 7명의 고객이 주문을 하러 들어올 때, 평균 대기 시간은?

  • L = 14
  • λ = 7
  • W = 14/7 = 2


➡️ 즉, 평균 대기 시간은 2임을 알 수 있다.


카테고리:

업데이트:

댓글남기기

참고