OS - Multilevel Queue

Multi-Level Queue

ready queue를 여러 개의 독립적인 큐로 나누고, 레벨을 부여한 것.

우선순위 고정 방식 (Fixed Priority)

• foreground 큐(대화형)는 높은 우선 순위, background 큐(배치)는 낮은 우선순위를 가진다.
• foreground 큐가 완전히 비워져야 background 큐가 실행된다.

시간 할당 방식 (Time Slice)

• 각 큐에 CPU 시간의 일정 비율을 할당한다.(예: foreground 80% RR, background 20% in FCFS) - 각 큐마다 다른 알고리즘 적용 가능

MultiLevel Feedback

프로세스의 상태나 행동에 따라 동적으로 우선순위를 바꾸는 큐 기반 스케줄링이다.

• 여러개의 우선순위 큐를 만들고, 프로세스의 행동에 따라 큐 간 이동을 허용하여 더 효율적인 스케줄링을 하는 방식이다.

• 프로세스는 다양한 큐 사이를 이동할 수 있다.
• 오래 기다리는 프로세스는 Aging을 이용해 상위 큐로 올려서 Starving을 방지한다.

다단계 피드백 큐 스케줄러 매개변수

• Number of Queues
• Scheduling 알고리즘 for each queue
• 프로세스의 우선순위를 언제 올리고 내릴지
• 새로운 프로세스가 어떤 큐로 처음 들어갈지

• 초기 진입시 Q0에서 시작함.
• Q0에서 시간이 초과되면 Q1으로 강등된다. (시간 퀀텀은 더 크다.)
• Q2로 오면 FCFS방식으로 순서대로 진행된다.
• 상위가 비워져 있을때만 하위 큐를 실행한다. (Q1은 Q0가 완전히 비워져 있어야 실행된다.)

<장점>

• 반응성 향상
• 빠른 작업 처리
• 자동 우선순위 적용

⚠️멀티 레벨 큐는 큐간 이동이 불가능 하다. 하지만 feedback은 가능

Window 스케줄링

• Window는 우선순위 기반의 선점형 스케줄링을 사용한다.

• 스레드는 (블로킹, 타임 슬라이스 소진, 우선순위가 더 높은 프로세스에 의한 선점)중 하나가 발생하기 전까지 실행된다.

• Real-Time Thread는 non-real time을 preempt 할 수 있다.

• 우선순위는 32단계로 구성된다.(1-15은 일반 우선순위 클래스, 16-31은 실시간 클래스) - 숫자가 높을 수록 우선도 높음

• 우선순위 0은 메모리 관리 스레드에 할당된다. -> 시스템 내부용, 거의 항상 백그라운드에서 메모리 관련 작업을 처리한다. (0이기 때문에 다른 작업이 없을 때만 실행)

• 각 우선순위 마다 별도의 큐가 있다. -> 같은 우선순위의 작업들은 같은 큐에 들어가고 FIFO, time-slice방식으로 구현된다.

• 실행 가능한 스레드가 없으면, idle thread(유휴 스레드)를 실행한다.
  idle = 아무것도 안한다.

Windows Priority

• 할당된 시간이 다 지난다. -> 우선도가 낮아지지만 기본 우선순위(base)밑으로는 내려가지 않는다.
• 스레드가 어떤 이유로든 Wating상황이 생기면, 기다린 종류에 따라 우선순위를 일시적으로 올려준다.
• 화면에 활성화된 창의 스레드는 일반보다 3배 더 긴 시간을 받는다.
  -> 사용자가 보고있는 화면이라 빨리빨리 반응하기 위해

Linux

• 스케줄링 시간이 일정하게 O(1)이다.

• 선점형이고, 우선순위에 따라 결정되는 스케줄링이다.

• 우선순위는 두종류로 나뉜다 : 타입 쉐어링, 실시간

• RealTime(0~99), nice(100~140), Linux는 낮을 수록 우선순위가 높음

• 우선순위가 높은 프로세스일수록 더 많은 CPU 시간을 할당받는다.

• 각 CPU코어는 자체 runqueue를 가진다.

• runqueue는 두 부분으로 나뉘어져 있다.

  • active priority array : 아직 cpu 시간을 남겨둔 작업들
  • expired priority array : cpu시간을 다 써서 당장은 실행 불가능한 작업들

• 작업은 할당된 time slice가 남아있는 동안 active 상태에서 실행 가능하다.

