실제로 os에서 사용되는 스케쥴링, 다중프로세서에서 강결합된 공유 메모리 주소 2가지 비교, 다중 프로세서 스레드 스케줄링

실제로 os에서 사용되는 알고리즘

우선순위가 위쪽으로 갈수록 큽니다.

priority에 따라 time quantum을 따로 줍니다.

priority가 높을수록 time quantum이 작습니다.(= 빨리빨리 바꾼다는 뜻입니다.)

 

Solaris에서 사용하는 스케줄링은 preempive인가?

time quantum이 있다는 건 preemptive 한다는 뜻입니다.
강제로 뺏습니다.

실제 운영체제에서는 우리가 배운 알고리즘 여러 개를 복합적으로 사용합니다.

 

Linux

 

완벽히 공평한 스케줄러를 사용하고 있습니다.

이미 실행한 시간을 기록하고 있습니다.

 

레드 블랙트리는 뭐에다가 써먹나요?

어떤 노드에 가든 일정한 시간이 걸리도록
log(n) 시간 안에 삽입, 삭제할 수 있도록

 

노드들 하나가 프로세스입니다.

 

이미 실행한 시간이 가장 많은 것은?

T6, 제일 오른쪽에 있는 것입니다.

 

그러면 누구한테 cpu를 할당해줘야 하나요?

T7
지금까지 실행한 시간이 짧으니깐 먼저 cpu에 넣어줘야 합니다.

 

이게 라운드 로빈이긴 합니다.

이게 왜 라운드 로빈과 priority를 합친 알고리즘인가요?

기본적으로 돌아가면서 cpu를 할당받을 수 있습니다(그래서 virtual runtime이라는 계념을 만든 것입니다.)
제일 실행을 못한 T7부터 cpu를 할당받으니 실행시간이 작은 것부터 우선순위가 높아집니다.

 

preemptive인가요?

라운드 로빈은 time quantum이 있어야 합니다.
T7가 트리를 나가서 cpu를 사용하고 나서 다시 트리로 돌아올 때 사용시간은 더 커져서 들어올 것입니다.

 

 

Window Xp

클래스 내에서 처음에는 기본 우선순위 (normal)를 가지나 time quantum 소모하면 낮아지고, IO 마치면 높아짐.

 

Preemtive인가?

맞습니다.
라운드 로빈이니깐요

 

---

 

 

다중 프로세서(많은 cpu)

 

공유 메모리 구조(=강 결합된 구조)

 

이렇게 생긴 애들은 대칭, 비대칭으로 나눕니다.

 

대칭 다중 처리 SMP, Symmetric MultiProcessing

각자 프로세서가 다 똑같다.

각자 메모리를 차지하는 영역이 있습니다.

 

 

비대칭 다중 처리 AMP, Asymmetric MultiProcessing

• 마스터에서만 os가 돌아갑니다.
• 마스터에서만 커널이 돌아가고 나머지 프로세스들에게 자원을 나눠줍니다.
• 나머지 cpu는 유저 프로세스만 실행합니다.
• 전체 컴퓨터의 메모리와 i/o는 마스터에게 허락받고 사용합니다.
• 마스터가 성능의 병목지점이 됩니다, 마스터가 무너지면 다 무너집니다.

 

부하 분산(load balancing) 면에서 어느 쪽이 유리한가?

1번이 유리합니다.
아녔습니다.
일이 있어도 노는 애들이 발생할 수 있습니다.

2번이었습니다
일이 있는 한(큐에 있는 한) 노는 애들은 없습니다.

 

공유를 위한 locking 메커니즘이 필요한 쪽은? Locking 메커니즘 고장 시 전체 시스템에 문제가 생기는 쪽은?

2번입니다.
상호 배제를 해야 합니다

---

 

스래드를 어떻게 분배하는가?

주목해야 할 것

