chapter 7. Scheduling

 xv6는 다중 프로세스를 지원하기 위해 멀티플렉싱 기법을 사용하며, 한정된 CPU 자원을 여러 프로세스 간에 효과적으로 공유하도록 설계되었다.

 

Multiplexing

운영체제는 한정된 CPU를 여러 프로세스가 공유하도록 하기 위해 다음 두 가지 상황에서 CPU를 스위칭한다.

1) 프로세스가 I/O작업, 자식 프로세스 종료, 또는 sleep 호출로 대기 중일 때, CPU를 다른 프로세스에 양보

2) 프로세스가 오랫동안 CPU를 독점할 때 : 타이머 인터럽트를 통해 강제로 스위칭

이를 통해 xv6는 각 프로세스가 자신만의 CPU를 사용하는 것처럼 보이는 환상을 제공한다. 

하지만 멀티플렉싱을 구현하려면 몇 가지 과제를 해결해야 한다:

- context switching : 한 프로세스에서 다른 프로세스로 스위칭하는 메커니즘

- timer inerrupt based swithces forcing : 사용자 프로세스에 투명하게 구현

- multicore contention 조건 해결 : 모든 CPU가 동일한 프로세스를 관리

- 자원 정리 : 프로세스 종료 시 메모리와 스택을 안전하게 해제

- 프로세스 상태 관리 : 커널이 각 CPU의 현재 프로세스를 올바르게 관리

- sleep과 wakeup 동작 : 경장 조건 없이 효율적으로 구현

 

Code : Context switching

문맥 교환은 CPU 레지스터를 저장하고 복원하는 작업으로 이루어진다.

작동 흐름

1) swtch 함수는 현재 커널 스레드의 레지스터 상태를 저장하고 새로운 스레드의 상태를 복원한다.

2) 저장된 레지스터는 struct context 구조체에 기록되며, 이는 프로세스(p->context) 또는 CPU(cpu->context)에 할당된다.

3) swtch는 호출 당시의 복귀 주소(ra)를 저장하여, 새 스레드의 복구 시 올바른 코드 위치로 이동하도록 한다.

 

ex. sched 함수는 현재 프로세스의 p->context에 레지스터를 저장한 후, CPU의 cpu->context로 전환한다. CPU는 스케줄러 스레드로 전환되어 새로운 프로세스를 실행할 준비를 한다.

Switching from one user process to another. In this example, xv6 runs with one CPU(and thus one scheduler thread)

 

Code : Scheduling

스케줄링은 프로세스를 선택하여 실행하는 과정을 말한다.

xv6 스케줄러는 CPU당 하나의 스케줄러 스레드를 실행하며, 이 스레드는 프로세스를 선택하고 실행을 시작한다.

1. 스케줄러의 동작 

1) yield, sleep, exit 등의 함수에서 프로세스는 CPU를 포기하고 스케줄러에 제어권을 넘긴다.

2) 스케줄러는 RUNNABLE 상태의 프로세스를 검색하여 선택한다.

3) 선택된 프로세스의 상태를 RUNNING으로 업데이트하고, swtch를 호출하여 프로세스 실행을 시작한다.

 

2. 동기화의 잠금

xv6는 p->lock을 활용하여 프로세스 상태와 문맥이 일관성을 유지하도록 보장한다.

swtch 동안에는 잠금이 유지되며, 스케줄러가 제어권을 완전히 넘겨받은 후 잠금을 해제한다.

 

3. coroutine 패턴

sched와 scheduler는 서로 반복적으로 제어권을 주고받는다.

이는 코루틴 방식으로, 두 함수가 교대로 실행되며 스레드 전환을 수행한다.

 

Code : mycpu and myproc

운영체제가 현재 실행 중인 프로세스 또는 CPU를 추적하려면 효율적인 접근 방식이 필요하다.

xv6는 멀티코어 환경에서 각 CPU와 해당 프로세스를 관리하기 위해 mycpu와 myproc 함수를 사용한다.

1. mycpu

xv6는 각 CPU에 대해 struct cpu 구조체를 유지한다. 이 구조체는 :

- 현재 CPU에서 실행 중인 프로세스(c->proc)

