[Kernel 2.6]프로세스 스케쥴링

Programming/Linux 2009. 9. 22. 09:35
프로세스란?
프로그램이 움직이고 있는 상태를 뜻하며, 각 프로세스는 콘텍스트를 가진다. 콘텍스트란 프로세스가 동작하기 위한 프로세스 공간과 프로세스가 동작할 때의 레지스터 값 등을 말한다. 이 정보는 task_struct 구조체로 관리. 리눅스 커널에서는 스레드도 일종의 프로세스로 관리하고, 복수의 스레드는 동일한 프로세스 공간을 공유한다.

프로세스 전환( Process Switch )
/ 프로세스 디스패치( Process Dispatch )

: 스케쥴러가 CPU 상에 동작 하고 있던 프로세스의 실행을 중단하고, 새로운 프로세스에 실행 권한을 주는 처리

프로세스 디스패처( Process Dispatcher )
: 프로세스 전환을 수행하는 기능

프로세스 스케쥴러 는 언제 어느 프로세스에 실행 권한을 줄 것인지 판단하고, 프로세스 디스패처에 전환을 요청하면, 디스패처는 지정된 프로세스에 실행 권한을 준다.


스케쥴링

우선순위의 지표
프로세스는 실행우선 순위를 판가름 할 때, nice 명령으로 지정하는 고정 우선순위 외에 동적 우선 순위를 갖는다. 고정 우선순위는 nice 값으로 결정된다. 고정 우선순위와 동적 우선순위가 가장 큰 프로세스에 실행 권한을 준다. CPU를 보다 많이 이용한 프로세스는 낮은 동적 우선순위를 가지게 되고, 쉘과 같은 대화형 프로세스는 그다지 CPU를 이용하지 않기 때문에 상대적으로 높은 동적 우선순위를 할당 할 수 있게 됩니다. 프로세스 A가 실행 되고 있는 중에 대화형 프로세스 B가 실행 될 경우 B가 A보다 우선 순위가 높다고 판단되면 디스패처를 호출하여 선점( Preempt,l 실행 중인 프로세스의 실행 권한을 빼앗아 옴 ) 을 한다. 이러한 선점 방식을 이용하여 리눅스 커널은 응답성을 확보한다.

실행 보증
실행 가능 상태의 프로세스에 실행 할당 시간( Time Slice ) 를 준다. 실행 할당 시간이 남아 있는 동안에는 프로세스는 실행권한을 계속 가질 수 있으며, Time Slice 를 모두 사용하면 다른 프로세스에 실행 권한을 건네어 준다. 리눅스 커널 상에 Time Slice 가 남아 있는 실행 대기 프로세스가 하나도 남아 있지 않을 경우 새롭게 프로세스들에 Time Slice 를 할당해 준다.
TIme Slice 는 고정 우선순위를 기본으로 계산한다. 고정 우선순위가 높은 프로세스는 실행 시간이 약간 길게 할당되어 다른 프로세스에 비해 실행 권한을 잡을 수 있는 기회가 늘어난다. Timer 에 의해 Time Slice를 줄여가고, Time Slice가 없어지면 스케쥴러에 재스케쥴링을 요구한다.

스케쥴링 계기
첫 번째는, 어떤 이벤트를 만나기 위해 대기 상태로 이동 했을 때 스케쥴링을 한다. 이는 File 읽기 처리를 수행하는 프로세스가 있을 경우, 디스크 입출력을 요청한 후, 완료 될 때 까지 이를 대기한다.
두 번째는, 명시적으로 다른 프로세스에 실행 권한을 양보하는 경우이다. 매우 긴 커널 처리가 요구 될 때, 응답성에 악영향을 주지 않도록 스스로 실행 권한을 양보한다.
세 번째는, 선점을 하는 경우이다. 새로운 프로세스가 현재 실행 중인 프로세스 보다 우선 순위가 높으면 재 스케쥴링을 요청한다. 하지만, 실제로 요청 즉시 스케줄링이 일어나지 않고, 커널이 수행해야 할 처리가 완료 될 때 까지 스케줄러의 실행은 지연된다
네 번째는, Time Slice를 모두 소비한 경우.

