일자 : 2023. 05. 13

범위 : 리눅스 커널 내부 구조 3장

참가 : 약 40명

 

 

Chapter 3

 

6. 상태 전이(State Transition)와 실행 수준 변화

상태 전이 : 태스크를 대기시켰다가 다시 수행시켰다가 하는 과정이 있기 때문에, 상태 전이가 일어난다.

 

상태 전이는 어떻게 구현되는가

상태는 task_struct 구조체의 필드값으로 표현된다.

a. exit_state라는 필드는 EXIT_ZOMBIE와 EXIT_DEAD 상태를 나타낸다.

b. 그 외의 상태는 state 필드에 저장된다.

 

태스크의 실행

1. 태스크가 생성되면, 초기값이 준비 상태(TASK_RUNNING)이다.
2. 스케줄러가 태스크를 실행시키면 TASK_RUNNING 상태로 전이 이 때 여유로운 CPU를 배정받아 실행하게 된다. 즉 한 CPU당 하나의 태스크가 실행된다. N개의 CPU가 있는 머신이라면 동시에 실행될 수 있는 태스크의 갯수도 N개이다.된다.

실행된 태스크의 상태 전이

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

1. TASK_DEAD
   1. 태스크가 자신이 해야 할 일을 모두 끝내고 exit()를 호출하면 (혹은 kill이 되면) TASK_DEAD 상태로 전이된다. 구체적으로는 task_struct 구조체 내에 존재하는 exit_state 값과 조합해 TASK_DEAD(EXIT_ZOMBIE) 상태로 전이된다.
2. TASK_RUNNING(ready)
    수행되던 태스크(TASK_RUNNING(running)상태의 태스크)가
   1. 할당된 CPU시간을 모두 사용
   2. 보다 높은 우선순위를 가지는 태스크로 인해

TASK_RUNNING(ready)) 상태로 전이되는 경우이다.

 리눅스는 여러 태스크들이 CPU를 공평하게 사용할 수 있도록 해주기 위해 일반 태스크의 경우에는 CFS(Completely Fair Scheduling) 기법을 사용한다.

1. TASK_STOPPED / TASK_TRACED
    
   1. SIGSTOP, SIGTSTP, SIGTTIN, SIGTTOU 등의 시그널을 받은 태스크는 TASK_STOPPED 상태로 전이된다. 추후 SIGCONT 시그널을 받으면 다시 TASK_RUNNING(ready) 상태로 전환된다.
   2. 디버거의 ptrace() 호출에 의해 디버깅 되고 있는 태스크는 시그널을 받는 경우 TASK_TRACED 상태로 전이될 수 있다.

 

Q. p72. 그림 상 태스크를 Kill 하는 명령을 날리면 Task running 상태로 변하는 것처럼 나오는데 running 상태인가 dead 상태로 바뀌는가?

    A. 클린업하는 동작을 위해 스케줄링(Task running)이 되어야 하고, 그 이후에 dead 로 빠지는 것 같다.

Q. 상태를 정의하는 근본 적인 이유, 스케줄링 알고리즘을 통일되게 가져가기 위함인지, 상태정의의 구분을 짓는 이유는 어떤것이 있을까? 

    A. CPU 처리해야할 동작을 원활하게 하기 위해? 처리해야할 양이 많아지니, TASK 별 자원 사용의 효율을 높이기 위해?

    B. 70page 1문단 - 보다 높은 시스템 활용률을 제공하기 위하여.

Q. 컴파일러나 커널이나 등등 스테이트를 안나누는 대안이 있는가?

    A. 높은 시스템 활용율이 관건인데, 더 봐야 할 것은 wait 상태가 있어야 함일 것이다. IO 작업을 하면서 CPU는 원래 stop, 이때마저 실행시키기 위해서 wait 과 running 을 만들다 보니 상태를 만들어 관리하는 것이 아닌가.

    B. 상태를 관리하지 않는다면 프로세스가 스스로 상태를 Manage 하는 방식을 생각할 수 있을 텐데, 자기 자신이 OS에 자원을 반환하는 방식. But OS는 중앙집중식 리소스 매니징을 채택했고, 그에 따라 상태를 관리하지 않는 것은 불가능 하지 않나? 라는 생각임.

 

