개발의변화
3. 프로세스 스케줄링 본문
프로세스
CPU에 의해 처리되는 사용자 프로그램, 시스템 프로그램, 즉 실행 중인 프로그램을 의미하며, 작업 또는 태스크라고 한다
프로세스의 상태
하나의 프로세스는 여러가지 이벤트에 의해 일련의 서로 구분된느 상태 변화를 겪는다
생성 상태, 준비 상태, 실행 상태, 대기 상태, 완료 상태를 가질 수 있다.
생성상태
사용자에 의해 프로세스가 생성된 상태
준비 상태
- CPU를 할당받을 수 있는 상태
- 준비 리스트: 각각 우선순위를 부여하여 가장 높은 우선순위를 갖는 프로세스가 다음 순서에 CPU를 할당 받음
실행 상태
- 프로세스가 CPU를 할당받아 동작 중인 상태
대기 상태
- 프로세스 실행 중 입출력 처리 등으로 인해 CPU를 양도하고 입출력 처리가 완료까지 대기 리스트에서 기다리는 상태
- 대기 리스트: 우선 순위가 존재하지 않음
완료/종료 상태
- 프로세스가 CPU를 할당받아 주어진 시간 내에 완전히 수행을 종료한 상태
프로세스 상태 전이
디스패치(Dispatch)
준비 상태에 있는 여러 프로세스 중 실행될 프로세스를 선정하여 CPU를 할당
프로세스는 준비 상태에서 실행 상태로 전이
할당 시간 초과(TImeout)
CPU를 할당받은 프로세스는 지정된 시간이 초과되면 스케줄러에 의해 PCB 저장, CPU 반납 후 다시 준비 상태로 전이됨
프로세스는 실행 상태에서 준비 상태로 전이
타임 슬라이스 만료, 선점 시 타임아웃 발생
입출력 발생(Block)
실행 상태에 있는 프로세스가 지정된 할당 시간을 초과하기 전에 입출력이나 기타 사건이 발생하면 CPU를 스스로 반납하고 입출력이 완료될 때 까지 대기 상태로 전이됨
즉시 실행 불가능한 시스템 콜, I/O 작업 시작, 프로세스 간 통신 시 Block 발생
깨움(Wake-up)
입출력이 종료되면 대기 상태의 프로세스에게 입출력 종료 사실을 wait & signal 등에 의해 알려주고, 준비 상태로 전이됨
프로세스는 대기 상태에서 준비 상태로 전이
사용자 작성 코드 사용자 사용 코드, 스택, 프로세스 제어 블록
프로세스 제어 블록: 운영체제가 프로세스 관리를 위해 필요한 자료를 담고 있는 자료 구조
프로세스 생성 시 만들어지고, 메인 메모리에 유지되며, 운영체제에서 한 프로세스의 전체를 정의함
PID, 프로세스 상태, 프로그램 카운트, 레지스터 저장 영역, 프로세서 스케줄링 정보, 계정 정보, 입출력 상태 정보, 메모리 관리 정보
스레드
프로세스 보다 가벼운, 독립적으로 수행하는 순차적인 제어의 흐름이며, 실행 단위입니다
프로세스에서 실행 제어만 분리한 실행 단위로 한 개의 프로세스는 여러 개의 스레드를 가질 수 있다
스레드 종류
생성 주체에 따라 커널 수준 스레드와 사용자 수준 스레드로 구분된다
| 항목 | 커널 수준 스레드 | 사용자 수준 스레드 |
| 개념 | 스레드를 생성하고 스케줄링하는 주체가 커널인 스레드 | 사용자 영역에서 라이브러리를 통해 구현되는 스레드 |
| 장점 | - 커널이 각 스레드를 개별적으로 관리할 수 있음 - 다른 스레드가 입출력 작업이 다 끝날 때까지 다른 스레드를 사용해 다른 작업을 진행할 수 있음 - 커널이 직접 스레드를 제공해 주기 때문에 안정성 과 다양한 기능이 제공 |
스케줄링 결정이나 동기화를 위해 커널 모드로 전환하지 않기 때문에 인터럽트가 발생할 때 오버헤드가 적음 사용자 영역 스레드에서 행동하기 때문에 OS 스케줄러의 문맥 교환이 없음 |
| 단점 | 사용자 모드에서 커널 모드로의 전환이 빈번하게 이뤄져 오버헤드가 많음 사용자 스레드에 비해 생성 및 관리하는 것이 느림 |
스케줄링 우선순위를 지원하지 않으므로 어떤 스레드가 먼저 동작할지 알 수 없음 여러 개의 사용자 스레드 중 하나의 스레드가 시스템 호출 등으로 블록이 걸리면 나머지 모든 스레드 역시 블록됨 |
프로세스 스케줄링
CPU를 사용하려고 하는 프로세스들 사이의 우선순위를 관리하는 작업
처리율과 CPU 이용률을 증가시키고 오버헤드, 응답시간, 반환시간, 대기시간을 최소화시키기 위한 기법
서비스시간 = 프로세스가 결과를 산출하기까지 소요되는 시간
응답시간 = 프로세스들이 입력되어 서비스를 요청하고 반응하기 시작할 때까지 소요되는 시간
반환시간 = 프로세스들이 입력되어 수행하고 결과를 산출하기까지 소요되는 시간 = 대기시간 + 수행시간
응답률 (대기시간 + 서비스시간)/서비스시간
시간 할당량 = 한 프로세스가 프로세서를 독점하는 것을 방지하기 위해 서비스되는 시간 할당량
선점형 스케줄링 vs 비선점형 스케줄링
선점형 스케줄링
하나의 프로세스가 CPU를 차지하고 있을 떄, 우선 순위가 높은 다른 프로세스가 현재 프로세스를 중단시키고 CPU를 점유하는 스케줄링 방식
- 장점
비교적 빠른 응답
대화식 시분할 시스템에 적합
- 단점
높은 우선순위 프로세스들이 들어오는 경우 오버헤드 초래
-알고리즘: SRT(Shortest Remaining Time First), 다단계 큐(MLQ: Multi-Level Queue), 다단계 피드백 큐(MLFQ), 라운드 로빈
- 활용: 실시간 응답환경, Deadline 응답환경
비선점형 스케줄링
한 프로세스가 CPU를 할당 받으면 작업 종료 후 CPU 반환 시까지 다른 프로세스는 CPU 점유가 불가능한 방식
-장점
응답시간 예상이 용이, 모든 프로세스에 대한 요구를 공정하게 처리
-단점
짧은 작업을 수행하는 프로세스가 긴 작업 종료 시까지 대기
-알고리즘
우선순위(Priority),기한부(Deadline), HRN(High Response Ratio Next), FCFS(First Come First Served), SJF(Shortest Job First)
-활용
처리시간 편차가 적은 특정 프로세스 환경
선점형 스케줄링 알고리즘의 유형
SRT(Shortest Remaining Time First): 가장 짧은 시간이 소요되는 프로세스를 먼저 수행, 남은 처리 시간이 더 짧다고 판단되는 프로세스가 준비 큐에 생기면 언제라도 프로세스가 선점됨 -> 잛은 수행 시간 프로세스 우선 수행
다단계 큐(Multi Level Queue): 작업들을 여러 종류 그룹으로 분할, 여러 개의 큐를 이용하여 상위단계 작업에 의한 하위단계 작업이 선점 당함 -> 독립된 스케줄링 큐
다단계 피드백 큐: 입출력 위주와 CPU 위주인 프로세스의 특성에 따라 큐마다 서로 다른 CPU 시간 할당량 부여
FCFS와 라운드 로빈 스케줄링 기법을 혼합한 것으로, 새로운 프로세스는 높은 우선순위, 프로세스의 실행시간이 길어질수록 점점 낮은 우선순위 큐로 이동하고 마지막 단계는 라운드 로빈 방식을 적용
라운드 로빈: 프로세스는 같은 크기의 CPU 시간을 할당, 프로세스가 할당된 시간 내에 처리 완료를 못하면 준비 큐 리스트의 가장 뒤로 보내지고, CPU는 대기 중인 다음 프로세스로 넘어감 -> 균등한 CPU 점유 시간, 시분할 시스템 사용
-> 시분할 시스템 (Time Sharing System) CPU 스케줄링과 다중 프로그래밍을 이용해서 각 사용자들에게 컴퓨터 자원을 시간적으로 분할하여 사용할 수 있는ㄴ 대화식 시스템
비선점형 스케줄링 알고리즘
우선순위 : 각 프로세스 별로 우선순위가 주어지고, 우선순위에 따라 CPU를 할당함 -> 주요/긴급 프로세스에 대한 우선 처리, 설정, 자원 상황 등에 따른 우선순위 선정
기한부: 작업들이 명시된 시간이나 기한 내에 완료되도록 계획 -> 요청에 명시된 시간내 처리를 보장
FCFS: 프로세스가 대기 큐에 도착한 순서에 따라 CPU를 할당함, FIFO 알고리즘이라고도 함 -> 도착한 순서대로 처리
SJF: 프로세스가 도착하는 시점에 따라 그 당시 가장 작은 서비스 시간을 갖는 프로세스가 종료 시까지 자원 점유 -> 기아 현생 발생
* 기아(starvation) 현상: 시스템 부하가 많아서 낮은 등급에 있는 준비 큐에 있는 프로세스가 무한정 기다리는 현상 -> 오랫동안 기다린 프로세스에게 우선순위를 높여줌으로써 처리하는 기법인 에이징(Aging) 활용
HRN(Highest Response Ratio Next): 대기 중인 프로세스 중 대기시간이 긴 프로세스일 경우 우선순위가 높아지게 하여 우선순위를 결정하는 스케줄링 기법, 서비스 받을 시간과 서비슷를 기다린 시간을 고려하여 가변적 우선순위를 결정 , (대기시간 + 서비스시간)/서비스시간 -> SJF의 약점인 기아 현상을 보완하는 기법으로 긴 작업과 짧은 작업 간의 지나친 불평등 해소
Deadlock : 교착상태는 다중프로세싱 환경에서 두 개 이상의 프로세스가 특정 자원할당을 무한정 대기하는 상태
발생조건:
- 상호배제: 프로세스가 자원을 배타적으로 점유하여 다른 프로세스가 그 자원을 사용할 수 없는 상태
- 점유와 대기: 한 프로세스가 자원을 점유하고 있으면서 또 다른 자원을 요청하여 대기하고 있는 상태
- 비선점: 한 프로세스가 점유한 자원에 대해 다른 프로세스가 선점할 수 없고 오직 고유한 프로세스만이 해제 가능한 상태
- 환형 대기: 두 개 이상의 프로세스 간 자원의 점유와 대기가 하나의 원형을 구성한 상태
해결방법
- 예방: 상호배제를 제외한 나머지 교착상태 발생 조건을 위배하는 방안
- 회피: 안전한 상태를 유지할 수 있는 요구만 수락 (은행원 알고리즘)
- 발견: 시스템의 상태를 감시 알고리즘 통해 교착 상태 검사
- 복구: 교착상태가 없어질 때까지 프로세스를 순차적으로 Kill하며 제거, 희생자 선택해야하고 기아상태 발생
디스크 스케줄링
사용할 데이터가 디스크상의 여러 곳에 저장되어 있을 경우, 데이터를 액세스하기 위해 디스크 헤드를 움직이는 경로를 결정하는 기법
FCFS(선입선출), SSTF(제일 짧은 거리 탐색), SCAN(양끝 중 제일 가까운 거리 탐색 후 방향 반대로 이동), C-SCAN(양끝 중 제일 가까운 거리 탐색 후 다시 바깥쪽으로 탐색), LOOK(엘리베이터 알고리즘 요청까지만 가다가 다시 꺾는 운영), N-STEP SCAN, SLTF
