http://www.kocw.net/home/search/kemView.do?kemId=1046323
-> 해당 강의를 듣고 정리한 내용
6. CPU 스케쥴링
6-1 프로세스의 종류 - [ cpu, I/O ] bound 프로세스
1) CPU 버스트와 I/O 버스트
CPU 버스트 : 사용자 프로그램이 CPU를 직접 가지고 빠른 명령을 수행
I/O 버스트 : I/O 요청이 발생해 커널에 의해 입출력 작업을 진행하는 비교적 느린 단계
프로그램이 실행된다는 것은 I/O버스트와 CPU버스트가 번갈아가며 실행된다는 것이다.
프로그램에 따라 각 버스트의 빈도와 길이가 다르다.
cpu bound 프로세스(job)와 I/O bound 프로세스가 있다.
-
I/O bound 프로세스 : cpu를 짧게 쓰는데 빈도가 높다.
-> cpu를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job -
cpu bound 프로세스 : 계산 위주의 job
여러 종류의 프로세스들이 섞여 있기 때문에 CPU 스케쥴링이 필요하다.
I/O bound 프로세스는 사용자들과 interective 한 job이기에 빠른 응답이 중요하다. 즉, cpu 스케줄링을 할 때 cpu버스트가 짧은 프로세스(I/O bound 프로세스)에게 우선적으로 cpu를 사용할 수 있도록 하는 스케줄링이 필요하다.
6-2 CPU 스케쥴러
준비 상태에 있는 프로세스들 중 어떠한 프로세스에게 cpu를 할당할지 결정하는 운영체제의 코드이다.
디스패처(Dispatcher) : CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다. <문맥교환이라고 함>
cpu 스케줄링 방식에는 비선점형(nonpreemptive)과 선점형(preemptive)이 있다.
비선점형(nonpreemptive) : 강제로 빼앗지 않고 자진 반납
선점형(preemptive) : 강제로 빼앗음
1) 성능평가 척도
척도는 시스템 관점과 사용자 관점으로 구분할 수 있는데
시스템 관점에서는 CPU이용률, 처리량(주어진 시간 동안 준비 큐에서 기다리고 있는 프로세스 중 몇 개를 끝마쳤는지)
사용자 관점에서는 소요시간(준비 큐에서 기다린 시간 + 실제로 CPU를 사용한 시간), 대기시간(준비 큐에서 CPU를 얻기 위해 기다린 시간의 합), 응답시간(준비 큐에 들어온 후 첫 번째 CPU를 획득하기까지 기다린 시간) 등 기다린 시간과 관련되어있다.
소요시간은 프로그램이 시작해 종료하는 데까지 걸리는 시간이 아니라
해당 CPU 버스트가 완료될 때까지 소요된 시간이다.
프로그램이 시작해서 종료하기까지 CPU 버스트는 여러 차례 있을 수 있다.
[소요시간은 CPU 버스트의 수만큼 각각 별도로 측정된다.]
2) 스케쥴링 알고리즘
1 . FCFS(first come first served) : 선입선출 (비선점형)
- 일상생활(은행, 공항, 화장실)
- 비효율적
단점 : 콘보이 현상
CPU 버스트가 짧은 프로세스가 CPU 버스트가 긴 프로세스보다 나중에 도착해 오랜 시간을 기다려야 하는 현상
- SJF ( Shortest - Job First) : 최단작업 우선 (비선점형, 선점형 두가지로 구현가능)
- 가장 짧은 프로세스에게 제일 먼저 CPU를 할당
- 평균 대기시간을 가장 짧게 하는 최적 알고리즘
단점 : 기아현상 (starvation) CPU사용시간을 미리 알 수 없다.
7. Process Synchronization[프로세스 동기화] (=Concurrency Control)[병행 제어]
공유 데이터의 동시 접근은 데이터의 불일치 문제를 발생시킬 수 있다.
Race Condition :
여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
언제 발생할 수 있니?
1. Multiprocessor system
2. 공유 메모리를 사용하는 프로세스들
3. 커널 수행 중 인터럽트 발생 시
해결책 : 커널 모드에서 수행 중일 때는 CPU를 preempt하지 않음
커널 모드에서 사용자 모드로 돌아갈 때 preempt
Critical section : 공유 데이터를 접근하는 코드
7-1 프로그램적 해결법
1) 프로그램적 해결법의 충족 조건
-
Mutual Exclusion (상호 배제)
프로세스가 critical section을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안 된다.
-
Progress (진행)
아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야한다.
-
Bounded Waiting (유한 대기)
프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야한다.
첫 번째 알고리즘
-> 상호 배제 만족
-> progress를 만족 X (들어가고 싶은 빈도가 다른 경우)
두 번째 알고리즘  -> 깃발을 둘 다 들고있고 아무도 못들어가는 문제가 발생할 수 있다.
세번째 알고리즘(피터슨 알고리즘)
깃발과 turn을 모두 사용
-> 중간 어디에서 cpu를 빼앗겨도 문제가 없다. 세가지 조건 모두 만족
-> But, 단점 : Busy Waiting (=spin lock)!
하드웨어적으로 atomic하게 수행할 수 있도록
데이터를 읽으면서 동시에 쓰면 도중에 cpu를 빼앗기지 않을것이므로 문제를 해결할 수 있다.
<test_and_set>
-> 이런 작업은 귀찮음
-> 세마포어를 이용
7-2 Semaphores(세마포어)
세마포어 -> 일종의 추상 자료형, Integer variable 을 가지고 자원의 개수를 센다.
세마포어에는 P연산, V연산이 있다. 각 연산은 atomic 연산이다.
P연산 : 자원의 획득 - 자원이 있으면 가져가고 없으면 생길 때까지 기다림
V연산 : 자원의 반납
P연산에서 발생할 수 있는 busy-wait는 효율적X
Block & Wake up방식의 구현 가능 (=sleep lock)
Block & Wake up는 오버헤드가 있다.
critical section의 길이가 짧은 경우 busy wait해도 괜찮음
긴 경우 Block & Wake up 이 적당
일반적으로는 Block & Wake up 추천
- Binary semaphore(mutex) : 0 또는 1 값만 가질 수 있는 semaphore
- Counting semaphore
Deadlock
둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
하나씩 차지하여 상대방 것을 요구한다.
획득의 순서를 정하면 이 문제는 해결된다.
Starvation
indefinite blocking.
7-3 Classical Problems of Synchronization
1) Bounded - Buffer Problem
- Producer : Empty 버퍼를 기다린다.
- Consumer : Full 버퍼를 기다린다.
mutex ; lock을 걸기위한 세마포어 변수
full ; 내용이 들어있는 버퍼의 개수를 세는 변수
empty ; 내용이 비어있는 버퍼의 개수를 세는 변수
#### 2) Readers-Writers Problem
Process가 읽는 프로세스, 쓰는 프로세스 2종류가 있다.
읽는 것은 동시에 여럿이서 해도 상관 X, but writer는 한명만
쓰는 동안에 다른 쓰는 친구가 오면 lock을 걸고, 읽는 것은 누군가 읽고 있어도 동시에 읽어도 상관 X
Reader에서 readcount를 lock하기위해 mutex를 이용
공유데이터
- DB
- readcount; 읽는 것은 여러 명이 읽을 수 있도록 만듦
starvation 발생 가능
3) Dining - Philosophers Problem
철학자가 배가 고프면 젓가락을 잡아 밥을 먹고 다 먹으면 생각을 한다.
각자 생각하는 시간과 밥을 먹는 시간 주기가 다르다.
왼쪽, 오른쪽 젓가락이 모두 있어야 밥을 먹을 수 있다.
젓가락은 공유 자원이다.
-> Deadlock의 문제가 발생할 수 있다.
모두 왼쪽 젓가락을 잡는다면?
아무도 오른쪽 젓가락을 잡을 수 없다.
해결 방안
- 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다.
- 양쪽 젓가락을 모두 잡을 수 있을 때에만 집을 수 있게 한다.
self ; 양쪽 젓가락을 집을 수 있는 상태
7-4 Monitor <모니터>
High-level synchronization construct
세마포어의 문제점 -> 코딩하기 힘들다. -> 정확성의 입증이 어렵다. -> 자발적 협력이 필요하다. -> 한번의 실수가 모든 시스템에 치명적 영향
프로그래밍 언어 차원에서 동기화 문제 해결법
공유 데이터를 접근하기 위해서는 내부의 프로시저를 통해서만 접근할 수 있도록 만듦
모니터는 동시 접근을 허용 X, 한번에 하나의 프로세스만이 활동 가능
lock을 걸 필요가 없다.
condition variable
x.wait() // blocked상태로 큐에 줄서기
x.signal() // 큐에 있는 것 깨워주기