Q. 임베디드에서도 상태 관리가 필요 한가?

    A. 임베디드의 센싱 프로세스가 STOP으로 변하는 경우가 있다. 이럴 때 별도의 Back Ground 프로세스를 돌리는식으로 관리하기에 임베디드에서도 상태 관리가 필요하다.

    B. 가상메모리 VFS를 사용하는 이유가 제한된 리소스를 가지고 시스템을 잘 활용해보자는 취지일 것이다. 리소스를 최대한 효율적으로 관리하는 취지에서 라면 p70과 정확히 동일하진 않겠지만, 비슷한 모델로써 관리를 할 것이다.

 

Q. 커널 수준에서 무한루프를 도는 태스크 관리   

    A. 무한루프 태스크는 (어중간한 priority를 가진 프로세스) 커널단에서 인터럽트를 걸어 종료 시킴

 

Q. 커널 수준 실행 상태는 어떤 수준을 실행하는 것인지 자세한 예시가 있는가?

    A. 리소스 자체에 차이가 있음. 사용자 수준에서 바꿀 수 없는 레지스터 등, 

    B. 간단히 printf를 유저 모드에서 실행하면, printf 실행 시점에 system call에 의해 커널로 주도권이 넘어가 printf 라이브러리의 커널 코드를 실행하고, 이를 완료하면 다시 유저 모드로 이동하는데, 방금 말씀하신 부분의 예 정도로 볼 수 있을것 같네요.

 

 

 

 

7. 런 큐와 스케줄링

 

7-1 런 큐와 태스크

 

Q. 실시간 테스크란, 사용자 레벨에서 

    A. 반응성이 매우 중요한 테스크

        https://man7.org/linux/man-pages/man7/sched.7.html

 

 

Q. rt_priority 를 사용자 레벨에서 지정할 수 있는가?

    A. 커널이 rt 프로세스를 돌릴 수 있는 케파가 된다면 돌리고, 그렇지 않다면 reject 한다.

 

 

Q. 우선순위 단계가 0~139 총 140여 단계  어떻게 단계를 시스템 콜로 줄 수 있는가?
    A. sched_setscheduler()
    B. https://man7.org/linux/man-pages/man7/sched.7.html
    C. 82p 자료구조

 

Q. p.78 NUMA 구조의 시스템에서는 load_balance() 함수에서 CPU부하 뿐만 아니라 메모리 접근 시간의 차이 등도 고려하여 규하 분등을 시도 한다는데, 메모리 접근 시간 등을 고려한다는 것은 어떤 의미인가?

    A. Cache 와 Memery(RAM) 둘다 고려 (?)

    B. MAC 도 NUMA 형태인데, 모든 CPU가 모든 메모리를 접근하는 것은 아니고, 자신과 더 가깝게 붙어있는 메모리를 우선적으로 접근하도록 퍼포먼스를 향상 시키고 있다.

    C. 서버 컴퓨터에서 CPU는 두개 정도 가지는데, 테스트 결과 CPU에 따라 최단 시간에 메모리를 엑세스할 수 있는 시간이 다름. (결국 물리적 거리)

    D. 코어 마다 담당하는 RAM BANK 가 다름, 코어 별로 접근하는 물리적인 BANK 가 다르므로 종합적으로 고려.

 

 

Q. 방금 말씀하신 부분은 NUMA의 경우 CPU 그룹당 메모리 버스가 따로 연결되어 있다는 의미일까요?

