[UCB CS162 OS] Lec06 Synchronization(1)

Context Switch

• Kernel은 각 프로세스를 PCB(process control block)으로 나타낸다.
• process 간의 문맥전환은 기존 프로세스의 상태를 해당 PCB에 저장하고, 실행하려는 새로운 프로세스의 상태를 해당 PCB로부터 열어와서 실행한 뒤에 다시 그 PCB에 저장하고, 처음에 저장해 둔 PCB로부터 기존 프로세스를 다시 불러와서 실행하는 방식으로 이루어진다.
• 여기서 PCB로의 save/load는 kernel에서 이루어진다(privilege level: 0). 이를 위해서는 system call이나 interrupt가 필요하다.

Process(내지 Thread)의 수명주기

• process는 new, ready(run될 수 있는 상태), running(실행되는 상태), waiting(I/O나 event를 기다리는 상태), terminated(종료)의 상태를 지닐 수 있다.
• 부모 프로세스가 자식 프로세스의 종료를 알아갸 하기 때문에 terminated 상태가 존재한다.

Scheduling

• PCB들은 여러 queue를 옮겨다니게 된다. 기본적으로 CPU에 대한 ready queue 이외에도 I/O나 signal 등을 위한 별도의 큐가 있다.
• ready queue에서는 ready 상태의 프로세스가 있는지를 확인해서, 있다면 특정한 정책에 따라 다음으로 실행할 프로세스를 선택하여 실행하고, 없다면 idle process를 실행한다.

Concurrency

• 스케줄링 루프는 위와 같은 형태다. 기본적으로 이는 infinite loop이며, machine을 종료할 때에 exit한다.

Running a Thread

• thread state를 CPU로 불러온 뒤, environment를 불러오고, PC로 jump하여 실행한다. 그런데 PC로 jump한다는 것은 이 스레드에게 control을 주었다는 것인데, 이것을 어떻게 돌려받을 수 있을까?

Internal Events(자발적으로 반환)

• 종류
  • Blocking on I/O(I/O를 요청함에 따라 implicitly yield the CPU)
  • Waiting on signal from other thread
  • Execute yield()

Yield에 의한 Context Switch

• user thread에서 yield를 하게 되면 kernel로 넘어오게 되며, 각 thread stack별로 kernel stack이 1:1로 대응된다.
• 새로운 thread를 실행하기 위해서는 PC, register, stack pointer를 미리 저장해 놓음으로써 각 스레드에 대한 isolation을 유지한다.

Context Switch에 대해

• TCB + stacks(user/kernel) contains complete restartable state of thread
• context switch 과정에서 작은 실수를 할 경우 어떠한 경고 없이 계속해서 간헐적으로 문제가 발생할 수 있다. 하지만 그렇다고 해서 switch code를 완전히 테스트할 수는 없다.
• context switch는 process switch에 비해 훨씬 cheap하다는 장점이 있다.
  • switching between threads: 100 ns
  • switching between processes: 3-4 microsec
  • frequency of context switch: 10-100ms
• (현재 수업에서는 user thread 하나당 kernel thread 하나가 대응하는 모델을 다룬다)

Processes vs. Threads 비교

• process 간에는 parallelism이 없으며, 서로 다른 프로세스로의 switch overhead, sharing overhead, protection level은 모두 높다(같은 프로세스 내에서는 낮다)
• thread를 사용하게 되면 다른 것은 대체로 같지만, sharing overhead 측면에서 서로 다른 프로세스라 하더라도 동시에 CPU core를 이용하고 있다면 중간 수준이라 볼 수 있고, parallelism이 가능하다.
• simultaneous multithreading(내지는 hyperthreading)은 한 CPU 내에서도 서로 다른 스레드를 별도의 CPU인 것처럼 스케줄링할 수 있어서 속도가 더 빨라진다.

I/O Block에 의한 context switch

• I/O system call이 이루어지면 kernel이 read를 하면서 사실상 yield가 일어나고, 다른 스레드로 전환된다.

External Events

• 특정 프로그램이 모든 자원을 점유해버리는 것을 방지하기 위해 외부 이벤트를 이용한다.
  • interrupt: 시그널을 보내서 코드를 종료하고 kernel로 jump시킨다
  • Timer: 알람시계처럼 일정한 주기마다 꺼진다

Interrupt

• device로부터의 interrupt line으로 촉발되는데, interrupt controller에서 interrupt mask로 enable/disable할 수 있고, priority encoder가 highest enabled interrupt를 선택한다.
• CPU는 internal flag를 가지고 모든 interrupt를 disable할 수 있다. 단, NMI(Non-Maskable Interrupt line)은 disable될 수 없다.
• interrupt는 HW-invoked context switch이므로 다음에 무엇을 run할지 선택하는 별도의 과정이 없고, 바로 interrupt handler를 가동한다.

Timer Interrupt

• timer interrupt는 강제로 scheduling하도록 한다.

How to start a new thread

• TCB의 register fields를 먼저 초기화한다.
  • stack pointer는 새로운 user stack을 가리킨다.
  • PC는 ThreadRoot code를 가리키도록 한다.
  • 함수 및 인자를 가리키는 포인터를 레지스터에 넣는다.
• 하지만 stack data는 별도로 초기화하지 않고, 실제로 스레드가 시작될 떄 초기화된다.
• 실제로 스레드가 시작되는 시점에 stack의 ThreadRoot로 오고나면 user thread에서 코드가 실행되고 stack growth가 일어난다.

Correctness

• concurrent threads간에는 어떤 순서로든(in any order) 실행될 수 있고, 아무때나(at any time) 변경될 수 있다.
• event-driven 방식으로 코드를 바꾸어 I/O를 computation과 overlap시킬 수는 있지만, 수도 없이 많은 event를 하나하나 다루는 것은 쉽지 않다.
• 스레드를 사용하면 yield를 통해 이 목적을 달성할 수 있지만, shared state는 corrupt될 수 있다.

Atomic Operations

• 완전히 실행되거나 아니면 전혀 안 되는 것이다(즉 indivisible)
• lock을 사용하게 되면 한번에 한 스레드만이 critical section에 들어올 수 있다.
• race condition: 두 개의 스레드가 동일한 데이터를 동시에 접근하려고 하면서, 그 중 하나가 write를 하는 상황