cs 면접 1주차 ) 스케줄러

Q. 스케줄링이란?

여러 프로세서가 번갈아 사용하는 자원을 어떤 시점에 어떤 프로세스에 할당할지 결정하는 것이다.

Q. 스케줄링을 하는 이유?

다중 프로그래밍에서 프로세서(CPU)를 할당할 프로세스를 선택할때 전략이 필요하기 때문이다.
☑️

🤔 다중 프로그래밍의 목적은?

• 프로세서 이용률 ↑
• 프로세서 처리율(단위 시간당 작업 처리량) 증가

Q. 프로세스를 스케줄링하기 위한 세 가지 종류 Queue는 무엇이 있을까?

• Job Queue : 현재 시스템 내에 있는 모든 프로세스의 집합
  secondary storage에 형성되어 있는 큐
• Ready Queue : 메모리에 load되어있는 프로세스들 , 현재 메모리 내에 있으면서 CPU 를 잡아서 실행되기를 기다리는 프로세스의 집합
• Device Queue : Device I/O 작업을 대기하고 있는 프로세스의 집합
  device controller(하드웨어)에 있는 프로세스

☑️ 각 큐는 PCB들의 연결리스트

🤔 각각의 Queue 에 프로세스들을 넣고 빼주는 스케줄러에도 크게 세 가지 종류가 존재한다.

장기스케줄러(Long-term scheduler or job scheduler)

메모리는 한정되어 있는데 많은 프로세스들이 한꺼번에 메모리에 올라올 경우, 대용량 메모리(일반적으로 디스크)에 임시로 저장된다. 이 pool 에 저장되어 있는 프로세스 중 어떤 프로세스에 메모리를 할당하여 ready queue 로 보낼지 결정하는 역할을 한다.

• 메모리와 디스크 사이의 스케줄링을 담당.
• 프로세스에 memory(및 각종 리소스)를 할당(admit)
• degree of Multiprogramming 제어
  (실행중인 프로세스의 수 제어)
• 프로세스의 상태
  new -> ready(in memory)

cf) 메모리에 프로그램이 너무 많이 올라가도, 너무 적게 올라가도 성능이 좋지 않은 것이다. 참고로 time sharing system(시분할 시스템) 에서는 장기 스케줄러가 없다. 그냥 곧바로 메모리에 올라가 ready 상태가 된다.

🤔 time sharing system(시분할 시스템)

CPU 스케줄링과 다중 프로그래밍을 이용해서 각 사용자들에게 컴퓨터 자원을 시간적으로 분할하여 사용할 수 있게 해 준다.
시스템은 한 사용자에서 다음 사용자로 빠르게 전환함으로써 각 사용자에게 자신만이 컴퓨터를 사용하고 있는 것과 같은 착각을 주지만, 실제로는 여러 사용자가 하나의 컴퓨터를 공유하여 사용하고 있는 것이다.

단기스케줄러(Short-term scheduler or CPU scheduler)

• CPU 와 메모리 사이의 스케줄링을 담당.
• Ready Queue 에 존재하는 프로세스 중 어떤 프로세스를 running 시킬지 결정.
• 프로세스에 CPU 를 할당(scheduler dispatch)
• 프로세스의 상태
  ready -> running -> waiting -> ready

단기스케줄링 = CPU스케줄링

중기스케줄러(Medium-term scheduler or Swapper)

• 여유 공간 마련을 위해 프로세스를 통째로 메모리에서 디스크로 쫓아냄 (swapping)
• 프로세스에게서 memory 를 deallocate
• degree of Multiprogramming 제어
• 현 시스템에서 메모리에 너무 많은 프로그램이 동시에 올라가는 것을 조절하는 스케줄러.
• 프로세스의 상태
  ready -> suspended

🤔 Process state - suspended

Suspended(stopped) : 외부적인 이유로 프로세스의 수행이 정지된 상태로 메모리에서 내려간 상태를 의미한다. 프로세스 전부 디스크로 swap out 된다. blocked 상태는 다른 I/O 작업을 기다리는 상태이기 때문에 스스로 ready state 로 돌아갈 수 있지만 이 상태는 외부적인 이유로 suspending 되었기 때문에 스스로 돌아갈 수 없다.

