[OS] Ch.4 CPU 스케줄링

1. 스케줄링의 개요

프로세스는 생성, 준비, 실행, 대기와 같은 여러 상태를 거치며 작업이 이루어진다. CPU 스케줄러는 프로세스가 생성된 후 종료될 때까지 모든 상태 변화를 조정하는 일을 한다. 

 

스케줄링의 단계

1. 고수준 스케줄링

• 시스템 내의 전체 작업 수를 조절
• 어떤 작업을 시스템이 받아들일지 또는 거부할지를 결정
• 동시에 실행 가능한 프로세스의 총 개수가 정해짐

1. 저수준 스케줄링
   • 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정
2. 중간 수준 스케줄링
   • 중지(suspend)와 활성화(active)로 전체 시스템의 활성화된 프로세스 수를 조절하여 과부하를 막음

 

스케줄링의 목적

• 공평성 : 모든 프로세스가 자원을 공평하게 배정받아야 하며, 자원 배정 과정에서 특정 프로세스가 배제되어서는 안 됨
• 효율성 : 시스템 자원이 유휴 시간 없이 사용되도록 스케줄링을 하고, 유휴 자원을 사용하려는 프로세스에는 우선권을 주어야 함
• 안정성 : 우선순위를 사용하여 중요 프로세스가 먼저 작동하도록 배정함으로써 시스템 자원을 점유하거나 파괴하려는 프로세스로부터 자원을 보호해야 함
• 확장성 : 프로세스가 증가해도 시스템이 안정적으로 작동하도록 조치해야 함, 또한 시스템 자원이 늘어나는 경우 이 혜택이 시스템에 반영되게 해야 함
• 반응 시간 보장 : 응답이 없는 경우 사용자는 시스템이 멈춘 것으로 가정하기 때문에 시스템은 적절한 시간 안에 프로세스의 요구에 반응해야 함
• 무한 연기 방지 : 특정 프로세스의 작업이 무한히 연기되어서는 안 됨

보통은 모든 프로세스가 공평하게 CPU를 할당받아야 하지만, 일정 부분 공평성을 희생하게 된다.

 

 

2. 스케줄링 시 고려 사항

선점형 스케줄링과 비선점형 스케줄링

구분	선점형	비선점형
작업 방식	실행 상태에 있는 작업을 중단시키고 새로운 작업을 실행할 수 있음	실행 상태에 있는 작업이 완료될 때까지 다른 작업이 불가능
장점	프로세스가 CPU를 독점할 수 없어 대화형이나 시분할 시스템에 적합함	CPU 스케줄러의 작업량이 적고 문맥 교환의 오버헤드가 적음
단점	문맥 교환의 오버헤드가 많음	기다리는 프로세스가 많아 처리율이 떨어짐
사용	시분할 방식 스케줄러	일괄 방식 스케줄러
중요도	높음	낮음

 

CPU 집중 프로세스와 입출력 집중 프로세스

• CPU 집중 프로세스 : 수학 연산과 같이 CPU를 많이 사용하는 프로세스
• 입출력 집중 프로세스 : 입출력을 많이 사용하는 프로세스

CPU 집중 프로세스와 입출력 집중 프로세스가 같이 있을 때는 입출력 집중 프로세스를 먼저 실행 상태로 옮기는 것이 효율적이다. 입출력 집중 프로세스가 실행 상태로 가면 입출력 요구에 의해 대기 상태로 옮겨지기 때문에 다른 프로세스가 CPU를 사용할 수 있기 때문이다.

 

전면 프로세스와 후면 프로세스

• 전면 프로세스
  • GUI를 사용하는 운영체제에서 화면의 맨 앞에 놓인 프로세스
  • 현재 입력과 출력을 사용하는 프로세스
  • 사용자와 상호작용 가능 - 상호작용 프로세스
• 후면 프로세스
  • 사용자와 상호작용이 없는 프로세스
  • 사용자의 입력 없이 작동하기 때문에 일괄 작업 프로세스라고도 함

 

3. 다중 큐

준비 상태의 다중 큐

PCB에 프로세스의 중요도가 표시되지만, 항상 PCB에 담겨져 있는 중요도를 읽는 것은 효율성이 떨어진다. 그렇기 때문에 중요도(우선순위)에 따라 PCB를 미리 정렬해두면 편리하다. 이렇게 우선순위 별로 정리한 상태를 준비 상태의 큐라고 한다.

 

• 고정 우선순위 방식 :운영체제가 프로세스 우선순위를 부여하면 프로세스가 끝날때까지 바꾸지 않음
• 변동 우선순위 방식 : 프로세스가 작업 중간 변하는 방식(시스템의 효율을 높임)

 

대기 상태의 다중 큐

 

