11강 CPU Scheduling 2/ Process Synchronization 1

https://core.ewha.ac.kr/publicview/C0101020140401134252676046?vmode=f 

반효경 [운영체제] 11. CPU Scheduling 2 / Process Synchronization 1

cpu 스케쥴링 이어서 시작됨

 

Round robin 추가설명

round robin 이 가능 했던 이유는 context switching 메커니즘이 제공되기 때문에 가능했던 이야기이다.

근데 실제 세계에서는 context switching 이 불가하지않나 -> 은행같은경우나 화장실의경우 fcfs 인 이유가 똥을 중간에 끊었다가 다시 완벽하게 문맥에 맞게 쌀수는 없으니까 이런식으로 예시가 들었다.

 

지난번에 이은 순서라 5번부터 시작한다.

 

5.multilevel queue

기존에는 ready queue가 한줄서기함  -> mulitlevel 이 붙는 앞으로 나올것들은 여러줄을 세우는 방법이다.

이런식인데 위에 있는 queue가 우선순위가 제일 높은거고 점점 우선순위가 낮은것이다.

우선순위가 나뉘어있고 우선순위별로 줄이있는것이다.

 

여기 그림에서는 우선순위가 5가지가 있는데 

1.시스템 관련 프로세스

2.사람과 상호작용하는 프로세스

3.사람과 상호작용하지만 조금 적게 상호작용하는 것

4.cpu만 오래잡고 일하는 프로세스

5.student process??설명이 이상함

 

어쨋든 우선순위는 정형화 되있는거 같지는 않고 이것은 어느 교재에서 가져온것이라함

 

이 우선순위는 완전 계급제임 애초에 성골 진골 노비 프로세스가 나뉘어있음

 

cpu가 주어지는것이 성골이 기다리면 일단 성골부터 주고 그 다음 순위가 진골 이런식이다.

출신에 따라서 우선순위를 극복할수 없다.

 

줄은 여러개지만 cpu 는 하나이기에 고려사항이있다.

1.프로세스를 어느줄에 넣을것인가?

2.높은 우선순위에만 cpu 사용권을 준다면 우선순위가 낮은 줄은 starvation 이 올것이다.

 

 ready queue를 여러개로 분할한다

이 자료에서는 foreground ,background 두줄로 분할한다.(이거 나누는건 자료에 따라 다 다른가보다.)

foreground  : 사용자와 상호작용하는것 넣음

background : cpu 만 주구장창 쓰는것 넣음

 

각 큐마다 스케쥴링 방식이 필요할것임(각각 다르게 적용가능하다)

foreground  는 사람과 상호작용하니  ->RR 적용

background 는 cpu 만 그냥 오래 쓰니 응답성 필요없으므로 context switching 비용을 줄이고자 그냥 fcfs 씀

 

그래서 큐에 특성에 맞는 큐별 스케쥴링이 필요함

 

어떤 큐에게 cpu 를 줄것인지 결정해야함

-> 우선순위를 강하게 적용하는 스케쥴링은 무조건 우선순위 순으로 큐에게 cpu를 줌 (높은 우선순위의 큐가 비어야 낮은 순위의 큐에게 사용권이 돌아감)

 우선순위가 낮다면 starvation 이 올수있음

 

-> time slice

starvation 을 막기위해

각 줄별로 cpu를 할당하는 시간을 %로 줌 우선순위가 높은줄에 80% 낮은줄에 20% 이런식으로 

이러면 일단 starvation 이 없어 지긴함

 

스케쥴링의 요소가 두가지임 

1. 어느줄에게 cpu를 줄것인가?

2. 큐내에 어떤 프로세스에게 줄것인가?

 

 

6.multi level feedback queue

이건 현대사회처럼 계급이있지만 계급간에 신분상승과 하락이 가능하다.

 

여러줄의 큐를 쓰지만 프로세스가 경우에 따라서 큐간의 이동이 가능한것이다.

그래서 이런 multilevel 에서는 queue의 수와 각 큐의 스케쥴링을 어떻게 적용할것인가는 기본으로 깔고 가는 내용이다.

