CS : 운영체제(2)

참고 영상 : https://youtu.be/1PEe33_INZc?si=Y-qh8Rpy8q0yp6Nj

운영체제 (2) : https://shine-slowly.tistory.com/70

CS : 운영체제(1)

4. CPU 스케줄링

운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 분배하는 것

제대로 스케줄링되지 않으면 꼭 실행되어야 하는 프로세스가 실행이 되지 않거나 급하지 않은 프로세스만 반복해서 실행하는 일이 발생한다

 

프로세스마다 우선순위가 다르기 때문에 (= 빨리 처리해야 하는 프로세스가 있기 때문에) CPU를 사용하는 싶어하는 프로세스들이 차례로 돌아가면서 하는 것은 딱히 좋은 방법은 아니다.

 

입출력 작업이 많은 프로세스(=입출력 집중 프로세스, ex - 비디오 재생)의 우선운위는 CPU 작업이 많은 프로세스(=CPU 집중 프로세스)의 우선순위보다 높다.

입출력 집중 프로세스는 실행상태보다는 대기 상태에 많이 머물게 된다. 대기 상태에 가면 CPU를 안쓰기 때문에 입출력 집중 프로세스의 우선순위를 높여서 빠르게 처리하는 것이 CPU 집중 프로세스에게 CPU를 좀 더 많이 할당할 수 있게 된다. 

 

프로세스 우선순위(priority)

프로세스의 우선순위는 PCB에 저장된다. 우선순위가 높은 프로세스는 더 빨리 더 자주 실행되게 된다. 

운영체제가 다음 실행할 프로세스를 선정하기 위해서 모든 프로세스의 PCB를 확인하는 것은 비효율적이다.

그래서 운영체제는 스케줄링 큐를 사용한다. 자료구조에서 큐가 FIFO 구조이지만 스케줄링 큐에서 큐는 FIFO는 아니다.

먼저 큐에 삽입되었다고 먼저 CPU를 사용할 수 있는 것은 아니다.

스케줄링 큐의 종류에는 대표적으로 준비 큐와 대기 큐가 있다.

준비 큐는 CPU를 이용하기 위해 기다리는 줄이고 대기 큐는 입출력장치를 이용하기 위해 기다리는 줄이다.

준비 큐는 준비상태에 접어든 프로세스로 언제든지 CPU를 할당받아서 실행할 순 있지만 아직 자신의 차례가 되지 않아서 기다리고 있는 프로세스들이 서는 줄이다.

대기 큐는 대기상태에 접어든 프로세스가 서는 줄로 현재 당장 CPU를 사용할 필요가 없는 프로세스들이 서는 줄이다.

 

 준비 상태

• 당장이라도 CPU를 할당 받아 실행할 수 있지만 자신의 차례가 아니기에 기다리는 상태
• 자신의 차례가 되면 실행 상태로 간다. 준비 상태가 실행 상태가 되는 것을 디스패치라고 한다

대기 상태

• 프로세스가 실행 도중 입출력장치를 사용하는 경우
• 입출력 작업은 CPU에 비해 느리기 때문에 이 경우 대기 상태로 접어든다
• 입출력 작업이 끝나면 (입출력 완료 인터럽트를 받으면) 준비 상태로 간다

 

대기 큐 부분만 확대해서 보면 이런 방식으로 작동한다. 대기 큐에서 같은 장치를 요구한 프로세스들은 같은 큐에서 대기하게 된다.

 

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

한 프로세스가 CPU 할당받아서 CPU를 사용하는 실행하는 상태라고 했을 때, 그 프로세스보다 급한 프로세스가 발생하게 된다면 취하게 되는 방식에는 선점형과 비선점형이 있다.

- 선점형 스케줄링

• 현재 CPU를 사용 중인 프로세스로부터 CPU 자원을 빼앗아 다른 프로세스에게 할당
• 지금까지 다뤘던 정해진 시간만큼 돌아가면서 쓸 수 있던 것이 선점형 스케줄링의 일종이다
• 어느 한 프로세스의 독점을 막고 프로세스들에 골고루 자원을 배분할 수 있다
• 그만큼 문맥 교환 과정에서 오버헤드가 발생할 수 있다

? 문맥 교환 과정이란

