[운영체제] 4. 프로세스 스케쥴링

본 게시물은 운영체제 과목의 강의영상과 강의자료를 바탕으로 작성한 학습용 게시물입니다.

---

스케쥴링 개념

# 장기, 중기, 단기 스케쥴러

• 장기 스케쥴러 (작업 스케쥴러)
  - 오프라인과 연계되는 일괄처리 큐를 별도로 유지하는 경우에 필요 
  - 어떤 프로그램을 하드디스크로부터 메모리로 적재할지를 결정하는것 
• 단기 스케쥴러 (또는 CPU 스케쥴러)
  - 메모리 내의 준비 상태에 있는 작업 중 실행할 프로세스를 선택하여 CPU를 할당 
  - 일반적으로 스케쥴러라 함은 단기 스케쥴러를 말함 
• 중기 스케쥴러 
  - 가상메모리 체제에서 너무 많은 프로세스가 적재되면 하드디스크 입출력이 과다해져서 시스템이 거의 멈추는 형상이 발생 
  - 스와핑 : 일부 프로세스를 메모리에서 디스크로 내보내고, 시간이 흘러 메모리의 여유가 생기면 다시 적재 

# 스케쥴링이 일어나는 경우 

• 다음 실행시킬 프로세스의 선정이 필요한 경우 
• 스케쥴링 대상 - 준비리스트에 들어있는 프로세스들에 한함 

# 성능 평가의 기준 

• CPU 사용률
• 처리율
• 반환 시간
• 대기 시간 
• 반응 시간 

# CPU Burst Time : CPU 할당 후 입출력 요구시까지의 시간 
- 히스토그램은 평균적으로 hyperexponential 분포를 보임

---

스케쥴링 알고리즘 - 비선점 스케쥴링

# 비선점 스케쥴링

• 프로세스가 입출력 요구 등으로 CPU를 자진 반납할 때까지 CPU에 의한 실행을 보장해주는 스케쥴링
• 작업 실행시간 전체, 또는 한번의 CPU 배당에 대해 적용 
• ex) FCFS , 최단 작업 우선 , 우선순위 스케쥴링 

# FCFS (First-Come-First-Served)

• 프로세스 도착순으로 CPU 배정 
• 장기 스케쥴러에서 사용 가능 
• 호위효과 문제 

# 최단작업우선 (Shortest Jpb First : SJF) 

• 대기하는 작업 중 CPU 버스트 타임이 가장 작은 작업에 CPU를 할당
• 평균 대기 시간에 있어서 최적 알고리즘 
• 선점 스케쥴링에도 적용가능 
• 문제점 : CPU 버스트 타임 미리 알기가 어렵다
• 해결방안 : 이전 버스트 타임들을 통해 다음 버스트 시간을 예측해서 활용 

 

# 우선 순위 스케쥴링 (priority sheduling)

• 우선순위가 제일 높은 프로세스에게 할당하되, 같은 경우 FCFS 적용 
• 문제점 : 기아상태 유발 
• 해결방안 : 에이징 

 

---

스케쥴링 알고리즘 - 선점 스케쥴링 

# 선점 스케쥴링

• 타임슬라이스가 소진되었거나, 현프로세스보다 높은 우선순위의 프로세스가 나타나는 경우 현프로세스로부터 강제로 CPU를 회수 
• 라운드 로빈 스케쥴링
• 다단계 큐 스케쥴링
• 다단계 피드백 큐 스케쥴링 
• 선점 : 현 프로세스로부터 CPU를 회수하여 다른 프로세스에게 할당하는 행위
• 타임 슬라이스 양은 동적으로 변할 수 있다.

# 라운드 로빈 스케쥴링 

• 준비 큐를 원형 큐로 간주하고 순환식으로 각 프로세스에게 타임퀀텀만큼씩 CPU 할당 
• 기아상태 x, 평균반환시간 큼 
• 잦은 문맥교환 오버헤드로 처리율 감소 
• 타임퀀텀의 크기에 큰 영향 

