CPU Scheduling [ 임베디드 설계 ]

System calls 

-> os에서 자체적으로 제공해주는 프로그램 인터페이스 / os에서 제공하는 함수 

 

os : 하드웨어를 컨트롤하는 소프트웨어 

 

- File Open

O_APPEND : 시작지점에서 파일을 오픈할떄 , 파일의 마지막부분에 추가하는것

O_CREAT : 파일이 존재하지않으면, 새로만드는것

O_DIRECTORY : 디렉토리를 여는것

O_EXEL : 이미 존재할경우 에러 

O_TRUNC : 일반적인 파일일 경우, 파일을 다 지우고 처음부터 새로 씀 

 

- Mode 

( S_I 는 공통)

 

write와 append의 차이 

write는 오픈시 그냥 긴 문자열들의 나열 ->이후 풀이는 사용자의 몫 (위치지정. 등) ( 기본적으로 파일의 첫지정으로감) 

append 은 오픈시 앞의 내용은 보전하고 뒤부터 ..

---

- CPU Scheduling 

프로세스 스케줄링 vs 스레드 스케줄링

->  CPU 스케줄러는 OS 내부에 존재하며, CPU가 놀고있으면 안되므로, ready queue에 있는 것을 하나를 선택하여 수행함 : = cpu scheduler의 업무중 하나   

 

CPU I/O burst : 실제 cpu를 점유하고 사용하는데 걸리는 시간을 의미 

 

Nonpreemtive  

-> 어떤 프로세스가 cpu를 장악하여 running 상태가 되었을떄, 스스로 이제 cpu를 사용하지않고 리소스를 넘겨주겠다고 하는것 

Preemtive 

-> 프로세스가 cpu내에서 수행하고있을떄, 외부에서 이제 그만작업하라고 할떄 

 

- Dispatcher

레디큐에 있는 프로세스를 cpu 스케줄러가 선택을하면, cpu에 그 프로세스를 할당하여 실행하라고 해주는 것 

---

Scheduling Criteria

좋은 스케줄링이란 ? 

CPU utilization : cpu를 켜놨을떄 실제로 몇번이나 움직였나 . .

Throughput : 프로세스를 몇개 실행했을떄 얼마만에 끝났나 .. (시간측정)

Turnround time : 프로세스 하나가 끝나는데 걸리는 평균시간 ( 평균시간이 너무 들쭉날죽이면 안된다 . .)  

Waiting time : 프로세스가 들어가면 ready에서 들어가는 시간이 얼마나 되나를 따짐 

Response time : 프로세스가 요청을 받은 후에 반응하는데까지 걸리는시간 

---

Process - Burst Time 

Burst Time? : 프로세스를 돌리는데 걸리는 시간 

-> 위 사진과 같다면, 프로세스 1,2,3 전체 프로세스를 돌리는데 걸리는 Burst Time은 30이다 .

여기서, Waiting time 은 각, P1은 0, P2는 24, P3는 27 이다. ( 순서대로 실행되기 때문 ) 

그렇다면 Average waiting time 은 ( 0 + 24 + 27 )/3 = 17 이다. 

이떄 만약, 프로세스 수행의 순서가 다르다할시, Waiting time은 6,0,3 순서이다. 

-> 그렇다면  Average waiting time 은 ( 6 + 0 + 3)/3 = 3이다. 

 

-> 이것을 Convoy effect 라고 한다. 

ex) 계산할떄 껌하나살때는 먼저 양보하는등의 효율적 구조 . but, 컴퓨터는 직접 알려주어야함

---

-> ' Shortest-Job-First '(SJF) :  빨리 끝나는 작업부터 수행

: 순서에 상관없이 Burst-time 순서대로 수행 -> average waiting time을 줄이는데 가장 효과적인 방법

P1,2,3,4 를 버스트타임순서대로 수행하였을떄 아래와 같이 평균 waiting time 을 누적, 계산할수있다.

---

-> but, 프로그램(프로세스)가 수행되기 전까지 얼마나걸릴지 정확히 계산불가 . (예측은 가능) 

how to 예측? : 유저에게 물어보기 , 예측 . .

 