feedback 큐에서는 프로세스 승격 강등 규칙이 생기는것이다.

 

보통의 Multilevel feedback queue를 어떻게 운영하는가 함은

 

처음 들어오는 프로세스는 우선순위가 가장 높은큐에 집어넣는다. (맨윗줄 자료에서)

우선순위가 높은 큐는 RR방식을 사용하는데 타임 quantum 을 매우 짧게 준다.

 

그리고 우선순위가 낮아질수록  타임 quantum 을 점점 늘려나간다.

 

제일 아래큐는 FCFS 방식을 채택한다.

 

프로세스가 들어와서 queue에 주어진 할당시간(time quantum) 을 다쓰면 아래 큐로 강등되고 이런식으로 계속 아래큐로 강등되는 형식이다.

 

그래서 cpu burst 가 아주 짧은 프로세스는 들어오자마자 처리되어 나가고 

 cpu burst 가 긴 프로세스는 점점 우선순위가 낮은 큐로 이동해서 할당시간을 더 받게 되지만 큐간의 우선순위에서 밀려서 대기시간이 길어진다.

그래서 일단 프로세스가 들어오면  우선순위가 높은것이다.

 

이런방식은 cpu사용시간이 짧은 프로세스에게 우선순위를 많이 주는것이다. -> RR보다 더 강하게 우선순위를 주는것이다.

이방식또한 사용시간 예측도 필요없지만 사용시간이 짧은게 우대받음

 

이런식으로 돌아감

 

지금까지 본것은 cpu 가 하나일때의 스케쥴링이다.

---

이제부터 볼것은 cpu가 여러개 이거나 real time 으로 시간의 deadline 이 있거나 thread 가 여러개인 경우 같은것 보는것이다.

 

일단 multi processor 부터 보자

복잡하게 생각할 필요 없단다. -> 화장실 한칸에서 화장실 여러칸으로 늘어난것 뿐이란다.

 

 1.Homogenous processor 인경우

그냥 queue에 한줄세우기 하고 프로세스가 일하는대로 꺼내가게 시킬수 있다.

-> 복잡해지는 경우 : 특정 프로세서에서 꼭 실행되야하는 프로세스가 있는 경우 복잡해진다.(미용실가서 특정 선생님 찾는거 같은것임)

Homogenous 가 궁금하다면 보자

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=hermet&logNo=145992504 

멀티코어 구성 방식

 

2. Load sharing(부하 하나에만 안걸리게 하는것)

cpu 가 여러개가 있다며뉴  load sharing 이 잘되어야함

특정cpu에만 일이 몰리지 않도록 부하를 적절히 나눠야함

 

위에서는 한줄서기를 한다고 말했는데 한줄서기 뿐만아니라 각각의 cpu 마다 queue 를 만들어서 사용할수도 있다.

 

3. symmetric Multiprocessing(SMP)

모든 cpu가 대등한 것이다 -> 각프로세서가 알아서 스케쥴링을 결정함

 

4.Asymmetric Multiprocessing

cpu가 여러개 있는데 그중 하나의 cpu가 전체적인 컨트롤을 담당한다. 데이터의 접근이나 공유를 책임지고 나머지 cpu들은 따른다.

->어디로 가서 일할지 한 cpu가 정해줌 

비행기털때 짐붙이는거 줄 어디에 설지 정해주는 직원처럼 cpu하나가 그일을함

 

real time 스케쥴링

리얼타임의 경우 데드라인이 있는것임 정해진 시간안에 반드시 실행해야하는 것임

cpu 스케쥴링을 할때도 반드시 데드라인을 보장해야함(먼저 cpu를 주네마네 하는 문제가 아님)

real time job 이 주어지고 미리 스케쥴링을해서 종료시점이 보장되도록 적재적소에 배치되도록 하는 방법을 이용함

 

리얼타임의 경우 오프라인으로 미리 스케쥴링을 해놓거나