• 만약 CPU시간을 다 썻다면(expired상태) 그 프로세스는 다른 모든 active task가 끝나길 기다려야 한다.

• 모든 active task가 실행되고 나면 active와 expired 큐를 바꾼다.(swap 한다)(task를 다시 다 옮기는건 더 오래걸리기 때문에 역할만 바꿔줌)

• realTime Task는 고정된 우선순위를 가진다.

• Other Task는 우선도가 바뀌는데 nice value를 기반으로 한다.

  • 사용자 입력을 기다리는 interactive한 프로그램일수록 자주 sleep상태가 되고 -> 우선순위가 높아진다.(-5처럼)
  • 반대로 CPU를 많이 쓰고 Sleep하지 않는 연산중심은 우선순위가 낮아진다. (+5처럼)
  • Task가 expired로 가면, 우선순위가 재계산된다. (동적 우선순위를 반영하기 위해)
  • active/expired를 swap하는 구조가 우선순위 재조정의 핵심이다.

Window vs Linux 정리

내용	Window	Linux
스케줄러 종류	Multilevel feedback queue + dispatcher	O(1) 스케줄러
우선순위 조정 방식	time을 다 쓰면 우선순위 감소, foreground app은 time이 3배	nice value에 따라 동적 우선순위

Process Concurrency 문제

• 여러 데이터가 동시에 공유 데이터에 접근할 때, 데이터 불일치가 발생할 수 있다.
• 데이터의 일관성을 유지하기 위해서는 협력 프로세스들이 순서대로 실행되도록 제어하는 동기화 메커니즘이 필요하다.

Shared Buffer Problem

• 기존 circular buffer
• in==out일 경우 : 버퍼가 비워져 있는 상태
• (in+1)%BS == out : 버퍼가 가득찬 상태
• 이 구조에서는 항상 1칸을 비워야 가득찬 상태를 비교할 수 있다.

따라서..! 해결책으로는 카운터 변수를 추가하는 것이다.

• counter == 0 : 버퍼가 비워져 있다.
• counter == BS : 버퍼가 가득 차 있다.
• 생산자가 버퍼를 쓸 때 : counter++
• 생산자가 데이터를 읽을 때 : counter--

//<Producer>
while (true) {
    while (counter == BUFFER_SIZE); // 버퍼가 꽉 차면 대기
    buffer[in] = nextProduced;
    in = (in + 1) % BUFFER_SIZE;
    counter++;
}

//<Consumer>
while (true) {
    while (counter == 0); // 버퍼가 비면 대기
    nextConsumed = buffer[out];
    out = (out + 1) % BUFFER_SIZE;
    counter--;
}

이런식으로 구현할 수 있다.

Race Condition

하지만 counter을 생산자와 소비자가 둘 다 실행하면 문제가 발생할 수 있다.

(초기 counter가 5라고 가정)

Producer: register1 = counter → 5
Producer: register1 = register1 + 1 → 6

Consumer: register2 = counter → 여전히 5
Consumer: register2 = register2 - 1 → 4

Producer: counter = register1 → 6
Consumer: counter = register2 → counter = 4 ← 💥 값 덮어씌워짐!

• 결과적으로 공유 변수 값이 꼬이거나 손실 될 수 있음.

Critical Section Problem

여러 프로세스가 공유 자원에 접근할 때 임계구역을 두고, 한번에 하나의 프로세스만 진입하게 해야한다.

• n개의 프로세스로 구성된 시스템 p1,p2....pn이 있다고 하자. 각 프로세스는 임계구역을 가진다.
• Critical Section이란 여러 프로세스가 함께 사용하는 자원(데이터, 장치)에 접근하는 코드 부분을 의미한다.
• 하나의 프로세스가 임계 구역에 있으면, 다른 프로세스는 올 수 없다.
  ⚠️ 각 프로세스는 진입 구역(entry section)에서 임계구역 접근 허가를 받아야 하고, critical section을 실행을 한 뒤는 exit section을 가지고, 그 이후에는 나머지 작업을 수행하는 remainder section을 가진다.

해결방법

• Mutual Exclusion - 동시에 두 프로세스가 critical section에 들어가면 안됨.
• Progress - 진입 가능한 프로세스가 있다면 결정이 지연되면 안된다.
  -> 누군가는 critical section에 들어가야함.
• Bounded Waiting - 어느 프로세스도 무한히 기다려선 안된다.
  -> 진입 요청한 프로세스는 언젠가는 들어갈 수 있어야 한다.