7.스케쥴링 척도, FCFS

CPU 스케쥴링

프로그램은 하드디스크안에 들어있고 아무런 동작도 하지안흔다. 메인메모리에 올라가서 실행이 되면 활동한다.

활동중에 있는 프로그램을 프로세스라함.

프로세스에 대한 것들을 PCB안에 넣어놓는다.

컴퓨터 안에는 여러가지 큐가 있는데 job queue, ready queue, device queue가 있다.

메인메모리에 여러 프로그램이 올라와있는게 멀티 프로그래밍
프로그램이 몇개인가에 대한것이 Degree of multiprogramming

잡스케줄러가 하는일은 i/o-bound 를 CPU-bound process 적절히 분배하는것.

short-term scheduler : 메모리에 올라온 프로세스들은 CPU를 받기위해 줄서있는데 어느놈을 선택해서 서비스해줄지에 대한것
Long-term scheduler : 하드디스크에서 메인메모리에 올라가기 위해 job queue에 대기하는 프로그램중 어느놈을 먼저 올려야하는지에 대한것

메인메모리에 올라온 프로세스중에 일정시간동안 사용되지 않는것을 물리적인 하드디스크에 Swap out 한다.
Medium-term scheduler : Swap out 리스트중 어느것을 Swap in 할지에 대한것을 의미함.

하드디스크는 파일시스템목적, Backing store(물리적인 하드디스크에 Swap out할 때 목적지) 용도로 사용된다.

Context switching

CPU가 p1을 실행하다 p2로 넘어가는데 이를 문맥교환이라 한다.

Scheduler

레디큐에 있는 놈 중 어느놈을 CPU로 보내줄까에 대한것.
지금있는 프로세스가 끝나면 어느놈을 선택할것인가에 대한것.
O/S안에 들어있는 컴퓨터 프로그램이다.

Dispatcher

스케줄러가 선택한 프로세스를 실행하도록 여러가지 상태를 변경해주는것.
p2가 선택되었다면 p2를 돌리기 위해 p1의 현재상태 프로그램카운터,스택포인터,레지스터,베이스레지스터 등을 P1의 PCB 에 저장해 놓아야한다.

즉 p1의 현재상태를 pcb1에 저장해놓는다. p2의 PCB에저장된 값을 복원(restore)
이런일을 하는것이 디스패처라 한다.
이런일을 하는것은 오버헤드(부담)이 발생하게 된다. 이를 Context Switching Overhead라고 한다.

즉 컨텍스트 스위칭을 자주하는것은 손해이다.
Dispatcher는 주로 어셈블리어와같은 low 레벨로 짜서 효율을 높인다.

CPU스케줄링

현재 실행중인 프로세스가 끝나면 어느것을 실행해줄까

Preemptive vs Non-preemptive

Preemptive : CPU가 어떤일을 하고 있는데 IO를 만나거나 끝나지도 않았는데 강제로 끝내고 들어갈 수 있는것
Non-preemptive : 이미 어떤프로세스가 실행중이면 끝나거나 IO를 만나지 않으면 변경되지 않는것

Scheduling criteria(척도)

특정 Scheduling 기법을 판단하는 기준

  • CPU Utilization (CPU 이용률) : CPU가 놀지않고 얼마나 열심히 일하는가. a방법은 100%로 돌고 b방법은 80%로 들 때 a방법을 채택

  • Throughput (처리율) : 시간당 몇개의 작업을 처리하는가.

  • Turnaround time (반환시간) : 작업이 ready queue로 들어가 작업을 끝내고 나오는 시간.

  • Waiting time (대기시간) : CPU를 받기위해 ready queue에서 얼마나 기다려야 하는가. 당연히 짧을수록 좋다.

  • Response time (응답시간) : interactive 환경에서 중요하다. 처음 응답이 나올때 까지 걸리는 시간. 주로 대화형 컴퓨터에서 척도로 삼음

기타 요소 존재….


First-Come, First-Served (FCFS)

먼저온놈을 먼저 처리해준다. - Non-preemptive schedulling
레디큐에 프로세스가 대기중이다.

p1은 burst time 24
p2는 3
p3는 3 일때

평균적으로 기다린 시간은 (0 +24 + 27)/3 = 17 이다.

P3,P2,P1 순으로 들어왔다고 할 경우 (0+3+6)/3 = 3 이라고 할 수 있다.
당연히 아래방식이 더 좋다.

간트차트 추가

즉 이런방식으로 해주면 평균 대기시간을 고려할 때 그리 좋은방법이 아니다.

Convoy Effect (호위효과) : CPU를 많이 잡아먹는놈이 앞에있으면 뒤에놈들이 오래 기다려야 한다.

Shortest-Job-First (SJF)

짧은 작업을 먼저 처리해준다.

Shortest-Remaining-Time-First

Priority

Round-Robin (RR)

Multilevel Queue

Multilevel Feedback Queue

Share