주기적으로 활성화되야하는 성격을 지니는 경우가 많아서 10초에 한번씩 1초씩 cpu 를 써야한다 이런식이라 이런걸 보장하는거라 10초 안에는 어디든 배치되어도됨 이런거 잘 배치함

 

soft real time 같은거는 동영상 스트리밍에서 많이 쓰이는데

무조건 보장이런건 아니지만 그런일들을 우선순위를 많이 높여주는 형식으로 방법을 가져감

 

 

쓰레드 스케쥴링

쓰레드: 프로세스 하나 안에 cpu 수행단위가 여러개인것 

thread 구현방법이 2가지였음 그러므로 스케쥴링 방법도 그에 맞춰서 두가지임

 

1.local Scheduling 

유저 레벨 쓰레드는 사용자 프로세스가 직접 스레드를 관리하고 커널은 모르기 때문에 운영체제는 그냥 프로세스에게 cpu 를 어떻게 줄지만 결정하는거고

프로세스 내부에서 어떤 쓰레드에게 cpu 를 줄것인지는 프로세스가 자체적으로 결정함

 

2.global Scheduling

운영체제가 쓰레드의 존재를 알고있기에 프로세스 처럼 그냥 커널의 스케쥴러가 어떤 쓰레드에게 cpu 를 줄지 결정한다.

---

어떤 알고리즘이 좋은지에 대한 평가 방법에 대해서 살펴보자

크게 3가지로 나눠볼수있다

 

그림을 보면 server 라고 되어있는데 cpu를 말한다.

arrivlal rate: 프로세스의 도착률

service rate: 처리율

 

1.Queueing models

아주 이론적인 방법이다.

도착률과 처리율이 확률분포로 주어질때 복잡한 수식계산을 해서 결과로 성능척도 결과가 나온다.

도착률과 처리율이 주어진다면 계산할수있는것이다.

옛날에는 이런방식을 많이썻는데 요즘에는 실제로 돌려보는것을 많이씀

 

2.implementation & measutrment

큐잉 모델과 아주 상반된 방법임

실제시스템에 구현을 하 고 정말로 돌려보고 성능을 측정하는것이다.

ex) cpu 스케쥴링 알고리즘을 만들었다보자 그것을 좋은지 평가하는 방법은 리눅스같은 실제 운영체제에 새로은 스케쥴링 알고리즘으로 소스코드를 수정해서 새로운 알고리즘을 구현하고 원래 리눅스와 수정한 리눅스 커널을 실제 프로그램들을 돌려서 어느게 먼저끝나나 보는것임(실측하는 방법) 

쉽지않은 어려운 방법임

 

3. simulation

implementation & measutrment 방법이 시간과 노력이 많이 드니까 모의실험을 하는것이다

이런거 예시를 손으로 계산했지만 이런걸 알고리즘에 따라서 계산해주는 프로그램을 만들면 그게 시뮬레이션이다.

이런거 실제 시스템에서 사용했던 예시들(cpu burst) 케이스로 돌려본다.

이러한 들어가는 케이스 들을 trace 라고 한다.

trace 를 직접 만들수도, 실제 시스템에서 뽑을수도 있다.

 

---

6장 process synchroonization

컴퓨터 시스템 내에서 데이터의 접근 패턴

 

 

컴퓨터 시스템에서 어떤위치에 있던간에 데이터를 접근하는것은 위의 자료와 같은 패턴을 따른다.

 

데이터가 저장된 위치가 있고 그것을 읽어와서 연산을하고 그걸 다시 저장되어있던 위치에 저장을 하는것이다.

 

이건 교수님이 붙인 이름이라는데

연산하는 공간을 execution box 라고 명명하고

데이터를 불러오는 공간을 storage box 라고 명명한다.

 

데이터를 읽기만 하면 누가 먼저 읽어가든 상관없는데 

누가 먼저 읽어갔느냐에 따라 결과가 달라질수도 있고 (중간에 연산해서 덮어씌워지고 어쨋든 이상한일 많이 일어나니까)

이러한 문제들을 synchronization문제 이라고 부르고이를 해결할수 있는 방법을 이 단원에서 배운다고 한다.



 

