PINTOS 1주차 Blocked List, Scheduling

이번 주차에 Pintos 과제를 수행하며 배우게 된 개념은 다음과 같다.

 

*프로세스 state를 기준으로 정리하겠다.

 

1. Context Switching

 

2. Thread State

• New
  • 프로세스가 생성됨
• Ready
  • 프로세스가 CPU를 배정받기를 기다림
  • 여러 개의 프로세스가 있을 수 있음. 일종의 waiting queue이다. 리눅스에서는 run queue라는 이름을 쓰고 있다. run queue/ready list에 프로세스를 넣는다고 하면 어떤 자료구조를 넣으면 될까? PCB 자료구조를 ready queue에 넣는다고 생각하면 된다.
  • Dispatched: Ready → Running
    • CPU를 배정받음
• Running
  • instruction이 실행됨
  • 모든 자원과 함께 CPU도 배정받음
  • CPU가 한 개이면 running에는 instruction이 1개만 올 수 있음
  • Waiting for I/O or Event: Running → Waiting
    • 어떤 프로세스가 running을 하고 있는데 이 프로세스가 갑자기 synchronous I/O를 하게 됐다. DMA를 하게 되었다. 큰 disk block을 write해달라고 했다. 이 프로세스는 CPU를 스스로 양보하게 된다. 양보한 프로세스가 running state를 떠나고 새로운 state로 가게 되는데 그걸 우리가 waiting state라고 이야기한다.
  • Interrupted: Running → Ready
    • 한 프로세스가 CPU를 점유했을 때 간섭 없이 내버려두면 너무 오래 CPU를 사용하게 된다. 그러면 ready 상태에 있는 다른 프로세스들이 CPU들을 못 쓴다는 문제가 있다. 그러면 os가 타이머를 설정한다. 타이머가 expire할 때까지 CPU를 쓰고 있다면 타이머로부터 interrupt를 받게 된다. 그래서 OS에 핸들러가 뜨게 되고 os의 핸들러가 CPU를 너무 오래 사용하는 프로세스를 쫓아낸다. 근데 이 프로세스는 무슨 waiting 때문에 쫓아내는 프로세스가 아니다. 프로세스는 돌 수 있는데 CPU 자원을 양보해야만 했기 때문에 나가는 것이다. 그래서 그 프로세스는 ready 상태로 가게 된다.
• Waiting: 프로세스가 새로운 이벤트가 발생하기를 기다림
  • waiting 상태에 프로세스는 몇 개가 있을 수 있는가? 여러 개가 있을 수 있다. DMA에 의해서, 키보드 input을 기다림 등
  • 여러 개의 프로세스 PCB를 묶은 자료 구조가 필요하다. ready와는 다르다. 내가 왜 waiting하고 있는지 이유에 따라 분류가 된다. DMA를 기다리는 큐, 다른 건 다른 큐. waiting reason별로 큐를 따로 만든다.
  • I/O Completion or Event Occurrence: Waiting → Ready
    • DMA 컨트롤러가 부여받은 미션을 다 수행해서 DMA를 종료하면 interrupt mechanism을 이용해서 CPU에게 interrupt를 건다. CPU가 interrupt를 받으면 os에 핸들러가 뜨게 된다. os에 핸들러가 떠서 보면 나를 DMA 시켜준 프로세스가 지금 waiting queue에 지금 대기하고 있다는 걸 알게 된다. 걔가 다음에 수행할 수 있도록 해줘야 되겠다고 생각하며 waiting state에 있는 프로세스를 ready state로 보낸다.
    • 왜 waiting state에 있는 프로세스를 running state로 보내지 않고 ready 상태로 보낼까? 왜냐하면 지금 러닝 상태에서 DMA completion interrupt를 받은 프로세스가 wait에서 깨어난 프로세스보다 더 중요한 프로세스일 수도 있다. 그러니까 이 프로세스를 반드시 ready 상태로 보내서 priority arbitration 다시 말해서 스케줄링을 받도록 하고 걔가 자격이 되면 running으로 가게 되는 그런 절차를 밟아야 한다.
• Terminated
  • 프로세스가 실행을 끝냄

3. CPU 스케줄링

 

운영체제가 멀티 태스킹을 지원할 때 발생하는 문제는 무엇일까?

OS의 가장 중요한 목적 중 하나는 멀티 태스킹 multi-tasking이다. OS를 사용하는 이유는 멀티 태스킹을 지원하기 위한 것이라고 해도 과언이 아니다. 멀티 태스킹이란 동시에 여러 개의 작업을 병렬적으로 수행하는 것이다.

(1) 스케줄링 scheduling

