[운영체제] 운영체제 반효경 교수님 2017년 - 4. CPU 스케줄링

June·2021년 4월 28일
0

fork() 시스템 콜

자식 프로세스도 fork 다음부터 시작된다. 다만 리턴 값이 부모 프로세스에는 자식의 PID 값이 오고 자식 프로세스에는 0이 넘어온다.

exec() 시스템 콜

하나의 프로세스를 완전히 다른 프로세스로 덮어 씌우는 것이다.

wait() 시스템 콜

자식이 끝날때까지 부모를 blocked 상태로 만드는 것이다. 이렇게 하지 않으면 부모와 자식은 자원을 두고 경쟁한다.

예를 들면, 리눅스에서 명령어를 입력하면 명령어를 받는 프로세스는 멈추고 열린 프로그램이 실행된다.

exit() 시스템 콜

모든 자원을 반납하고 죽게된다.

프로세스 간 협력

원칙적으로 각각의 프로세스는 다른 프로세스를 고려하지 않는다. 다른 프로세스의 메모리 주소 공간도 볼 수 없다. 경우에 따라서는 메모리끼리 협력할 수 있게 만들 수도 있다.

IPC (Interprocess Communication)을 통해 프로세스간 통신을 할 수 있다.

쓰레드 간에는 메모리 공간을 공유하고 있으므로 협력이 훨씬 쉽다.

Message Passing

메시지는 직접 보낼 수 없고 커널이 매개가 되어서 메시지를 전달해 준다.

Shared memory

프로세스 간에 서로 신뢰할 수 있다는 전제하에 메모리를 공유하게 해야 한다.

CPU and I/O Bursts in Program Execution

기계어를 수행할 때는 CPU Bursts라고 하고 IO를 할때는 IO Bursts라고 한다
사람과 interaction하는 프로그램이 CPU burst와 IO burst를 자주 번갈아 가며 한다.

CPU-burst Time의 분포

IO bound job은 IO가 상대적으로 더 많이 차지하는 작업이다. IO bound job과 CPU bound job이 함꼐 있으면 IO bound job에게 먼저 cpu를 주는 것이 낫다. 유저 입장에서 적게 기다려도되고, 금방 CPU를 쓰고 IO를 하러 가기 때문이다.

프로세스의 특성 분류

CPU Scheduler & Dispatcher

운영체제 코드의 일부이다.

context switch가 일어날 때 뺴앗기는 process는 save하고 새로운 프로세스는 load해야하는데 이를 cpu dispatcher가 한다.

preemptive는 강제로 빼앗는 것을 뜻한다. 1번과 4번 같은 경우는 자진해서 cpu를 내놓는 것이다.

Scheduling Criteria

  • 소요시간:
    ready 큐에서 대기한 시간 + 작업 처리한 시간
  • 대기 시간:
    큐에서 기다리는 시간
  • 응답시간:
    처음 반응을 해줄 때까지 시간. 중국집에서 단무지

Scheduling Algorithms

FCFS (First-Come First-Served)

FCFS는 선착순이므로 nonpreemptive이다.

convoy effect란 긴 프로세스가 앞에 와서 짧은 프로세스가 뒤에서 기다리는 것이다.

SJF (Shortest-Job-First)

SJF는 waiting time의 측면에서는 optimal하다.

SJF는 preemptive버전과 nonpreemptive버전 두 개가 있다.
preemptive 버전을 Shortest-Remaining-Time-First (SRTF)이다.

Example of Non-Preemptive SJF

Example of Preemptive SJF

SJF는 starvation을 발생시킨다는 단점이 있다.

또한 CPU burst time을 미리 알 수가 없다.

다음 CPU Burst Time의 예측

과거 n개의 데이터를 바탕으로 n+1번째를 예측하는 것이다.

Exponential Averaging

Priority Scheduling

앞에서 본 SJF도 priority schedule의 일종이다.

starvation의 해결책으로 aging이 있다. 기다리면 우선순위를 올려주는 것이다.

Round Robin

현재 가장 많이 사용되는 알고리즘이다. timer에 근거하여 preemptive 방식을 쓰는 것이다.

할당 시간이 너무 크면 FCFS와 같고 너무 작으면 context switch 오버헤드가 커진다.

Example: RR with Time Quantum = 20

round robin은 response time이 짧은 것이 장점이다. (처음으로 cpu를 얻기까지의 시간)
interactive job이 많을 때는 response time을 짧게 하는 것이 중요하다.

long job과 short job이 섞여 있으니 효과적이다. 전부 homomegeous하다면 round robin은 오히려 비효율적일 수도 있다.

round robin은 long job과 short job이 공평하게 처리된다.

Turnaroud Time Varies With Time Quantum

Multilevel Queue

CPU는 하나지만 여러 줄을 서는 것이다. 줄마다 우선 순위를 가지고 있다. 큐 간의 이동이 불가능하다. starvation이 발생할 가능성이 크다.

interactive한 것과 batch를 구분해서 줄을 세운다.

Multilevel Feedback Queue

8초동안 쓰고 나면 16 큐에 들어가고 그다음에도 작업이 안끝나면 FCFS로 들어가는 방식이다. 이것은 multilevel feedback queue의 한 예다. 각 큐마다 다른 알고리즘을 구현할 수 있다.

Example of Multilevel Feedback Queue

Multiple-Processor Scheduling

0개의 댓글