이제 storage box 를 하나의 사용처 에서만 이용한다면 문제가 없지만 

s-box 를 여러 e-box 가 공유한다면 생기는 문제를 race condition(경쟁상태) 이라고 부른다.

그래서 이런것들을 조율하는 방법이 필요함

 

ex ) 그림과 같이 하나가 count++ 이고 하나는 count-- 인데  한번씩 적용하면 원래값이 그대로 나와야한다.

하지만 count++ 이 먼저 읽어가고 연산중에 count-- 가 읽어가서 연산해서 덮어씌우면 결과값은 원래값에서 -1 을 한 값이 나올것이다.

 

근데 이런일 많이 일어날려나?

-> 이런일들이 여러군데에서 일어날수 있다.

cpu 와 메모리, 컴퓨터와 하드디스크, 프로세스와 메모리 주소공간들 이런경우에 이런일들이 일어날수있다.

 

이런것들에서 cpu 가 하나면 1번의 경우는 안일어나지 않은가 싶다

프로세스도 그냥 일반적인 경우라면 이런일이 안일어나지 않은가 생각할수있는데

 

멀티프로세서의 경우 1번문제가 발생하고

공유메모리를 사용하는 프로세스들 사이에서 3번 문제가 발생할수 있다.

그리고 3번의 경우 운영체제 커널과 관련되서 생길수있다 

-> 프로세스 자기 메모리 영역만 접근하기에 이런 문제들이 생길일이 없다. 근데 특정 어떤일을 할때는 시스템 콜을 하는데 그때는 

커널의 코드가 실행되는데 그럼 커널의 데이터 변수에 접근하게 되는것이다. 그래서 메모리를 읽어드리고 수정하고 하는데 그와중에 cpu를 뺏겨서 새로 cpu 를 받은 프로세스도 시스템콜을해서 같은 부위를 접근하게된다면 이러한 문제들이 발생할수 있다.

 

또한 커널의 코드가 실행중일때(메모리를 건드리고있을떄) 인터럽트가 들어올수있다 인터럽트 코드도 커널코드이기 때문에 커널 메모리에 접근한다. 인터럽트 들어오면 중간에 하던일 잠시 멈추고 인터럽트 관련코드 처리할텐데 그것도 커널코드이므로 커널의 데이터를 건들여서 문제가 생길수있다.

 

사용자 프로그램에서는 이러한 일 그닥 안생기는데

커널의 경우 공유데이터이므로 문제가 많이 생긴다.

운영체제에서 race condition 이 생기는 3가지 예시를 살펴볼것이다.

 

1. kernel 수행중 인터럽트 발생시

 

운영체제 커널이 cpu 에서 실행중에 count 라는 변수의 값을 증가시키는 중임을 가정해보자

이러한 count++ 이런 고급 언어는 cpu 내부에서는 여러개의 instrustion 으로 나뉘어서 실행된다 로드(cpu 레지스터로 값 불러들이기)하고 작업(레지스터의 값 1 증가시키고)하고 저장(메모리에 레지스터의 값 저장) 이런식으로 실행된다.

 

근데 load instrustion 만 처리하고 intrrupt 가 들어오면 하던 작업을 잠시 멈추고 intrrupt 처리 루틴으로가는데

interrupt handler 코드도 커널에 있는 코드이다. 그래서 핸들러가 커널에 있는 데이터인 count 에 접근할수 있다 . count 변수에서 1을 뺸다고 가정하고 그것을 처리하고 하던일 마저하러 돌아왔다고 가정해보자 그때 load 는 이미 해놓았으니 증가시키고 저장할것이다 그럼 count-- 작업은 처리가 안된채로 저장될것이다.

 

그래서 문제를 해결하기위한 방법을

중요 변수 값을 건드리는 동안은 작업을 하는 도중에 interrupt 가 들어와도 작업이 끝날때까지 interrupt 처리를 하지않음 (interrupt 작업을 disable시킴) 작업이 끝난후 interrupt 작업을 처리하게 된다.

 