(참고링크입니다. https://gamedoridori.tistory.com/202)

링크를 확인해보니 NUMA의 경우 CPU당 메모리가 1대1 할당된것으로 보입니다.

-> 최근 x86 CPU들의 경우, 메모리 컨트롤러가 CPU 내에 존재합니다. 

 

Q. 75p 7-1 런큐와 태스크 - 수행 가능한 상태의 태스크를 자료구조를 통해 관리한다에서 수행 가능한의 기준이 궁금합니다 좀비 프로세스 같은 애들은 제외인가 생각드네요.

    A. 사용자 영역에서 돌릴때 바로 돌아갈 수 있는 상태. TASK_RUNNING(ready)
    B.Task_Running(ready)는 새로 생성된 Task(fork())와 스케쥴링에 의해 대기 상태로 된 Task(preempt)를 말하는 것 같습니다.

 

Q. 태스크들의 우선순위 (0~140) 값이 결정되면 실시간 혹은 일반 태스크로 분류되는 것인지, 실시간 혹은 일반 태스크인지 결정되어야 우선 순위 값이 결정되는 것인지 헷갈립니다.
    A. 실시간으로 처래해야 하는 태스크인지 아닌지 프로그래머(혹은 사용자)가 결정을 해야합니다.

 

Q. p77 - tasklist -> 런 큐 로 가는 과정이 있고, 런 큐 내에서 작업 순위를 정해 실행되는 과정이 있는 것으로 이해됩니다. 후자의 경우 스케줄러가 수행되면 테스크를 골라내는 것 (77p) 로 나와있는데, 전자는 태스크가 스스로 판단하여 런 큐를 결정하는 것 일까요? 정리하면, 후자는 '스케줄러' 라는 것으로 수동적으로 작업되는 것 같고, 전자는 결정을 해주는 것이 내부 함수 인 것 같아서요 -> 런 큐에서는 스케줄러로 결정하는 것 같았는데, tasklist 에서 런 큐로 가는 과정은 누가 결정하지?

    A. 태스크 스스로가 런 큐에는 못들어갈겁니다. 다른 프로세스나 인터럽트, 혹은 커널이 깨워주기때문에

    B. 커널 코드 상 수행. 정확하게 스케줄러라고 단정 지을 수 있는지 의문.

 

7-2 실시간 태스크 스케줄링 

 

Q. 테스크가 2개가 있고, 같은 우선순위, 하나는 FIFO나 RR 의 Policy 를 가지고 있고 하나는 Deadline 으로 policy를 가지고 있을 때 두개중 어떤 것을 먼저 실행?

    A. Deadline Policy 를 가진 태스크는 Priority 는 Negative Priority 값을 가져 가장 높은 우선 순위를 가짐.

 

Q-1 Deadline 을 가지는 프로세스이면 시간복잡도가 worst case인가?
    A. https://lwn.net/Articles/743740/  조금 전에 말씀드린 링크입니다. example에서 worst case time으로 runtime을 세팅했는데, “이렇게 해야 한다”라고 권장한다고 까진 보기 어렵지 않을까 싶습니다

 

 

Q. 79페이지 중간.. 

1. 실시간 태스크를 생성하는 것은 스케줄링 정책을 SCHED_FIFO, SCHED_RR, SCHED_DEADLINE 중 하나로 바꾸게 되면 실시간 태스크가 되는 것이다 라고 되어 있는데..

    A. 일반 태스크의 스케줄링 정책을 바꾸면 실시간 태스크가 되는 것임.

2. 실시간 정책을 사용하는 태스크는 고정 우선순위를 가지게 된다고 되어 있는데..

    A.→ 우선 순위는 변경되지 않는 것일까요?

 

 

Q. 기존 스케쥴러에서 태스크가 증가함에 따라 스케쥴링에 소모되는 시간 예측을 할 수 없기때문에, 비트맵을 사용하여 해결했다고 했는데 자세한 부분에 대한 자세한 설명 

    A. 

 

 

7-3 일반 태스크 스케줄링 (CFS)

 

Q. 82p 사용시간이 1:1로 같다의 의미가 Round Robin을 의미하는 것인가?
    A. 공평하다의 의미이지 RR을 말하지는 않는다고 생각

    B. 기아상태 방지, 일반 테스크도 RR로 할 수 있으나, 우선순위 개념이 사라지게 된다. 우선순위 까지 고려하면서 모든 태스크들이 적절하게 time slice 를 받을 수 있게 한다는 개념이 아닐까?

    C. application level 에서의 스케줄링

 

 

Q. 그림 3.24 에 대한 개괄적인 설명

    A. 테스크는 동적으로 스케줄 정책에 따라 적절한 sched_class 를 가리키게 할 수 있는데, 그것을 표현한 그림

    B. C++ 의 인터페이스, implementation 만 변경하면 되기에, 사용하는 쪽에서 코드가 변경될 필요가 없음

 

 

Q. 왜 “Completely Fair” 인가?

    A.  "80% of CFS's design can be summed up in a single sentence: CFS basically models an 'ideal, precise multi-tasking CPU' on real hardware."

CFS 알고리즘에 엄청난 자신감을 가지고 “Completely” 라는 prefix 를 붙였나 봅니다

• https://web.archive.org/web/20120207010702/http://kerneltrap.org/node/11737

    B. 실시간 태스크 같은 경우 우선순위가 높은 태스크가 끝나고 낮은 태스크가 실행됩니다.

 

예를 들어 아래의 두개의 태스크

/////////////////////////////////////

// A 테스크 

while(1){

printf("A Task\n");

}

 

 

/////////////////////////////////////

// B 테스크

while(1){

printf("B Task\n");

}

/////////////////////////////////////

---------------------------------------------------------- 

스케줄러 REAL TIME  A(우선순위 1), B(우선순위 2) - cpu 1개

일경우

 

A Task

A Task

...

이 출력되고 영원히 B Task는 실행되지 않습니다.

 

----------------------------------------------------------

스케줄러 CFS  A(우선순위 100), B(우선순위 110) - cpu 1개

일경우

 

A Task

A Task

B Task

A Task

A Task

B Task

...

 

이런식으로 그래도 A와 B가 동시에 실행됩니다.

물론 A태스크가 높은 우선순위가 있어서 A가 더 많이 실행됩니다.

    C. 이전에는 너무 어둠의 시대여서 priority가 높은 task들이 마음만 먹으면 resource를 다 잡기가 쉬웠나 봅니다. 저렇게 강력한 워딩을 쓰기도 쉽지 않은데 그러면 보통 까일 일만 있으니ㅋㅋ 근데 대단하네요. 참고로, 저런 강력한 워딩이 실제로 까이지 않고 대다수에게 respect 되었던 건 diffie hellman key exchange 제안하는 “New Directions in Cryptography” paper 하나가 생각나는데, 그런 느낌이 나게 하네요

    D. 제 생각에는 여기에서 '공평한' 스케줄링이라는 의미가 우선순위가 높다면 그만큼 실행시간을 길게 가져가게 해준다는 의미인 것 같습니다. 우선순위를 반영하는 것이 공평하다고 생각할 수 있으니까요. 그래서 책에서 '보통은'(우선순위를 반영하지않는 상황) CPU 사용시간을 의미한다라고 표현한 것 같아요. 또 완벽한을 앞에 붙인 이유는 vruntime 개념을 도입해서 기아현상도 발생하지 않게 한다는 의미이지 않을까 싶습니다.

 

 

8. 문맥교환

 

Q1. 멀티코어 SMP 환경에서 일반적으로 문맥교환 발생 방식은 어떤것인지..궁금합니다.

Q2. 스케쥴링에 관련해서 Context Switcing . Arm 계열에서 context switching / 스케쥴러 컨텍스트 스위칭과 매칭되나? / 3.27 과 같이 TASK 가 두개가 아닌 상황이 많을 것인데, 그런 경우 문맥교환은 어떻게 연결 되는가.

• Arm 컨텍스트의 경우 특정 register (special register) 에 저장해서 스위칭을 하는데, 여러 TASK 가 있을 때 어떻게 동작할 것인가 가 궁금.

    A. 그림 3.27과 다르지 않을 것, 이미 CPU가 돌리고 있던 TASK, 다음 TASK, 그 다음 TASK 등등 이 있을 것인데, 그림 3.27 과의 TASK A, TASK B 의 경우처럼 단건으로 생각하면 되지 않을까?

 

 

Q. 결국 task 마다 stack이 존재하니, 콘텍스트 스위치 전 스위치 off되는 task의 stack에 task 콘텍스트를 저장하고 복구 될 때 다시 저장된 task의 stack에서 기존 콘텍스트 값을 복구한다고 보면 되겠네요.

    A. 가상 메모리상 커널 스페이스 영역에 컨텍스트 Push, 다시 커널 스페이스에서 Restore. 등 질문 내용으로 일반화 하긴 어렵다.

 

 

9. 태스크와 시그널

 

Q. 전반적인 동작 원리

    A. 시그널을 받을 경우 커널이 User용 Space에서 시그널 프레임을 새로 만듬 ( 마치 Multi-thread) , 종료가 되면 Signal return ( Instruction ) 이후  다시 User 에게 돌려줌 

• Signal Safe 함수 참고
• http://egloos.zum.com/studyfoss/v/5182475
  • signal handler 실행 과정에 대해 자세히 설명되어 있음.

 

Q. Signal Safe에서 안전하다의 의미 ?

    A. 시그널 핸들러는 하나의 스케줄링 단위에 있다보니, 스케줄링 Out 상황에서, 시그널 핸들러가 여전히 Lock 을 잡아버리려고 한다. 

시그널 핸들러에서 Call 하면 Dead Lock 이 걸리거나, 예상치 못한 동작이 발생하는 경우 시그널 핸들러에서 call 하면 안되게 해야한다.

즉, 시그널 세이프티한 함수들만 호출해야한다.
아래 man 7 signal-safety 참고

• https://man7.org/linux/man-pages/man7/signal-safety.7.html
• http://egloos.zum.com/bigs/v/6038172 

 

Chater 4

 

2. 물리 메모리 관리 자료 구조

 

Q. ISA 버스 기반 디바이스 란

 

 

Q. p.97 왜 “Bank” 인가, 이름의 유래

 

 

 

공유내용.

 

(강준원님 공유 내용)Deadline 테스크를 고려할때 deadline, runtime, period 를 할때 worst case를 고려하여 줄 것

https://lwn.net/Articles/743740/

조금 전에 말씀드린 링크입니다. example에서 worst case time으로 runtime을 세팅했는데, “이렇게 해야 한다”라고 권장한다고 까진 보기 어렵지 않을까 싶습니다.

 

 

(이경재님 공유 내용) ARM Cortex-M4 기반 RTOS 환경에서의 컨택스트 스위칭 로직 간단 예시:

// 태스크 스위칭 OUT

1. 현재 실행중이던 태스크의 컨택스트 (16개 레지스터)를 해당 태스크의 스택에 push!

2. Push 이후 최종 업데이트 된 stack pointer를 저장. (sp 저장 위치는 디자인에 따라 다르겠지만 저의 경우 해당 태스크 TCB에 하도록 했었습니다.)

 

// 태스크 스위칭 IN

1. 선택 된 태스크의 stack pointer를 먼저 복구

2. 복구 된 stack pointer를 이용하여 해당 태스크의 스택에 저장되어있던 컨택스트 (16개 레지스터)를 프로세서 코어 레지스터들에 복구 (pop!)