CPU scheduling 2

Round Robin은 cpu를 기다리는 시간이 사용하려는 시간에 비례해서 어느 정도 공정성을 보장한다. 

 

multilevel queue는 여러 줄로 선다. 위로갈수록 우선순위가 높다. 우선순위에 따라 cpu가 부여된다. 

ready queue를 여러 개로 분할(여러 줄) - foreground queue와 background queue가 있다. 각 큐의 특성에 맞는 스케줄링 방법을 적용해야 한다. 

- 우선 순위 높은 줄에 cpu를 준다. starvation이 발생할 수도 있다. 

- time slice : 각 큐에 cpu time을 적절한 비율로 할당. ex) 80%는 우선순위 높은 곳에 주고 20%는 우선순위 낮은 곳에 준다. 

foreground queue(interactive)- round robin을 쓰는 것이 좋다. 

background queue(batch-no human interaction)- FCFS가 좋다. 

system processes

interactive processes

interactive editing processes

batch processes

student processes

 

multilevel feedback queue - 여러 줄로 줄을 서지만 경우에 따라 프로세스 이동 가능. 

프로세스가 다른 큐로 이동 가능. process를 상위 큐로 보내는 기준, 하위 큐로 보내는 기준. cpu 사용시간이 짧은 프로세스를 높은 우선순위에 놓는다. 위로 갈수록 cpu 할당 시간 짧게 주고 맨 밑은 FCFS를 쓴다. 

 

<CPU가 여러개인 경우> multipe processor scheduling

 

cpu가 여러 개인 경우 스케줄링은 더욱 복잡해짐. 

- homogeneous processor인 경우

queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다. 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐. 

 

- load sharing

일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요

별개의 큐를 두는 방법vs공동 큐를 사용하는 방법

 

- symmertric multiprocessing(SMP) 모든 cpu 대등

각 프로세서가 각자 알아서 스케줄링 결정

 

- asymmetric multiprocessing 하나의 cpu가 전체적인 컨트롤 담당. 

하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름. 

 

<Real-time scheduling>

deadline이 있는 job. 정해진 시간 안에 반드시 끝내도록 스케줄링해야 한다. 

주기적으로 실행되어야하는 성질을 가진 작업이 많다. ex) 10초에 한 번씩 cpu를 잡아서 적어도 1초는 사용을 해야 한다는 제약조건

- hard real-time systems : hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링해야 한다. 

- soft real-time computing : deadline이 존재하지만 조금 어겨도 되는 시스템. 다른 프로세스들도 많이 존재하고 일반 프로세스에 비해 높은 우선순위를 부여해서 cpu를 먼저 얻을 수 있게 하지 deadline을 반드시 보장하지는 못한다. 

 

<Thread Scheduling>

쓰레드를 구현하는 방식 

- local scheduling - 사용자 프로세스가 직접 스레드를 관리하고 운영체제는 스레드의 존재를 모르는 경우. 운영체제의 경우는 쓰레드의 존재를 모르기 때문에 그 프로세스에게 cpu를 줄지 안 줄지 결정. 그 프로세스에게 cpu가 갔을 때 프로세스 내부에서 어떤 스레드에게 cpu를 줄지는 프로세스 내부에서 결정한다. (user level thread의 경우)

 

- global scheduling - 운영체제가 쓰레드의 존재를 이미 알고 있는 상황. 프로세스 스케줄링하듯이 운영체제가 어떤 스레드에게 cpu를 줄지 결정한다. (kernel level thread의 경우)

 

< Algorithm Evaluation>

- queueing models : 굉장히 이론적인 방법. queue에 job들이 도착을 하는 도착율, server(cpu)의 능력에 따라 처리하고 빠져나가는 처리율이 확률 분포로 주어지고 수식 계산을 하면 성능 척도 결과가 나온다. cpu의 throughput이 계산에 의해 나오게 된다. 예전에는 많이 썼지만 요즘에는 실제 시스템에서 돌려보는 방식을 더 의미 있게 보기 때문에 이론적으로만 사용된다. 

 

- implementation(구현)&Measurement(성능 측정) : 실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정. 실제로 돌려보고 성능을 측정한다. 실측하는 방법. 실제 운영체제 내부에 있는 커널을 고치는 것은 어려운 일이다. 따라서 아래의 방법이 나왔다. 

 