TLB
: 가상 주소를 물리 주소로 빠르게 변환하기 위한 캐시. CPU는 주소 변환을 수행하기 위해 페이지 테이블 등의 메모리의 저장된 데이터 구조를 추적하여 실제 주소를 구한다. 그러나 이때 엄청난 부하가 걸린다. 그래서 최근에 이용된 주소 변환 정보는 TLB 영역에 캐시해 둔다. 즉, 프로세스 공간에 대한 TLB 정보를 재사용하려면 프로세스를 재스케줄링할 때 동일한 CPU에서 실행하는 것이 유리하다.

실행 큐
: 리눅스 커널 2.6 에서는 O(1) 스케줄링 을 기법을 수행한다. 2종류의 실행 큐가 있는데, active 와 expired 실행 큐 라고 부르며, active 큐에는 실행 가능한 프로세스( Time Slice 를 가지고 있는 프로세스 ), expired 큐에는 실행 가능한 상태지만, Time Slice 를 모두 써 버런 프로세스를 등록한다. active 와 expired 큐는 동일한 구조이고, active 큐에서 프로세스가 Time Slice 를 모두 소비하면 Expired 로 이동하거나 event 를 기다리기 위해 대기 상태로 이동한다. active 큐에 모든 프로세스가 없어지게 되면, 포인트 주소를 바꿔주어 active와 expired 큐를 교환해 준다.
멀티프로세서 시스템에서는 실행큐를 CPU별로 준비를 해준다. 실행 큐 간의 부하 상태가 한 쪽으로 너무 치우치게 되었을 때는 실행 큐 간의 실행 대기 프로세스를 이동시켜 밸런스를 취한다.

아이들( idle ) 프로세스
: 실행 가능한 프로세스가 하나도 존재 하지않을 때, 스케줄러 자체가 Idle 상태가 되는 OS도 있지만, 리눅스 커널에서는 아무것도 실행 하지 않는 Idle Process 를 준비하여, 이에 실행 권한을 부여한다. Idle Process 는 아무 것도 하지 않고 실행 가능한 프로세스가 나타나 선점될 때 까지 계속 기다린다.
Idle Proce는 각 CPU 별로 하나씩 있다. Idle Process 는 실행 큐에는 등록되지 않고, 실행 큐 상에 실행 가능한 프로세스가 하나도 존재하지 않게 되었을 때에만 실행 대상으로 선택된다.

wake_up 함수 집합
: 대기 상태 프로세스를 실행 큐에 등록하고, 프로세스 상태를 TASK_RUNNING 으로 변경한다.


CFS Scheduler (Completely Fair Scheduler)

