학습 기록 | w6 지현
#CPU스케줄링 #우선순위 #스케줄링 큐 #준비 큐 #대기 큐 #선점형 스케줄링 #비선점형 스케줄링
CPU 스케줄링
- 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것
❓공정한 CPU스케줄링은 차례대로 실행하는 것이다? → X
💡 프로세스마다 우선순위가 다르다!
입출력 집중 프로세스 > CPU 집중 프로세스
(I/O bound process > CPU bound process)
- 입출력 작업이 많은 프로세스는 잠깐 실행하면 대기 상태로 접어들기 때문에 먼저 실행하고
이후에 CPU 작업이 많은 프로세스를 실행한다.
- PCB에 우선순위 명시
- 우선순위가 높은 프로세스는 더 빨리, 더 자주 실행 가능
- 운영체제가 모든 PCB를 검사하여 자원을 이용할 프로세스를 결정하는 것은 비효율적
- 프로세스들에 줄을 서서 기다리도록 함
- FIFO 방식일 필요는 없음
준비 큐 (ready queue)
- CPU를 이용하기 위해 기다리는 줄
대기 큐 (waiting queue)
- 입출력장치를 이용하기 위해 기다리는 줄
- 같은 장치를 요구한 프로세스 들은 같은 큐에서 대기
- 같은 큐에서도 우선순위 별로 처리
preemptive scheduling
- 현재 CPU를 사용 중인 프로세스로부터 CPU 자원을 빼앗아 다른 프로세스에 할당
- 프로세스마다 정해진 시간동안 CPU를 사용하는 것
➕ 어느 한 프로세스의 자원 독점을 막고 프로세스들에 골고루 자원을 배분 가능
➖ 문맥 교환 과정에서 오버헤드 발생 가능
non-preemptive scheduling
- 현재 CPU를 사용 중인 포르세스의 작업이 끝날 때까지 프로세스 기다리기
➕ 문맥 교환 과정에서 발생하는 오버헤드가 적음
➖ 모든 프로세스가 골고루 자원을 이용하기 어려움
#선입 선처리 스케줄링 #최단 작업 우선 스케줄링 #라운드 로빈 스케줄링 #우선순위 스케줄링 #다단계 피드백 큐 스케줄링
-
선입 선처리 스케줄링
= FCFS 스케줄링 (First Come First Served Scheduling)
- 단순히 준비 큐에 삽입된 순서대로 처리하는 비선점 스케줄링
- 먼저 CPU를 요청한 프로세스부터 CPU 할당
➖ 호위 효과(convoy effect) 발생 : 프로세스들이 기다리는 시간이 매우 길어지는 부작용
-
최단 작업 우선 스케줄링
= SJF 스케줄링 (Shortest Job First)
- 호위효과를 방지하기 위해
- CPU 사용이 긴 프로세스는 나중에 실행, 사용시간이 짧은 프로세스는 먼저 실행
- CPU 사용 시간이 가장 짧은 프로세스부터 처리하는 스케줄링 방식
- 비선점형
-
라운드 로빈 스케줄링
= RR 스케줄링 (Round Robin)
- 선입 선처리 스케줄링 + 타임 슬라이스(time slice)
- 타임 슬라이스 : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
- 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링
- 정해진 시간을 모두 사용해도 프로세스가 완료되지 않았다면 큐의 맨 뒤에 삽입(문맥교환)
💡 타임 슬라이스의 크기가 중요
-
최소 잔여 시간 우선 스케줄링
= SRT 스케줄링 (Shortest Remaining Time)
- 최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링
- 최단 작업 우선 스케줄링 : 작업시간이 짧은 프로세스부터 처리
- 라운드 로빈 스케줄링 : 정해진 타임 슬라이스만큼 돌아가며 사용
- 정해진 시간 만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스는 남은 작업 시간이 가장 적은 프로세스 선택
= 선점형 최단 작업 우선 스케줄링
- 최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링
-
우선순위 스케줄링
- 프로세스들에 우선순위를 부여하고, 우선순위가 높은 프로세스부터 실행
- 우선순위가 같은 프로세스 = 선입 선처리
- 최단 작업 우선 스케줄링, 최소 잔여 시간 스케줄링 ⊂ 우선순위 스케줄링
➖ 기아(starvation) 현상
- 우선순위 높은 프로세스만 계속 실행
- 우선순위 낮은 프로세스는 (준비 큐에 먼저 삽입되어도) 실행 연기
💡 에이징 (aging)
- 기아 현상 방지 기법
- 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식
- 대기 중인 프로세스의 우선순위를 마치 나이 먹듯 점차 증가시키는 방법
- 우선순위가 낮아도 언젠가는 우선순위가 높아짐
-
다단계 큐 스케줄링
= Multilevel queue 스케줄링
- 우선순위 스케줄링이 발전된 형태
- 우선순위 별로 준비 큐를 여러개 사용하는 방식
- 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리
- 우선순위가 가장 높은 큐가 비어있으면 다음 우선순위 큐의 프로세스 처리
- 큐별로 스케줄링을 다르게 적용할 수 있음
➖ 큐 간의 이동이 불가능하여 기아 현상 발생 가능
-
다단계 피드백 큐 스케줄링
= Multilevel feedback queue 스케줄링
-
다단계 큐 스케줄링의 발전된 형태
-
큐 간의 이동이 가능
- 새로 준비 상태가 된 프로세스가 있다면 우선순위가 가장 높은 우선순웨 큐에 삽입되고 일정 시간(타임 슬라이스)동안 실행됨
- 해당 큐에서 끝나지 않는다면 다음 우선순위 큐에 삽입되어 실행(우선순위가 점차 낮아짐)
-
CPU 집중 프로세스의 우선순위는 상대적으로 낮아지고
입출력 집중 프로세스의 우선순위는 상대적으로 높아짐
-
aging 기법 적용하여 기아 현상 예방 가능
-
- 가장 일반적인 CPU 스케줄링 방식
#동기화 #공유 자원 #임계 구역 #상호 배제
- 동시다발적으로 실행되는 프로세스/스레드는 서로 협력하며 영향을 주고 받는다. 이 과정에서 자원의 일관성을 보장해야 한다.
→ 동기화되어야 한다.
synchronization
- 프로세스들의 수행 시기를 맞추는 것
- 실행의 문맥을 갖는 모든 대상은 동기화 대상(프로세스, 스레드)
-
실행 순서 제어
- 프로세스들을 올바른 순서대로 실행하기
- 실행의 순서 존재
ex) reader writer problem - 특정 조건이 만족되어야만 실행 가능
-
상호 배제 (mutual exclusion)
- 동시에 접근해서는 안 되는 자원에 하나의 프로세스만 접근하게 하기
ex) Bank account problem, Producer & Consumer problem
생산자와 소비자 문제 (Producer & Consumer problem)
- 생산자 : 버퍼에 데이터 삽입, 총합 변수 1 증가
- 소비자 : 버퍼에서 데이터 빼내기, 총합 변수 1 감수
→ 예상치 못한 결과 발생!
- 여러 프로세스 혹은 스레드가 공유하는 자원
ex) 전역 변수, 파일, 입출력장치, 보조기억장치
- 동시에 실행하면 문제가 발생하는 자원에 접근하는 코드 영역
ex) ‘잔액’ 변수, ‘총합’ 변수
- 진입한 프로세스 외의 임계 구역에 진입하고자 하는 프로세스는 대기해야 함
레이스 컨디션 (race condition)
- 잘못된 실행으로 여러 프로세스가 동시 다발적으로 임계 구역의 코드를 실행하여 문제가 발생한 경우
- 데이터의 일관성이 깨짐
상호 배제를 위한 동기화를 위한 원칙
-
상호 배제 (mutual exclusion)
- 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 임계 구역에 들어올 수 없다.
-
진행 (progress)
- 임계 구역에 어떤 프로세스도 진입하지 않았다면 임계 구역에 진입하고자 하는 프로세스는 들어갈 수 있어야 한다.
-
유한 대기 (bounded wating)
- 한 프로세스가 임계 구역에 진입하고 싶다면 그 프로세스는 언젠가 임계 구역에 들어올 수 있어야 한다.
- 임계 구역에 들어오기 위해 무한정 대기해서는 안된다.
#뮤텍스 락 #세마포 #모니터
Mutex lock; MUTual EXclusion lock
- 상호배제를 위한 동기화 도구(자물쇠 역할)
- 소유권 존재. 락을 한 프로세스만 해제 가능
- 프로세스들이 공유하는 전역변수 lock : 자물쇠 역할
- acquire 함수 : 임계 구역을 잠금
- release 함수 : 임계 구역의 잠금을 해제
acquire();
// 임계 구역
release();- 바쁜 대기 (busy wait)
- 임계 구역이 열릴 때 까지 반복적으로 확인
semaphore
-
공유 자원이 여러개 있는 경우 적용 가능
-
종류 : 바이너리 세마포(0 또는 1), 카운팅 세마포(자원 개수)
-
임계 구역 앞에서 멈춤 신호를 받으면 잠시 기다리기
임계 구역 앞에서 가도 좋다는 신호를 받으면 임계 구역 진입 (진입가능 개수 확인)
- 전역변수 S : 임계 구역에 진입할 수 있는 프로세스 개수(사용 가능한 공유 자원의 개수)
- wait 함수 : 임계 구역에 들어가도 좋은지, 기다려야 할지 판단
- signal 함수: 임계 구역 앞에 기다리는 프로세스에게 ‘GO’ 신호를 전달
wait();
// 임계 구역
signal();-
상호 배제를 위한 동기화에서 busy wating을 해결하는 방법
→ CPU 주기 낭비 방지 위해 대기상태/준비상태 활용하기!
-
사용할 수 있는 자원이 없을 경우 대기 상태로 만듦
(해당 프로세스의 PCB를 대기 큐에 삽입)
-
사용할 수 있는 자원이 생겼을 경우 대기 큐의 프로세스를 준비 상태로 만듦
(해당 프로세스의 PCB를 대기 큐에서 꺼내 준비 큐에 삽입)
-
-
실행 순서 제어를 위한 동기화
- 세마포 변수 S를 0으로 두고
- 먼저 실행할 프로세스 뒤에 signal 함수
- 다음에 실행할 프로세스 앞에 wait 함수
- 개발자가 다루기 편리한 동기화 도구, JAVA
- 공유 자원과 공유 자원에 접근하기 위한 인터페이스(통로)를 묶어 관리
- 프로세스는 반드시 인터페이스를 통해서만 공유 자원에 접근 가능
- 모니터 안에는 하나의 프로세스만이 있을 수 있다.(상호배제)
- 상호 배재를 위한 동기화
- 공유자원에 접근하고자 하는 프로세스를 (인터페이스를 위한) 큐에 삽입
- 큐에 삽입된 순서대로 (한 번에 하나의 프로세스만) 공유 자원 이용
- 실행 순서 제어를 위한 동기화
-
조건변수(condition variable) 이용
- 조건변수.wait() : 대기상태로 변경, 조건변수에 대한 큐에 삽입
- 조건변수.signal() : 대기 상태 → 실행상태
-
조건변수(condition variable) 이용
💡 상호 배재를 위한 큐 ≠ 조건 변수에 대한 큐
| 동기화 메커니즘 | 특징 | 장점 | 단점 |
|---|---|---|---|
| 뮤텍스 (Mutex) | - 한 번에 하나의 스레드만 접근 가능 | - 간단하고 직관적 | - 교착 상태 발생 가능 |
| - 소유권이 있음 | - 안전한 자원 접근 보장 | - 락 해제하지 않으면 다른 스레드 접근 불가 | |
| 세마포어 (Semaphore) | - 카운팅 방식으로 다수 스레드 접근 가능 | - 여러 스레드 동시 접근 가능 | - 교착 상태 발생 가능 |
| - 바이너리/카운팅 세마포어 구분 | - 자원 수에 따른 동적 할당 가능 | - 사용 복잡성 증가 | |
| 모니터 (Monitor) | - 자동 락 관리 | - 사용 간편하고 코드 깔끔 | - 구현 복잡성 증가 |
| - 자원과 메서드 함께 캡슐화 | - 교착 상태 방지에 유리 | - 성능 저하 가능 |
💡 세마포어는 자원의 상태를 나타내는 일종의 '변수'로써 소유 개념이 아니지만, 뮤텍스는 자원을 점유한 프로세스나 쓰레드가 잠시 소유하였다가 작업이 끝나면 반환하는 개념
#교착 상태 #식사하는 철학자 문제 #자원 할당 그래프 #교착 상태 발생 조건
dining philosophers problem
- 계속 생각을 하다가 왼쪽 포크가 사용 가능하면 집어든다.
- 계속 생각을 하다가 오른쪽 포크가 사용 가능하면 집어든다.
- 왼쪽과 오른쪽 포크를 모두 집어들면 정해진 시간동안 식사를 한다.
- 식사 시간이 끝나면 오른쪽 포크를 내려놓는다.
- 오른쪽 포크를 내려놓은 뒤 왼쪽 포크를 내려놓는다.
- 다시 1번부터 반복한다.
철학자 : 프로세스/스레드
포크 : 자원(임계 구역)
생각 : 자원을 기다리는 것
교착 상태 dead lock
- 일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상
자원 할당 그래프 (resource-allocation graph)
- 네모 : 자원
- 원 : 프로세스
- 점 : 사용가능한 자원의 개수
- [자원 → 프로세스]화살표 : 프로세스가 자원을 할당받아 사용 중
- [프로세스 → 자원] 화살표 : 프로세스가 자원 할당 대기 중
- 상호 배제 (mutual exclusion)
- 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태
- 점유와 대기 (hold and wait)
- 자원을 할당 받은 상태에서 다른 자원을 할당받기를 기다리는 상태
- 비선점 (nonpreemptive)
- 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태
- 원형 대기 (circular wait)
- 프로세스들이 원의 형태로 자원을 대기하는 형태
#교착 상태 예방 #교차 상태 회피 #교착 상태 검출 후 회복
- 교착 상태 발생 조건 중 하나를 제거
-
상호 배제 없애기
- 모든 자원을 공유 가능하게 만든다 → 이론적으로 가능, 현실적으로 불가능
-
점유와 대기 없애기
- 특정 프로세스에 자원을 모두 할당하거나 아예 할당하지 않기
→ 자원의 활용률이 낮아짐
-
비선점 조건 없애기
- 이용중인 자원을 빼앗기
- 선점이 가능한 자원(CPU)에 대해 효과적
- but 모든 자원이 선점 가능한 것은 아니다
-
원형 대기 조건 없애기
- 자원에 번호를 붙이고 순서대로 자원을 할당
- 모든 자원에 index 부여 과정 어려움, indexing에 따라 활용률이 달라짐
- 무분별한 자원 할당으로 인해 발생했다고 간주하고 배분할 수 있는 자원의 양 내에서 할당하기
- 항상 안정 상태를 유지하도록 자원을 할당하는 방식
- ex) 은행원 알고리즘
안전 순서열 : 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
안전 상태 : 교착 상태 없이 모든 프로세스가 자원을 할당 받고 종료될 수 있는 상태
- 안전 순서열 O
불안정 상태 : 교착 상태가 발생할 수도 있는 상태
- 안전 순서열 X
- 선점을 통한 회복
- 교착 상태가 해결될 때까지 한 프로세스 씩 자원을 몰아주기
- 프로세스 강제 종료를 통한 회복
- 교착 상태에 놓인 프로세스 모두 강제종료 → 작업 내역을 잃을 위험
- 교착 상태가 해결될 때까지 한 프로세스씩 강제 종료 → 오버헤드
교착 상태 무시
- 드물게 발생하는 잠재적 문제를 무시로 대처
- 타조 알고리즘
우선순위 스케줄링은 선점형? 비선점형?
https://eun-jeong.tistory.com/17
HRN (Highest Response Ratio Next)
필로소퍼는 교착 상태 회피?
-
옳지 않은 것을 모두 고르시오.
- 라운드 로빈 스케줄링의 타임 슬라이스 크기를 키우는것이 스케줄링에 효과적이다.
- 최소 잔여 시간 우선 스케줄링은 선점형 스케줄링이다.
- 자원 할당 그래프가 원의 형태로 그려지면 교착상태가 발행한 것이다.
- 모니터는 사용자가 사용하기 편한 동기화 도구로 조건 변수를 사용한다.
- 임계 구역의 코드를 여러 프로세스가 동시에 실행하여 데이터의 일관성이 깨진 것을 레이스 컨디션이라고 한다.
-
교착 상태 발생 조건 4가지
-
스케줄링 알고리즘 중 다단계 피드백 큐 스케줄링은 [ A ] 의 발전된 형태로 [ B ] 가 가능해져 [ C ]를 해결할 수 있다.
-
동기화 기법 중 뮤텍스 락과 세마포어의 차이점
정답
1. 1, 3
2. 상호 배제, 점유와 대기, 비선점, 원형 대기
3. 다단계 큐 스케줄링, 큐간의 이동, 기아현상
4. 뮤텍스 락은 소유권이 존재하여 하나의 자원이 있는 경우에만 적용 가능하지만 세마포어는 자원이 여러개 있는 경우에도 적용이 가능하다.
뮤텍스 - 메모리 안, 프로세스 내에 동기화, 세마포어 - 파일, 프로세스 사이 동기화