한 프로세스(프로세스A)에서 다른 프로세스(프로세스B)로 실행 순서가 넘어가면, 기존 실행되던 프로세스 A는 지금까지의 중간 정보(프로그램 카운터 등 각종 레지스터 값, 메모리 정보, 열었던 파일, 사용한 입출력장치 등)를 백업

 

- 비선점형 스케줄링

•  현재 CPU를 사용 중인 프로세스의 작업이 끝날 때 까지 프로세스 기다린다
• 선점형 스케줄링에 비해 문맥 교환에서 발생하는 오버헤드가 적다
• 모든 프로세스가 골고루 자원을 이용하기 어렵다

 

CPU 스케줄링 알고리즘

운영체제마다 사용하는 CPU 스케줄링 알고리즘은 다르고 여기서는 7가지만 다루게 된다. 

 

- 선입 선처리 스케줄링 (FCFS 스케줄링, First Come First Served)

• 단순히 준비 큐에 삽입된 순서대로 처리하는 비선점 스케줄링
• 먼저 CPU를 요청한 프로세스부터 CPU 할당
• 프로세스들이 기다리는 시간이 매우 길어질 수 있다 (=호위 효과)

- 최단 작업 우선 스케줄링 (SJF 스케줄링, Shortest Job First)

• 호위 효과를 방지하기 위해서 CPU 사용이 긴 프로세스는 나중에 실행, CPU 사용 시간이 짧은 프로세스는 먼저 실행한다
• CPU 사용시간이 가장 짧은 프로세스부터 처리하는 스케줄링 방식
• 선점형으로 구현될 수도 있고 비선점형으로 구현될 수도 있다 (보통 비선점형으로 구분됨)

- 라운드 로빈 스케줄링 (RR 스케줄링, Round Robin)

• 선입 선처리 스케줄링 + 타임 슬라이스(time slice)
• 타임슬라이스: 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
• 정해진 타임 슬라이스만큼의 시간동안 돌아가며 CPU를 이용하는 선점형 스케줄링
  • 큐에 삽입된 프로세스들을 순서대로 CPU를 이용하되 정해진 시간만큼만 이용
  • 정해진 시간을 모두 사용하였음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입 (문맥교환)

- 최소 잔여 시간 우선 스케줄링 (SRT 스케줄링, Shortest Remaining Time)

• 최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링
• 최단 작업 우선 스케줄링 : 작업 시간이 짧은 프로세스부터 처리를 하는 스케줄링 알고리즘
• 라운드 로빈 스케줄링 : 정해진 타임 슬라이스만큼 돌아가며 사용하는 스케줄링 알고리즘
• 정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스로는 남은 작업시간이 가장 적은 프로세스 선택

- 우선순위 스케줄링

• 프로세스들에 우선순위를 부여하고, 우선순위 높은 프로세스부터 실행
• 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링
• 최단 작업 우선 스케줄링, 최소 잔여 시간 스케줄링은 넓은 의미에서 우선순위 스케줄링이라고 볼 수 있다
• 우선순위 스케줄링의 근본적인 문제점에는 기아 현상이 있다
  • 기아 현상(starvation) : 우선순위가 높은 프로세스만 계속 실행하게 되고 낮은 프로세스는 계속 연기된다
• 기아 현상을 방지하기 위해 에이징(aging) 방식을 사용한다
  • 에이징(aging) : 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식
  • 우선순위가 낮아도 언젠가는 우선순위가 높아진다

- 다단계 큐 스케줄링 (Multilevel queue 스케줄링)

• 우선순위 스케줄링의 발전된 형태
• 우선순위별로 준비 큐를 여러개 사용하는 방식
• 큐마다 스케줄링을 달리 처리해서 처리할 수가 있게 된다
• 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리
• 우선순위가 가장 높은 큐가 비어있으면 그 다음 우선순위 큐에 있는 프로세스 처리
• 큐 간 이동이 불가능하므로 기아현상이 발생할 수가 있다 (우선순위 고정)

- 다단계 피드백 큐 스케줄링 (Multilevel feed back queue 스케줄링)

