[운영체제] 3. 프로세스 & 스레드(4/5)

2.3.7 모니터 : 고급 동기화 프리미티브 : 정확한 프로그램 작성을 도움(프로그래밍 언어 자체 지원 -> 세마포어의 위험성을 배제)

모니터의 속성 : 상호배제 성취 -> 단 하나의 프로세스만 한 순간에 모니터에서 활동 가능.

But 프로세스가 진행할 수 없을 때 대기하는 방법도 필요. 버퍼가 가득 차면 생산자는 어떻게 블록되어야 하는가?

-> 조건 변수와 wait, signal 연산을 통해 해결

 

두 프로세스가 동시에 모니터에서 활동하는 것을 피하기 위해, signal이후 어떻게 될 것인가에대한 규칙 필요

wait와 signal이 sleep와 wakeup과 유사하나, 자동적으로 상호배제가 이루어짐.

 

 

기찬아 이거 모르겠어 알려줘.

아이템 만들고 집어넣는다. 뺴고, 쓴다.

모니터를 선언하고, 컨디션은 꽉 차있거나 비어있거나.

인티저는 카운트.

카운트가 꽉차면 wait(full) -> 잔다.

그기아니면, 아이템 넣고 카운트 +1하고,

카운트 1이라도 있으면 시그널(엠프티)을 보내서 깨운다.

 

소비자, 카운트가 0이면 자고

그게아니면 리무브 하고 카운트 빼고, 카운트가 하나라도 비면 생산자를 깨움.

-필기참조.

 

 

Hoare : 기존 프로세스 중단, 새 프로세스 수행 : if문으로 비교, 에러를 줄일 수 있음

람슨 & 리들 : 깨워준 스레드 먼저, 이후 깨어난 스레드 : while문으로 비교, 계속 체크하니 에러가 없음.

signal과 notify의 단어적 의미차이도 존재. ->while문은 원래 한바퀴 더 돌면서 확인을 한다.

 

자바는 synchronized 메서드를 사용

 

Lock free 데이터 구조

스레드의 개수가 많아질수록 경쟁 심화 ->멀티 코어에서 락이 많이 걸리면 성능 저하 -> cpu에서는 아토믹 cas라는 명령어 지원.

기존의 값을 비교해서 일치하면 새로운 값을 적용하는 방식으로 작동

주소 P에 저장된 값이 x와 같으면, p에 저장된 값이 x+nd로 바뀌고, 다르면 다시 do로 감.

 

Head에 접근할 땐 lock을 걸여줘야 함. CAS명령어를 통해 리스트나 트리 등을 만들어서 구현하는게 락 컨디션을 줄일 수 있음.

push와 pop을 보면, 헤드가 가리키는 노드 넣는게 푸시, 첫번째 노드 빼는게 pop -> 성능 개선.

락 프리 데이터 스트럭쳐를 구현해서 사용할 때, ABA 문제가 있음.

리스트 100개를 잡아놓고, 필요할 때 빼오고 하는 식으로 구현하는데,

그림을 보면 스레드 1에서 pop. CAS전에 다른 스레드가 실행될 수 있음 -> 리스트가 꺠져버릴 수 있음.

해결 -> 시퀀스 번호를 잘 확인해야 함.

 

2.3.8 메세지 패싱 : 상호배제 뿐만 아니라 동기화 까지 해결

- 센드 쪽이 블로킹, 즉 센드 쪽이 보내려 하면 리시버쪽이 준비될 때 까지 기다림. 이 방법을 랑데뷰라 부름.

- 센더 쪽은 논블로킹, 리시브 쪽은 블로킹 : 센더는 보내고 자기일을 함. 리시버는 메세지가 올 때 까지 기다림

- 둘 다 논블로킹 : 메세지를 저장하는 별도의 큐, 어드레싱이 필요해짐.

-> 메세지를 어디서 가져오고 어디로 보낼 것인가? : 프로그래밍을 하는 시점에 PID(컴퓨터 네트워크에서 데이터 패킷을 구분하기 위한 식별자)를 모르기에 주소로 사용할 수 없음 -> 큐 내부에 주소를 부여 -> 키를 가지고 큐에 접근하여 메세지를 가져가는 등의 메세지 큐를 이용하여 ipc(프로세스 간에 데이터를 주고받기 위한 기술이나 메커니즘)를 함.

 

포트 : 서버를 구분함. 웹 클라이언트가 서버에 잡속하면 아이디와 포트로 접속하게 되는 것.

 

상호배제 코드가 없음 -> 블로킹 되기 떄문.

 

 

2.3.9 배리어

배리어를 왜 써야하냐면, 컴파일러가 인위적으로 코드의 순서를 바꿀수도 있고, cpu에서 실행순서를 자기 마음대로 할 수도 있음.

일반적 배리어는 배리어까지 모든 프로세스의 실행이 될 때 까지 기다림. (b)를 보면, C까지 도착해야 abcd프로세스가 동시에 통과

 

 

2.4 스케쥴링

비용 과다 발생 -> 시스템은 적절한 균형 유지 필요. 응답성은 10ms단위가 좋음.