swap out: 메모리로부터 제거
swap in : 다시 메모리를 차지하면 중간 단계부터 실행

1단계 : 수행빈도가 낮은 장기 스케줄링
2단계 : 수행빈도가 중간인 중기 스케줄링
3단계 : 수행빈도가 높은 단기 스케줄링

장기 스케줄러 -> 준비 큐 -> 단기 스케줄러 -> 프로세서 -> 종료
or
장기 스케줄러 -> 준비 큐 -> 단기 스케줄러 -> 프로세서 -> 입출력장치 큐 -> 입출력장치 -> 준비 큐....반복

요즘은 장기를 사용x , 메모리가 차고 넘치기 때문이다.

Q. CPU 스케줄러란

프로세스가 생성된 후 종료될 때까지 모든 상태 변화를 조정하는 일
스케줄링 대상은 Ready Queue 에 있는 프로세스들이다.

Q. 스케줄러 알고리즘

FCFS(First Come First Served)

• 특징
  • 먼저 온 고객을 먼저 서비스해주는 방식, 즉 먼저 온 순서대로 처리.
  • 비선점형(Non-Preemptive) 스케줄링
  • 일단 CPU 를 잡으면 CPU burst 가 완료될 때까지 CPU 를 반환하지 않는다
    할당되었던 CPU 가 반환될 때만 스케줄링이 이루어진다.
• 문제점
  - convoy effect
  -소요시간이 긴 프로세스가 먼저 도달하여 효율성을 낮추는 현상이 발생한다.

🤔 convoy effetct 란

소요시간이 긴 프로세스가 먼저 도달하여 시간을 잡아먹고 있는 부정적인 현상을 의미한다. 짧은 작업을 먼저 처리하는 방식으로 CPU burst time이 짧은 프로세스에게 CPU를 선할당하는 방식이다.

🤔 비선점형(Non-Preemptive) 스케줄링

프로세스가 CPU를 점유하고 있다면 이를 빼앗을 수 없는 방식
필요한 문맥 교환만 일어나기 때문에 오버헤드가 상대적으로 적지만 프로세스의 배치에 따라 효율성 차이가 많이 난다.

🤔 선점형(Non-Preemptive) 스케줄링

프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 방식
CPU 처리 시간이 매우 긴 프로세스가 CPU 사용 독점을 막을 수 있어 효율적인 운영이 가능하다.
하지만 잦은 문맥 교환으로 오버헤드가 많이 발생한다.

SJF(Shortest - Job - First)

• 특징
  - 다른 프로세스가 먼저 도착했어도 CPU burst time 이 짧은 프로세스에게 선 할당
  - 비선점형(Non-Preemptive) 스케줄링
• 문제점
  - starvation(기아 상태)
  효율성을 추구하는게 가장 중요하지만 특정 프로세스가 지나치게 차별받으면 안되는 것이다. 이 스케줄링은 극단적으로 CPU 사용이 짧은 job 을 선호한다. 그래서 최악의 경우 사용 시간이 긴 프로세스는 거의 영원히 CPU 를 할당받을 수 없다.

SRTF(Shortest Remaining Time First)

• 특징
  - 새로운 프로세스가 도착할 때마다 새로운 스케줄링이 이루어진다.
  - 선점형 (Preemptive) 스케줄링
  - 현재 수행중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time 을 가지는 새로운 프로세스가 도착하면 CPU 를 뺏긴다.
• 문제점
  - starvation(기아 상태)
  새로운 프로세스가 도달할 때마다 스케줄링을 다시하기 때문에 CPU burst time(CPU 사용시간)을 측정할 수가 없다.

Priority Scheduling

• 특징
  - 우선순위가 가장 높은 프로세스에게 CPU 를 할당하는 스케줄링이다. 우선순위란 정수로 표현하게 되고 작은 숫자가 우선순위가 높다.
  - 선점형 스케줄링(Preemptive) 방식
  더 높은 우선순위의 프로세스가 도착하면 실행중인 프로세스를 멈추고 CPU 를 선점한다.
  - 비선점형 스케줄링(Non-Preemptive) 방식
  더 높은 우선순위의 프로세스가 도착하면 Ready Queue 의 Head 에 넣는다.