리눅스 스케줄러는 커널 2.6부터 O(1) 스케줄러가 사용되고 있으며, O(1) 스케줄러 의 단점은 각각의 태스크는 기본적으로 100ms의 time slice를 가지게 되므로 보통 100ms마다 Context Swti이 일어납니다. 하지만 만약 우선순위가 19(nice값이 19)인 태스크라면 각각의 태스크는 기본적으로 5ms의 time slice를 할당받기 때문에 5ms마다 문맥전환이 일어나는 비효율성이 유발됩니다. 또한 우선순위 0과 1의 사용자 태스크는 각각 100ms와 95ms의 time slice를 할당 받는 반면 우선순위 18과 19의 태스크는 각각 10ms와 5ms의 time slice를 할당 받게 되므로 한 단계의 우선순위 차이로 인해 두 배의 할당 시간 차이가 생긴다. 또한 새로운 태스크가 계속 생기는 경우 expired 배열에 들어가있는 태스크의 평균 대기시간이 길어질 수 있는 문제점이 제기되어 최근 2.6.23버전부터는 CFS 스케줄러가 도입되었다.
CFS는 SCHED_NORMAL, SCHED_BATCH, SCHED_IDLE 세 가지의 정책을 지원합니다. 태스크의 입장에서 본다면 이제 더 이상 SCHED_OTHER 스케줄링 정잭은 존재하지 않으며 대신 CFS 모듈이
제공하는 SCHED_NORMAL, SCHED_BATCH, SCHED_IDLE 세 가지의 정책과, 실시간 스케줄링 모듈이 제공하는 SCHED_RR과 SCHED_FIFO 정책을 사용하는 것이 가능하다. CFS를 위한 런 큐를 살펴보면, struct cfs_rq라는 자료구조와 struct rt_rq라는 이름의 자료구조를 담고 있다. struct_rt_rq를 보면 알 수 있듯이 실시간 스케줄링 기법은 기존과 마찬가지로 비트맵을 이용한 우선순위 기반 스케줄링을 하고 있음을 알 수 있다. 한편 비 실시간 태스크는 struct cfs_rq 자료구조로 관리된다. struct cfs_rq 자료구조에서 태스크들은 rb_node라는 필드로 관리됩니다. 이 자료구조로부터 우리는 CFS 스케줄러가 레드-블랙 트리(Red-Black Tree)를 이용하여 태스크를 관리하고 있음을 확인할 수 있다. 이 기법은 기존 O(1) 스케줄러와 달리 우선순위 배열을 유지하지 않는다. 대신 우선순위를 고려한 가중치를 통해 태스크별로 키(key)값을 정하고, 이 키 값을 이용하여 태스크를 레드-블랙 트리로 유지한다. 이 트리에서 가장 좌측에 존재하는 태스크가 다음번 스케줄링의 대상이 된다(rb_left_most 필드). 스케줄링 된 태스크는 수행 될수록 키 값이 증가되며 따라서 트리의 가장 좌측에서 점차 우측으로 이동된다. 반면 스케줄링 되지 않은 태스크는 대기하는 동안 점점 자신의 키 값이(상대적으로) 감소되며 따라서 점차 트리의 좌측으로 이동하게 된다.


자식 프로세스의 스케줄링
: 자식 프로세스가 먼저 수행된다. 이유는 COW( Copy-on-Write ) 가 필요한지 불필요 한지 여부에 따라 필요시에 COW를 수행해야 하기 때문이다. 만약, 부모 프로세스가 먼저 수행을 하게 되면, 자시그 프로세스가 COW 가 필요한지 알 수 없기 때문에 COW를 불필요할 경우에도 수행해야 한다. COW 는 말 그대로 쓸때 복사한다는 의미로, 자식 프로세스가 부모 프로세스의 메모리 영역을 참조하는 경우 변경이 일어 나기 전까지는 동일한 메모리 페이지를 참조 할수 있도록 공유하는 것이다.
COW 에 대한 자세한 설명은 여기에 설명 되어 있다.  http://en.wikipedia.org/wiki/Copy-on-write

'Programming > Linux' 카테고리의 다른 글

기본 명령어  (0) 2009.10.08
리눅스란?  (0) 2009.10.08
명령어( 폴더, 파일 관련 )  (0) 2009.09.19
디버깅  (0) 2009.09.19
Vi 편집기  (0) 2009.09.19

설정

트랙백

댓글

명령어( 폴더, 파일 관련 )

Programming/Linux 2009. 9. 19. 01:12
mkdir 디렉토리명
디렉토리 만들기

rm 파일명
파일을 삭제

rm -r 디렉토리명
디렉토리와 그 하위 디렉토리 및 파일을 모두 삭제
만약, 삭제할 때 삭제할 것이냐고 계속 묻는다면 -f 옵션을 준다.

'Programming > Linux' 카테고리의 다른 글

리눅스란?  (0) 2009.10.08
[Kernel 2.6]프로세스 스케쥴링  (0) 2009.09.22
디버깅  (0) 2009.09.19
Vi 편집기  (0) 2009.09.19
Virtual Box 게스트 확장 설치  (0) 2009.09.15

설정

트랙백

댓글

디버깅

