[운영체제]6장. cpu스케줄링

프로그램 동작순서

1. 프로그램이 시작되어 메모리에 올라감

2. PC(프로그램 카운터)라는 레지스터가 현재 CPU에서 수행할 코드의 메모리 주소값을 가지게 됨

3. CPU는 PC가 가리키는 주소의 기계어 명령을 하나씩 수행

 

기계어 명령 종류

1. cpu내에서 수행되는 명령 (예 : ADD명령)
2. 메모리 접근을 필요로 하는 명령 (예 : Load명령, Store명령)
3. 입출력을 동반하는 명령

1번, 2번은 비교적 빠른명령 (사용자 프로그램이 직접 cpu를 가지고 수행) 👉 CPU버스트

3번은 상대적으로 느린 명령 👉 I/O 버스트

 

프로그램들은 CPU버스트가 긴 경우도 있고 짧은 경우도 있고, I/O버스트가 긴 경우, 짧은 경우 있고 다양하다.

따라서 CPU 스케줄링이 필요함.

 

CPU스케줄링의 두 가지 분류

• 비선점형 방식 :  CPU를 획득한 프로세스가 스스로 CPU를 반납하기 전까지는 CPU를 빼앗기지 않는 방법
• 선점형 방식 : 프로세스가 CPU를 계속 사용하기를 원하더라도 강제로 빼앗을 수 있는 스케줄링 방법(대부분 이 방식을 사용)

CPU스케줄링의 성능 척도

• 시스템 관점
  • CPU이용률(CPU utilization) : 전체 시간 중에서 CPU가 일을 한 시간의 비율
  • 처리량(throughput) : 주어진 시간 동안 준비 큐에서 기다리고 있는 프로세스 중 몇 개를 끝마쳤는지
• 사용자 관점
  • 소요시간(turnaround time) : 준비큐에서 기다린 시간 + 실제로 CPU를 사용한 시간 (해당 CPU버스트가 완료될 때가지 소요된 시간으로, 프로그램이 시작해 종료하는 데가지 걸리는 시간이 아님!)
  • 대기시간(waiting time) : 준비 큐에서 CPU를 얻 위해 기다린 시간의 합
  • 응답시간(response time) : 준비큐에 들어온 후 첫 번째 CPU를 얻기까지 기다린 시간 

응답시간은 대화형 시스템에 적합한 성능 척도. 사용자 입장에서 가장 중요한 성능 척도.

 

cpu스케줄링 알고리즘

• FCFS (First-Come First-Served)
  • 비 선점형 스케쥴링이다.
  • ❗단점 : 콘보이 현상

콘보이 현상 :  cpu버스트가 짧은 프로세스가 cpu 버스트가 긴 프로세스보다 나중에 도착해 오랜 시간을 기다려야 하는 현상

• SJF(Shortest-Job First)
  • 비선점형
  • 선점형 (=SRTF)
  • 선점형 방식의 SJF는 평균 대기시간을 가장 짧게 하는 최적 알고리즘.
  • ❗ 단점 : 기아현상
  • ❗ 현실적으로 어려운 부분 : CPU버스트의 시간을 미리 알 수 없다는 점 👉 예측을 통해 CPU버스트 타임을 구함

기아현상 : CPU 버스트가 긴 프로세스는 준비 큐에 줄 서서 무한정 기다려야 하는 문제

 

• 우선순위 스케줄링
  • 비선점형
  • 선점형
  • highest priority를 가진 프로세스에게 cpu를 할당
  • SJF는 일종은 priority scheduling이다.
  • ❗단점 : 기아현상
  • 💡해결방법 : 노화(aging) 기법 : 기다리는 시간이 길어지면 우선순위를 조금씩 높여, 언젠가는 가장 높은 우선순위가 되어 pcu를 할당 받을 수 있게 해주는 방법

 

• 라운드 로빈 스케줄링
  • 각 프로세스는 동일한 크기의 할당시간을 가짐
  • 할당 시간이 지나면 프로세스는 선점당하고, 준비큐의 제일 뒤에 가서 다시 줄을 선다
  • 응답시간(cpu를 최초로 얻는 시간)이 빨라진다.
  • 할당시간이 너무 크면 : FCFS와 같은 알고리즘이 됨
  • 할당시간이 너무 짧으면 : 문맥교환(context switch)의 오버헤드가 커짐
  • 대기시간이 본인의 cpu를 사용하려는 시간이 비례하게 된다.
• 멀티레벨 큐
  • 준비 큐를 여러개로 분할
    • foreground(interactive)
    • background(batch - no human interaction)
  • 각 큐는 독립적인 스케줄링 알고리즘을 가짐
    • foreground - 라운드로빈
    • background - FCFS
  • 큐에 대한 스케줄링이 필요
    • Fixed priority scheduling
      • foreground 큐 에게 cpu를 다 할당한 다음, background 큐 에게 cpu를 주는 방식
      • 기아현상이 발생할 수 있
    • Time slice
      • 각 큐에 cpu time을 적절한 비율로 할당
      • 예) 80%는 foreground, 20%는 background
• 멀티레벨 피드백 큐
  • 프로세스가 다른 큐로 이동 가능
  • 에이징(aging)기법 활용
  • 예시

출처 : 이화여자대학교 반효경 교수님의 운영체제 2014년 강의 (kocw)

• 다중처리기 스케줄링
  • cpu가 여러 개인 경우 스케줄링은 더욱 복잡해짐
  • 큐에 한 줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다.
  • 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 더 복잡해짐
  • Load sharing
    • 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
  • 대칭형 다중처리 : 각 cpu가 각자 알아서 스케줄링을 결정
  • 비대칭형 다중처리 : 하나의 cpu가 다른 모든 cpu의 스케줄링 및 데이터 접근을 책임지고 나머지  cpu는 거기에 따라 움직이는 방식
• 실시간 스케줄링
  • (시분할 시스템에서는 데드라인이 없지만) 실시간 스케줄링은 데드라인이 있음  
  • 경성 실시간 시스템 : 시간이 정확히 지켜야 하는 시스템
  • 연성 실시간 시스템 : 데드라인이 존재하기는 하지만 데드라인을 지키지 못했다고 해서 위험한 상황이 발생하지 않음