준비 큐는 한 번에 하나의 프로세스를 꺼내어 CPU를 할당하는 반면, 대기 큐는 여러 개의 프로세스 제어 블록을 동시에 꺼내어 준비 상태로 옮긴다.

 

 

4. 스케줄링 알고리즘

스케줄링 알고리즘의 선택 기준

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

 

비선점형 알고리즘

1. FCFS
   • 준비큐에 도착한 순서대로 cpu에 할당
   • 처리시간이 긴 프로세스가 작업을 하면 다른 프로세스의 기다리는 시간이 길어짐
   • 작업 효율이 안좋음
2. SJF
   • 준비 큐에 있는 프로세스중 실행시간이 가장 짧은 작업부터 cpu에 할당
   • 아사현상이 생길수 있음
3. HRN
   • SJF 스케줄링에서 발생하는 아사 현상을 해결하기 위해 만들어진 알고리즘
   • 서비스를 받기 위해 기다린 시간과 cpu 사용 시간을 고려한 스케줄링
   • 우선순위 = (대기시간 + cpu 사용시간) /  cpu사용시간
   • 공평성 위배

 

선점형 알고리즘

1. 라운드 로빈
   • FCFS 방식인데 타임슬라이스가 추가된 방식
   • 문맥교환 시간이 추가
2. SRT
   • SJF 와 라운드 로빈이 혼합된 방식
   • 기본적으로 라운드 로빈 스케줄링을 사용
   • cpu를 할당 받을 때 남은 작업이 가장적은 프로세스를 할당
   • 문맥교환을 하고 아사현상이 일어날수 있음
   • 큐에 있는 프로세스의 남은 시간을 주기적으로 계산해야 하는 작업이 추가됨
3. 다단계 큐
   • 고정 우선순위에 따라 준비큐를 여러 개 사용하는 방식
   • 프로세스는 운영체제로부터 부여받은 우선순위에 따라 순위큐 삽입
   • 우선순위에 따라 타임슬라이스를 조절해 작업 효율을 높일 수 있음
4. 다단계 피드백 큐
   • 우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점을 보완한 방식
   • cpu를 사용하고 난 프로세스는 원래 큐로 돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어감
   • 우선순위가 낮은 큐의 타임슬라이스를 크게 설정
   • 오늘날의 운영체제가 CPU 스케줄링을 위해 일반적으로 사용하는 방식

 

둘 다 가능

우선순위 스케줄링

• 우선순위대로 프로세스를 CPU에 할당
• 선점/비선점 둘 다 가능
  • 선점 : 프로세스가 작업 중일 때 새로운 프로세스가 큐에 들어오면, 그 즉시 우선순위를 계산하여 우선순위가 더 높은 프로세스를 CPU가 선점
  • 비선점 : 작업 중인 프로세스가 끝나면 우선순위대로 차례대로 CPU에 할당

 

5. [심화학습] 인터럽트 처리

인터럽트의 개념

입출력을 요청하고 입출력이 완료되면 이벤트를 발생시켜 이 사실을 알리는 것

 

동기적 인터럽트와 비동기적 인터럽트

• 동기적 인터럽트 : 프로세스가 실행 중인 명령어로 인해 발생
  
  • 프로그램 상의 문제 때문에 발생하는 인터럽트
  • 컴퓨터 작업자가 의도적으로 프로세스를 중단하기 위해 발생시킨 인터럽트
  • 입출력장치 같은 주변장치의 조작에 의한 인터럽트
  • 산술 연산 중 발생하는 인터럽트
• 비동기적 인터럽트 : 실행 중인 명령어와 무관하게 발생
  • 하드디스크 읽기 오류, 메모리 불량 등의 하드웨어적 오류로 발생

 

인터럽트 처리 과정

인터럽트 = 인터럽트 번호(IRQ) + 함수

 

1. 인터럽트가 발생하면 현재 실행중인 프로세스는 일시정지, 재시작하기 위해 상태 정보를 PCB에 임시 저장함
2. 인터럽트 컨트롤러가 실행되어 인터럽트 처리 순서 결정
3. 먼저 처리할 인터럽트가 결정되면 인터럽트 벡터에 등록된 인터럽트 핸들러 (해당 이벤트를 처리할 함수의 시작 주소) 실행
4. 핸들러가 인터럽트 처리를 마치면 일시정지된 프로세스가 다시 실행되거나 종료

 

인터럽트와 이중 모드

이중 모드

• 운영체제가 커널 모드와 사용자 모드를 전환하며 일 처리를 하는 것
• 궁극적인 목적은 자원 보호

 

• 사용자 프로세스가 자원에 접근하려면 시스템 호출을 이용해야 함
• 사용자 프로세스는 API가 준비해놓은 다양한 함수를 이용해 시스템 자원에 접근