- simulation(모의 실험) : 실제로 돌리는 것이 아니라 모의실험을 한다. 시뮬레이션 프로그램에 input으로 들어갈 데이터를 trace라고 한다. trace를 임의로 만들 수도 있꼬 실제 프로그램을 돌리면서 뽑을 수도 있다. 실제 프로그램을 사용하면 좀 더 실제 상황을 잘 반영할 수가 있다. 

 

 

 

process synchronization - 공유 데이터의 동시접근은 데이터의 불일치 문제를 발생시킬 수 있다. 일관성 유지를 위해서는 협력 프로세스 간의 실행 순서를 정해주는 메커니즘이 필요하다. 

 

데이터가 접근되는 패턴. 연산할 데이터를 주고 연산 결과를 받아 데이터에 저장한다. 데이터가 저장되어 있는 부분을 storage box라고 하고 연산하는 부분을 execution box라고 하고 한다. (이 강의에서 임의로 붙임)

storage 박스를 여러 개의 execution box가 공유하게 되면 storage 안의 데이터에 동시에 접근하려고 할 때 race condition(경쟁 상태)라고 한다. 해당 상태일 때 원치 않는 결과를 얻을 수도 있다. 

연산하는 주체 cpu, 데이터 저장 메모리. 

프로세스가 연산의 주체이고 프로세스가 관리하는 메모리 주소 공간. 즉 프로세스의 주소 공간. 프로세스는 일반적으로 각자의 주소공간에만 접근한다. 이때는 race condition이 발생할 수 없다. 

하지만

cpu가 여러 개인 시스템에서는 메모리를 공유하게 되면 race condition이 발생할 수 있다. 

 

Race condition:  여러 프로세스들이 동시에 공유 데이터를 접근하는 상황. 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐

 

race condition을 막기 위해서는 concurrent process는 동기화(synchronize)되어야 한다.(동시에 실행되는 프로세스가 동기화되어야 한다.)

 

프로세스는 본인이 직접 실행할 수 없고 운영체제에 요청해야 하는 것은 시스템콜로 요청을 하게 된다. 커널의 코드가 그 프로세스를 대신해서 실행이 되고 커널의 코드가 실행된다는 것은 커널에 있는 데이터에 접근을 하는 것이다. 만약 cpu를 빼앗겨서 또 다른 프로세스에 cpu가 넘어갔는데 또 시스템 콜을 해서 운영체제에 요청을 해서 커널의 코드가 실행되면서 커널의 데이터에 접근할 수 있다. 이런 경우에 race conditon문제가 발생할 수 있다. 

또는 커널의 코드가 실행중인데 interrupt가 들어올 수 있다. 이 인터럽트를 처리하는 커널 코드를 수행하기 때문에 커널의 데이터를 건들게 된다. user mode에선 별 문제가 생기지 않는 것이 운영체제 커널에 있는 데이터는 여러 프로세스들이 동시에 사용할 수 있는 그런 데이터이기 때문에 문제가 생긴다. 문제를 해결하기 위해 interrupt가 들어와도 커널의 작업을 마치기 전까지는 interrupt를 disable 시켰다가 커널의 작업을 마치고 인터럽트 처리 루틴으로 넘겨 race condition이 나타나지 않게 한다. 

 

OS에서 race conditon이 생기는 경우

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

2. process가 system call을 하여 kernel mode로 수행 중인데 context switch가 일어나는 경우 - 커널 모드에서 실행 중일 때는 cpu를 preempt하지 않음(뺏지 않음). 커널 모드에서 사용자 모드로 돌아갈 때 preempt. 이러면 할당 시간이 정확하게 지켜지지는 않는다. 하지만 이는 real time system이 아니라 오히려 쉽게 해결할 수 있다. 

3. multiprocessor에서 shared memory내의 kernel data - cpu가 여러 개인 환경 - lock을 건다. 어떤 cpu가 마지막으로 count를 저장하는가? -> race condition

multiprocessor의 경우 interrupt enable/disable로는 해결되지 않음. 

 

한번에 하나의 cpu만이 커널에 들어갈 수 있게 하는 방법 - 커널 전체를 하나의 lock으로 막고 나올 때 lock을 풀어주면 된다. 커널에 하나의 cpu만 들어갈 수 있게

커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대한 lock/unlock을 하는 방법. - 해당 데이터만 접근하는 게 아니라면 여러 cpu가 동시에 커널 코드를 실행할 수 있게 하는 해당 방식을 쓰면 더 좋다. 

 

The Critical-Section Problem

n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우

critical section(임계 구역) : 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재.