지나간 삶

1. 프로세스 스케줄러란 ?

   • 다음번에 실행될 프로세스를 선택하는 커널 컴포넌트.
   • 시스템에 있는 실행 가능한 프로세스들에게 유한한 프로세서 시간을 분배해 주는 커널의 하위 시스템.
   • 리눅스와 같은 멀티태스킹 운영체제의 기본요소로 어느 프로세스를 실행할 것인가를 선택하는 동시에, 시스템의 성능을 최적화하고, 여러개의 프로세스가 마치 동시에 실행되고 있는 것과 같이 보이도록 해야 하는 책임을 갖는다.

   • 동작시나리오

     • 실행가능한 프로세스가 여럿 있다고 할 때 프로세서(CPU)를 최대한 이용하기 위해서는 항상 어떤 프로세스든 실행중이면 되는 것이다. 만약 시스템의 프로세서 수보다 많은 프로세스가 있을 경우 몇몇 프로세스는 실행될 수 없다. 이러한 프로세스들을 실행하기 위해 대기중이라는 상태가 있다.

   • 여러 프로세스 중에서 다음 프로세스를 선택하는 것이 스케줄러가 행하는 가장 중요한 작업이다.

     
     

2. 멀티태스킹 운영체제

   • 협력형(cooperative) 멀티  태스킹과 선정형(preemptive) 멀티태스킹이 있다.
   • 리눅스는 다른 최신 운영체제 들과 마찬가지로 선점형 멀티태스킹을 지원한다.
   • 선점형 멀티태스킹은 프로세스가 언제 실행을 중지하고 또는 실행을 계속할 것인가를 바로 스케줄러가 결정.

   • 협력형 멀티태스킹은 프로세스가 자발적으로 실행을 중단할 때까지 중단되지 않는다. 자발적으로 자신을 중단시키는 일을 양보(yield)라 한다.

     
     

3. I/O 중심 과 프로세서 중심 프로세스

   • I/O 중심 프로세스 들은 그 시간의 대부분을 I/O 요청을 보내고 기다리는 데 사용한다. 짧은 기간 동안만 실행가능하게 되는데, 왜냐하면 다른 I/O 요청에 의해 결국 또다시 대기 상태로 되기 때문이다.( 디스크, 키보드 )
   • 프로세서 중심 프로세스 들은 코드를 실행하는 데 대부분의 시간을 보낸다. 보통 선점되기 전까지 계속 실행되는데, 왜냐하면 I/O 요청 등으로 중단되지 않기 때문이다.
   • 스케줄러 정책은 항상 대립되는 두 가지 목표를 갖는다. 빠른 응답 시간(낮은 지연)과 높은 프로세스 처리량 을 만족시켜여 한다. 이러한 요구조건을 만족시기 위해 스케줄러는 다른 프로세스와의 공정성을 고려하여 실행시키기 가장 알맞은 프로세스를 결정한다.

   • 리눅스는 좋은 응답성을 제공하기 위해 프로세스 응답 시간에 최적화 되었기 때문에 프로세서 중심보다 I/O 중심 프로세스를 선호한다.

     
     

4. 프로세스 우선순위

   • 스케줄링 알고리즘 중 가장 흔한 형태가 우선순위에 기반을 둔 알고리즘으로 리눅스 커널은 두 가지의 우선순위를 구현하고 있다.

     • 첫 번째는 nice값으로 -20에서 +19까지의 값을 갖는다.(기본값 0) 큰 nice값은 낮은 우선순위를 의미한다. 따라서 낮은 nice값을 갖는 프로세스들은 높은 nice값을 갖는 프로세스보다 먼저 실행된다. nice 값은 각 프로세스가 얼마나 타임슬라이스를 할당받는가를 결정하는 데도 사용된다. nice값이 -20인 프로세스는 최대 타임슬라이스를 할당받고, 19인 프로세스는 가장 작은 타임슬라이스를 할당받는다.

     • 두 번째는 실시간 우선순위로서, 0에서 99까지의 값을 갖는다. 또 모든 실시간 프로세스는 일반 프로세스보다 높은 우선순위를 부여받는다.

       
       

5. 타임슬라이스

   • 정의 : 어떤 태스크가 선점되기 전까지 실행될 수 있는 시간이 얼마나 남았는가를 가리키는 값이다.( 좀 헷갈리는 구문.. 남아있는 시간? 아니면 선점시간? )
   •  타임슬라이스가 너무 길면 시스템의 InterActive한 성능을 떨어뜨려 프로세스가 동시에 수행되는 것처럼 느껴지지 않을 것이며, 너무 짧으면 프로세스간의 스위칭이 자주 일어나 자원낭비의 비효율성이 발생.

   • 높은 우선순위를 갖는 작업이 좀더 길게, 자주 수행되게 되는데 프로세스가 모든 타임슬라이스를 반드시 한번에 소비해야 하는 것은 아니다.

     
     

6. 프로세스 선점 과정

   • 리눅스는 선점형 운영체제로 어떤 프로세스가 TASK_RUNNING  상태가 되면 커널은 이 해당 프로세스의 우선순위가 현재 실행중인 프로세스보다 높은가를 검사한다. 만약 높다면 스케줄러가 동작하여 실행할 새 프로세스를 선택한다. 또한 프로세스의 타임슬라이스가 0이 됐을 경우에도 프로세는 선점되고 스케줄러가 동작하여 실행할 새 프로세스를 고르게 된다.

     
     