• 문제점
  - starvation(기아 상태)
  - 무기한 봉쇄(Indefinite blocking)
  실행 준비는 되어있으나 CPU 를 사용못하는 프로세스를 CPU 가 무기한 대기하는 상태
  해결책
  - aging
  아무리 우선순위가 낮은 프로세스라도 오래 기다리면 우선순위를 높여주자.

Round Robin

• 특징
  - 현대적인 CPU 스케줄링
  - 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 갖게 된다.
  - 할당 시간이 지나면 프로세스는 선점당하고 ready queue 의 제일 뒤에 가서 다시 줄을 선다.
  - RR은 CPU 사용시간이 랜덤한 프로세스들이 섞여있을 경우에 효율적
  - RR이 가능한 이유는 프로세스의 context 를 save 할 수 있기 때문이다.
• 장점
  -Response time이 빨라진다.
  - n 개의 프로세스가 ready queue 에 있고 할당시간이 q(time quantum)인 경우 각 프로세스는 q 단위로 CPU 시간의 1/n 을 얻는다. 즉, 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.
  프로세스가 기다리는 시간이 CPU 를 사용할 만큼 증가한다.
  공정한 스케줄링이라고 할 수 있다.
• 주의할 점
  설정한 time quantum이 너무 커지면 FCFS와 같아진다. 또 너무 작아지면 스케줄링 알고리즘의 목적에는 이상적이지만 잦은 context switch 로 overhead 가 발생한다. 그렇기 때문에 적당한 time quantum을 설정하는 것이 중요하다.

Q. 동기와 비동기의 차이는 무엇일까?

해야할 일(task)가 빨래, 설거지, 청소 세 가지가 있다고 가정한다. 이 일들을 동기적으로 처리한다면 빨래를 하고 설거지를 하고 청소를 한다. 비동기적으로 일을 처리한다면 빨래하는 업체에게 빨래를 시킨다. 설거지 대행 업체에 설거지를 시킨다. 청소 대행 업체에 청소를 시킨다. 셋 중 어떤 것이 먼저 완료될지는 알 수 없다. 일을 모두 마친 업체는 나에게 알려주기로 했으니 나는 다른 작업을 할 수 있다. 이 때는 백그라운드 스레드에서 해당 작업을 처리하는 경우의 비동기를 의미한다.

Sync(함께) + Chrono (시간) = 대상들의 시간이 맞춰지는가?

Sync(동시에 일어나는) vs Async(동시에 일어나지 않는)

일반적으로 동기와 비동기의 차이는 메소드를 실행시킴과 동시에 반환 값이 기대되는 경우를 동기 라고 표현하고 그렇지 않은 경우에 대해서 비동기 라고 표현한다. 동시에라는 말은 실행되었을 때 값이 반환되기 전까지는 blocking되어 있다는 것을 의미한다. 비동기의 경우, blocking되지 않고 이벤트 큐에 넣거나 백그라운드 스레드에게 해당 task 를 위임하고 바로 다음 코드를 실행하기 때문에 기대되는 값이 바로 반환되지 않는다.

🤔 자바는 sync 기반에 block 이다.

Q. 동기의 장단점은?

+) 설계가 간단하고 직관적이다
-) 결과가 주어질 때 까지 대기해야 한다(다른 작업 불가)

Q. 비동기의 장단점은?

+) 결과가 주어지는 데 까지 걸리는 시간 동안 다른 작업이 가능하다. 자원의 효율적 사용!
-) 설계가 동기식 보다 복잡하다

🤔 Block

bolck은 호출 메소드가 다른 메소드를 호출했을때 제어권도 같이 넘긴다.
호출 메소드는 아무것도 못하는 상태가 된다.
return 될때 제어권도 같이 return된다.

🤔 Non-Block

호출 메소드가 다른 메소드를 호출했을때 제어권은 넘어가지 않는다.

4. 동기와 비동기의 차이점
   동기는 request 후 response 기다림.
   비동기는 기다리지 않음.

5. 비동기 처리의 대표적인 예
   ajax, fetch, axios 등으로 json 통신하기.

Q. 프로세스 동기화란 무엇일까?

Critical Section(임계영역)