- CPU의 스케줄러 스레드 상태(레지스터 값 등)

- 중첩된 스핀락 카운트를 관리

RISC-V의 tp 레지스터는 각 CPU의 고유 식별자(hartid)를 저장한다. xv6는 이를 사용하여 cpu 배열에서 해당 CPU의 구조체를 찾는다.

start와 usertrapret 등에서 tp 값을 유지하여 정확성을 보장한다.

 

2. myproc

현재 CPU의 struct cpu를 통해 현재 실행 중인 프로세스(c->proc)를 반환한다.

인터럽트를 비활성화한 상태에서만 사용해야 한다. 이는 타이머 인터럽트로 프로세스가 다른 CPU로 이동하는 상황을 방지하기 위함이다.

 

Sleep과 wakeup

sleep과 wakeup은 프로세스 간의 의도적인 상호작용을 지원하는 메커니즘이다. 

이를 조건 동기화로 활용하여 효율적인 스케줄링을 제공한다.

기본 동작 방식

- sleep(chan) : 특정 채널(chan)에서 대기 중인 프로세스를 대기 상태로 전환

- wakeup(chan) : 해당 채널에서 대기 중인 모든 프로세스를 깨움

 

lock과 sleep을 결합하여 atomic 작업을 보장해야 한다.

1) sleep 호출 시 잠금을 전달 : 

- sleep(chan, &lock)은 프로세스를 대기 상태로 설정하기 전에 잠금 해제

- 잠금 해제로 V가 안전하게 coun를 증가시키고 wakeup 호출 가능

- wakeup 이후, sleep이 프로세스를 깨운 뒤 잠금을 다시 획득 

void V(struct semaphore *s){
	acquire(&S->lock);
    s->count += 1;
    wakeup(s);
    release(&s->lock);
}

void P(struct semaphore *s){
	acquire(&s->lock);
    while(s->count==0)
    	sleep(s, &s->lock);
    s->count -= 1;
    release(&s->lock);
}

문제 해결

1) Lost Wakeup

sleep(s, &s->lock)은 s->lock을 원자적으로 해제하고 프로세스를 대기 상태로 전환

이 과정에서 

- 다른 CPU가 V를 실행하더라도, sleep이 프로세스를 대기 상태로 정확히 등록한 이후에야 wakeup이 호출됨

- wakeup은 항상 대기 중인 프로세스를 깨움

2) 동기화 보장 : P가 s->count==0을 확인하고 sleep으로 대기 상태에 들어가는 과정이 중단되지 않음

 

효율성 유지

- 바쁜 대기를 제거하고 CPU 자원 낭비를 방지

- sleep과 wakeup의 올바른 사용

 

Code : Sleep and wakeup

1. 핵심 동작

sleep(chan, &lock)

1) 프로세스를 대기 상태(SLEEPING)로 전환

2) 전달받은 lock을 원자적으로 해제

3) CPU를 양보하여 다른 프로세스가 실행되도록 함

wakeup(chan)

1) 특정 chan에서 대기 중인 모든 프로세스를 RUNNABLE 상태로 변경

2) 이후 스케줄러가 해당 프로세스를 실행

 

2. 문제 해결 : Lost Wakeup 방지

sleep과 wakeup은 p->lock을 활용하여 경쟁 조건을 방지한다.

sleep이 프로세스를 대기 상태로 설정하고 CPU를 양보하기 전에, wakeup이 실행되지 않도록 보장한다.

1) sleep이 p->lock을 유지하는 동안, wakeup은 동일한 락을 얻기 위해 대기

2) wakeup은 항상 sleep이 프로세스를 안전하게 대기 상태로 설정한 이후 실행

 

3. 여러 프로세스 대기

동일한 chan에서 여러 프로세스가 대기할 수 있다.

wakeup은 해당 채널에서 대기 중인 모든 프로세스를 깨우지만, 첫 번째로 락을 획득한 프로세스만 조건을 만족한다.

나머지 프로세스는 "spurious wakeup(잘못된 깨움)" 을 경험하고 다시 대기 상태로 전환한다.

 

Code : Pipes

파이프는 생산자-소비자 모델을 구현한 좋은 예시이다.

