Skip to content

15.04.08

Jump to bottom Edit New page
WHITESH2P edited this page Apr 8, 2015 · 14 revisions

상태 전이

  • 하나의 프로그램이 실행되면 그 프로그램에 대응되는 프로세스가 생성되어 준비 리스트의 끝에 들어간다. 준비 리스트 상의 다른 프로세스들이 CPU를 할당받아 준비 리스트를 떠나면, 그 프로세스는 점차 준비 리스트의 앞으로 나가게 되고 언젠가 CPU를 사용할 수 있게 된다. (위키백과 - 프로세스)

실행 수준 변화

  • 태스크가 생성되면 그 태스크는 준비(TASK_RUNNING)상태가 된다. 스케줄러는 여러 태스크 중에서 실행시킬 태스크를 선택하여 수행시킨다.
  • 준비(TASK_RUNNING)상태는 구체적으로 준비(TASK_RUNNING(ready))상태와 실제 CPU를 배정받아 명령어들을 처리하고 있는 실행(TASK_RUNNING(running))상태로 나뉜다.

태스크의 상태 전이

실행 상태에 있는 태스크들은 발생하는 사건에 따라 다음과 같은 상태로 전이할 수 있다.

  1. 태스크가 자신이 해야할 일을 다 끝내고 exit()호출하여 **TASK_DEAD(EXIT_ZOMBIE)**상태로 전이.
  • **TASK_DEAD(EXIT_ZOMBIE)**상태란 자신이 종료된 이유(예: error번호), 자신이 사용한 자원의 통계 정보 등을 부모 태스크에게 알려주기 위해 유지되고 있는 상태.

부모 태스크가 wait()등의 함수를 호출하면 자식 태스크의 상태는 TASK_DEAD(EXIT_DEAD) 상태로 바뀌면서 자신이 유지하고 있던 자원을 모두 반환하고 최종 종료. 2. 실행(TASK_RUNNING(running))상태에서

  • 실제 수행되던 태스크가 자신에게 할당된 CPU시간을 다 사용하였거나,
  • 보다 높은 우선순위를 가지는 태스크로 인해

준비(TASK_RUNNING(ready))상태로 전환.

  1. SIGSTOP, SIGTSTP, SIGTTIN, SIGTTOU 등의 시그널을 받은 태스크는 TASK_STOPPED 상태로 전이.
    추후 SIGCONT 시그널을 받아 다시 TASK_RUNNING(ready) 상태로 전환.

  2. 실행(TASK_RUNNING(running))상태에 있던 태스크가 특정한 사건을 기다려야 할 필요가 있으면 대기 상태(TASK_INTERRUPTIBLE, TASK_UNINTERRUPTIBLE, TASK_KILLABLE)로 전이.

  • TASK_UNINTERRUPTIBLE상태는 시그널에 반응하지 않는다는 점에서 TASK_INTERRUPTIBLE과 구분.
  • TASK_KILLABLE상태는 태스크가 종료되지 않는 문제점을 보완하여 중요한 시그널에만 반응한다.

언젠가 태스크가 기다리고 있던 event가 발생하면 대기 상태에 있던 태스크가 다시 준비(TASK_RUNNING(ready))상태로 전이하게 된다. 다시 다른 태스크들과 함께 스케줄링 되기 위해 경쟁하게 된다. 생성된 태스크는 위 그림과 같이 동적으로 전이하며 실행되다가 자신의 임무를 다하면 TASK_DEAD 상태를 거쳐 소멸한다.

TASK_RUNNING(running) 상태의 수준

종류 설명
사용자 수준 실행 CPU에서 사용자 수준 프로그램의 제작자가 만든 응용 프로그램이나 라이브러리 코드를 수행하는 상태로, 사용자 수준의 권한으로 동작.
커널 수준 실행 CPU에서 커널 프로그램의 일부분을 수행하고 있는 상태로, 사용자 권한보다는 더 강력한 커널 권한으로 동작.
  • 사용자 수준 실행상태에서 커널 수준 실행 상태로 전이할 수 있는 방법
    • 시스템 호출의 사용
    • 인터럽트의 발생