멀티 스레딩에 문제점에서 나오듯, 동일한 자원을 동시에 접근하는 작업(e.g. 공유하는 변수 사용, 동일 파일을 사용하는 등)을 실행하는 코드 영역을 Critical Section 이라 칭한다.

Section Problem(임계영역 문제)

프로세스들이 Critical Section 을 함께 사용할 수 있는 프로토콜을 설계하는 것이다.

Requirements(해결을 위한 기본조건)

• Mutual Exclusion(상호 배제)
  프로세스 P1 이 Critical Section 에서 실행중이라면, 다른 프로세스들은 그들이 가진 Critical Section 에서 실행될 수 없다.

• Progress(진행)
  Critical Section 에서 실행중인 프로세스가 없고, 별도의 동작이 없는 프로세스들만 Critical Section 진입 후보로서 참여될 수 있다.

• Bounded Waiting(한정된 대기)
  P1 가 Critical Section 에 진입 신청 후 부터 받아들여질 때가지, 다른 프로세스들이 Critical Section 에 진입하는 횟수는 제한이 있어야 한다.

해결책

• Lock
  하드웨어 기반 해결책으로써, 동시에 공유 자원에 접근하는 것을 막기 위해 Critical Section 에 진입하는 프로세스는 Lock 을 획득하고 Critical Section 을 빠져나올 때, Lock 을 방출함으로써 동시에 접근이 되지 않도록 한다.
• 한계
  다중처리기 환경에서는 시간적인 효율성 측면에서 적용할 수 없다.

Semaphores(세마포)

소프트웨어상에서 Critical Section 문제를 해결하기 위한 동기화 도구
세마포는 교착 상태 및 경쟁 조건을 방지하는 데 사용

종류

OS 는 Counting/Binary 세마포를 구분한다

• 카운팅 세마포(Counting Semaphores)
  가용한 개수를 가진 자원 에 대한 접근 제어용으로 사용되며, 세마포는 그 가용한 자원의 개수 로 초기화 된다. 자원을 사용하면 세마포가 감소, 방출하면 세마포가 증가 한다.

• 이진 세마포
  MUTEX 라고도 부르며, 상호배제의 (Mutual Exclusion)의 머릿글자를 따서 만들어졌다. 이름 그대로 0 과 1 사이의 값만 가능하며, 다중 프로세스들 사이의 Critical Section 문제를 해결하기 위해 사용한다.

단점

• Busy Waiting(바쁜 대기)
  Spin lock이라고 불리는 Semaphore 초기 버전에서 Critical Section 에 진입해야하는 프로세스는 진입 코드를 계속 반복 실행해야 하며, CPU 시간을 낭비했었다. 이를 Busy Waiting이라고 부르며 특수한 상황이 아니면 비효율적이다. 일반적으로는 Semaphore에서 Critical Section에 진입을 시도했지만 실패한 프로세스에 대해 Block시킨 뒤, Critical Section에 자리가 날 때 다시 깨우는 방식을 사용한다. 이 경우 Busy waiting으로 인한 시간낭비 문제가 해결된다.

🤔 바쁜 대기(영어: busy waiting 또는 spinning)

어떠한 특정 공유자원에 대하여 두 개 이상의 프로세스나 스레드가 그 이용 권한을 획득하고자 하는 동기화 상황에서 그 권한 획득을 위한 과정에서 일어나는 현상이다.

• Deadlock(교착상태)
  세마포가 Ready Queue 를 가지고 있고, 둘 이상의 프로세스가 Critical Section 진입을 무한정 기다리고 있고, Critical Section 에서 실행되는 프로세스는 진입 대기 중인 프로세스가 실행되야만 빠져나올 수 있는 상황을 지칭한다.

모니터

모니터는 공유 데이터에 대한 액세스를 제어하는 ​​데 사용되는 프로그래밍 언어 구조

• 고급 언어의 설계 구조물로서, 개발자의 코드를 상호배제 하게끔 만든 추상화된 데이터 형태이다.
• 공유자원에 접근하기 위한 키 획득과 자원 사용 후 해제를 모두 처리한다. (세마포어는 직접 키 해제와 공유자원 접근 처리가 필요하다. )