01 스케줄링의 개요

CPU 스케줄러
여러 프로세스의 상황을 고려해 CPU와 시스템의 자원의 배정 결정

고수준 스케줄링

• 시스템 내 전체 작업 수 조절
• 동시에 실행 가능한 프로세스이 총 개수가 정해짐
• 장기 스케줄링, 작업 스케줄링, 승인 스케줄링

저수준 스케줄링

• 어떤 프로세스에 CPU를 할당할지, 프로세스의 상태를 결정
• 단기 스케줄링

중간 수준 스케줄링

• 저수준 스케줄링이 원만하게 이루어지도록 완충하는 역할
  (스왑 영역으로 내려주는 역할)
• 중지와 활성화로 프로세스 수 조절 -> 과부하 막음
  

1-3 스케줄링의 목적

시분할 시스템

CPU 스케줄링의 목적
1. 공평성 : 특정 프로세스가 배제되어서는 안됨
2. 효율성 : 유휴 시간 없이 사용되도록
3. 안정성 : 중요 프로세스가 먼저 작동, 시스템 자원을 무단/과도하게 점유 하려는 프로세스로부터 자원 보호
4. 확장성 : 프로세스가 증가해도 시스템이 안정적으로 작동하도록
5. 반응 시간 보장 : 적절한 시간 안에 프로세스의 요구에 반응해야 함
6. 무한 연기 방지 : 무한히 연기 되어서는 안됨(배제X)

02 스케줄링 시 고려 사항

선점형 스케줄링

• 운영체제가 강제로 끌어올 수 있음 (인터럽트 가능)

• 빠른 응답 시간 요구하는 대화형 시스템, 시분할 시스템에 적합

• 저수준 스케줄러가 사용하는 방식

비선점형 스케줄링

• 운영체제가 강제로 끌어올 수 없음(인터럽트 불가)

• 실행중인 프로세스가 종료되거나 자발적으로 대기 상태에 들어가기 전까지 계속 실행

• 스케줄러 작업량 적음, 문맥 교환에 의한 낭비 적음

• 처리율 떨어짐
  

프로세스 우선순위
커널 프로세스 >> 일반 프로세스
커널 프로세스가 멈추면 시스템이 막히는 경우가 있음

우선순위가 높은 프로세스가 CPU를 먼저, 더 오래 차지

어디에 초점을 두는가
1. CPU 집중 프로세스: CPU 많이 사용하는 프로세스(수학 연산)
2. 입출력 집중 프로세스: 입출력을 많이 사용하는 프로세스(저장장치에서 데이터 복사)

스케줄링 할 때) 입출력 집중 프로세스 > CPU 집중 프로세스 시스템 효율 향상

전면 프로세스
GUI. 화면의 맨 앞에 놓인 프로세스
입출력 사용
상호 작용 프로세스

후면 프로세스
사용자와 상호작용 X
일괄작업 프로세스(사용자의 입력 없이 작동해서)

우선순위: 후면 < 전면

CPU 스케줄링 시 고려사항

03 다중 큐

3-1 준비상태의 다중 큐

자신의 우선순위에 해당하는 큐의 끝에 삽입

한 번에 하나의 프로세스를 꺼내 CPU 할당

우선순위를 배정하는 방식

• 고정 우선순위 방식
  초기에 부여 -> 중간에 안바뀜
  구현 쉬움
  시스템 변화에 대응 어려움 -> 작업효율 떨어짐

• 변동 우선순위 방식
  우선순위가 프로세스 작업 중간에 변함(기준: 얼마나 오래 기다렸는가)
  구현 어려움
  시스템 효율성 증가

3-2 대기상태의 다중 큐

시스템의 효율 향상) 같은 입출력을 요구한 프로세스끼리 모아 놓음

여러 개의 PCB를 동시에 꺼내 준비상태로
인터럽트 벡터: 대기 큐에서 동시에 끝나는 인터럽트 처리

04 스케줄링 알고리즘

4-1 스케줄링 알고리즘의 평가 기준

1. CPU 사용률 : 높을 수록 好 (유휴 시간 낮음)
2. 처리량 : 초 당 많은 프로세스 종료할 수록 好
3. 대기시간 : 프로세스 생성 후 실행되기 전까지
4. 응답시간 : 첫 작업 시작 후 첫 출력까지
5. 실행시간 : 프로세스 작업 시작 후 종료까지
6. 반환시간 : 대기시간 포함해서 실행이 종료될 때 까지
7. 평균 대기시간 : 모든 프로세스의 대기시간 / n
   

4-2 FCFS

• 도착한 순서대로 할당
• 프로세스가 끝나야 다음 프로세스(비선점형)
• 모든 프로세스 우선순위 동일(큐 1개)
  (커널 프로세스가 뒤로 물리면 시스템이 멈춤)