커널 수준 실행

  • 리눅스 커널은 태스크가 생성될 때마다 태스크 별로 task_struct 구조체와 커널 스택을 할당해준다.

thread_union 구조

  • 커널 스택은 thread_union이라 불리며, thread_info 구조체를 포함하고 있다.

  • thread_info 구조체 안에는 해당 태스크의 task_struct를 가리키는 포인터와, 스케줄링의 필요성 여부를 나타내는 플래그, 태스크의 포맷을 나타내는 exec_domain 등의 필드가 존재.

  • 커널로 진입되는 시점에 커널 스택 pt_regs 공간 안에 현재 레지스터의 값들을 구조체를 이용하여 일목요연하게 저장.

    • 태스크가 커널 수준 실행 상태에서 수행해야 할 일을 모두 마치고 사용자 수준 실행상태로 복귀하여 수행하던 곳에서부터 다시 작업을 시작하기 위해...

  • 커널 수준 실행 상태에서 사용자 수준 실행 상태로 전이할 때 리눅스 커널이 처리하는 일

    • 커널은 현재 실행 중인 태스크가 시그널을 받았는지 확인, 받았다면 필요한 경우에 한 해 시그널 처리 핸들러를 호출.
    • 다시 스케줄링 해야 할 필요가 있다면 스케줄러를 호출.
    • 커널 내에서 연기된 루틴들이 존재하면 이들을 수행.

##런 큐와 스케줄링 ###스케줄링

  • 여러개의 태스크들 중에서 다음번 수행시킬 태스크를 선택하여 CPU라는 자원을 할당하는 과정.
  • 리눅스가 제공하는 140단계의 우선순위
    • 0~99단계 : 실시간 태스크 (숫자가 낮을수록 높은 우선 순위를 나타냄)
    • 100~139단계 : 일반 태스크

###런 큐와 태스크

  • 운영체제는 스케줄링 작업 수행을 위해, 수행 가능한 상태의 태스크를 자료구조를 통해 관리. 리눅스에서는 이 자료구조를 런 큐라 한다.
  • ~/kernel/sched/sched.h 파일 내에 struct rq 라는 이름으로 정의되고, 부팅이 완료된 이후 각 CPU 별로 하나씩의 런 큐가 유지된다.

런 큐 구조와 태스크

  • 태스크가 처음 생성되면 init_task를 헤드로 하는 이중 연결 리스트에 삽입된다. (그림에서는 간단히 tasklist로 나타냄.)

  • 리눅스 시스템에 존재하는 모든 태스크들은 tasklist에 연결되어 있다.

    • wake_up_new_task()는 새로 생성되어 TASK_RUNNING 상태가 된 태스크가 런 쿠로 삽입되는 과정
    • wake_up()는 이벤트를 대기하다 깨어나서 런 큐로 삽입되는 과정

  • 다중 CPU 환경에서 런 큐가 여러 개라면 새로이 생성된 태스크는 어느 런 큐에 삽입될까?

    • 새로 생성되는 태스크는 부모 태스크가 존재하던 런 큐로 삽입됨.
    • 대기 상태에서 깨어난 태스크는 대기 전에 수행되던 CPU의 런 큐로 삽입됨.
      • 자식과 부모 태스크와 같은 CPU에서 수행될 때 더 높은 캐시 친화력을 얻을 수 있기 때문

  • 스케줄러가 수행되면 해당 CPU의 런 큐에서 다음번 수행시킬 태스크를 골라낼 때 고려사항.

    1. 어떤 태스크를 선택할 것인가?
    • 일반 태스크 : CFS(Completely Fair Scheduler)
    • 실시간 태스크 : FIFO, RR, DEADLINE
    1. 런 큐간의 부하가 균등하지 않은 경우 어떻게 할 것인가?
    • 부하 균등(load balancing)기법
    • load_balance() : 특정 CPU가 많은 작업을 수행하고 있느라 매우 바쁘고 다른 CPU들은 한가하다면 다른 CPU로 태스크를 이주시켜서 시스템의 전반적인 성능 향상을 시도.

  • '어느 CPU'로 이주시킬 것인가?
    CPU 구조와 스케줄링 도메인/그룹

    • 위 그림은 하이퍼 스레딩을 지원하는 dual-core 칩이 두 개 장착되어 있는 시스템을 개념적으로 나타냄.
    • 0~7번까지 총 8개의 논리적인 CPU가 존재하는 것으로 인식.
    • 0번 CPU에서 태스크를 이주시키려고 한다면?
      • 우선순위 : 2번 -> 1,3번 -> 4,6,5,7번 CPU