cpu바운드 프로세스(a) 길게길게 가는 것. i/o바운드 프로세스(b) 쪼끔 계산하고 아이오 요청 기다리고 하는게 바운드 프로세스. 일반적으로 I/O에 우선순위를 둠. : 숏 텀 스케쥴링

숏 텀 스케쥴링을 위한 큐

batch job이 시작되면 새로운 잡들이 생겨나고 큐에 매달리게 됨. 대화형 프로세서들이 만들어지는데, batch job보다 먼저 처리되도록 함.

 

 

스케쥴링 알고리즘의 부류

1. 배치 : 통계작업이나 정형화된 작업. 은행 계좌이체, 이자 계산 등 정기적인 작업. : 하나를 오래 실행

2. 인터랙티브(대화식) : 일반적인 사용자 프로세스 : 번갈아 실행

3. 리얼 타임(실시간) : 데드라인이 있을 경우 당장 필요한 프로그램만 실행. 

 

스케쥴링 알고리즘의 목표

1. 모든 시스템에서 CPU를 공정히 배분.

2. Batch 시스템은 처리율, 작업시간 및 종료시간 사이(turnaround time)을 최소화, cpu를 최대한 놀게 하지 않음.

3. 인터랙티브 시스템은 응답시간이 짧아야 하고, 사용자의 기대에 비례하여 동작

4. 리얼타임은 데드라임을 기준으로함. 꼭 지켜야 하면 하드 리얼타임 시스템. 그게 아니면 소프트 리얼타임 시스템.

 

 

배치 시스템의 스케쥴링

1. 선입선출 : 프로세스에 대한 정보를 필요로 하지 않음. : waiting time 길어짐

이걸 개선하고자 한게

2. 짧은 잡 먼저 -> 프로세스와 관련한 시간에 대한 정보 필요 -> 실행 통계를 가지고 스케쥴링 : 비선점 배치 시스템

: 긴 게 자꾸 밀림.

or 3. 최단 잔여시간 우선 : 남은 실행시간이 가장 짧은 작업을 선택. : 2의 선점형 버전

+HRRN : Response Ratio에따라.

(대기시간 + 서비스 시간) / 서비스 시간

 

2.4.3 인터랙티브 시스템 스케쥴링

1. 라운드 로빈 : 끝나면 뒤로 미루기(번갈아). time slice를 모두 소모하면 다음 프로세스를 실행. 이 슬라이스 값(퀀텀)을 잘 설정해야함. 자주 해야 응답성이 높은거니까. 이상적인 퀀텀은 프로세스에 할당된 타임 퀀텀이 다 소비되기 전에 사용자의 입력을 기다리는게 베스트. 응답시간보다 약간 길게 주는 것.

-> 작업을 끝내기전(I/O요청 전) 퀀텀을 다 소비하면 다시 스케쥴링 해야하며, 응답성 떨어짐

2. 버츄얼 라운드 로빈 : 보조 큐에서 먼저 수행을 하게 됨. 각 사용자마다 독립적인 타임 슬라이스(Time Slice)를 부여하여 작업을 처리

 

3. Priority 스케쥴링 : 우선순위마다 큐를 두고, 높은 순서 부터 실행

 

4. multilevel feedback queue(다단계 큐) : 다단계임. 총 100개의 할당 시간이 필요한 프로세스를 예로 들면 처음엔 한 번, 다음엔 두 번, 이렇게 쭉 가서 100번의 스왑이 필요한 라운드 로빈에 비해 7번으로 해결. 심지어 점점 낮은순위의 클래스로 이동하므로 점점 덜 자주 수행되면서 짧은 대화식 프로세스가 cpu를 차지하게끔 함.

 

5. short process next : 최단 작업(계산을 조금 하고 기다리는 것들)을 먼저 실행. 식에서 a는 가중치.

6. 개런티드 : 프로세서 타임을 n빵

7. 로터리 : 추첨하여 나눠진 비율대로 스케쥴링

 

8. Fair-share : 그룹 스케쥴링을 할 수 있도록 수식 도입 : 그룹 별로 CPU 할당 

• CPUj(i) = CPUj(i-1)/2 GCPUj(i) = GCPUj(i-1)/2
• Pj(i) = Basej+CPUj(i)/2 + GCPUk(i)/(4*Wk)

우선순위 동일, a는 그룹1, bc는 그룹 2 한번도 cpu를 할당하지 못했기에 프로세스 자체가 수행한 카운트, 그룹 카운트 모두 0

임의로 a를 먼저 실행 ->Wk는 0.5 했으니 4* 0.5 : 2 따라서 CPU시간이 반으로 줄어 30 30이 됨. -> 우선순위가 90이 됨

-> B,C는 여전히 60. 임의로 다음 B를 실행하면 C는 그룹 시피유를 할당받아 그룹cpu시간은 60이 됨. 따라서 우선순위를 다시 계산하면 74 90 75가 됨. 따라서 A가 스케쥴링. -> 96, 74, 67이 됨. 뭐 이렇게 하는거고 유닉스에서 이 알고리즘으로 스케쥴링.

 

스케쥴링 메카니즘은 스케쥴링 정책에서 메커니즘을 구분시킨 것.