처리시간이 긴 프로세스가 CPU를 차지 -> 효율성 떨어짐
입출력 작업 요청 시 CPU 유휴 시간 증가 -> 작업 효율 떨어짐

4-3 SJF

• 실행시간이 짧은 순서부터
• 비선점형
• 최단 작업 우선 스케줄링

종료시간 정확한 예측 어렵
아사현상 : 작업시간이 길면 계속 뒤로 밀려 공평성 떨어짐
ㄴ 에이징: 순서를 양보할 때마다 나이를 한 살씩 먹어 최대 몇살까지 양보하도록 규정(상한선)
ㄴ HRN 스케줄링

4-4 HRN

Highest Response Rate Next
SJF로 인한 아사현상 해결하기 위함

• SJF + 에이징 기법) 기다린 시간과 CPU 사용시간 고려
• 비선점형
  

아사현상 완화: 실행 시간 짧은 것 우선 순위 높음 + 대기시간 고려
여전히 공평성 위배

4-5 라운드 로빈

• 한 프로세스가 할당받은 시간(타임 슬라이스) 동안 작업하다가 완료하지 못하면 준비큐의 맨 뒤로 가서 차례를 기다리는 방식
• 선점형
• 작업을 완료할 때까지 계속 순환
  

적절한 타임슬라이스: 문맥교환에 따른 추가시간 고려
-클 때) FCFS와 같아짐
-작을 때) 문맥 교환이 너무 多 -> 문맥교환 시간이 실제 작업시간보다 상대적으로 커짐

4-6 SRT

• SJF를 선점형태로 변형
• 기본적으로 라운드 로빈 사용
• 남아있는 작업 시간이 가장 적은 프로세스 선택

남은 시간을 주기적으로 계산 + 문맥교환 -> SJF에 없는 작업 추가
프로세스 종료 시간 예측 어렵
아사현상

4-7 우선순위 스케줄링

• 중요도에 따른 우선순위를 반영한 스케줄링
• 비선점, 선점형 방식에 모두 적용 가능
  • SJF(비선점): 작업시간 짧은 프로세스 순
  • HRN(비선점): 작업시간 짧거나 대기시간 긴 프로세스 순
  • SRT(선점): 남은 시간이 짧은 순

• 고정 우선순위 알고리즘: 쉽지만 효율성 낮음
• 변동 우선순위 알고리즘: 복잡하지만 효율성 좋음

아사현상
우선순위를 매번 바꿔야함 -> 오버헤드 -> 효율성 떨어짐

4-8 다단계 큐

• 우선순위에 따라 준비큐를 여러개 사용
• 고정형 우선순위
• 상단 큐의 작업이 모두 끝나야 다음 우선순위 큐 작업 시작
  
• CPU 할당될 때마다 프로세스의 우선순위 낮춤 (아사현상 완화)
• 커널 프로세스가 일반 프로세스 큐에 삽입 X
• 우선 순위에 따른 타임 슬라이스 크기 (순위 낮을 수록 타임슬라이스 큼)
• 우선순위가 가장 낮은 프로세스는 무한대 타임슬라이스
• 우선순위가 가장 낮은 큐는 FCFS

05 인터럽트 처리

폴링
주기적으로 입출력 장치 직접 확인

인터럽트
입출력 요청, 완료되면 이벤트 발생시켜 알림
폴링보다 효율 좋음

동기적 인터럽트(사고)
프로세스가 실행중인 명령어로 인해 발생

프로그램상의 문제, 예측 가능
의도적으로 프로세스를 중단하기 위함
주변장치 조작
산술연산 중(0으로 나눔)

비동기적 인터럽트(사고+사용자)
하드웨어적, 예측 불가
사용자가 직접 작동하는 인터럽트(signal)

하드웨어적 오류(하드디스크 읽기 오류, 메모리 불량)
키보드 인터럽트, 마우스 인터럽트

인터럽트 처리 과정
1. 인터럽트 발생 -> 프로세스 일시정지 -> 현재 프로세스 정보 임시 저장(PCB)
2. 인터럽트 컨트롤러가 인터럽트 처리 순서 결정
3. 인터럽트 벡터에 등록된 인터럽트 핸들러 실행
4. 일시정지 프로세스 다시 실행 또는 종료

인터럽트와 이중 모드
1. 커널 모드: 운영체제 관련 커널 프로세스 실행 상태
2. 사용자 모드: 사용자 프로세스 실행 상태
3. 이중 모드: 운영체제가 커널 모드와 사용자 모드 전환하며 일 처리 => 자원보호 목적

시스템 호출과 API: 사용자 프로세스가 자원에 접근하기 위해서 이용