스케줄링 동작 원리

  • 처리율과 반응성 높은 스케줄링을 하기 위해 task_struct 구조체에 policy, prio, rt_priority 등의 필드가 존재한다.
    • policy 필드 : 태스크가 어떤 스케줄링 정책을 사용하는지 나타냄.
    • rt_priority : 0~99까지의 우선순위를 가짐.

스케줄링 정책

  • 실시간 태스크 : SCHED_FIFO, SCHED_RR, SCHED_DEADLINE
  • 일반 태스크 : SCHED_NORMAL, SCHED_IDLE, SCHED_BATCH
    • SCHED_IDLE : 중요하지 않은 일을 수행하는 태스크가 CPU를 점유하는 것을 막기 위해 가장 낮은 우선순위로 스케줄링되는 정책.
    • SCHED_BATCH : 사용자와의 상호 작용이 없는 CPU 중심의 일괄작업 태스크를 위한 정책.

실시간 태스크

  • 실시간 태스크란 SCHED_FIFO, SCHED_RR, SCHED_DEADLINE 정책을 사용하는 태스크를 의미한다.

    • sched_setscheduler() 등의 함수를 통해 태스크의 스케줄링 정책을 위 세 가지 중 하나로 바꾸게 되면 실시간 태스크가 됨.

  • task_struct 구조체의 rt_priority 필드를 사용하여 0부터 99까지의 우선순위를 가질 수 있다.

  • 실시간 정책을 사용하는 태스크는 고정 우선순위를 가진다.

    |종류|설명| |-------|-----------| |FIFO| 태스크가 수행을 종료하거나, 스스로 중지할 때까지 CPU를 사용한다.| |RR| 태스크가 수행을 종료하거나, 스스로 중지하거나, 자신의 타임 슬라이스를 다 쓸 때까지 CPU를 사용한다. ||동일 우선순위를 가지는 태스크가 복수개인 경우 타임슬라이스 기반으로 스케줄링 된다. |DEADLINE|dealine이 가장 가까운 태스크를 스케줄링 대상으로 선정한다.|

  • 실시간 태스크 중 우선순위가 가장 높은 태스크를 어떻게 찾을까? ####FIFO & RR FIFO와 RR 정책을 위한 비트맵과 큐

  • FIFO 혹은 RR 정책을 사용하는 실시간 태스크들이 가질 수 있는 모든 우선순위 레벨(0~99)을 표현할 수 있는 비트맵을 준비한다.

  • 태스크가 생성되면 비트맵에서 그 태스크의 우선순위에 해당하는 비트를 1로 set한 뒤, 태스크의 우선순위에 해당하는 해당하는 큐에 삽입된다.

  • 스케줄링하는 시점이 되면 커널은 비트맵에서 가장 처음으로 set되어 있는 비트를 찾아 낸 뒤, 그 우선순위 큐에 매달려 있는 태스크를 선택하게 된다.

####DEADLINE

  • DEADLINE 정책을 사용하는 각 태스크들은 dealine을 이용하여 RBTree(Red-Black Tree)에 정렬된다.
  • 스케줄러가 호출되면 가장 가까운 deadline을 가지는 태스크를 스케줄링 대상으로 선정한다.

###일반 태스크 스케줄링

Add a custom footer
Add a custom sidebar

Clone this wiki locally