멀티 태스킹을 지원한다는 것은 하드웨어 자원들을 여러 job들에게 잘 배분한다는 뜻이다. 예를 들어 single processor system이 있고 지금 수행하고자 하는 job이 10개가 있다고 해보자. 어느 한 시점에는 하나의 job에게만 CPU를 줘야 한다. 그럼 나머지 9개의 job은 언제 CPU의 배분을 받을 수 있을까? 이러한 CPU의 배분은 효율적이어야 되고 공평해야 되는데, 이 스케줄링 scheduling 문제는 운영체제가 멀티 태스킹을 지원하기 때문에 발생하는 것이다. 싱글 태스킹 single-tasking을 한다면 이런 스케줄링 문제가 없을 것이다.

(2) 동기화 synchronization

task 또는 job들이 동시에 수행이 되고 있고 이들이 공유된 데이터에 접근한다면 여기에는동기화 synchronization 문제라는 것이 발생한다. job들이 수행되는 과정에서 공유된 데이터에 잘못된 값이 들어가지 못하도록 OS가 적절한 조치를 해줘야 한다. 이를 두고 동기화 선점 synchronization preemptive를 제공한다고 이야기한다.

 

어떤 프로세스가 running 상태에 있다가 synchronous I/O 때문에 자발적으로 CPU를 양보하는 waiting 상태로 가는 경우가 있고, 또 다른 경우는 running 상태에 있는 프로세스가 자기는 돌고 싶은데 시스템에서 강제로 CPU를 빼앗기게 되는 그런 transition이 있다. 어떤 프로세스가 running을 하다가 자발적으로 CPU를 양보하는 것을 non-preemptive scheduling이라고 얘기한다.

running에서 waiting 상태로 가는 것은 synchronous interrupt 또는 system call 같은 것으로 구현이 된다. OS라고 하는 것은 PCB라고 하는 프로세스를 구현하는 자료 구조를 가지고 시스템 안에서 발생되는 여러 가지 이벤트에 따라서 그 PCB를 이 큐에서 저 큐로 옮겨주는 이런 연산을 하는 개체 entity다. 아주 기계적으로 해석하면 그렇다.

그런데 running 상태에 있는 프로세스가 자기 의지와 무관하게 OS의 강제 명령에 의해서 CPU를 빼앗겨 가지고 ready 상태로 가는 것을 우리는 preemptive scheduling이라고 이야기한다. preemptive scheduling을 하려면 반드시 OS의 개입이 필요하다. 왜냐하면 OS의 코드가 돌아서 나를 ready 상태로 옮겨줘야 하기 때문이다.

dual mode operation…user code는 user mode에서 돌고 os system code는 kernel mode에서 돈다. 어떤 프로세스가 지금 수행하고 있다고 하면 마이크로 프로세스의 모드는 user mode가 된다. 그런데 그 프로세스가 CPU를 빼앗겨서 preemptive scheduling을 당해서 ready queue로 가려면 os의 코드 특히 scheduler code가 돌아야 한다. 그러려면 모드 체인지가 필요하다. 유저 모드에서 커널 모드로 모드 체인지가 일어나고 거기서 scheduler code가 돌아야 한다.

유저 모드에서 커널 모드로 모드 체인지가 일어나려면 어떤 Hardware mechanism이 필요할까? 바로 interrupt mechanism이 필요하다. running 상태에 있는 프로세스가 ready 상태로 넘어가려면 timmer interrupt 등이 개입이 되었다. 그래서 preemptive scheduling은 반드시 HW interrupt가 필요하다. 왜냐하면 asynchronous 비동기적이기 때문이다.

프로세스를 한 state에서 다른 state로 옮겨주는 것이 바로 스케줄링 동작이다.

 

dispatcher는 운영체제의 가장 안 속 깊은 곳에 있는 일종의 무한루프라고 생각해보면 된다. 여기 슬라이드에 나와 있는 그런 구조를 갖고 있다. 이 dispatcher는 본인이 과거에 선택한 프로세스를 한동안 수행을 시킨다. 그러다가 rescheduling을 해야 될 필요가 발생을 하게 되면 현재 수행 중인 프로세스의 수행을 중단시킨다. 그리고 그 프로세스의 context를 안전하게 대피시킨다. 그리고 나서 새로 수행해야 될 next process를 선택하고 그 프로세스가 수행을 하기 위해서 필요한 저장된 context를 다시 로드해온다. 그리고 나서 그 프로세스를 한동안 수행을 시킨다. 이런 것을 지속적으로 반복하는 무한루프를 도는 os의 아주 inner-most portion을 우리가 dispatcher라고 할 수 있다.