Programming/Linux 2009. 9. 19. 00:57

디버깅을 위해 먼저 컴파일 할 때 디버깅 정보를 포함하도록 컴파일을 한다.

gcc -g file1.c file2.c -o run 을 하면 run 에 디버깅 정보가 포함되어 있다.

gdb run 을 수행하면 디버깅을 시작하게 된다. 그리고 난 뒤에는 아래에 있는 디버깅 명령어를 사용해서 디버깅을 하도록 한다.

- break

break 숫자 : break 포인터를 해당 줄에 지정


- next( n )
한줄 씩 수행 가능 - 함수 안으로 들어가지 않음


- step ( s )
한줄 씩 수행 가능 - 함수 안으로 들어감


- continue
디버깅 중에 프로그램을 계속 수행 가능


- info breakpoints

브레이크 포인터가 설정된 곳의 위치를 보여줌


- delete

delete + 숫자 : 해당 줄의 브레이크 포인터를 삭제


- list

list 
실행하고 있는 부분의 소스를 출력

list + 숫자 
특정 줄의 소스를 출력

list + 함수이름
특정 함수의 소스코드를 출력



'Programming > Linux' 카테고리의 다른 글

[Kernel 2.6]프로세스 스케쥴링  (0) 2009.09.22
명령어( 폴더, 파일 관련 )  (0) 2009.09.19
Vi 편집기  (0) 2009.09.19
Virtual Box 게스트 확장 설치  (0) 2009.09.15
vi / vim 단축키 모음  (0) 2009.09.10

설정

트랙백

댓글

Vi 편집기

Programming/Linux 2009. 9. 19. 00:03
블록을 지정해서 잘라내서 붙이기

1. 명령모드에서 v를 입력하여 비쥬얼 모드로 변경
2. 이동 버튼으로 블록을 지정
3. d 를 입력 하면 내용이 잘라지고,  p를 입력하면 붙여진다.

'Programming > Linux' 카테고리의 다른 글

명령어( 폴더, 파일 관련 )  (0) 2009.09.19
디버깅  (0) 2009.09.19
Virtual Box 게스트 확장 설치  (0) 2009.09.15
vi / vim 단축키 모음  (0) 2009.09.10
리눅스  (0) 2009.03.25

설정

트랙백

댓글

Virtual Box 게스트 확장 설치

Programming/Linux 2009. 9. 15. 22:18

Virtual Box 에서 게스트 확장 을 설치 하여야 해상도를 늘릴 수 있다.


"장치 - 게스트 확장 설치" 를 클릭하면, 위의 화면과 같이 시디 이미지 파일이 생성 되는 것을 알수 있다.


터미널 창에서 VBoxLinuxAdditions-x86.run 파일을 실행하면 설치가 된다.
( 루트 권한으로 가능하다 )

그리고 재부팅을 하고 나면 아래와 같이 해상도가 증가하여 화면에 꽉 찬 것을 볼 수 있을 것이다.



'Programming > Linux' 카테고리의 다른 글

디버깅  (0) 2009.09.19
Vi 편집기  (0) 2009.09.19
vi / vim 단축키 모음  (0) 2009.09.10
리눅스  (0) 2009.03.25
1. Red Hat Linux 5 - basic instructions ①  (0) 2009.03.23

설정

트랙백

댓글

vi / vim 단축키 모음

Programming/Linux 2009. 9. 10. 03:58

'Programming > Linux' 카테고리의 다른 글

Vi 편집기  (0) 2009.09.19
Virtual Box 게스트 확장 설치  (0) 2009.09.15
리눅스  (0) 2009.03.25
1. Red Hat Linux 5 - basic instructions ①  (0) 2009.03.23
1. Red Hat Linux 5 - basic instructions ①  (0) 2009.03.23

설정

트랙백

댓글

리눅스

Programming/Linux 2009. 3. 25. 12:10

'Programming > Linux' 카테고리의 다른 글