• 한 프로세스 내에 여러 개 스레드들이 있을 때 
• 다중 프로세서 환경에서는 한 프로세스 내의 스레드들을 동시 실행하여 큰 성능 향상 가능

 

다중 프로세서 스레드 스케줄링(multiprocessor thread-scheduling)

다중 프로세스 스레드 스케줄링은 4가지 종류가 있습니다.

 

다중 프로세서 스레드 스케줄링 - 부하공유

 

각 프로세스를 스레드를 넣어주는 것입니다.

 

내가 어느 프로세서에 할당될지 모릅니다.

그냥 cpu가 비면 가는 것입니다.

이것과 비슷해 보입니다.

cpu부하를 모든 프로세서가 공유합니다.

 

 

장점

• 부하를 나눌 수 있습니다.(노는 애들이 없습니다.)

관련된 게 없다면 프로세서에 들어갔다 나올 수 있습니다.

 

 

다중 프로세서 스레드 스케줄링 - 갱 스케줄링

• 한 프로세스가 들어갈 때
• 성격이 비슷한 한 프로세스의 스레드는 다 같이 들어갑니다
• "한 프로세스에 A가 들어갈 때는 같이 들어가자!"

 

장점

• 관련된 스레드를 동시 수행할 수 있습니다.

단점

• A라는 프로세스가 들어가려면 cpu 가 자리를 비워놔야 합니다.

 

 

다중 프로세서 스레드 스케줄링 - 전용 프로세서 할당

스케줄링을 안 하는 것입니다

 

프로세스가 "나 10개 필요해" 하면

cpu가 프로세서 10개를 줍니다.

 

"무조건 작업을 빨리 끝내는 것에 초점을 맞춥니다."

 

 

 

다중 프로세서 스레드 스케줄링  - 동적 스케줄링

동적 스케줄링은 부하공유, 갱 스케줄링 같은 것을 적절히 섞어서 사용하는 것입니다

 

요청 개수란?

프로세스가 시작하면서 os에 요청하는 것

 

갱 스케줄링입니다.

 

 

전용 프로세서 할당입니다.

---

 

 

프로세스 실행시간은 스케줄링과 관련 없습니다!

 

평가척도가 다양한데, 스케줄링 알고리즘을 실제로 어떻게 선택하는가?

• 요구사항 기반으로
• 상대적으로 중요한 거부터

 

1. cpu 사용량, 응답 시간

• cpu 사용량을 최대로 올리려면 일괄처리 작업을 해야 합니다.
• cpu burst가 높은 거부터 하면 cpu는 계속해야 합니다
• 그러면 response time은 낮아지겠지요
• 즉, 서로 충돌합니다. 한쪽이 높아지면 한쪽은 낮아지죠

 

2. 평균 반환 시간, 최대 기다리는 시간(SJF)

• 최대 기다리는 시간이 높아진다면 불공정하게 됐다는 것입니다.
• 평균 반환시간이 짧다면 짧은 프로세스들이 먼저 합니다.
• 그렇다면 계속 기다리는 애들이 있을 수도 있습니다(기아 현상)

 

3. i/o를 사용, cpu사용량

• cpu사용량을 높이려면 cpu burst가 긴 거를 먼저 하면 됩니다.
• context switch도 없이 cpu를 계속 실행하는 것입니다.
• 그러면 i/o 사용량은 낮아지겠지요
• i/o를 계속 사용하면 cpu 사용률이 낮아질 수 있습니다.

 

 

결정론적 모델링 - 우리가 지금까지 평가를 했습니다. 그걸로 결정하는 것입니다.(우리가 해왔던 것입니다.)

큐잉 모델 - 수학적인 확률 모델인 큐잉에 실험하는 것

모의실험 - 소프트웨어로 알고리즘을 실험하는 것

구현 - 진짜로 해보는 것

 

결정론적 모델링 (Deterministic Modeling)

 

큐잉 모델

모의실험, 구현

 

결정론적 모델링

 

구현 

 

큐잉 모델