7.  스케줄링 정책 시나리오

   • 2개의 실행 가능한 프로세스, 텍스트 에디터와 비디오 인코더가 태스크가 있는 시스템을 가정해 보자!
   • 텍스트 에디터는 대부분의 시간을 사용자 입력을 기다리고 있으므로, I/O 중심 프로세스이다.
   • 비디오 인코더는 프로세스 중심이다. 인코더는 대부분의 시간을 원본 데이터에 비디오 코덱을 적용하는데 소비한다.
   • 텍스트 에디터는 InterActive 한 작업이므로 스케줄러는 텍스트 에디터에게 높은 우선순위와 긴 타임슬라이스를 주게 된다. 이로 인해 텍스트 에디터는 쓰고 남을 만큼의 타임슬라이스를 갖는다. 또한 텍스트 에디터는 높은 우선순위를 가지므로, 필요에 따라 비디오 인코더를 선점할 수 있다. 이렇게 하여 텍스트 에디터는 사용자의 키 입력에 즉각적으로 반응할 수 있다.
   • 비디오 인코더에게 손해인 것처럼 보이지만 텍스트 에디터는 잠깐 동안만 실행되므로 사실 비디오 인코더가 남은 시간을 거의 독점하여 사용할 수 있다.

   • 결과적으로 두 응용프로그램의 성능이 최대화 된다.

     
     

8.  리눅스 스케줄링 알고리즘 - 이상적인 구현

   • 완전한 O(1) 스케줄링을 구현. 스케줄러의 알고리즘은 실행중인 프로세스의 개수에 무관하게 상수 시간안에 완료돼야 함.
   • 완변한 SMP 확장성을 가짐. 각각의 프로세스는 자신만의 락과 실행큐를 가짐.
   • SMP와의 상성을 개선할 것. ( 메모리는 프로세서보다 느리다. 단일 프로세서라도 메모리로부터 읽는 작업에 상당한 시간을 소비한다. SMP는 이를 더욱 악화시키는데, 한 번에 한 개의 프로세서만이 동일한 메모리에 접근 가능하기 때문이다. )
   • 자연스럽게 태스크를 특정 CPU와 연계시키고, 계속 그 CPU에서 실행 되도록 함. 오직 실행큐 크기의 밸런스를 맞추기 위해서만 태스크를 CPU에서 다른 CPU로 이동시켜야 함.
   • 좋은 InterActive 성능을 보장. 시스템에 많은 부하가 걸리는 경우에라도, InterActive 태스크에 대해 시스템이 즉각적으로 반응을 보여야 함.
   • 공평성을 유지. 어떤 프로세스도 일정 시간 이상 타임슬라이스 없이 존재해서는 안되며, 어떤 프로세스도 너무 많은 타임슬라이스를 할당 받아서는 안됨 .

   • 대부분의 경우인 1~2개의 실행가능한 프로세스가 있는 경우를 위해 최적화하되, 많은 프로세스가 있는 멀티프로세서로도 확장이 가능하게 함.

     
     

9. 실행큐(Runqueue)

   • 스케줄러의 기본 자료구조. 각 프로세스를 스케줄하기 위한 주요 자료구조임.
   • 어떤 프로세서에 있는 실행가능한 프로세스의 목록으로, 한 프로세스당 하나의 실행큐가 존재한다.
   • 실행가능한 프로세스는 오직 하나의 실행큐에만 포함되어 있어야 한다. 중복포함 불가.
   • 여러 태스크가 실행큐를 동시에 조작하는 것을 방지하기 위해 스핀락이 사용되는데, 이것은 문을 열기 위한 열쇠와 같다. 문에 처음 도착하는 태스크는 손잡이에 꽃힌 열쇠를 빼낸 다음 문을 담고 잠근다. 안에서 문을 잠근 상태 열쇠는 없다.안에 있는 태스크가 문을 열고 나와서 열쇠를 반납할 때 까지 기다려야 한다.

   • Spinning 상태가 발생하게 된다. 열쇠의 반납여부를 검사하기 위해 루프를 돌고 있기 때문이다.

     
     

10. 우선순위 배열( Queue 와 Bitmap을 가짐!! )

    • 실행큐는  2개의 우선순위 배열을 가진다. 활성(Active), 비활성(Expired) 의 성격을 지닌다. O(1) 스케줄링의 핵심 자료구조이다.
    • 각 우선순위 배열은 각 우선 순위 레벨마다의 실행가능 프로세스 큐를 가지고 있다. ( 각 큐에는 해당 우선순위 레벨의 실행가능한 프로세스 목록이 존재 )

    • 시스템의 가장 높은 우선순위의 실행가능 태스크를 효과적으로 찾아내기 위한 우선순위 비트맵을 포함하고 있다.

      
      

11. 타임슬라이스의 재계산

12. • 태스크의 타임슬라이스가 0이 됐을 때 타임슬라이스를 다시계산하기 위한 방법.

    • for ( each task on the system ) {

      recalculate priority

      recalculate timeslice

      }     

    1. • 시간이 오래 걸릴 가능성이 있다. 최악의 경우 시스템에 잇는 태스크의 수가 n이라면 O(n) 시간이 걸린다.
       • 재계산을 위해서는 태스크 목록과 각 프로세스 서술자를 보호하는 락을 사용해야 하므로, 높은 락 경쟁 상태가 발생할 수 있다.
       • 무작위적으로 발생하는 타임슬라이스의 재계산은 실시간 프로그램이 확정적 이어야 함에 장애 요인으로 작용할 수 있다.

       • 이 방법은 세련되지 않은 방법으로 커널2.6에서는 개선되어 있다.

13. 
    
    

이 글은 스프링노트에서 작성되었습니다.