Vi 편집기  (0) 2009.09.19
Virtual Box 게스트 확장 설치  (0) 2009.09.15
vi / vim 단축키 모음  (0) 2009.09.10
1. Red Hat Linux 5 - basic instructions ①  (0) 2009.03.23
1. Red Hat Linux 5 - basic instructions ①  (0) 2009.03.23

설정

트랙백

댓글

1. Red Hat Linux 5 - basic instructions ①

Programming/Linux 2009. 3. 23. 18:01
User Identification confirmation

whoami - to confirm login account

su - It means 'substitue user'. It's used to change another user ID, not to login,to use another new shell. Commonly it's used to change root account for a moment to do management work. then return to the previous login account.

passwd <ID>- used to change password.

File, Directory
ls [directory] [option]- Show Files and directories list.
  -l : Show specific info of files.
  -a : Show all files,regardless of the type of files.

mv <original filename> <new filename>: move or rename files.

chmod( permission ) <permission option> <objective file>
 
d rwx rwx rwx : The first character is either directory or file. 'd' means directory, '-'
                           means file. The first "rwx" is the authority of an owner. The second one 
                           is the authority of a group. The final one is the authority of other users.
   To give an authority 
      1) rwx(421) add the number. - give owner, all groups, all users an authority.
              read + write + execution 7, read + write 6,
              read + execution 5,  read 4, write + execution 3, write 2, execution 1
      2) a( all ), u( user ), g( groups ), o( other ) / r( read ), w( write ), x( execution )
          + ( add permission ), - ( remove permission )
        ex ) chmod 777 redhat -> Give all owners, groups, users all authorities.
               chmod u+x redhat -> Give owner execution autority.

Link
ln -s <object of link> <filename of link> : object can be file or directory.
  ex ) ln -s a b : Make b link to point at a file or directory.
         cd b : Enter a which a point at



'Programming > Linux' 카테고리의 다른 글

Vi 편집기  (0) 2009.09.19
Virtual Box 게스트 확장 설치  (0) 2009.09.15
vi / vim 단축키 모음  (0) 2009.09.10
리눅스  (0) 2009.03.25
1. Red Hat Linux 5 - basic instructions ①  (0) 2009.03.23

설정

트랙백

댓글

1. Red Hat Linux 5 - basic instructions ①

Programming/Linux 2009. 3. 23. 08:13
User Identification confirmation

whoami - to confirm login account

su - It means 'substitue user'. It's used to change another user ID, not to login,to use another new shell. Commonly it's used to change root account for a moment to do management work. then return to the previous login account.

passwd <ID>- used to change password.

File, Directory
ls [directory] [option]- Show Files and directories list.
  -l : Show specific info of files.
  -a : Show all files,regardless of the type of files.

mv <original filename> <new filename>: move or rename files.

chmod( permission ) <permission option> <objective file>
 
d rwx rwx rwx : The first character is either directory or file. 'd' means directory, '-'
                           means file. The first "rwx" is the authority of an owner. The second one 
                           is the authority of a group. The final one is the authority of other users.
   To give an authority 
      1) rwx(421) add the number. - give owner, all groups, all users an authority.
              read + write + execution 7, read + write 6,
              read + execution 5,  read 4, write + execution 3, write 2, execution 1
      2) a( all ), u( user ), g( groups ), o( other ) / r( read ), w( write ), x( execution )
          + ( add permission ), - ( remove permission )
        ex ) chmod 777 redhat -> Give all owners, groups, users all authorities.
               chmod u+x redhat -> Give owner execution autority.

Link
ln -s <object of link> <filename of link> : object can be file or directory.
  ex ) ln -s a b : Make b link to point at a file or directory.
         cd b : Enter a which a point at



'Programming > Linux' 카테고리의 다른 글

Vi 편집기  (0) 2009.09.19
Virtual Box 게스트 확장 설치  (0) 2009.09.15
vi / vim 단축키 모음  (0) 2009.09.10
리눅스  (0) 2009.03.25
1. Red Hat Linux 5 - basic instructions ①  (0) 2009.03.23

설정

트랙백

댓글