• 다단계 큐 스케줄링의 발전된 형태
• 큐 간의 이동이 가능한 다단계 큐 스케줄링
• 다단계 큐 스케줄링의 기아 문제 해결
• CPU를 많이 써야하는 CPU 집중 프로세스는 점차 우선순위가 낮아지고 CPU를 비교적 적게 사용하는 입출력 집중 프로세스는 우선순위가 높아진다
• 자기 차례 때 실행이 안 끝났으면 우선순위가 낮아진 큐에 삽입된다
• 어떤 프로세스의 CPU 시간이 길면 우선순위가 낮아지고 어떤 프로세스가 낮은 우선 순위 큐에서 너무 오래 기다리면 우선순위를 높이는 방식
• CPU 스케줄링의 가장 일반적인 형태

 

5. 프로세스 동기화

동시다발적으로 실행되는 프로세스들은 서로 협력하며 영향을 주고 받는다. 이 과정에서 자원의 일관성을 보장해야 한다.

워드 프로세서 프로그램의 경우 맞춤법 검사 프로세스, 입력 내용을 화면에 출력하는 프로세스 등이 있다. 올바른 수행을 위해서는 아무렇게나 마구 실행되는 것이 아니라 수행 시기를 맞추어야 한다. 

 

프로세스 동기화란 프로세스의 수행 시기를 맞추는 것이다.

• 실행 순서 제어 : 프로세스를 올바른 순서대로 실행하기
• 상호 배제 : 동시에 접근해서는 안되는 자원에 하나의 프로세스만 접근하게 하기

 

실행 순서 제어를 위한 동기화 : reader writer problem

Writer : Book.txt 파일에 값을 저장하는 프로세스

Reader : Book.txt 파일에 저장된 값을 읽어들이는 프로세스

 

두 프로세스를 무작정 동시에 실행하면 안된다. Reader 프로세스는 'Book.txt 안에 값이 존재한다'라는 조건이 만족되어야만 실행이 가능하다. 동시에 실행된다고 하더라도 Writer 프로세스가 선행되어야 한다는 것이다.

동시다발적인 두 개 이상의 프로세스가 있을 때 실행순서를 제어하도록 동기화 하는 것을 실행순서제어를 위한 동기화이다.

상호 배제를 위한 동기화 (1) : Bank account problem

공유가 불가능한 자원의 동시 사용을 피하기 위한 동기화

현재 계좌에 잔액이 10만원이 있다고 가정했을 때, 프로세스 A와 B를 동시에 실행했을 때 17만원이 되지 않을 수 있다.

상호 배제를 위한 동기화 (2) : Producer & Consumer problem

물건을 계속해서 생산하는 생산자(producer, 프로세스 혹은 스레드)와 물건을 계속해서 소비하는 소비자(consumer, 프로세스 혹은 스레드)가 존재하고 총합 변수를 공유하게 된다.

이 상태에서 생산자와 소비자를 각 10,000번 실행했을 때 총합이 0과 다른 값이 되거나, 오류가 발생하기도 한다.

동기화가 되지 않았기 때문에 발생하는 문제이다. (동시에 접근해서는 안되는 자원에 동시에 접근해서 발생한 문제)

 

공유 자원 : 여러 프로세스 혹은 스레드가 공유하는 자원 (전역변수, 파일, 입출력장치, 보조기억장치)

임계 구역 : 동시에 실행하면 문제가 발생하는 자원에 접근하는 영역 구역

 

임계 구역에 진입하고자 하면 진입한 프로세스 이외에는 대기해야한다.

임계구역에 동시에 접근하면 자원의 일관성이 깨질 수 있다. 이를 레이스 컨디션(race condition)이라고 한다.

 

운영체제가 임계 구역 문제를 해결하는 세가지의 원칙

1. 상호 배제 : 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 들어올 수 없다.
2. 진행 : 임계 구역에 어떤 프로세스도 진입하지 않았다면 진입하고자 하는 프로세스는 들어갈 수 있어야 한다.
3. 유한 대기 : 한 프로세스가 임계 구역에 진입하고 싶다면 언젠가는 임계 구역에 들어올 수 있어야 한다. (무한정 대기 X)

동기화 기법

 

동기화 기법 중 뮤텍스 락, 세마포, 모니터 총 세 가지 기법을 다룰 것이다. (어떻게 상호배제를 이루고 실행 순서 동기화를 하는지)

 

뮤텍스 락 (상호배제)

상호 배제를 위한 동기화 도구 (자물쇠 역할)