버퍼를 중심으로 sleep과 wakeup을 사용하여 동기화를 관리한다.

 

1. 파이프의 구성 요소

struct pipe : 

- lock : 버퍼와 상태(nread, write)를 보호

- buf : 데이터를 저장하는 버퍼

- nread, nwrite : 버퍼이 읽기/쓰기 위치

piperead와 pipewrite

- 각각 데이터를 읽고 쓰는 역할

- 읽기와 쓰기 중 하나가 완료될 때까지 다른 프로세스는 대기

 

2. 생산자-소비자 동작 흐름

1) 생산자(쓰기) 프로세스 : 데이터를 버퍼에 작성, 버퍼가 가득 차면 sleep 호출로 대기

2) 소비자(읽기) 프로세스 : 데이터를 버퍼에서 읽음. 버퍼가 비어 있으면 sleep 호출로 대기

3) 동기화 

- pipewrite는 버퍼가 비었을 때 wakeup 호출로 소비자를 깨움

- piperead는 버퍼가 찼을 때 wakeup 호출로 생산자를 깨움

4) 스케줄링 : sleep을 호출한 프로세스는 대기 상태로 전환되고, 다른 프로세스가 실행

 

3. 동시성 문제 해결

버퍼 보호 : lock을 사용해 동시 접근 방지, 읽기와 쓰기 작업이 충돌하지 않도록 함

별도 채널 사용 :  읽기와 쓰기에 서로 다른 채널(nread, nwrite)을 사용하여 효율성 증가

 

Code : wait, exit, and kill

1. exit : 프로세스 종료

자원을 정리하지 않음 : 자식 프로세스는 ZOMBIE 상태로 전환, 부모 프로세스가 이를 확인하여 자원을 해제

wakeup 호출 : 부모가 wait 호출로 대기중일 수 있으므로, 이를 깨움

2. wait : 자식 종료 대기

sleep 사용 : 자식이 종료되지 않은 경우, 부모는 sleep으로 대기

락 순서 : wait_lock과 p->lock을 순서대로 획득하여 데드락 방지

3. kill : 프로세스 강제 종료

p->killed 플래그 설정 : 직접 종료하지 않고, 프로세스가 커널로 들어오면 종료되도록 설계

wakeup 호출 : 대기 중인 프로세스를 깨워 종료를 유도

 

Process Locking

p->lock은 xv6에서 가장 복잡하고 중요한 락이다.

이는 프로세스의 주요 상태 및 데이터를 보호하며 다양한 상황에서 경쟁 조건(race condition)을 방지한다.

p->lock이 보호하는 데이터 : p->state, p->chan, p->killed, p->xstate, p->pid

 

1. p->lock의 역할

1) 프로세스 생성/삭제 보호 : 새 프로세스를 할당하거나 종료 중인 프로세스가 다른 코어에 의해 접근되지 않도록 보호

2) 스케줄러와의 상호작용 : 스케줄러가 RUNNABLE 상태의 프로세스를 선택하고 실행하는 과정에서 충졸 방지. 프로세스가 CPU를 양보한 뒤에도 스케줄러가 안전하게 상태를 관리하도록 보장

3) sleep과 wakeup의 동기화 지원 : 프로세스가 sleep 상태로 전환될 때, wakeup이 프로세스를 정확히 깨울 수 있도록 동기화

4) kill의 안정성 보장 : 프로세스 종료 플래그를 설정하고, 상태 변경이 충돌 없이 원자적으로 이루어지도록 보장

5) 인터럽트가 발생해 yield가 호출되더라도 프로세스가 안전하게 상태를 전환할 수 있도록 보호

 

2. wait_lock의 역할

p->parent 필드는 p->lock 대신 wait_lock으로 보호

- 이유 : 부모와 자식 간의 상호작용(wait, exit)은 전역적인 동기화를 요구하며, 이를 위해 wait_lock 사용

역할 : 

1) 부모가 자식의 종료를 기다리는 동안 경쟁 조건 방지

2) 자식 프로세스가 ZOMBIE 상태로 전환된 후 부모가 이를 안전하게 확인할 수 있도록 보장