2. Process가 system call 을 하여 kernel mode 로 수행중인데 context switch가 일어나는 경우

프로세스가 실행된다는게 본인의 코드만 실행하는것이 아닌 system call을 통해서 운영체제에게 서비스를 대신해달라고 요청하는 경우가 많은데 -> 프로그램은 유저모드와 커널모드를 번갈아가며 수행하는 경우가 많다.

 

이떄 그 프로세스가 cpu를 독점적으로 사용하는것이 아닌 할당시간이 끝나면 cpu를 반납하게 된다.

 

그럴때 이런경우가 나오는데 프로세스 A 가 cpu 를 사용하다 할당시간을 다써서 cpu를 b가 가져갔다가 다시 A에게 돌아온 경우인데

 

이런경우에 중간에 cpu를 뺴앗긴 시점이 커널모드일때 count 라는 변수에 접근중일때 뺏기고 프로세스 b가 커널모드로 count 변수에 접근해서 수정후 a에게 다시 cpu 를 넘겨준다면 b에서 했던 일들은 또 없어진다.

 

이것에 대한 해결 방법은 프로세스가 커널모드에 있을때는 할당시간이 끝나더라고 cpu 를 뻇기지 않도록 하여 이러한 문제를 해결한다.

그래서 커널모드가 끝날때 cpu를 뺏어간다. -> 할당시간 정확하게 지켜지지는 않음

 

3. Multiprocessor에서 shared memory 내의 kernel data

 

cpu 가 여러개 있는 환경이다.

이러한 환경은 자주 등장하지는 않는데 앞전의 해결법 들로는 해결이 안된다.

앞의 방법들은 cpu 가 하나였을때고 이제 cpu가 여러개이므로 작업 주체가 여러개이기 때문에 생기는 문제들이다.

 

그래서 cpu가 여러개가 있는 상태에서는 어떤식으로 race condition 을 막는가하면

데이터에 접근할때 lock 를 건다 즉 cpu 하나가 데이터를 들고갈때  데이터에 대해서 들고가기전에 lock을 걸어서다른 누구도 데이터에 접근 못하도록 해놓고 데이터를 변경후 저장하고 lock 를 풀어주는 방식이다.

이런 lock 을 걸고 푸는 방법이 소프트웨어 적인것인데 이런 방식은 다음시간에 본다고 한다.

 

개별데이터에 대해서 lock 을 걸었다가 풀어주는 방법도 있고

 

좀더 쉬운방법으로는 결국 문제가 생기는 이유는 사용자 프로그램이 아닌 운영체제 커널을 여러 cpu가 접근하게 되어서 생기는 문제이므로

커널을 접근하는 cpu 를 매순간 하나로만 제한시키면 된다 커널을 cpu 가 들어갈때 lock 을 걸고 나올때 lock 를 풀어주는 방식이다.

-> 하지만 이런 방법은 매우 비효율 적이다.

 

process synchronization 문제는 공유데이터에 대해서 여럿이서 동시에 접근하려해서 시간적으로 잘 맞아떨어지지 않기 때문에 발생하는 문제이다.

이런것에 해결방법으로 협력 프로세스 간의 실행순서를 정해주는 메커니즘이 필요하다

결과적으로 프로세스들 사이의 동기화가 필요하다는것이다.

 

위에서 계속 나왔던 ++과 -- 를 동시에 접근해서 실행하고있는데 고급언어의 하나의 명령은 여러개의 instrustion으로 나뉘어있어 결과적으로 원하는결과가 안나올수있다는것임 

용어가 여러개 등장하는데 critical section이라는 용어가나온다 한국말로 임계구역

critical section : 공유데이터를 접근하는 코드를 말한다. 코드 그자체

 

 

하나의 프로세스가 critical section에 있다면 다른 어떤 프로세스도 critical section 에 들어가지 못하게 해야한다는 것이다.

이제 p1이 먼저 접근했다면 p2로 중간에 cpu 소유권이 넘어가도 p2의 critical section 은 실행하면안되고 기다려야한다는 뜻이다.