탈의실 문이 잠겨 있으면 누가 사용 중이라는 것을 아는 것과 같은 동작

• 자물쇠 역할 : 프로세스들이 공유하는 전역 변수 lock
• 임계 구역을 잠그는 역할 : acquire 함수
• 임계 구역을 여는 역할 : release 함수

acquire(){
	while(lock == true){
	// 잠겨 있는지를 반복적으로 확인
	}
	lock = true;
}

release() {
	lock = false;
}

임계 구역이 잠겨 있으면 임계 구역이 열릴 때까지 임계 구역을 반복적으로 확인한다.

⇒ 바쁜 대기 (busy waiting) : 무한히 임계 구역을 확인함

 

세마포 (상호배제, 실행순서)

뮤텍스 락과 비슷하지만 좀 더 일반화된 방식의 동기화 도구

뮤텍스 락은 탈의실이 하나 있는 경우 (공유자원이 하나)였는데, 공유 자원이 여러 개 있는 경우에도 적용 가능한 일반화된 도구가 세마포이다.

임계 구역 앞에서 멈춤 신호를 받으면 잠시 기다리고 접근 가능하다는 신호를 받으면 임계 구역에 진입한다.

• 임계 구역에 진입할 수 있는 프로세스의 개수 (사용 가능한 공유 자원의 개수) 를 나타내는 전역변수 S
• 임계 구역에 들어가도 좋은지, 기다려야 할지를 알려주는 wait 함수
• 임계 구역 앞에서 기다리는 프로세스에 '이제 가도 돼'라고 신호를 주는 signal 함수

wait() {
	while(S<=0){
    // 무한히 반복
    }
    S--; // 사용할 수 있는 프로세스 1 낮추고 (내가 들어갈거니까) 들어가기
}
// 임계 구역
signal() {
	S++; // 빠져나갔으니까 1 증가
}

세마포도 busy waiting이 적용되어있다. ⇒ 반복적으로 확인 (CPU 사이클 낭비)

 

Busy Waiting 해결법

• 사용할 수 있는 자원이 없을 경우 대기 상태로 만든다 (PCB를 대기 큐에 삽입한다)
• 사용할 수 있는 자원이 생겼을 경우 대기 큐의 프로세스를 준비 상태로 만든다 (PCB를 대기 큐에서 꺼내 준비 큐에 삽입한다)

자원 다 사용한 프로세스가 signal을 호출하면 그 함수 안에서 대기 큐에 p 제거하고 준비상태로 만드는 것! (계속 지켜볼 필요 X)

 

세마포는 실행 순서를 보장할 수도 있다.

• 세마포 변수 S를 0으로 두고
• 먼저 실행할 프로세스 뒤에 signal 함수,
• 다음에 실행할 프로세스 앞에 wait를 붙인다

 

모니터 (상호배제, 실행순서)

임계구역 앞뒤로 wait(), signal() 호출 순서 헷갈리거나 실수할 가능성이 높다 -> 사용자가 다루기에 편리한 동기화 도구

공유자원과 공유자원 접근 통로는 묶어서 관리한다. 공유자원에 접근하고자 하는 프로세스랑 스레드는 반드시 특정 인터페이스를 통해서만 접근 가능하다. 

 

실행 순서 제어를 위한 동기화는 조건 변수를 사용한다. 조건 변수란 프로세스나 스레드의 실행 순서를 제어하기 위해 사용하는 특별한 변수이다 (wait랑 signal 호출할 수 있는 특별한 변수)

조건변수에 대한 큐로 실행 순서를 제어할 수 있다. 상호배제를 위한 큐랑 조건 변수를 위한 큐는 다른 큐이다.

 

조건 변수는 wait와 signal을 호출할 수 있는데,

• 조건변수.wait() : 대기 상태로 변경, 조건 변수에 대한 큐에 삽입
• 조건변수.signal() : 대기 상태인 프로세스를 준비 상태로 변경 ⇒ 먼저 실행되어야 하는 프로세스가 끝나면서 signal을 호출하면서 대기 하고 있던 프로세스가 준비 상태가 된다

⇒ 특정 프로세스가 아직 실행될 조건이 되지 않으면 wait로 실행 중단하고 조건이 충족되면 signal을 통해 실행 재개