Prediction of Next CPU Burst

 -> 최근 결과값들을 더 많이 반영하여 예측하는 구조를 가진다. 

Tn* = 지난번에 예측했던 값 

---

-> ' Shortest-Remaining-Time-First '( Preemptive 버전의 SJF) :  빨리 끝나는 작업부터 수행

위와 같이 P1이 0번쨰로 가장먼저 들어왔기떄문에(Arrival Time 0) 일단 한번 실행된다 .

하지만 그다음부터 Arrival Time 1 에 P2 가 들어오고, 이떄, Burst Time(남은 수행시간)이 P1 보다 낮으므로, 가장 우선순위로 배정 및, 수행을 시작한다. 

그 이후, 순서대로 P3가 들어왔지만, 여전히 P2가 버스트타임이 가장 낮으므로 계속 P2를 수행한다. 

P4가 들어온 Arrival Time3 에서도 마찬가지이다. 

이후, P2의 수행이 끝나고, P4가 그다음으로 낮으므로, 수행 -> 이후 그다음으로 낮은 P1 -> P3 순으로 수행한다. 

이런 작업이 완료 되면 최종적으로 보았을떄 평균 waiting time은 위의 표와 같이 된다. 

---

-> 'Round Robin' ( RR )

: 타임슬라이스를 나누어서 한번에 사용할수있는 타임슬라이스를 사용하면, 한번씩 양보하면 돌아가며 수행하는 방법 

-> 아래와 같이 P1 =24 / P2 =3 / P3 =4 일 경우, 4칸씩 타임슬라이스를 나누어서, P1(24)에서 4번 / P2(3)에서 3번만에 종료 후 , / P3(3) 에서도 3번만에 종료 / 이후 하나남은 P1이 쭉 수행 

구현이 쉽다는 장점이 있다. 

-> Average waiting time : [(10-4)+4+7]/3 = 5.66  

: preemptive 하나는 성질이있음 

---

-> 'Priority Scheduling'

수행시간에 상관없이 공평한 스케쥴링 

-> Average waiting time : [6+0+16+18+1]/5 = 8.2 

---

-> Starvation 

: 처음 들어온 프로세스가 이후 들어오는 프로세스들에 순위가 밀려 무한대기를 하게되는 상태 

-> 가장 일반적인 해법 : Aging : 일정 시간이 지나면, 대기하고있던 프로세스의 Priority를 올려줌 

time slice : 2 

: RR 과 Priority 스케쥴링을 믹스하여 수행

---

Multilevel Queve 

Priority 의 등급 기준 

 

---

- Simulaneous Multithreading (SMT)

코어에서 하드웨어적으로 스레드를 지원하는것 

-> 멀티스레딩을 사용할떄 CPU를 두개이상내는 것과 성능이 같지는 않다. 

-> ( Hyper 스레딩을 한다고 성능이 두배가 되진않음 )

---

- Real-Time CPU Scheduling 

Soft real-Time systems : 시간을 안지키면 급격하게 품질이 낮아짐

Hard real-Time systems : 시간을 안지키면 끝 

---

- Practice 1 

- nonpreemptive 스케줄링을 사용하는 아래와 같은 프로세스 입력이있다. 

nonpreemptive 일시, 기본적으로 첫번쨰 프로세스는 그냥 수행 ? 

1. 위와 같을시, FCFS 스케줄링으로 계산했을떄, Average turnaround time 은 ?

-> 그냥 순서대로 P1 = 8 / P2 는 12초 기다렸지만 0.4 를뺴고, / P3 = 13 - 1.0  ->  평균값 계산 

1-1. 만약, FCFS 스케줄링으로 계산했을떄, Average waiting time 은 ?

-> 말그대로 waiting time 이므로, P1 = 0, P2 = 7.6 , P3 = 11 -> ( 0+7.6+11)/3 

 

2. 위와 같을시, SJF 스케줄링으로 계산했을떄, Average turnaround time 은 ?

-> nonpreemptive 일시, 기본적으로 첫번쨰 프로세스는 그냥 수행 이므로 P1 8 전부다 먼저 수행 - >이후 SJF 스케줄링으로 P3 1먼저 수행 -> 이후 P2 수행 -> 이후 각 arrival time별로 뺴줌