# 다단계 큐 스케쥴링

• 우선순위마다의 준비 큐 형성 
• 가장 높은 우선 순위 큐의 프로세스에 CPU 할당 
• 각 큐는 라운드 로빈이나 FCFS 등 독자적 스케쥴링 사용 가능 

# 다단계 피드백 큐 스케쥴링 

• 다단계 큐 + 동적인 프로세스 우선순위 변화 적용 
• 맨 아래 큐에서 너무 오래 대기하면 다시 상위 큐로 이동 → 기아상태 예방 
• 매우 복잡한 판단 

---

다중처리기 스케쥴링

• 한 시스템 내에 여러 처리기의 사용 가능하다면 부하 공유가능 

# 비대칭 다중 처리 

•  주 처리기가 모든 스케쥴링 결정, 입출력 처리, 다른 시스템 활동을 취급 
• 다른 처리기들은 사용자 코드만을 수행
• 한 처리기만 시스템 자료구조에 접근, 자료 공유의 필요성을 배제 

# 대칭 다중 처리

• 각 처리기가 독자적인 스케쥴링 수행 
• 모든 프로세스는 공동의 준비 큐 혹은 각 처리기의 준비 큐에 존재 
• 여러 처리기가 동시에 공유 자료에 접근 시 신중한 스케쥴링 필요 

# 처리기 친화성 

• 프로세스가 다른 처리기로 이주하게 되면 각 처리기의 캐시 메모리 갱신 필요 → 비용 낭비 
• 처리기 친화성 : 프로세스의 처리기 이주를 제한하고 같은 처리기에서 계속 실행시키려 하는 성질
• 연성 친화성 : 동일한 처리기에서 실행시키기 위한 정책 o, 보장 x
• 강성 친화성 : 시스템 콜을 통해 각 프로세스가 실행될 처리기 명시 가능
• 시스템의 메인 메모리 구조가 처리기 친화성에 영향을 줄 수 있음 

# 부하 균등화 

• 각 처리기가 자신만의 큐를 가지는 SMP (symmetric multiprocessing) 경우 두가지 균등화 방안 존재
• push 이주 (migration) : 특정 태스크가 주기적으로 각 처리기의 부하를 검사하다 불균형 상태일 경우 다른 처리기로 프로세스를 이주
• pull 이주 : 쉬고 있는 처리기가 부하가 높은 처리기를 기다리는 프로세스를 pull하여 이주 
• 두 방식 병렬적으로 구현 가능 
• 부하균등화는 processer affinity와의 이익이 상충되는 개념으로 두가지 모두 만족하는 절대적 규칙 존재 x 

# 멀티코어 프로세서 

• 멀티코어 : 하나의 프로세서 칩 내에 여러 처리기 코어 내장 
• 메모리 멈춤 : Cache miss 등 여러 원인에 대해, 프로세서가 메모리 접근 시 데이터 가용 시점까지 대기시간 발생
• 멀티 쓰레드 멀티코어 : 한 쓰레드가 메모리 멈춤으로 인해 멈추게 되면, 다른 쓰레드로 전환해 작업 지속 수행 

# 멀티 쓰레딩 방법 

• 거친 멀티쓰레딩 : 쓰레드가 긴 지연시간이 발생할 때 까지 한 처리기에서 계속 수행
  - 지연시간이 발생하면 다른 쓰레드로 전환 
• 세밀한 멀티쓰레딩 : 명령어 사이클 경계에서 쓰레드 교환 발생 
  - 쓰레드 교환 위한 회로 필요, 교환 비용 감소 

# 2레벨 스케쥴링 

• 멀티쓰레드-다중코어 프로세서는 기본적으로 두 레벨의 스케쥴링이 필요 
  - 레벨 1) 어느 소프트웨어 쓰레드가 하드웨어 쓰레드에서 실행될지 결정 
  - 레벨 2) 각 코어가 어느 하드웨어 쓰레드를 실행토록 할지 결정