Data Science Lab

32_가상 메모리(Virtual Memory)

가상 메모리(Virtual Memory)는 프로세스 전체가 메모리에 올라와 있지 않아도 실행이 가능하도록 하는 기법이다. 주요 장점중의 하나는 프로그램이 물리 메모리보다 커도 된다는 것이다. 가상 메모리는 물리 메모리로부터 사용자 관점의 논리 메모리를 분리시켜 주 메모리를 균일한 크기의 저장공간으로 구성된 큰 배열로 추상화 시켜 준다. 또한 파일 공유를 쉽게 해주고 공유 메모리 구현을 가능하게 한다. 단점으로는 구현이 어렵고 잘못 사용하게 된다면 성능이 현저히 저하될 수 있다.

한 프로세스의 가상 주고 공간은 그 프로세스가 메모리에 저장되는 논리적인(또는 가상적인) 모습(View)을 말한다. 일반적으로 특정 논리 주소에서(보통 0번지)시작하여 연속적인 공간을 차지 한다. 물리 메모리는 페이지 프레임들로 구성되며 프로세스에 할당된 페이지 프레임들이 실제적으로 연속적인 것들이 아닐 수 있다. 물리적인 페이지 프레임을 논리적인 페이지로 매핑하는 것은 메모리 관리 장치(Memory Management Unit)에서 담당한다.

힙(heap)은 동적 할당 메모리를 사용함에 따라 주소 공간 상에서 위 쪽으로 확장된다. 스택은 함수 호출을 거듭함에 따라 주소 공간 아래 쪽으로 확장 된다. 힙과 스택사이의 공백도 가상 주소 공간의 일부이지만 힙 또는 스택이 확장되어야만 실제 물리 페이지를 요구하게 된다.

공백을 포함하는 가상 주소 공간을 Sparse 주소 공간이라고 한다. Sparse 주소 공간의 공백은 스택이나 힙 세그먼트가 확장될 때 사용되거나 프로그램 실행 중 동적으로 라이브러리를 링크할 필요가 있을 때 사용한다.

논리 메모리를 물리 메모리로 분리시켜 주는 것 외에 가상 메모리는 페이지 공유를 통해 파일이나 메모리가 둘 또는 그 이상의 프로세스들에 의해 공유되는 것을 가능하게 한다.

[참고자료]

Operating System Concepts / 홍릉과학출판사

31_페이지 세그먼테이션(Segmentation)

메모리 관리에서 사용자가 바라보는 메모리 관점과 실제 물리적인 메모리의 관점을 분리되어 있다는 것은 매우 중요하다. 그렇다면 사용자는 메모리를 관리할 때 어떤 관점으로 바라보아야 하는가?

세그먼테이션(segmentation)은 사용자 관점 그대로 메모리를 관리하는 기법이다. 논리 구조 공간을 세그먼테이션 집합으로 정의하고 각 세그먼트는 이름과 길이를 가진다. 시스템에서는 논리 주소가 세그먼트 이름과 세그먼트 내에서의 변위로 나누어 진다.

사용자 프로그램이 컴파일 되면 컴파일러는 자동으로 입력 프로그램을 읽어 세그먼트들을 만들어 내며 구현을 쉽게 하기 위해 세그먼트 이름 대신 세그먼트 번호가 시스템에 의해 매겨진다. 따라서 논리주소는 <segment-number, offset>으로 구성 된다.

C에서 컴파일러는 다음과 같은 세그먼트를 생성한다. 컴파일 타임에 링크되는 라이브러리는 별도의 세그먼트에 할당 되어야 한다. 적재기는 이런 세그먼트 마다 번호를 매겨준다.

1. 코드
2. 전역변수
3. 메모리 할당을 위한 힙(heap)
4. 각각의 스레드를 위한 스택(stack)
5. 표준 C 라이브러리

사용자는 세그먼트를 추가한 이차원 주소로 객체(obect)를 지정할 수 있지만 메모리는 바이트들의 일차원 구조이다. 그래서 사용자가 정의한 이차원 주소는 일차원 실제 주소로 매핑되어야 한다. 이 매핑은 시그먼트 테이블에 의해서 이루어진다.

세그먼트 테이블은 세그먼트 기준(base)과 세그먼트 한계(limit)를 가지고 있다. 세그먼트 기준은 세그먼트의 시작 주소를 나타내며 세그먼트 한계는 세그먼트의 길이를 명시 한다.

세그먼트 테이블의 논리 주소는 두 부분으로 구성 된다. 세그먼트 번호(s)와 세그먼트 내의 변위(offset, d)로 구성된다. 세그먼트 번호는 세그먼트의 색인으로 사용되며 변위(d)는 0과 세그먼트 크기 사이의 값이어야 한다. 그렇지 않을 경우 트랩이 발생 한다.

변위가 범위 안에 있으면 세그먼트 기준과 변위가 더해져서 원하는 바이트의 실제 주소가 얻어진다. 세그먼트 테이블은 기본적으로 베이스/한계 레지스터의 쌍으로 이루어진 배열이다.

• 베이스/ 한계 레지스터 : http://sqlmvp.kr/140191334564

[참고자료]

• Operating System Concepts / 홍릉과학출판사
• x86 memory segmentation : http://en.wikipedia.org/wiki/X86_memory_segmentation

30_페이지 테이블 구조 (page table structure)

현대의 컴퓨터 환경에서는 매우 큰 주소 공간을 가진다. (2^32 ~ 2^64) 이러한 환경에서는 페이지 테이블도 커진다.

예를 들어 32bit 환경에서 페이지의 크기가 4KB(2^12)이면 페이지 테이블은 100만개(2^32/2^12)로 구성되며 각 항목은 4byte로 구성되기 때문에 각 프로세스는 페이지 테이블만해도 4MB가 필요하다.

[계층적 페이지]

큰 페이지 테이블은 작은 조각으로 나누어 관리하는 것이 효율적이며 이러한 방법을 2단계 페이징 기법(two-level paging scheme)이라 한다.

2단계 페이지 기법은 페이지 자체가 다시 페이지화 되는 것으로 4KB의 크기를 가진 32bit 환경을 예로 들면 논리주소는 20bit 짜리 페이지 번호와 12bit의 페이지 변위로 이루어 진다. 그리고 페이지 테이블도 페이지로 나누어 지기 때문에 페이지 번호는 다시 10bit짜리 페이지 번호와 10bit짜리 페이지 변위로 나누어 진다.

주소 변환이 바깥에서 안쪽으로 들어오므로 이러한 방식을 포워드 매핑 (forward-mapped)페이지 테이블이라고도 부른다.

VAX 구조가 2단계 페이징을 지원한다. VAX는 페이지 크기가 512byte이고 32bit 환경이다. 프로세스의 논리 주소 공간은 동일한 4개의 영역으로 나누어지는데 각각은 2^30byte로 구성된다. 각 영역은 다른 공간 부분을 나타내며 논리 주소의 처음 2개 bit는 영역을 표시, 다음의 21bit는 그 영역에서의 페이지 번호, 마지막 9bit는 선택된 페이지 내에서의 변위를 나타낸다.

VAX에서 하나의 영역을 사용하는 프로세스의 1단계 페이지 테이블의 크기는 2^21bit * 항목당 4byte = 8MB 이다. VAX는 메인 메모리 사용량을 줄이기 위해 사용자 페이지 테이블도 페이지화 한다.

64비트 논리 주소 공간을 가진 시스템은 페이지 테이블을 페이지화 하더라도 큰 페이지를 가지고 있기 때문에 바깥 페이지 테이블을 다시 작게(3단계 페이징) 나눈다. 아니면 2번째 바깥 페이지 테이블도 페이징 시킴으로써 4단계 페이징 기법을 사용 할 수 있다.

• 3단계 페이징 사용 시스템 – SPARC 구조
• 4단계 페이징 사용 시스템 – Motorola 68030
• 7단계 페이징 사용 시스템 – UltraSPARC (논리주소 매핑에 너무 많은 메모리 접근이 발생하여 비현실적)

[해시형 페이지 테이블(Hashed Page Table)]

주소 공간이 32bit보다 크면 해시 값이 가상 페이지 번호가 되는 해시형 페이지 테이블을 많이 쓴다. 해시형 테이블의 각 항목은 연결 리스트를 가지고 있다. 해시 원소는 세 개의 필드(가상 페이지 번호, 매핑 페이지 프레임 번호, 연결 리스트 상의 다음 포인터)를 가지고 있다.

해시 알고리즘은 다음과 같은 순서로 운영 된다.

1. 가상 주소 공간으로부터 페이지 번호가 오면 그것을 해싱 한다.
2. 해시형 페이지 테이블에서 연결 리스트랄 따라가며 첫 번째 원소와 가상 페이지 번호를 비교한다.
3. 일치하면 그에 대응하는 페이지 프레임 번호(두 번째 필드)를 가져와 물리적 주소를 얻는다.
4. 일치하지 않으면 연결 리스트의 그 다음 포인터로 3의 순서를 반복한다.

해시형 페이지에서 각 항목들이 한 개의 페이지만 가리키는 대신 64bit에서는 해시 알고리즘을 약간 변경하여 클러스터형 페이지 테이블이라고 하여 각 항목들이 여러 개의 페이지를 가리킨다. 따라서 한 개의 페이지 테이블 항목이 여러 페이지 프레임에 대한 매핑 정보를 지닐 수 있다. 클러스터형 페이지 테이블은 메모리 접근이 불연속적이면서 전 주소 공간으로 넓게 퍼져 나오는 경우에 유용하다.

[역 페이지 테이블(Inverted Page Table)]

테이블은 가상 주소에 대해 오름차순으로 정렬되어 있으며 운영체제는 이 테이블에서 원하는 페이지가 어느 곳에 있는지 계산하여 접근한다. 이러한 기법의 단점으로는 페이지 테이블의 크기이다. 이러한 문제를 해결하기 위해 역 페이지 테이블(inverted page table)방법을 사용한다.

역 페이지 테이블에서는 메모리 프레임마다 한 항목씩을 할당한다. 각 항목은 프레임에 올라와 있는 페이지 주소, 그리고 그 페이지를 소유하고 있는 프로세스ID를 표시하고 있다. 이렇게 되면 시스템에는 단 하나의 페이지 테이블만이 존재하게 되고 테이블 내 각 항목은 메모리 한 프레임씩을 가리키게 된다.

역 페이지 테이블 구성 순서

• 가상 주소는 <process-id, page-number, offset> 세 가지 항목으로 구성
• 각 역 페이지 테이블의 항목은 <process-id, page-number>의 쌍으로 이루어져 있으며 process-id느 주소 공간 ID의 역할을 한다.
• 메모리 참조가 발생하면 <process-id, page-number>의 쌍으로 이루어진 가상 주소의 일부 메모리 서브시스템에 전달 된다.
• 역 페이지 테이블에서 일치하는 것이 있는지 검색 한다.
• 일치하는 것이 i 번째 항목에서 발견되면 물리 주소는 <i, offset>가 되고 일치 하는 것이 없으면 잘못된 메모리로 간주 한다.

장점으로는 논리 페이지마다 항목을 가지는 대신 물리 프레임에 대응되는 항목만 테이블에 저장하기 때문에 메모리에서 훨씬 작은 공간을 점유 한다.

단점으로는 역 페이지 테이블은 주소 변환 시간이 더 오래 걸릴 수 있으며 프레임에 따라 저장되어있어 탐색은 비효율적이다.

페이지 테이블을 해싱이 느린경우 최근에 사용된 항목들을 TLB 연관 메모리 레지스터에 저장시켜 다음 참조 시 레지스터만 검사하면서 시간을 단축 시킨다.

역 페이지 테이블을 사용하는 시스템에서 메모리의 공유는 어렵다. 페이지 테이블이 공유된 물리 주소에 대해 하나의 가상 주소를 매핑하기 때문에 매핑되지 못한 다른 가상 주소가 공유된 영역을 참조하게 되면 페이지 폴트(page fault)가 발생 한다.

[참고자료]

Operating System Concepts / 홍릉과학출판사

29_메모리 페이징(2) (Paging)

각 운영체제는 페이지 테이블을 저장하기 위한 고유의 방법을 가지고 있다. 디스패처가 어떤 프로세스를 시작 시킬 때 이 레지스터들을 다시 적재하면 페이지 테이블도 함께 사용 할 수 있게 된다.

페이지 테이블은 레지스터의 집합으로 구현되기도 한다. 메모리의 모든 액세스는 이 페이징 맵을 통해야 하므로 매핑의 효율은 매우 중요하다. 디스패처는 이들 레지스터를 채우며 운영체제가 이를 담당한다.

페이지 테이블에 레지스터를 사용하는 것은 페이지 테이블이 작은 경우 적합하다. 하지만 대부분의 컴퓨터들은 수백만 항목에 이를 만큼 매우 크다. 이러한 컴퓨터의 페이지 테이블을 구현하기 위해서 빠른 레지스터를 사용하는 것은 부적절하다.(레지스터 비용이 비싸기 때문이다.) 그래서 대부분의 컴퓨터는 페이지 테이블을 주 메모리에 저장하고 페이지 테이블 기준 레지스터(PTBR, Page-Table Base Register)로 하여금 페이지 테이블을 가리키도록 한다. 다른 페이지 테이블을 사용하려면 단지 이 레지스터만 변화시키면 되기 때문에 문맥 교환시간을 줄일 수 있다.

PTBR의 문제점은 메모리의 접근 시간이다. 원하는 주소에 접근하기 위해서는 페이지 테이블에 접근해야 하는데 요청한 번지에 접근하기 위해서는 [프레임 번호 + 페이지 변위를 통한 실제 주소 의 접근]으로 2번의 접근이 필요하기 때문이다. 이런 지연이 반복되면 너무 느리기 때문에 스와핑 방법이 유리 할 수도 있다.

PTBR의 메모리 속도 문제를 해결하기 위해 TLB(Translation Look-aside Buffer)이라 불리는 캐시가 사용된다. TLB는 매우 빠른 연관 메모리(associative memory)로 구성된다. TLB 내의 각 항목은 키(key)와 값(value)의 두 부분으로 구성 된다.

TLB는 비싸므로 페이지 테이블의 일부분 밖에 가지고 있을 수 없다. CPU에 의해 논리 주소가 생성되면 그 페이지 번호를 TLB에 제시한다. 사용하려는 페이지를 찾으면 그 프레임 번호를 알 수 있으며 메모리로 접근하는데 사용할 수 있다. 페이지 번호가 TLB에서 발견 되는 비율을 적중률(hit ratio)라 부른다. 90%의 적중률은 TLB에서 원하는 페이지 번호를 발견할 횟수가 90%라는 것을 의미한다.

일부 TLB는 각 항목에 ASID(address-space identifier)를 저장하기도 한다. ASID는 그 TLB 항목이 어느 프로세스에게 속한 것인지를 알려주며 그 프로세스의 정보를 보호하기 위해 사용된다.

페이지화된 환경에서 메모리 보호는 각 페이지에 붙어 있는 보호 비트(protection bit)에 의해 구현 된다. 이 비트들은 보통 페이지 테이블에 속해 있다. 메모리에 대한 모든 접근은 페이지 테이블을 거치므로 이때 주소의 매핑과 함께 쓰기가 허용되는지 검사도 할 수 있다. 위반 시 운영체제가 하드웨어로 트랩(메모리 보호 위반)을 걸어 준다.

페이지 테이블의 각 항목에는 유효(valid)/무효(invalid)라는 하나의 비트가 더 있다. 이 비트가 유효로 설정되면 관련된 페이지가 합법적인 페이지이며 무효로 설정되면 그 페이지는 프로세스의 논리 주소 공간에 속하지 않는다. 이 비트를 이용해 페이지의 접근을 제한 할 수 있다.

대부분의 프로세스들은 일정한 시각에 일정 부분의 주소 범위만 사용한다. 이런 경우 모든 페이지에 페이지 테이블 항목을 배정하는 것은 낭비이다. 일부 시스템은 페이지 테이블의 크기를 나타내기 위해 페이지 테이블 길이 레지스터(PTLR, Page Table Length Register)라는 레지스터를 제공 한다.

페이지는 공유를 쉽게 할 수 있다. 여러 프로세스들이 동시에 같은 코드를 수행 할 수 있으며 코드 부분을 공유하더라도 프로세스들은 레지스터의 복사 값과 프로세스가 저장소는 따로 가지고 있다. 물론 서로 프로세스의 자료는 다르다. 공유가 가능한 프로그램으로는 컴파일러, 시스템, 실시간 라이브러리, 데이터베이스시스템 등이 있다.

공유를 위해서는 반드시 코드 재진입이 가능해야 하며 공유 코드의 읽기 전용 특징만으로는 코드의 정확성을 보장할 수 없기 때문에 운영체제에서 이를 보호해 주어야 한다.

[참고자료]

Operating System Concepts / 홍릉과학출판사

28_메모리 페이징 (Paging)

페이징은 논리적 주소 공간이 한 연속적인 공간에 다 모여 있어야 한다는 제약이 없다. 따라서 페이징을 사용하면 메인 메모리에 올라와 있던 부분을 디스크로 내보낼 때 디스크상에 이들을 연속적으로 수용할 수 있는 자유 공간을 탐색하는 오버헤드가 발생하지 않는다. (대부분의 오버헤드는 메모리에 있던 코드의 일부가 스왑 아웃되고 이들을 저장하기 위한 공간을 디스크(backing store)에서 찾는 과정에서 발생한다.)

• 메모리 스와핑 : http://sqlmvp.kr/140191090013

물리 메모리는 프레임(frame)이라 불리는 같은 크기 블록으로 나누어져 있다, 논리 메모리는 페이지(page)라 불리는 같은 크기의 블록으로 나누어 진다.

한 프로세스가 실행 될 때 그 프로세스의 페이지는 보조 메모리로부터 메인 메모리 프레임 안으로 들어온다. 보조 메모리는 메모리 프레임과 같은 크기의 블록들로 나누어져 있다.

CPU에서 나오는 모든 주소는 페이지 번호(p)와 페이지 변위(d:offset) 두 개의 부분으로 나누어 지며 페이지 번호는 페이지 테이블(page table)을 액세스할 때 사용된다.

프레임 크기와 같이 페이지 크기도 하드웨어에 의해 정의 된다. 페이지의 크기는 컴퓨터 구조에 따라 페이지당 512byte ~ 16MB 사이이며 2 제곱근으로 증가한다. 논리적 주소 공간의 크기가 2^m이고 페이지가 2^n 크기라면 논리 주소의 상위 m-n비트는 페이지 번호를 나타내고 하위 n 비트는 페이지 전위를 나타낸다. P는 페이지 테이블에 대한 색인이며 d는 페이지 내에서의 변위로 사용 된다.

페이징 그 자체는 동적 재배치의 한 형태이다. 모든 논리 주소는 페이징 하드웨어(paging hardware)에 의해 물리 주소로 매핑 된다. 페이징 기법을 사용하면 모든 놀고 있는 프레임이 프로세스에 할당 될 수 있기 때문에 외부 단편화가 발생되지 않는다. 그러나 할당은 항상 프레임의 정수 배로 할당 되기 때문에 내부 단편화 문제가 발상 하게 된다.

평균적으로는 프로세스 당 반 페이지 정도의 내부 단편화가 예상된다. 이런 측면에서는 작은 페이지 크기가 바람직하다는 것을 알 수 있다. 그러나 페이지 크기가 작아지면 그에 반비례하여 페이지 테이블의 크기가 커지게 되고 이 테이블이 차지하는 공간은 낭비 된다. 디스크의 입장에서는 페이지가 클수록 효율적이다.

일반적으로 페이지 크기는 4byte이며 변경이 가능하다. 32bit 항복은 2^32개의 물리 페이지 프레임을 가리킬 수 있다 프레임 크기가 4KB 이면 4byte 크기의 항목은 2^44byte(16TB)개의 물리 주소를 저장할 수 있다.

한 프로세스가 실행되기 위해 도착하면 그 프로세스의 크기가 페이지 몇 개 분에 해당하는가를 조사한다. 각 사용자 페이지는 한 프레임씩을 필요로 한다. 프로세스가 n개의 페이지를 요구하면 메모리에서 이용할 수 있는 프레임이 n개가 있어야 한다. n개의 프레임을 사용할 수 있다면 이 프레임들은 이 프로세스에 할당 한다. 그리고 프로세스의 처음 페이지가 할당된 프레임들 중 하나에 적재되고 그 프레임 번호가 페이지 테이블에 기록된다. 그 다음 페이지는 또 다른 프레임에 적재되고 또 그 프레임 번호가 페이지 테이블에 기록되며 이 과정이 반복 된다.

페이징의 가장 중요한 특징은 메모리에 대한 사용자 인식과 실제 내용이 서로 다르다는 것이다. 사용자 프로그램은 메모리가 하나의 연속적인 공간이며 메모리에는 이 프로그램만 있다고 생각한다. 실제로는 프로그램은 여로 곳에 프레임 단위로 분산되어 있고 많은 다은 프로그램이 올라와 있다. 사용자 프로그램이 만들어내는 논리 주소는 실제 물리 주소로 변환 된다. 이 매핑은 운영체제에 의해 조정되며 사용자 프로그램은 접근 할 수 없다.

운영체제는 메모리를 관리하기 때문에 물리 메모리의 자세한 할당에 대해 파악하고 있어야 한다. 즉 어느 프레임에 할당되고 어느 프레임이 사용가능한지, 총 프레임은 몇 개나 되는지 등을 알아야 한다. 이런 정보는 일반적으로 프레임 테이블(frame table)이라는 자료 구조에 있다.

프레임 테이블은 각 프레임 당 하나의 항목을 가지고 있으며 그것이 놀고 잇는지 할당되어 있는지, 할당 되었다면 어느 프로세스의 어느 페이지에게 할당되었는지를 나타낸다.

운영체제는 모든 프로세스들의 주소들을 실제 주소로 매핑 할 수 있어야 한다. 사용자가 시스템 호출(system call)을 해서 매개변수로 어떤 주소를 매핑 된 실제 주소를 찾아가야 한다. 이를 위해 운영체제는 각 사용자에 대해 페이지 테이블의 복사본을 유지하여야 한다. 이 복사본은 운영체제가 시스템 호출을 처리하기 위해 사용자 프로그램의 물리 주소를 소프트웨어적으로 알아내어야 할 때 사용되며 페이징의 문맥 교환시간이 증가 한다.

27_연속 메모리 할당 (Contiguous Memory Allocation)

메인 메모리는 운영체제 뿐만 아니라 여러 사용자 프로세스도 수용해야 한다. 일반적으로 사용되는 연속 메모리 할당에 대해서 알아 보자.

메모리는 일반 적으로 두 개의 부분으로 나누어 진다.

• 메모리에 상주하는 운영체제를 위한 것
• 사용자 프로세스를 위한 것.

운영체제는 메모리의 어느쪽 끝에도 위치할 수 있으며 이 결정에 영향을 미치는 요인은 인터럽트 벡터 이다. 인터럽트 벡터는 흔히 0번지에 위치하기 때문에 운영체제는 하위 메모리에 위치시키는 것이 보통이다.

일반 적으로 여러 프로세스가 동시에 메모리에 올라와 있는 것이 바람직하기 때문에 메모리에 올라오고자 입력 큐에서 기다리는 중인 프로세스들에게 메모리를 얼만큼씩 어떻게 할당하는 것이 좋은가를 생각할 필요가 있다. 이러한 연속 메모리 할당 시스템에서는 각 프로세스는 연속된 메모리 공간을 차지하게 된다.

[메모리 매핑과 보호(Memory Mapping and Protection)]

재배치 레지스터는 가장 작은 물리주소의 값을 저장하고 상한 레지스터는 논리 주소의 범위 값을 결정 한다.

• 재배치 레지스터와 상한 레지스터 : http://sqlmvp.kr/140191021982

CPU 스케줄러가 다음으로 수행할 프로세스를 선택할 때 디스패처(dispatcher)는 문맥교환의 일환으로 재배치 레지스터와 상한 레지스터에 정확한 값을 적재 한다. CPU에 의해서 생성되는 모든 주소들은 이 레지스터들의 값을 참조해서 확인 작업을 하기 때문에 운영체제와 다른 사용자 프로그램의 접근으로부터 보호 할 수 있다.

재배치 레지스터를 사용함으로써 운영체제의 크기는 실행 중이라도 얼마든지 변경될 수 있다. 메모리에는 더 이상 사용하지 않는(작업이 끝난) 운영체제 코드가 존재 할 수 있다. 이러한 부분을 [일시적 운영 체제 코드(transient OS code)]라 부르며 이 기능을 잘 활용하면 전체 운영체제의 크기는 매우 작아 질 수 있다.

[메모리 할당(Memory Allocation)]

간단한 메모리 할당 방법은 메모리를 똑같은 고정된 크기로 분할(partition)하는 것이다. MTF라 불리우며 각 분할을 정확히 하나의 프로세스를 가질 수 있으며 이때 분할의 개수를 다중 프로그래밍 정도(multi programming degree)라 부른다. 다중 분할 방법은 한 분할이 비게 되면 한 프로세스가 입력 큐에서 선택되어 그 분할에 들어 오며 프로세스가 끝나면 다른 프로세스에 사용 될 수 있다.(현재는 거의 사용하지 않음)

MVT라 불리는 방법은 일괄 처리 환경에서 고정된 크기의 분할 영역을 사용하는 것이다. 또한 순수 세그멘테이션(pure segmentation)을 사용하는 시분할 환경에서 적용될 수 있는 메모리 기법들도 있다.

변수분할 기법에서 운용체제는 메모리의 어떤 부분이 사용되고 있고 어떤 부분이 사용되지 않고 있는가를 파악 할 수 있는 테이블을 유지 한다. 초기에 모든 메모리 공간은 한 개의 큰 사용 가능한 블록으로 간주되며(hole) 프로세스가 생성되고 기억 장소가 필요해지면 운영체제는 이 프로세스에게 충분한 크기의 공간을 찾아 주게 된다.

운영체제는 항상 가용 블록의 크기들과 입력 큐를 유지해야 한다. 운영체제는 공간을 차례로 할당해 주다가 메모리가 부족하면 다른 공간이 생길 때까지 프로세스를 입력 큐로 되돌려 보낸다.

일반적으로 메모리는 여러 크기의 공간이 산재하게 된다.(시간이 지날수록 조각화는 더 커진다.) 프로세스가 공간을 필요할 때 운영체제는 이 공간들의 집합에서 적절한 것을 찾아내는데 요청한 공간보다 큰 경우 두 부분으로 나누어서 프로세스에게 할당하고 나머지 부분을 공간(hole)로 소속 시킨다.

프로세스가 끝나면 할당 된 메모리를 회수하는데 이때 회수된 공간이 다른 공간 블록과 인접 하다면 이 두 개의 블록을 합쳐서 하나의 큰 공간 블록을 만들며 이 큰 공간이 필요한 프로세스에게 할당 한다. (물론 큰 공간이 없다면 다시 분할해서 할당 한다.)

이러한 것을 동적 공간 할당 문제(dynamic storage allocation problem)라 하며 이것은 일련의 공간집합 리스트로부터 크기 n바이트 블록을 요구하는 것을 어떻게 만족 시킬까 하는 것으로 최초 적합(first fit), 최적 적합(best-fit), 최악 적합(Worst-fit) 기법이 있다.

• 최초 적합 : 첫 번째 사용 가능한 공간을 할당 한다. 검색은 집합의 시작에서부터 하거나 지난 번 검색이 끝났던 곳에서 시작 될 수 있다. 충분히 큰 자유 공간을 찾았을 때 검색을 끝낼 수 있다.
• 최적 적합 : 사용 가능한 공간들 중에 가장 작은 것을 선택 한다. 리스트가 크기 순으로 정리되어 있지 않다면 전 리스트를 검색해야 한다. 가장 작은 나머지 공간을 만들어 낸다.
• 최악 적합 : 가장 큰 공간을 선택 한다. 이 방식에서 할당하고 남은 공간은 충분히 커서 다른 프로세스들을 위하여 유용하게 사용 될 수 있다.. 이 때 공간들이 크기 순으로 정렬되어 있지 않으면 전체 검색을 한다.

최초 적합, 최적 적합을 사용할 것인지에 대한 결정은 메모리 단편화(memory fragmentation)의 크기에 영향을 받는다.

[메모리 단편화 (Memory Fragmentation)]

위에서 기술한 알고리즘에는 메모리의 외부 단편화가 발생한다. 프로세스들이 메모리에 적재되고 제거되는 일이 반복되다 보면 자유 공간들이 너무 작은 조각화가 되어 버린다. 외부 단편화는 모든 조각들을 합치면 충분한 공간이 만들 수 있지만 여러 곳에 분산되어 있어 발생 한다.

단편화 문제는 매우 심각한 문제를 일으킬 수 있다. 최악의 경우 모든 공간들이 작은 조각으로 세분화 되어 있어 프로세스들이 사용 할 수 없는 것이다.

어떤 적합 모델(최초, 최적, 최악 적합)을 사용하더라도 단편화 문제는 발생 한다. 최초 적합의 경우 통계적 분석결과 N개의 블록을 할당되었을 때 0.5N 개의 블록이 단편화 때문에 손실 될 수 있다. 즉 메모리의 1/3이 쓸 수 없게 될 수 있다는 것이다. 이 현상은 50%(50 percent rule) 규칙으로 알려져 있다.

메모리 공간을 낭비하는 현상은 외부 단편화 뿐만 아니라 내부 단편화도 발생 할 수 있다. 내부 단편화의 예를 들면 공간이 100byte로 할당 되어 있고 어떤 프로세스가 98byte 크기의 공간을 요구한다면 98byte를 할당하고 2byte 공간을 관리하는데 더 큰 부담이 될 수 있다. 이때는 두 개의 공간으로 나누지 않고(98byte, 2byte) 요구한 공간보다 조금 더 할당(100byte) 한다. 이때 할당 받고 남은 공간이 내부 단편화(internal fragmentation) 이다.

외부 단편화를 해결하는 방법은 압축(compaction)과 동떨어진 곳의 공간 배정이다.

• 압축은 은 메모리의 모든 내용은 한곳으로 이동하여 모든 자유 공간들을 모아서 한 블록의 큰 공간으로 만드는 것이다. 하지만 이렇게 하기 위해서는 실행되는 프로세스 내의 모든 주소들이 동적으로 재배치되어야 한다. 따라서 압축은 프로세스들의 재배치가 실행 시간에 동적으로 이루어 지는 경우에만 가능하며 압축이 가능하더라도 비용을 검토해 보아야 한다. (대부분 비용이 많이 든다.)
• 동떨어진 곳의 공간을 배정하는 대표적인 시스템으로는 페이징과 세그멘테이션이 있다. 세그멘테이션은 사용자의 메모리 관점과 물리적인 메모리 관점을 분리한다. 페이징과 세그멘테이션은 서로 합쳐 사용하기도 하지만 세그멘테이션 결함으로 인하여 대부분 페이징으로 사용한다.

[참고자료]

Operating System Concepts / 홍릉과학출판사

26_메모리 스와핑(Swapping)

프로세스가 실행되기 위해서는 메모리에 있어야 하지만 필요한 경우 프로세스는 실행도중에 임시로 보조 메모리로 보내어졌다가 다시 메모리로 되돌아 올 수 있다. 라운드로빈 스케줄링을 하는 경우 다중 프로그램 환경에서 한 프로세스가 CPU 할당 시간이 끝나면 메모리 관리기(MMU)가 이 프로세스를 보조 메모리로 보내고 다른 프로세스를 메모리로 불러올 수 있다.

CPU 스케줄러는 메모리 내의 다른 프로세스에게도 시간 할당량(time quantum)을 정해 놓고 그 할당량을 모두 소비했을 때 그 프로세스도 스왑시킬 수 있다. CPU 스케줄러는 할아 시간이 만료 되어 CPU를 새로 스케줄 할 때마다 메모리 관리기가 메모리 내에 준비시켜 놓은 여러 프로세스들 중 하나를 고르기만 하면 된다.

시간 할당량은 스왑 작업을 고려하여 원활한 작업 처리가 이루어 질 수 있도록 충분히 길어야 한다. 스와핑 정책은 시간 할당 외에도 우선순위 방식으로 바꿀 수도 있다. 이러한 스와핑의 변형을 롤인(roll-in), 롤 아웃(roll_out)이라고 한다.

스와핑은 보조 메모리를 필요로 하며 보통 디스크를 사용한다. 시스템은 실행 준비가 된 모든 프로세스를 모아 준비 완료 큐(Ready queue)에 가지고 있어야 한다. CPU가 스케줄을 고를 때 디스패처(dispatcher)를 호출하고 디스패처는 준비 완료 큐(Ready queue)에 있는 다음 프로세스가 메모리에 올라와 있는지 확인하여 메모리에 없다면 디스크로부터 읽어 들인다. 그런데 메모리에 이 프로세스에 대한 공간이 없다면 공간을 만들기 위해 현재 메모리에 올라와 있는 프로세스를 내보내고(swap out) 원하는 프로세스를 불러들인다. 그리고 나서 CPU의 모든 레지스터를 실행해야 할 프로세스의 것으로 다시 적재하고 제어권을 그 프로세스에게 넘긴다.

[문맥 교환 시간]

• 사용자 프로세스 크기 10MB
• 보조 메모리의 전송률 : 초당 40MB

10MB의 프로세스를 전송하는데 걸리는 시간 10,000KB / 40,000 kb = 1/4초 = 250ms

헤드 탐색 시간이 없다고 가정하고 평균 8 밀리초의 회전 지연시간을 가정 했을 때 스왑시간은 258ms가 된다. 스왑 시간의 대부분은 디스크 전송 시간이다.

한 프로세스를 스왑 아웃하고 다른 프로세스를 스왑인 해야 하므로 총 스왑시간은 516ms 가 필요하다. 효과적인 CPU 사용을 위해서 각 프로세스의 실행 시간은 스왑 시간보다 충분히 길어야 한다. 라운드 로빈 스케줄링의 경우 최소 0.516초보다 커야 한다.

[스와핑에 따른 제약]

한 프로세스를 스왑하기를 원한다면 그 프로세스는 완전히 유휴상태인지 확인해야 한다. 그 프로세스가 입출력 장치와 어떤 신호를 주고 받는 중이라면 입출력 에러가 발생하기 때문에 스왑하면 안된다. 이 문제를 해결하기 위해 입출력이 종료되지 않은 프로세스를 스왑하지 말거나 입출력은 항상 프로세스로 직접 하지 말고 운영체제의 버퍼만 하도록 한다. 운영체제와 프로세스 사이의 전송은 단지 프로세스가 스왑되어 들어온 상태에서만 하면 된다.

[참고자료]

Operating System Concepts / 홍릉과학출판사

25_메인 메모리(Main Memory)

CPU는 PC(Program Counter)가 지시 하는대로 메인 메모리로부터 다음 수행할 명령어를 가져오는데 그 명령어는 필요한 경우 추가적인 자료를 더 가져올 수 있으며 반대로 자료를 메모리로 내보낼 수도 있다.

메인 메모리와 CPU에 내장되어 있는 레지스터들은 CPU가 직접 접근할 수 있는 유일한 저장 장치이다. 모든 실행되는 명령어와 자료들은 CPU가 직접 접근할 수 있는 메인 메모리와 레지스터에 있어야 한다. 만약 자료가 메모리에 없다면 CPU가 처리하기 전에 메모리로 이동(Load)해야 한다.

레지스터들은 일반적으로 CPU클록(clock)의 1사이트(cycle)내에 접근이 가능하지만 메인 메모리의 경우 많은 CPU 클록 및 사이클이 소요되어 CPU가 필요한 자료가 없어서 명령을 수행하지 못하는 지연(stall)되는 현상이 발생하기도 한다. 이러한 지연 현상을 해결하기 위해 캐시(cache)라 부르는 메모리 버퍼가 사용된다.

프로세스들은 독립된 메모리 공간을 갖는다. 각 프로세스는 합법적인(legal) 메모리 주소 영역을 설정하고 접근하는데 가장 작은 합리적인 물리 주소의 값을 가진 베이스 레지스터, 주어진 영역의 크기를 저장하는 상한 레지스터를 이용하여 메모리를 보호 한다.

메모리 공간 보호는 CPU 하드웨어가 사용자 모드에서 만들어진 모든 주소와 레지스터를 비교함으로써 이루어진다. 사용자 프로그램이 운영체제 메모리 공간이나 다른 응용 프로그램 공간의 접근이 일어나면 오류로 간주하여 트랩(trap)을 발생 시킨다.

베이스와 상한 레지스터는 여러 가지 특권 명령(privileged instruction)을 사용하는 운영체제에 의해서만 적재 된다. 특권 명령은 오직 커널 모드에서만 수행되고 운영체제만 커널 모드에서 수행되기 때문이다.

운영체제는 사용자 프로그램을 사용자 메모리 영역에 적재하고 에러가 발생한 경우에 그 프로그램을 덤프(dump out)하고 시스템 호출(system call)의 매개변수(parameter) 값을 변경하는 것과 같은 일들을 수행 할 수 있다.

[주소의 할당 (Address Binding)]

프로그램이 실행되기 위해서는 메모리에 적재되어야 한다고 했다. 프로세스가 종료되면 이전 프로세스가 사용했던 기억 공간이 가용(available) 공간이 되며 다른 프로세스를 위해 사용 된다. 대부분의 시스템은 사용자 프로세스가 메모리 내 어느 부분으로도 올라올 수 있도록 지원하고 있다.

메모리 주소 공간에서 명령어와 자료의 바인딩은 이루어지는 시점에서 다음과 같이 구분 된다.

• 컴파일 시간(compile time) 바인딩 : 프로세스가 메모리 내에 들어갈 위치를 컴파일 시간에 미리 알 수 있으면 컴파일러는 절대 코드를 생성할 수 있다. 그러나 위치가 변경되어야 한다면 이 코드는 다시 컴파일 되어야 한다.
• 적재 시간(Load time) 바인딩 : 메모리 내의 어느 위치로 올라오게 될지를 컴파일 시점에서 알지 못하면 컴파일러는 일단 이진 코드를 재배치 가능 코드로 만든다. 이 경우 심볼과 진짜 번지수와의 바인딩은 프로그램이 메인 메모리로 실제 적재되는 시간에 이루어지게 된다. 재배치 가능 코드는 주소가 바뀌어도 코드를 다시 적재만 하면 된다.
• 실행 시간(Execution Time) 바인딩 : 프로세스가 실행 중간에 메모리 내의 다른 세그먼트로 옮겨질 수 있다면 이를 "바인딩이 실행 시간까지 허용되었다" 라고 한다.

[논리 대 물리 주소 공간(Logical Versus Physical Address Space)]

CPU가 생성하는 주소를 일반적으로 논리 주소(Logical Address)라 하며 반면에 메모리가 취급하게 되는 주소(MAR)는 물리 주소(Physical address)라 한다.

컴파일 시 바인딩과 적재 시 바인딩 기법 경우에는 논리, 물리 주소가 같다. 그러나 실행 바인딩 기법에서는 논리, 물리 주소가 다르다. 이 경우 논리 주소를 가상 주소(virtual address)라 한다.

프로그램에 의해 생성된 모든 논리 주소 집합을 논리 주소 공간(logical address space)이라 하며 이 논리 주소와 일치하는 물리 주소 집합을 물리 주소 공간(physical address space)이라 한다. 프로그램의 실행 중에는 이와 같은 가상 주소를 물리 주소로 바꾸어줘야 하는데 이 변환(mapping) 작업은 하드웨어 장치인 메모리 관리기 (MMU(Memory Management Unit))에 의해 실행 된다.

사용자 프로그램은 실제적인 물리 주소를 알 수 없기 때문에 베이스 레지스터에 대해 다시 바인딩 된다. 이때 베이스 레지스터를 재배치(relocation) 레지스터라 한다. 사용자 프로그램의 논리적 주소를 메모리의 물리적 주소로 바꾸는 것이다.

메모리 주소는 논리적 주소(0~max)와 물리적 주소(기준값 R에 대해 R+1 ~ R+max)가 있다는 것에 유의해야 한다. 이처럼 메모리의 주소 공간이 논리 주소 공간과 물리 주소 공간이 분리된다는 개념은 매우 중요하다.

[동적 적재(Dynamic Loading)]

프로세스가 실행되기 위해 프로그램 전부와 프로세스의 모든 자료가 메모리에 올라와 있어야 한다. 이 경우 프로그램은 메모리의 크기보다 클 수는 없다. 이런 단점을 보완하기 위해 동적 적재(Dynamic Loading)를 사용한다.

동적 적재(Dynamic Loading)는 각 루틴이 실제 호출되기 전까지는 메모리에 올라오지 않고 재배치 가능한 상태로 디스크에서 대기하고 있으며 먼저 주 프로그램이 메모리에 올라와 실행된다. 이 루틴이 다른 루틴을 호출하게 되면 호출 된 루틴이 이미 메모리에 적재 되어 있는지를 조사하여 적재되어 있지 않다면 재배치 가능 연결 적재기(relocatable linking loader)를 호출하여 요구된 루틴을 메모리로 가져오고 이러한 변화를 테이블에 기록한다. 그 후 CPU제어는 중단되었던 루틴으로 보내진다.

동적 적재의 장점은 사용되지 않는 루틴들의 경우 미리 적재 되지 않는다는 것이며 많은 양의 코드를 필요로 할 때 유용하다. 전체 프로그램이 클지라도 실제 사용되는 부분은 훨씬 작을 수 있다.

[동적 연결 및 공유 라이브러리 (Dynamic Linking & Shared library)]

동적 적재에서는 적재가 실행시 까지 미루어 졌다면 동적 연결에서는 연결(linking)이 실행 시 까지 미루어지는 것이다. 동적 연결은 주로 시스템 라이브러리에 사용 된다.

동적 연결에서는 라이브러리를 부르는 곳마다 스텁(stub)이 생긴다, 이 스텁은 그 라이브러리를 어떻게 찾을 것인가를 알려주는 작은 코드 조각이다. 스텁은 필요한 라이브러리 루틴이 이미 메모리에 존재하는가를 검사하여 없으면 디스크에서 가져온다.

동적 연결은 라이브러리 루틴을 바꿀 때 특히 유용하다. 라이브러리는 어느 때나 새로운 버전으로 교체될 수 있고 그렇게 되면 그 라이브러리를 사용하는 모든 프로그램은 자동적으로 이 새로운 라이브러리 버전을 사용하게 될 것이다.

여러 버전의 라이브러리들이 시스템에 존재할 수도 있기 때문에 각 프로그램은 라이브러리의 어느 저번을 사용해야 할지를 가려내기 위해 이러한 버전정보를 이용한다. 이러한 시스템을 공유라이브러리라 한다.

동적 적재와 달리 동적 연결은 일반적으로 운영체제의 도움이 필요하다. 메모리에 있는 프로세스들이 각자의 공간은 가지만 접근할 수 있도록 보호된다면 운영체제만이 기억공간에 루틴이 있는지 검사해 줄 수 있고 운영체제만이 여러 프로세스들로 하여금 같은 메모리 주소를 공용할 수 있도록 해줄 수 있다.

[참고자료]

Operating System Concepts / 홍릉과학출판사

24_교착 상태(Deadlock)

다중 프로그래밍 환경에서 여러 프로세스들이 한정된 자원을 사용하려고 서로 경쟁 할 수 있다. 한 프로세스가 자원을 요청 했을 때 그 시각에 그 자원을 사용할 수 없는 상황이 발생할 수 있고 그 때는 프로세스가 대기 상태로 들어 간다. 이처럼 대기중인 프로세스들이(요청된 프로세스가 다른 프로세스에 의해 대기) 다시는 그 상태를 변경 시킬 수 없으며 이러한 상황을 교착 상태라 한다.

교착 상태는 한 시스템 내에서 다음의 조건이 동시에 설립 될 때 발생한다.

• 상호 배제(Mutual exclusion) : 최소한 하나의 자원이 비공유 모드로 점유되어야 한다. 비공유 모드에서는 한 번에 한 프로세스만이 그 자원을 사용할 수 있다. 다른 프로세스가 그 자원을 요청하면 요청 프로세스는 자원이 방출 될 때까지 반드시 지연되어야 한다.
• 점유 대기(hold and wait) : 프로세스는 최소한 하나의 자원을 점유한 채 현재 다른 프로세스에 의해 점유된 자원을 추가로 얻기 위해 반드시 대기해야 한다.
• 비선점(No preemption) : 자원들을 선점할 수 없어야 한다. 자원이 강제적으로 방출될 수 없고 점유하고 있는 프로세스가 태스크를 종료 한 후 그 프로세스에 의해 자발적으로만 방출 될 수 있다.
• 순환대기(Circular wait) : 대기하고 있는 프로세스의 집합 {P0, P1, ,…Pn}에서 P0는 P1이 점유한 자원을 대기하고 P1은 P2가 점유한 자원을 대기하고 P2…Pn-1은 Pn이 점유한 자원을 대기하며 Pn은 P0가 점유한 자원을 대기 한다.

교착 상태는 시스템 자원 할당 그래프라고 하는 방향 그래프로 보다 정확하게 기술할 수 있다. 그래프는 정점(vertex) v의 집합과 간선(edge) E의 집합으로 구성된다.

• 프로세스 Pi로부터 자원유형 Rj로의 방향 간선은 Pi ->Rj로 표현하며 이것은 프로세스 Pi가 자원 유형 Rj의 인스턴스를 하나 요청하는 것으로 현재 이 자원을 기다리는 상태이다. (요청 간선(request edge)라 부른다.)
• 자원 유형 Rj로부터 프로세스 Pi로의 방향 간선은 Rj->Pi로 표현하며 이것은 자원 유형 Rj의 한 인스턴스가 프로세스 Pi에 할당된 것을 의미 한다. (할당 간선(assignment edge)이라 부른다.)

[교착 상태의 자원 할당 그래프]

P3가 자원유형 R2의 인스턴스를 하나 요청한다. 사용 가능한 자원이 없기 때문에 요청 간선 P3 -> R2를 그래프에 추가한다. 이 시점에서 시스템 내에 두 개의 최소의 사이클이 존재 한다. 프로세스 P1, P2, P3는 교착 상태이다. 프로세스 P2는 프로세스 P3를 점유하고 있는 자원 R2를 기다린다. 프로세스 P3은 프로세스 P1이나 P2가 자원 R2를 방출하기를 기다린다. 프로세스P1은 P2가 자원 R1을 방출하기를 기다린다.

[교착 상태 처리]

교착 상태를 처리하는 방법에는 세 가지 방법이 있다.

• 시스템이 결코 교착 상태가 되지 않도록 보장하기 위하여 교착상태를 예방하거나 회피하는 프로토콜을 사용
• 시스템이 교착상태가 되도록 허용한 다음에 회복시키는 방법
• 문제를 무시하고 교착 상태가 시스템에서 결코 발생하지 않는 척 한다.

[교착 상태 예방(Deadlock Prevention)]

• 상호배제(Mutual Exclusion) : 상호 배제 조건은 불가능한 자원에 대해서는 반드시 성립해야 한다.
• 점유 대기(Hold and wait) : 프로세스가 자원을 요청 할 때는 다른 자원들을 점유하지 않을 것을 반드시 보장해야 한다. 이용할 수 있는 한가지 프로토콜은 각 프로세스가 실행되기 전에 자신의 모든 자원을 요청하고 할당 받을 것을 요구 한다. 한 프로세스를 위해 자원을 요청하는 시스템 호출이 모든 다른 시스템 호출에 앞서 나타날 것을 요구함으로써 이 규정을 구현 할 수 있다.
• 비전섬(No Preemption) : 이미 할당된 자원이 선점되지 않아야 한다. 어떤 자원을 점유하고 있는 프로세스가 즉시 할당할 수 없는 다른 자원을 요청하면 현재 점유하고 있는 모든 자원들이 선점된다. 즉 이 자원들이 묵시적으로 방출된다.
• 순환대기(Circular Wait) : 모든 자원 유형들에게 전체적인 순서를 부여하여 각 프로세스가 열거된 순서대로 오름차순으로 자원을 요청하도록 요구.

[교착 상태 회피 (Deadlock Avoidance)]

교착 상태를 위해 필요한 조건 중 최소한 하나가 발생하지 않도록 보장하여 교착상태가 성립하지 못하게 한다. 이러한 방식의 교착 상태 예방은 장치의 이용률이 저하되고 시스템 처리율이 감소 되는 문제가 있다.

교착 상태를 회피하는 다른 대안은 자원이 어떻게 요청 될지에 대한 추가 정보를 제공하도록 요구하는 것이다. 각 요청에 대해 대기하는 결정을 하기 위해 현재 가용 자원, 현재 각 프로세스에 할당된 자원, 각 프로세스가 앞으로 요청하거나 방출할 자원을 고려해야 한다.

[교착 상태 탐지(Deadlock Detection)]

시스템의 교착 상태를 방지 하기 위해 교착 상태가 발생하였는지 검사하는 알고리즘과 교착 상태로부터 회복하는 알고리즘을 지원해야 한다.

모든 자원들이 한 개의 인스턴스만 있다면 대기 그래프라고 하는 자원 할당 그래프의 변형을 사용해 교착 상태 탐지 알고리즘을 정의할 수 있다. 자원 할당 그래프로부터 자원 유형의 노드를 제거하고 적절한 간선들을 결합함으로써 대기 그래프를 얻을 수 있다.

대기 그래프는 각 종류마다 자원이 여러 개씩 존재하는 상황에서는 사용할 수 없다.

교착 상태가 자주 발생한다면 탐지 알고리즘도 자주 돌려야 한다. 교착 상태가 된 프로세스로부터 자원을 회수하기까지는 그 자원들은 아무도 못 쓰는 자원으로 묶이게 되며 시간이 더 경과하면 교착 상태에 연루되는 프로세스의 수도 늘어 날 수 있다.

자원을 요청 할 때마다 탐지 알고리즘을 실행하면 오버헤드가 발생한다. 오버헤드를 방지하기 위하여 가끔 탐지 알고리즘을 실행하면 한꺼번에 여러 개의 사이클이 탐지될 수도 있다. 이 경우 어느 프로세스가 최종적으로 교착 상태를 발생시키는지 알 수 없게 된다.

[교착 상태로부터 회복(Recovery from Deadlock)]

프로세스 종료 (Process Termination)

• 교착 상태의 프로세스를 모두 중지 : 이 방식은 확실하게 교착 상태의 사이클을 깨뜨리지만 비용이 크다. 이 프로세스들은 오랫동안 연산했을 가능성이 있으며 이들 부분 계산의 결과들을 반드시 폐기해야 하며 이후 다시 계산해야 하기 때문이다.
• 교착 상태가 제거 될 때까지 한 프로세스씩 중지 : 각 프로세스가 중지 될 때마다 교착 상태 탐지 알고리즘을 호출해 프로세스들이 아직도 교착 상태에 있는지 확인해야 하기 때문에 오버헤드가 발생

자원 선점 (Resource Preemption)

• 희생자 선택(Selecting a victim) : 프로세스 종료와 같이 비용을 최소화하기 위해 선점 순서를 결정해야 한다. 비용요인으로는 교착 상태 프로세스가 점유하고 있는 자원의 수 그리고 교착 상태 프로세스가 지금까지 실행하는데 소요한 시간과 같은 매개변수들이 포함될 수 있다.
• 롤백(Rollback) : 일반적으로 안전 상태가 어떤 것인지 결정하기 어렵기 때문에 가장 단순한 해결안은 완전히 롤백 하는 것이다. 즉 프로세스를 중지(abort)하고 다시 시작하는 것이다. 그로나 프로세스를 단지 교착 상태만 깨뜨릴 정도로 롤백 할 수 있다면 매우 효과적이다. 반면에 이 방식은 시스템이 실행하는 모든 프로세스들의 상태에 대한 보다 많은 정보를 유지할 것을 필요로 한다.
• 기아 상태(Starvation) : 희생자의 선택이 주로 비요 요인에 근거한 시스템에서는 동일한 프로세스가 항상 희생자로 선택 될 수 있다. 그 결과 이 프로세스는 자신의 태스크를 결코 완료하지 못하는 기아 상태에 있게 되며 이러한 문제는 모든 실용적인 시스템에서 해결해야 할 문제이다. 대부분의 일반적인 해결 방법은 비용 요소에 롤백의 회수를 포함시키는 방법이다.

[참고자료]

Operating System Concepts / 홍릉과학출판사

23_원자적 트랜잭션 (Atomic Transaction)

• 직렬가능성(Serializability), 락킹 프로토콜(Locking Protocol), 타임스탬프 기반 프로토콜(Timestamp Base Protocol)

직렬 가능성이란 임계구역 내에서 다수의 트랜잭션들이 동시 활성화 될 경우 각 트랜잭션들은 원자적이기 때문에 여러 트랜잭션들을 병렬로 수행시키면 그 결과는 이 모든 트랜잭션들을 어떤 임의의 순서에 따라 하나씩 차례로 순차적으로 실행되는 것을 말한다.

직렬 가능성으로 트랜잭션이 병렬로 수행되면 원자성이 보장되기는 하지만 비효율이 발생 하므로 몇 가지 동시성 제어 알고리즘(concurrency-control algorithm)이 직렬성을 유지하면서 트랜잭션 수행을 중첩 시킬 수 있다.

[직렬 가능성(Serializability)]

각 트랜잭션들이 원자적으로 수행되는 스케줄을 직렬 스케줄(Serialzability)이라 부른다. 직렬 스케줄은 여러 트랜잭션들의 명령어들의 순서로 구성되고 특정 트랜잭션에 속한 명령어들은 연속된 집합 형태로 나타난다.

N 개의 트랜잭션이 있다면 N! 개의 유효한(valid) 직렬 스케줄이 존재 한다. 각 트랜잭션들을 임의의 순서로 원자적으로 수행시키는 것과 동등하기 때문에 각 직렬 스케줄은 올바르다(correct)라 한다.

두 개의 트랜잭션이 중첩되게 실행시키면 그 결과는 더 이상 직렬 스케줄이 아니다. 비직렬 스케줄이 반드시 잘못된(incorrect) 스케줄은 아니다. 이 때는 충돌 연산(conflicting operation)을 정의해야 한다.

충돌 연산의 예를 들어 두 개의 트랜잭션T1, T2에 속한 연산 O1, O2 를 실행하는 스케줄 S가 있을 때 O1과 O2가 다른 트랜잭션에 속해 있으면서 O1과 O2가 서로 충돌하지 않는다면 우리는 O1과 O2의 순서를 바꾸어(swap) 새로운 스케줄 S'를 만들 수 있다. 이 때 S와 S'은 동등하다고 기대 할 수 있다. 왜냐하면 두 스케줄에서 O1과 O2를 제외한 나머지 연산들은 다 동일하며 O1과 O2도 비록 그 순서는 바뀌었지만 아무런 영향을 미치지 않기 때문이다.

정리하면 다음과 같은 표로 나타낼 수 있다.

스케줄 S에 있는 비충돌 연산들을 스왑 시켜줌으로써 직렬 스케줄로 변환시켜 줄 수 있다면 [S가 충돌 직렬가능(conflict serialzable)하다] 라고 표현 한다.

[락킹 프로토콜(Locking Protocol)]

직렬 가능성을 보장하는 한 가지 방법은 각 자료 항목마다 락을 두고 각 트랜잭션이 일정한 락킹 프로토콜에 맞추어 락을 획득하고 반납하도록 규정하는 것이다.

• 공유(Shared) : 트랜잭션 T1이 자료 항목 Q에 대한 공유 모드(shared mode) 락(S)을 가지고 있으며 T1은 Q를 읽을 수 있지만 Q에 쓸 수는 없다.
• 독점(Exclusive) : 트랜잭션 T1가 자료 항목 Q에 대한 독점 모드(exclusive mode) 락(X)을 가지고 있으며 T1는 Q에 읽기와 쓰기를 모두 할 수 있다.

트랜잭션은 이전에 락을 걸었던 자료 항목에 대해서는 락을 해제할 수 있다. 그렇지만 그 자료 항목을 접근하는 기간 동안에는 계속 락을 유지하여야 한다.

자료 항목에 대한 마지막 접근이 끝난 직후 바로 락을 해제하는 것은 직렬 가능성이 보장되지 않을 수 있기 때문에 바람직 하지 않을 수 있다.

두 단계 락킹 프로토콜(tow phase locking protocol)은 직렬 가능성을 보장해 주는 프로토콜의 하나이다. 이 프로토콜은 락과 언락을 두 단계로 수행 할 것을 요구 한다.

• 확장 단계(Growing phase) : 트랜잭션은 락을 새로 얻을 수 있지만 얻었던 락을 반납해서는 안된다.
• 수축 된다(shrinking phase) : 트랜잭션은 얻었던 락을 반납할 수는 있지만 새로운 락을 얻어서는 안된다.

트랜잭션은 최초에는 확장 단계에서 시작하며 필요한 만큼 락을 확보 한다. 그러나 트랜잭션이 일단 한 개의 락을 해제하기 시작하면 수축 단계로 들어가며 기 이후부터는 새로운 락을 획득 해서는 안된다.

두 단계 락킹 프로토콜은 충돌 직렬가능성을 보장한다. 그러나 교착 상태 문제가 발생 할 수 있다.

[타임 스탬프 기반 프로토콜(timestamp based protocol)]

트랜잭션 충돌을 위해 직렬 가능한 순서를 정하는데 가장 많이 사용하는 방법이 타임 스탬프 순서 기법이다. 시스템의 각 트랜잭션마다 고유한 고정 타임스탬프를 부여한다.

타임 스탬프가 직렬 가능성을 보장하기 때문에 TS1 < TS2 라면 시스템은 T1을 처리한 후 T2를 처리하여 직렬 스케줄과 동등하도록 보장한다.

• 시스템 클록(system clock)방법은 이 트랜잭션이 시스템에 도착할 당시 클록의 값이 된다. 이 방법은 별도의 시스템에서 수행되거나 두 처리가 클록을 공유하지 않는 환경에서는 사용할 수 없다.
• 논리적 카운터(logincal counter)방법은 트랜잭션이 시스템에 도착할 당시 논리적 카운터의 값이 된다. 카운터는 새 타임스탬프가 부여된 후에 증가 된다.

타임스탬프 프로토콜은 트랜잭션들이 서로 기다리는 일이 없기 때문에 교착 상태를 유발하지는 않는다.

22_원자적 트랜잭션 (Atomic Transaction)

• 시스템 모델(system model), 로그 기반 복구(log based recovery), 검사점(checkpoint)

임계 구역의 상호 배제는 임계 구역이 원자적으로 수행된다는 것을 보장한다. 두 개의 임계 구역이 동시에 병렬로 수행된다고 하더라도 그 결과는 어떤 순서인지는 지정할 수 없지만 마치 두 개를 한번에 하나씩 순차적으로 수행시킨 것과 같게 된다.

가장 대표적인 예는 은행 이체 시스템이다. 자금 이체의 경우 한 통장에서 돈이 출금되어 다른 통장으로 입금된다. 이때 일관성을 위해서는 출금과 입금이 둘 다 발생하던지 둘 다 발생하지 않는 것이다.

[시스템 모델(System Model)]

하나의 논리적인 기능을 수행하는 명령(또는 연산)의 집합을 트랜잭션이라고 한다. 트랜잭션을 처리하는데 있어 주요 문제는 컴퓨터 시스템 안에서 어떤 고장이 발생할 가능성이 있더라도 원자성(atomicity)을 보장해야 한다는 것이다.

종료된 트랜잭션이 수행을 성공적으로 마쳤으면 이 트랜잭션은 완료(commit)된 것이고 그렇지 않으면 철회(rollback)된 것이다.

시스템이 어떻게 원자성을 보장해 줄 수 있는가를 살펴보려면 먼저 하드웨어 장치들이 어떻게 트랜잭션의 자료들을 저장하는지 살펴보아야 한다. 저장 장치에 따라 속도, 용량, 신뢰성 등 다양 하다.

• 휘발성(volatile) 저장 장치 : 시스템이 고장나면 사라진다. 속도가 빠르며 직접 접근이 가능하다. 메모리, 캐시 등이 있다.

  

• 비휘발성(Nonvolatile) 저장 장치 : 시스템이 고장나더라도 보존된다. 메모리보다 신뢰성은 높지만 속도가 느리다.

  

   

• 안전(Stable) 저장 장치 : 똑 같은 정보를 여러 대의 디스크에 중복해서 기록 한다. 한 대가 고장나도 다른 디스크에는 영향이 없는 독립 디스크여야 한다. 정보를 갱신 할 때 미리 정의된 방식으로 신중하게 갱신 해야 한다.

  

[로그 기반 복구(Log Based Recover)]

원자성을 보장해 주는 방법은 트랜잭션에 의해 접근된 자료에 가해지는 모든 변경 내역을 안전 저장 장치에 기록해 놓는 것이다. 이러한 형태의 기록을 많이 사용되는 기법은 로그 우선 쓰기(write ahead logging)방식이다.

• 트랜잭션 이름 : 쓰기 연산을 수행한 트랜잭션 고유한 이름
• 자료 항목 이름 : 써진 자료 항목의 고유한 이름
• 이전 값 : 쓰기 연산 이전에 그 자료 항목에 저장되어 있던 값
• 새 값 : 쓰기 연산 이후에 그 자료 항목에 저장 될 값

1. 트랜잭션 T1가 시작하기 전에 <T1 starts>라는 로그 기록
2. 트랜잭션 T1 수행중에 T1쓰기를 할 때마다 그 전에 해당하는 새로운 레코드가 로그에 기록
3. T1 완료되면 <T1 commits>레코드가 로그에 기록

로그를 쓰는 데는 성능 손실을 주의해야 한다. 각 논리적인 쓰기마다 두 번의 물리적인 쓰기가 필요하다. 또한 자료 자체와 변경을 기록하는 로그를 위하여 더 많은 저장 공간을 필요로 하며 기록을 하는 동안 오버헤드가 발생 한다. 중요한 자료의 경우 안정성 및 복구를 위하여 추가적인 비용이 필요하다.

로그를 사용하면 비휘발성(nonvolatile) 저장 장치 자체의 정보 손실을 야기 하지 않는 어떠한 고장도 처리할 수 있다. 복구 알고리즘은 두 개의 프로시저를 사용한다.

• Undo : 갱신한 모든 자료 항목의 값들을 T1 시작되기 이전의 값으로 되돌려 놓는다.
• Redo : 갱신한 모든 자료 항목에 새로운 값들을 넣는다.

트랜잭션 T1이 처리 도중 철회(rollback) 되면 단순히 undo(t1)을 호출 하여 지금까지 부분적으로 갱신했던 자료 항목들이 원래의 값으로 복구된다.

시스템 고장이 발생하면 로그를 보면서 redo, undo를 결정 한다.

• 로그에 <t1, start>레코드는 있지만 <t1, commits>레코드가 없다면 트랜잭션 t1은 undo 된다.
• 로그에 <t1, starts>와 <t1, commits> 두 개의 레코드가 다 있다면 트랜잭션 t1은 redo 된다.

[검사점(checkpoint)]

시스템 고장이 발생하면 우리는 로그를 보면서 redo 또는 undo 트랜잭션을 결정한다. 원칙적으로는 로그 전체를 조사하면서 이 작업을 진행해야 하지만 많은 시간 소모와 오버헤드가 발생 한다.

이러한 불필요한 오버헤드를 줄이기 위해 검사점(checkpoint)라는 개념을 도입한다. 시스템은 우선 쓰기 로그(write ahead log)를 유지하면서 주기적으로 검사점을 수행한다.

로그의 <checkpoint> 레코드는 시스템 복구 작업을 보다 능률적으로 만들어 준다, 트랜잭션 t1은 검사점 이전에 완료 했다고 하자. 그러면 로그에서 <T1, commits> 레코드가 <checkpoint> 레코드보다 앞서 나온다. 그러면 t1이 수행한 모든 변경은 checkpoint 이전에 안전 장치에 이미 기록 되었던지 아니면 검사점 작업의 일환으로 안전 저장 장치에 기록되었을 것이다. 따라서 시스템 복구 시 T1에 대한 redo 연산을 할 필요가 없다.

• T에 속한 모든 작업에 대해 <T, commits>가 로그에 기록되어 있으면 redo(t)를 수행 시켜 준다
• T에 속한 모든 작업에 대해 <T, commits>가 로그에 기록되어 있지 않으면 undo(t)를 수행 시켜 준다.

[참고자료]

Operating System Concept / 홍릉과학출판사

21_프로세스 모니터링

세마포가 프로세스들 간의 동기화를 위해서 편리하고 효과적으로 쓰일 수 있지만 세마포는 잘못하면 발견하기 어려운 타이밍 오류를 야기할 수 있다. 이러한 타이밍 오류들은 특정 실행 순서로 진행되었을 때만 발생하고 이러한 순서가 항상 일어나는 것은 아니기 때문이다.

• 세마포와 뮤텍스 : http://sqlmvp.kr/140188335482

모든 프로세스들은 mutex라는 세마포 변수를 공유하며 그 초기값은 1이다. 각 프로세스는 임계 구역에 진입하기 전에 wait(mutex)를 실행해야 하며 임계 구역을 나올 때 signal(mutex)를 실행 해야 한다. 이 순서가 제대로 지켜지지 않으면 두 프로세스가 동시에 임계 구역 안에 있을 수 있으며 이러한 문제점들은 하나의 프로세스라도 잘못 행동하면 발생하게 된다.

• 세마포에 대한 wait()와 signal() 연산순서가 바뀐 경우 동시에 임계 구역 안에 위치하게 되어 상호배제 요구 조건을 위배 한다.

• 프로세스가 signal(mutex)를 써야할 곳에 wait(mutex)를 사용 하였을 경우 교착 상태가 발생한다.

• 프로세스가 wait(mutex)나 signal(mutex) 또는 둘 다를 빠뜨린 경우 상호배제나 교착 상태가 발생한다.

[모니터(monitor type) 사용]

데이터 유형(type) 또는 추상화된 데이터 유형(abstract data type)은 사적인 자료(private data)를 조작하는 공개 메소드(public method)를 사용하여 보호 한다. 모니터 유형은 모니터 내부에서 상호 배제를 제공하는 프로그래머가 정의한 일련의 연산자를 제공한다.

모니터 유형은 변수들의 선언을 포함하고 있는데 이 변수들의 값은 그 유형에 해당하는 한 인스턴스의 상태를 정의한다. 그리고 모니터 유형은 이 변수들을 조작할 수 있는 프로시저 또는 함수들의 본체도 같이 포함하고 있다.

모니터 유형의 표현은 다른 프로세스들이 직접 사용할 수 없다. 따라서 모니터 내의 정의된 프로시저만이 프로시저 내에서 지역적으로 정의된 자신의 형식 매개변수를 접근할 수 있다. 모니터 구조물은 모니터 안에 항상 하나의 프로세스만 활성화 되도록 보장해 준다. 그러므로 개발자는 동기화 제약 조건을 명시적으로 코딩 해야 할 필요가 없다.

동기화 기법을 모델링하는 데에는 충분한 능력을 제공하지 않는다. 이를 위해 우리는 부가적인 동기화 기법을 정의해야 할 필요가 있다, 이 동기화 기법들은 condition 이라는 구조물로 제공될 수 있다. 자신의 주문형 동기화 기법을 작성할 필요가 잇는 프로그래머는 하나 이상의 conditicon() 유형의 변수를 정의 할 수 있다.

Condition x, y 유형 변수에 호출 될 수 있는 연산은 wait(), signal() 뿐이 없다. Wait()연산을 호출한 프로세스는 다른 프로세스가 signal()을 호출 할 때까지 일시 중단되어야 하는 것을 의미 한다.

x.signal() 연산은 정확히 하나의 일시 중단 프로세스를 재개 한다. 만약 일시 중단된 프로세스가 없으면 signal() 연산은 아무런 효과가 없다. 즉 x의 상태는 마치 연산이 실행되지 않은 것과 같다. Signal() 연산은 항상 세마포의 상태에 영향을 준다. 다음과 같은 예를 살펴 보자.

x.signal() 연산이 프로세스 P의 의해 호출 될 때 조건 x와 연관되어 있는 일시 중단(suspend)된 프로세스 Q가 있다고 가정 할 때 일시 중단된 프로세스 Q가 실행을 재개하도록 허용된다면 신호를 보낸 프로세스 P는 반드시 대기해야 한다. 그렇지 않으면 P와 Q는 모니터 안에서 동시에 활성화 된다. 이 때 두 가지 유형의 가능성이 존재 한다.

• Signal and wait : P는 Q가 모니터를 떠날 때까지 기다리거나 또는 다른 조건을 기다린다.
• Signal and continue : Q는 P가 모니터를 떠날 때까지 기다리거나 또는 다른 조건을 기다린다.

이 옵션은 어느 것이든 정당화 하는 근거는 있지만 P가 이미 모니터 안에서 실행 되고 있으므로 signal and continue 옵션을 선택하는 것이 더 합리적인 것처럼 보인다.

만약 P스레드를 계속 하도록 허용 한다면 Q가 재개될 때까지 Q가 기다리고 있는 논리적인 조건이 이미 참이 아닐 수도 있다. P스레드가 signal()을 선택하면 즉시 모니터를 떠나 Q가 즉시 재개 된다.

[세마포를 이용한 모니터 구현 (Implementing a Monitor Using Semaphore)]

각 모니터마다 mutex라는 세마포가 정의되고 그 초기값은 1이다. 프로세스는 모니터로 들어가기전에 wait(mutex)를 실행하고 모니터를 나온 후에 signal(mutex)를 실행 해야 한다.

신호를 수행하는 프로세스는 실행 재개되는 프로세스가 모니터를 떠나든지 아니면 wait() 할 때까지 그 자신이 다시 기다려야 하므로 next라는 세마포가 추가로 필요해 지고(초기값 0) 이곳에서 신호를 수행하는 프로세스가 일시 중단 된다. 정수형 변수 next_count도 next에서 일시 중단되는 프로세스의 개수를 세기 위해 제공 된다. 이와 같이 하면 상호 배제는 보장 된다.

[모니터 내에서 프로세스 수행 재개 (Resuming processes Within a Monitor)]

일시 중단된 프로세스는 FCFS순으로 재개 된다. 즉 가장 오래 기다렸던 프로세스가 가장 먼저 깨어나는 것이다. 그러나 많은 경우 이 방법이 충분하지는 않다. 연산이 호출 될 때 값이 계산되며 우선순위 번호라 불린다. 일시 중단되는 프로세스의 이름과 함께 저장 된다. Signal()이 수행 되면 가장 작은 우선순위 번호를 가진 프로세스가 다음 번 수행 재개 된다.

프로세스들이 올바른 순서를 지키도록 보장하기 위해서는 RsourceAllocator 모니터와 모니터가 관리하는 자원을 사용하는 모든 프로그램을 검사하여야 한다. 이 시스템에 제대로 동작하는지 알려면 두 가지 조건을 검사하여야 한다.

• 프로세스들이 모니터를 정확한 순서에 맞추어 호출하는지
• 비협조적인 프로세스가 접근제어 프로토콜을 사용하지 않아서 모니터가 정한 상호 배제 규칙 경로를 무시하여 공유 자원을 직접 접근하지 않는다는 것을 보장해야 한다.

이 두 가지 조건이 보장되었을 때에만 시간 종속적인 오류가 일어나지 않고 따라서 원하는 스케줄링이 지켜진다는 것을 보장할 수 있다.

이런 검사는 적은 규모이며 정적인 시스템에서는 가능할지라도 규모가 큰 프로그램 또는 동적인 시스템에서는 비합리 적이다.

[참고자료]

Operating System Concept / 홍릉과학출판사

20_프로세스 임계 구역

n 개의 프로세스 {P0, P1, P2, … Pn}이 있는 시스템에서 각 프로세스는 임계 구역(critical section)이라고 부르는 코드 부분을 포함하고 있으며 그 안에서는 다른 프로세스와 공유하는 변수를 변경하거나 테이블을 갱신하거나 파일을 쓰거나 하는 등의 작업을 수행 한다.

임계 구역의 특징은 "한 프로세스가 자신의 임계 구역에서 수행하는 동안에는 다른 프로세스들은 그들의 임계 구역에 들어갈 수 없다" 각 프로세스는 자신의 임계 구역으로 진입하려면 진입 허가를 요청해야 한다. 이러한 요청을 구현하는 코드 부분을 진입 구역(entry section)이라 한다. 임계 구역 뒤에는 퇴출 구역(exit section)이 따라올 수 있다. 코드의 나머지 부분들을 총칭하여 나머지 구역(remainder section)이라고 부른다.

[임계 구역 문제에 대한 해결 요구 조건]

• 상호 배제(Mutual exclusion) : 프로세스 Pi가 자기 임계 구역에서 실행 된다면 다른 프로세스들은 그들 자신의 임계 구역에서 실행될 수 없다.
• 진행(Progress) : 자기의 임계 구역에서 실행되는 프로세스가 없고 그리고 그들 자신의 임계 구역으로 진입하려고 하는 프로세스들이 있다면 나머지 구역에서 실행 중이지 않은 프로세스들만 다음에 누가 그 임계 구역으로 진입할 수 있는지를 결정하는 데 참여 할 수 있으며 이 선택은 무한정 연결 될 수 있다.
• 한정된 대기(Bounded waiting) : 프로세스가 자기의 임계 구역에 진입하려는 요청을 한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 그들 자신의 임계 구역에 진입 하도록 허용되는 횟수에 제한이 있어야 한다.

[임계 구역 접근]

임의의 한 순간에 많은 커널 모드 프로세스들이 운영체제 안에서 활성화 될 수 있다. 그 결과 운영체제를 구현하는 코드(커널 코드)는 경쟁 조건이 발생하기 쉽다. 운영체제 내에서 임계 구역을 다루기 위해서는 일반적으로 선점형 커널과 비선점형 커널 접근법이 사용된다.

• 선점형 커널 : 프로세스가 커널 모드에서 수행되는 동안 선점되는 것을 허용
• 비선점형 커널 : 커널 모드에서 수행되는 프로세스의 선점을 허용하지 않고 커널 모드 프로세스는 커널을 빠져 나갈 때까지 또는 봉쇄될 때까지 또는 자발적으로 CPU의 제어를 양보할 때까지 계속 수행 된다.

선점형 커널은 한 순간에 커널 안에서 실행중인 프로세스는 하나밖에 없기 때문에 커널 자료구조에 대한 경쟁 조건을 염려할 필요는 없다. 선점형 커널에 대해서는 동일한 주장을 할 수 없기 때문에 공유되는 커널 자료구조에서 경쟁 조건이 발생하는 않는 다는 것을 보장하도록 신중하게 설계 되어야 한다.

[선점형 커널을 선호하는 이유]

선점형 커널은 실시간 프로세스가 현재 커널에서 실행중인 프로세스를 선점할 수 있기 때문에 실시간 프로그래밍에 더 적당하다. 커널 모드 프로세스가 대기중인 프로세스에게 처리기를 양도하기 전에 오랫동안 실행할 위험이 적기 때문에 선점형 커널은 더 응답이 민첩 할 수 있다. 물론 이 효과는 커널 모드 프로세스가 이런 식으로 행동하지 않도록 커널 코드를 설계하여 최소화 할 수 있다.

[참고 자료]

Operating System Concept / 홍릉과학출판사

19_스케줄링 알고리즘

• 우선순위, 라운드 로빈, 다단계 큐, 다단계 피드백큐 스케줄링

[우선순위 스케줄링(Priority Scheduling)]

최단 우선 작업 스케줄링(SJF)은 우선 순위 스케줄링 알고리즘의 특별한 경우다. 우선순위가 각 프로세스들에게 연관되어 있으며 CPU는 가장 높은 우선순위를 가진 프로세스에게 할당 된다. 우선 순위가 같은 프로세스들은 선입 선처리(FCFS)순서로 스케줄 된다. SJF 알고리즘은 우선순위(p)가 예상되는 다음 CPU 버스트의 역인 안순한 우선 순위 알고리즘이다. CPU 버스트가 클수록 우선순위가 낮으면 그 역도 성립한다.

아래 표와 그림은 프로세스 순서대로 도착한 순서와 버스트 시간 그리고 프로세스 되는 스케줄링 간트 차트 이다.

우선순위는 내부적 또는 외부적으로 정의될 수 있다. 내부적으로 정의된 우선순위는 프로세스의 우선순위를 계산하기 위해 어떤 측정 가능한 양들을 사용한다. 우선순위 스케줄링은 선점형 또는 비선점형일 수 있다. 스케줄링 순서이다.

1. 프로세스 준비 완료 큐 도착
2. 새로 도착한 프로세스의 우선순위를 현재 실행 중인 프로세스의 우선순위와 비교
3. 선점형 우선순위 알고리즘은 새로 도착한 프로세스의 우선순위가 현재 실행되는 프로세스의 우선순위보다 높으면 CPU를 선점
4. 비선점형 우선순위 스케줄링 알고리즘은 단순히 준비 완료 큐의 머리 부분에 새로운 프로세스 삽입

우선순위 스케줄링의 알고리즘의 주요 문제는 무한 봉쇄(Idefinite blocking)와 기아 상태(starvation)이다.

• 무한 봉쇄(Idefinite blocking) : 실행 준비는 되어 있으나 CPU를 사용하지 못하는 프로세스는 CPU를 기다리면서 봉쇄된 것으로 간주 될 수 있다.
• 기아 상태(starvation) : 우선 순위 알고리즘의 경우 부하가 높은 컴퓨터에서 우선순위가 높은 프로세스들이 꾸준히 들어와 낮은 우선순위 프로세스들이 CPU를 무한히 대기하는 상태가 발생한다.

낮은 우선 순위의 프로세스들을 무한히 봉쇄하는 문제에 대한 해결방안으로 Aging이 있다. Aging는 오랫동안 시스템에 대기한 프로세스들의 우선 순위를 점진적으로 증가시키는 기법이다.

[라운드 로빈 스케줄링(Round Robin Scheduling)]

시분할 시스템을 위해 설계된 알고리즘. 선입 선처리 스케줄링 방식과 유사하지만 프로세스들 사이를 옮겨 다니기 위해서 선점이 추가된다. 시간 할당량(time quantum) 또는 시간 조각(time slice)이라고 하는 작은 단위의 시간을 정의한다. 시간 할당량은 일반적으로 10~100ms 이다. 준비 완료 큐는 원형 큐(circular queue)로 동작한다. CPU 스케줄러는 준비 완료 큐를 돌면서 한 번에 한 프로세스에게 한 번의 시간 할당량 동안 CPU를 할당한다.

1. 준비 완료 큐를 프로세스들의 선입선출 큐로 유지
2. 새로운 프로세스들은 준비 완료 큐의 꼬리에 추가
3. CPU 스케줄러는 준비 완료 큐에서 첫 번째 프로세스를 선택
4. 한 번의 시간 할당량 이후 인터럽트 되도록 타이머(timer) 설정 후 프로세스 디스패치(dispatch)

다음 예제에서 시간 할당량을 4로 한다면 다음과 같은 스케줄링이 할당 된다.

라운드 로빈 스케줄링 알고리즘에서는 유일하게 실행 가능한 프로세스가 아니라면 연속적으로 두번 이상의 시간 할당량을 할당 받는 프로세스는 없다. 프로세스의 CPU 버스트가 한 번의 시간 할당량을 초과하면 프로세스는 선점되고 준비 완료 큐로 되돌아간다

라운드 로빈 알고리즘의 성능은 시간 할당량 크기에 매우 많은 영향을 받는다. 시간 할당량이 매우 크면 선입 선처리 정책과 같아 지며 매우 적다면 문맥 교환에 의한 성능이 저하 된다. 대부분의 프로세스들이 단일 시간 할당량 안에 다음 CPU 버스트를 끝낸다면 평균 총 처리 시간은 개선된다. 일반적으로 버스트의 80%는 시간 할당량 보다 짧아야 한다.

[다단계 큐 스케줄링(Multilevel Queue Scheduling)]

준비 완료 큐를 다수의 별도 큐로 분류한다. 예를 들어 포어그라운드와 백그라운드 프로세스들을 위해 별도의 큐를 사용하는 것이다.

큐와 큐 사이에 반드시 스케줄링이 있어야 하며 일반적으로 고정 우선순위의 선점형 스케줄링으로 구현 된다. 예를 들어 포어그라운드 큐는 백그라운드 큐보다 절대적으로 높은 우선순위를 가질 수 있다.

[다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)]

다단계 큐 스케줄링 알고리즘에서는 일반적으로 프로세스들이 시스템 진입 시 영구적으로 하나의 큐에 할당 된다. 이러한 방식은 적은 스케줄링 오버헤드가 장점이지만 융통성이 적다.

다단계 피드백 큐 스케줄링 알고리즘은 프로세스가 큐들 사이를 이동하는 것을 허용 한다. 낮은 우선 순위에 너무 오래 대기하는 프로세스는 높은 우선순위의 큐로 이동 할 수 있다.

일반적의 다단계 피드백 큐 스케줄러는 다음 매개변수에 의해 정의 된다.

• 큐의 개수
• 각 큐를 위한 스케줄링 알고리즘
• 한 프로세스를 높은 우선순위 큐로 올려주는 시기를 결정하는 방법
• 한 프로세스를 낮은 우선순위 큐로 강등시키는 시기를 결정하는 방법
• 프로세스가 서비스를 필요로 할 때 프로세스가 들어갈 큐를 결정하는 방법

다단계 피드백 큐는 가장 일반적인 CPU 스케줄링 알고리즘이지만 모든 배겨 변수들의 값을 선정하는 특정 방법이 필요하기 때문에 가장 복잡한 알고리즘이기도 하다.

[참고자료]

Operating System Concept / 홍릉과학출판사

18_스케줄링 알고리즘

• 선입 선처리 스케줄링과 최단 작업 우선 스케줄링

CPU 스케줄링은 준비 완료 큐에 있는 어느 프로세스에게 CPU를 할당할 것인지를 결정하는 문제를 다룬다.

[선입 선처리 스케줄링(First-Come, First-Served Scheduling)]

선입 선처리(FCFS)스케줄링은 CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당 받는 방식으로 선입 선처리 정책의 구현은 선입선출(FIFO) 큐로 쉽게 관리 할 수 있다.

요청 및 처리 순서는 다음과 같다

1. 프로세스가 준비 완료 큐에 진입
2. 프로세스의 프로세스 제어블록(PCB)을 큐의 끝에 연결
3. CPU가 유휴 상태가 되면 준비 완료 큐의 앞 부분에 있는 프로세스에게 할당
4. 실행 상태의 프로세스는 준비 완료 큐에서 제거

선입 선처리 정책은 코드 작성이 쉽고 이해하기 쉬우나 선입 선처리 정책 때문에 평균 대기 시간이 길어 질 수가 있다.

다음의 예를 살펴 보자.

위의 표와 같이 프로세스 실행 순서로 서비스를 받는 다면 다음과 같은 Gantt 차트를 확인 할 수 있다.

프로세스 P1의 대기 시간은 0이며 P2의 대기시간은 24, P3는 27이다. 이들의 평균 대기 시간은 (0 + 24 + 27) / 3 = 17 이다.

다음과 같이 P2, P3, P1이 서비스되면 어떨까?

프로세스 P2의 대기 시간은 0이며 P3의 대기시간은 3, P1의 대기시간은 6이다. 이들의 평균 대기 시간은 (0 + 3+ 6) / 3 = 3 이다. 이러한 감소는 상당히 큰 것이다.

위의 그림을 통해서 선입 선처리 정책의 평균 대기 시간은 최소 시간이 아니며 프로세스 CPU 버스트 시간이 크게 변할 경우 평균 대기 시간도 크게 변할 수 있다.

모든 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 것을 호위 효과(convoy effect)라 한다. 이 효과는 짧은 프로세스들이 먼저 처리되도록 허용 될 때 보다 CPU와 장치 이용률이 저하되는 결과를 초래 한다.

선입 선처리 스케줄링 알고리즘은 비선점형이다. 일단 CPU가 한 프로세스에 할당되면 그 프로세스가 종료하든지 입/출력 처리를 요구하든지 하여 CPU를 방출할 때까지 CPU를 점유 한다. 선입 선처리 알고리즘은 특히 시분할 시스템에서 문제가 되는데 그 이유는 시분할 시스템에서는 각 사용자가 규칙적인 간격으로 CPU의 몫을 얻는 것이 매우 중요하기 때문이다. 한 프로세스가 지나치게 오랜 시간 동안 CPU를 점유하는 것은 매우 큰 손실 이다.

[최단 작업 우선 스케줄링(Shortest-Job First Scheduling)]

최단 작업 우선(SJF) 알고리즘은 각 프로세스에 다음 CPU 버스트의 길이를 연관 시킨다. CPU가 이용 가능해지면 가장 작은 다음 CPU 버스트를 가진 프로세스에게 할당 한다. CPU가 이용 가능해 지면 가장 작은 다음 CPU 버스트를 가진 프로세스에 할당 한다. 두 프로세스가 동일한 길이의 CPU 버스트를 가지면 선입 선처리 스케줄링 방식을 적용 한다.

SJF 스케줄링을 적용한 간트 차트를 만들어 보자.

평균 대기 시간은 (0 + 3 + 6 + 12 + 19) / 5 = 8 이다. 최단 작업 우선 스케줄링은 프로세스의 전체 길이가 아니라 다음 CPU 버스트의 길이에 의해 스케줄이 되기 때문에 다음CPU 요청의 길이를 파악하는 것이 중요하다.

일괄 처리 시스템에서 장기 스케줄링을 위해서는 사용자가 작업을 제출 할 때 지정한 프로세스 시간 제한 길이를 이용 할 수 있다. 그러므로 사용자들이 프로세스 시간 제한을 정확하게 예상하도록 하는 동기가 된다. SJF 스케줄링은 장기 스케줄링에 자주 사용 된다.

SJF 알고리즘이 최적이긴 하지만 다음 CPU의 버스트 길이를 알 수 있는 방법이 없기 때문에 단기 CPU 스케줄링 수준에서는 구현 할 수 없다.

한 가지 접근 방식은 SJF 스케줄링과 비슷한 방법을 사용 하는 것으로 다음 CPU 버스트의 길이를 알 수는 없으나 다음의 버스트가 이전의 CPU 버스트와 길이가 비슷하다고 기대하여 예측 하는 것이다. 그러므로 다음 CPU 버스트 길이의 근사값을 계산해 가장 짧은 예상 CPU 버스트를 가진 프로세스를 선택 한다.

SJF는 선점형 또는 비선점형일 수 있다. 앞의 프로세스가 실행 되는 동안 새로운 프로세스가 준비 완료 큐에 도착하면 선택이 발생 한다. 새로은 프로세스가 현재 실행되고 잇는 프로세스의 남은 시간보다도 더 짧은 CPU 버스트를 가질 수도 있다. 선점형 SJF 알고리즘은 현재 실행하는 프로세스를 선점할 것이고 반면에 비선점형 SJF 알고리즘은 현재 실행하고 있는 프로세스가 자신의 CPU 버스트를 끝내도록 허용 한다.

선점형 SJF는 최소 잔여 시간 우선(shortest remaining time first) 스케줄링 이라고 불린다.

선점형 SJF의 평균 대기 시간은 ((10-1) + (1-1) + (17-2) + (5-3)) / 4 = 6.5 이다.

비선점형 SJF 평균 대기 시간은 7.75 이다.

17_CPU 스케줄링 기본 개념

CPU 스케줄링(scheduling)은 다중 프로그램 운영체제의 기본 이다. 운영체제는 CPU를 프로세스들 간에 교환 함으로써 컴퓨터를 보다 생산적으로 만든다.

스레드를 지원하는 운영체제에서는 프로세스가 아니라 커널 수준의 스레드를 스케줄링 한다. 그러나 프로세스 스케줄링과 스레드 스케줄링 용어는 상호 교환적으로 사용 되며 일반적인 스케줄링을 논의하는 경우에는 프로세스 스케줄링을 사용하고 스레드에 국한된 개념을 가리키는 경우에 스레드 스케줄링이라는 용어를 사용한다.

단일 처리기 시스템에서는 한 순간에 오직 하나의 프로세스만이 실행 될 수 있다. 다중 프로그래밍의 목적은 CPU 이용률을 최대화 하기 위해 항상 실행중인 프로세스를 가지게 하는데 있다.

스케줄링은 운영체제의 기본 기능으로 다중 프로그래밍에서는 CPU의 대기 시간을 활용하기 위해 어느 한 순간에 다수의 프로세스들을 메모리 내에 유지한다. 어떤 프로세스가 대기해야 할 경우 운영체제는 CPU를 그 프로세스로부터 회수하여 다른 프로세스에 할당 한다. 이러한 패턴은 반복되며 하나의 프로세스가 대기해야 할 때마다 다른 프로세스가 CPU 사용을 양도 받을 수 있다.

따라서 거의 모든 컴퓨터 자원들은 사용되기 전에 스케줄링 되며 CPU의 스케줄링은 운영체제의 핵심이 된다.

[CPU 입/출력 버스트 사이클(CPU I/O Burst Cycle)]

프로세스 실행은 CPU 실행과 입/출력 대기의 사이클로 구성된다. 프로세스들은 이들 두 상태 사이를 교대로 이동 한다. 프로세스 실행은 CPU 버스트(Burst)로 시작된다. 뒤이어 입/출력 버스트가 발생하고 그 뒤를 이어 또 다른 CPU 버스트가 발생하며 이어 또 다른 입/출력 버스트 등으로 진행 된다. 결국 마지막 CPU 버스트가 또 다른 입/출력 버스트가 뒤따르는 대신 실행을 종료하기 위한 시스템 요청과 함께 끝난다.

입출력 중심의 프로그램은 전형적으로 짧은 CPU 버스트를 많이 가지며 CPU 지향 프로그램은 다수의 긴 CPU 버스트를 가진다. 이러한 분포는 CPU 스케줄링 알고리즘을 선택하는데 매우 중요 하다.

[CPU 스케줄러(CPU Scheduler)]

CPU가 유휴 상태가 될 때 마다 운영체제는 준비 완료 큐에 있는 프로세스들 중에서 하나를 선택해 실행 해야 한다. 선택 절차는 단기(short term) 스케줄러(CPU 스케줄러)에 의해 수행 된다.

스케줄러는 실행 준비가 되어 있는 메모리 내의 프로세스들 중에서 선택하여 CPU에 할당 한다.

준비 완료 큐는 반드시 선입선출(FIIO)방식의 큐가 아니라는 것에 유의하며 순서 없는 연결 리스트로 구현 할 수 있다. 큐에 있는 레코드들은 일반적으로 프로세스들의 프로세스 제어 블록(PCB)이다.

• 프로세스 개념 : http://sqlmvp.kr/140189245176

[선점 스케줄링(Preemtive Scheduling)]

CPU 스케줄링은 다음 네 가지 상황에서 발생 할 수 있다.

• 한 프로세스가 실행 상태에서 대기 상태로 전환 될 때.(종료되기를 기다리기 위해 wait를 호출 할 때)
• 프로세스가 실행 상태에서 준비 완료 상태로 전환 될 때
• 프로세스가 대기 상태에서 준비 완료 상태로 전환 될 때
• 프로세스가 종료 할 때

1,4의 스케줄링 방법을 비선점(Non-preemptive)또는 협조적(coorperative)이라고 하며 2.3번의 스케줄링을 선점(Preemptive)이라고 한다.

선점 스케줄링은 공유 자료에 대한 접근을 조정하는 데 필요한 비용을 유발하며 커널 설계에 영향을 준다. 시스템 호출을 처리할 동안 커널은 한 프로세스를 위한 활동으로 바쁠 수 있다. 그러한 활동은 (입/출력 큐와 같은)중요한 커널 자료 변경을 포함 할 수 있다. 만약 이러한 변경 도중에 해당 프로세스가 선점되어 동일한 구조를 읽거나 변경할 경우 혼란이 발생한다.

인터럽트는 어느 시점에서든 일어 날 수 있으며 커널에 의해서 항상 무시 될 수는 없기 때문에 인터럽트에 의해서 영향을 받는 코드 부분은 반드시 동시 사용으로부터 보호되어야 한다.

운영체제는 항상 인터럽트를 받아들일 필요가 있는데 그렇지 않으면 입력을 잃어버리거나 출력이 겹쳐서 쓰여질 수 있다. 이러한 코드 부분은 다수 프로세스가 병행으로 접근할 수 없도록 그 진입점에서 인터럽트를 불능화 하고 출구에서 인터럽트를 다시 가능화 한다.

인터럽트의 불능화 코드는 자주 발생해서는 안되며 아주 적은 수의 명령어들만 포함하여야 한다는 것을 주의하자.

[디스패처(Dispatcher)]

디스패처는 CPU의 제어를 단기 스케줄러가 선택한 프로세스에게 주는 모듈이며 다음의 작업을 포함한다.

• 문맥을 교환 하는 일
• 사용자 모드로 전환하는 일
• 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동(jump)하는 일

디스패처는 모든 프로세스의 문맥 교환 시 호출 되므로 가능한 빨리 수행되어야 한다. 디스패처가 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는데 소요되는 시간을 디스패치 지연(Dispatch latency)라고 한다.

[참고자료]

Operating System Concept / 홍릉과학출판사

16_스레드 이슈(Threading Issues)

다중 스레드 프로그램에서 발생하는 이슈에 대해서 알아 보자.

[Fork() 및 Exec() 시스템 호출]

다중 스레드 프로그램에서는 fork()와 exec() 시스템 호출의 의미가 달라질 수 있다. 한 프로그램의 스레드가 fork()를 호출하면 새로운 프로세스는 모든 스레드를 복사 또는 fork()시스템을 호출한 스레드만 복제 한다.

Exec() 시스템을 호출하면 exec()의 매개변수로 지정된 프로그램이 모든 스레드를 포함한 전체 프로세스를 대체 시킨다. fork()를 부르자마자 다시 exec()을 부른다면 exec()에서 지정한 프로그램이 곧 모든 것을 다시 대체할 것이기 때문에 모든 스레드를 복제해서 만들어주는 것은 불필요하다. Fork() 후 exec()를 하지 않는다면 새 프로세스는 모든 스레드들을 복제 해야 한다.

[취소(cancellation)]

스레드 취소는 스레드가 끝나기 전에 그것을 강제 종료시키는 작업이다. 취소 되어야 할 스레드를 목적 스레드라고 하며 두 가지 방식으로 발생 할 수 있다.

• 비동기식 취소(asynchronous cancelation) : 한 스레드가 즉시 목적 스레드를 강제 종료 한다
• 지연 취소(Deferred cancellation) : 목적 스레드가 주기적으로 자신이 강제 종료되어야 할지를 확인 한다.

스레드 취소를 어렵게 만드는 것은 취소 스레드의 할당된 자원 문제(스레드의 자원 공유 및 자료 구조 갱신 중 취소) 때문이다.

• 비동기 취소는 운영체제가 취소된 스레드로부터 자원을 회수 화지 못하여 사용 가능 상태로 못 만들 수 있다.
• 지연 취소에서 목적 스레드는 취소 예정이라고 표시하지만 실제 취소는 목적 스레드가 취소 여부를 결정하기 위해 플래그를 검사한 이후에 일어 난다. 스레드들은 자신이 취소되어도 안전하다고 판단되는 시점에서 취소 여부를 검사할 수 있으며 Pthread는 이 지점을 취소점(cancellation point)라 한다.

[신호 처리(Signal Handing)]

신호는 알려줄 사건의 근원지나 이유에 따라 동기식 또는 비동기식으로 전달 될 수 있으며 다음과 같은 형태로 전달 된다.

1. 신호는 특정 사건이 일어나야 생성 된다.
2. 신호가 생성되면 프로세스에게 전달 된다.
3. 신호가 전달되면 반드시 처리 되어야 한다.

동기식 신호의 예는 불법적인 메모리 접근, 0으로 나누기 등이 있으며 동기식 신호는 신호를 발생시킨 연산을 수행한 동일한 프로세스에게 전달 된다.

비동기식 신호의 예는 외부로부터 발생되는 프로세스 신호이며 <control><c>같은 특수한 키를 눌러 프로세스를 강제 종료 또는 타이머가 만료되는 경우를 포함한다. 비동기식 신호는 통상 다른 프로세스에게 전달 된다.

디폴트 신호 처리기는 커널에 의해 실행 된다. 이 신호를 처리하기 위하여 호출되는 사용자 정의신호 처리기에 의해 다른 방식으로 처리 될 수 있다. 신호에 따라 무시 또는 강제 종료 된다. 다중 스레드 프로그램에서의 처리는 다음과 같다.

1. 신호가 적용될 스레드들에게 전달 한다.
2. 모든 스레드들에게 전달한다
3. 일부 스레드에게만 선택적 전달 한다.
4. 특정 스레드가 모든 신호를 전달받도록 지정한다

동기식 신호는 그 신호를 야기한 스레드들에게 전달되어야 하고 다른 스레드들에게는 전달 되면 안된다. 비동기 스레드의 신호는 명확하지가 않아 프로세스 내 모든 스레드들에게 전달 되어야 한다.

Windows는 신호를 명시적으로 지원하지 않지만 비동기식 프로시저 호출(Asynchronous Procedure Call, APC)를 사용해 대리 실행(emulate)할 수 있다. APC는 사용자 스레드들이 특정 사건의 발생을 전달받았을 때 호출될 함수를 지정할 수 있다.

[스레드 풀(thread pool)]

요청마다 새로운 스레드를 생성하는 것은 새로운 프로세스를 생성하는 것보다는 확실히 오버헤드가 적지만 다음과 같은 문제점을 가지고 있다.

• 스레드를 생성하는데 소요되는 시간(사용 후 폐기될 용도라면 더 크게 느껴진다)
• 요청마다 새로운 스레드를 생성하여 제공한다면 시스템에서 동시에 실행 할 수 있는 스레드의 한계를 정해야 한다. 무한정 생성시 언젠가는 자원이 고갈되기 때문이다.

위의 두 가지 사례를 해결하기 위하여 스레드 풀을 이용한다. 스레드 풀은 프로세스를 시작 할 때 미리 일정한 수의 스레드들을 풀로 만들어 두는 것이다. 이 스레드들은 평소에 하는 일 없이 대기 하다가 요청이 들어오면 풀에서 할당한다. 요청 작업이 완료 되면 스레드는 다시 풀로 돌아가 다음 작업을 대기 한다. 풀에 남아 있는 스레드가 모두 소진되면 서버는 자유 스레드가 생길 때까지 기다린다.

스레드 풀의 스레드 개수는 CPU 수, 메모리 용량, 동시 요청 클라이언트 최대 개수 등을 고려하여 정한다. 스레드 풀 활용도를 동적으로 풀의 크기를 바꾸어 줄 수 도 있다. 이러한 구조는 부하가 작은 시스템에서 더 작은 풀을 유지하므로 적은 메모리를 사용한다.

[스레드 데이터(Thread Specific Data)]

스레드의 장점으로 한 프로세스에 속한 스레드들은 그 프로세스의 자료를 모두 공유한다. 그런 각 상황에 따라서 스레드들은 자기만 접근할 수 있는 자료를 가질 필요가 있다. 이러한 자료를 스레드별 데이터라고 한다. Win32, Pthread, JAVA를 포함한 대부분의 스레드 라이브러리들은 스레드별 데이터를 지원한다.

[스케줄러 액티베이션(Scheduler Activation)]

다중 스레드는 라이브러리와의 통신문제를 고려해야 한다. 다대다 또는 두 수준 모델을 구현하는 많은 시스템들은 사용자와 커널 스레드 사이에 중간 자료 구조를 둔다. 이 자료구조는 통상 경량 프로세스 또는 LWP라 부른다.

사용자 스레드 라이브러리와 커널 스레드간의 통신방법 중의 하나는 스케줄러 액티베이션(scheduler activation)이라고 알려진 방법이다.

1. 커널은 가상 처리기(LWP) 집합을 제공하고 응용프로그램은 사용자 스레드를 가용한 가상 처리기로 스케줄 한다.
2. 커널은 응용 프로그램에게 특정 사건에 대해 알려 주어야 한다. 이를 Upcall 이라 한다.
3. Upcall은 스레드 라이브러리의 upcall 처리기에 의해 처리되고 upcall 처리기는 가상 처리기 상에서 실행 되어야 한다.
4. 커널은 새로운 가상 처리기를 응용 프로그램에게 할당한다.
5. 응용프로그램은 새로운 가상 처리기 상에서 upcall 처리기를 수행하고 이 upcall 처리기는 봉쇄 스레드의 상태를 저장하고 스레드가 실행 중이던 가상 처리기를 반환한다.
6. Upcall 처리기는 새로운 가상 처리기에서 실행 가능한 다른 스레드를 스케줄러 한다.
7. 봉쇄 스레드가 기다리던 사건이 발생하면 커널은 이전에 봉쇄되었던 스레드가 이제 실행 가능 하다는 사실을 알려주는 또 다른 upcall을 스레드 라이브러리에 전달한다.
8. 커널은 새로운 가상 처리기를 할당하거나 사용자 스레드 하나를 할당하여 처리기에서 upcall 처리기를 실행 한다.
9. 봉쇄가 풀린 스레드를 실행 가능 상태로 표시한 후 응용프로그램은 가용한 가상 처리기 상에서 다른 실행 가능한 스레드를 실행 한다.

[참고자료]

Operating System Concept / 홍릉과학출판사

Thread Pool Pattern : http://en.wikipedia.org/wiki/Thread_pool_pattern

15_스레드 라이브러리

스레드 라이브러리(thread library)는 프로그래머에게 스레드를 생성하고 관리하기 위한 API를 제공한다. 스레드 라이브러리를 구현하는데는 두 가지 방법이 있다.

• 커널의 지원 없이 완전히 사용자 공간에만 라이브러리를 제공하는 것. 라이브러리를 위한 모든 코드와 자료구조는 사용자 공간에 존재한다. 라이브러리의 함수를 호출하는 것은 시스템 호출이 아닌 사용자 공간의 지역 함수를 호출하게 된다.
• 운영체제에 의해 지원되는 커널 수준의 라이브러리를 구현. 라이브러리를 위한 코드와 자료구조는 커널 공간에 존재한다. 라이브러리 API를 호출하는 것은 커널 시스템 호출을 사용한다.

[Pthread]

Pthread는 POSIX(IEEE 10031.1c)가 스레드 생성과 동기화를 위한 제정한 표준 API이다. 이것은 스레드의 동작에 관한 명세일 뿐 그것 자체를 구현한 것은 아니다. Solaris, Linux, Mac OSX, UNIX를 포함한 많은 시스템들이 Pthread 명세를 구현하고 있다. Windows 계열의 운영체제들을 구현은 퍼블릭 도메인(Public Domain)에서 쉐어웨어(shareware)형태로 얻을 수 있다.

[Win32 스레드 (Win32 Thread)]

Win32 스레드 라이브러리를 이용하여 스레드를 생성하는 기술은 많은 점에서 Pthread기법와 유사하다. Pthread 버전과 마찬가지로 개별 스레드가 서로 공유하는 자료는 전역변수로 선언된다. (DWORD 데이터형 유형은 부호가 없는 32비트 정수이다.)

[Java 스레드 (Java Thread)]

스레드는 Java 프로그램의 프로그램 실행의 근본적이 모델이고 Java 언어와 API는 스레드의 생성과 관리를 지원하는 풍부한 특성을 제공한다. 모든 Java 프로그램은 적어도 하나의 단일 제어 스레드를 포함하고 있다. 단지 main() 메소드로만 이루어진 단순한 Java 프로그램조차 JVM 내의 하나의 단일 스레드로 수행 된다.

Java 프로그램에서 스레드를 생성하는 기법에는 두 가지가 있다.

• Thread 클래스로부터 파생된 새로운 클래스를 생성하고 Thread 클래스의 run() 메소드를 무효화 (override)하는 것
• runnable 인터페이스를 구현하는 클래스를 정의하는 것. 클래스가 runnable 을 구현 할 때 run() 메소드를 구현해야 한다. run() 메소드를 구현하는 코드는 별도의 스레드로 실행 된다.

Win32와 Pthread에서는 공유 데이터가 단순히 전역 변수로 선언되기 대문에 스레드간의 자료 공유를 쉽게 할 수 있다. Java는 순수 객체지향 언어이기 때문에 그런 전역 변수의 개념을 제공하지 않는다. 만일 Java 프로그램에서 둘 이상의 스레드가 자료를 공유해야 한다면 공유 객체에 대한 참조를 적당한 스레드에게 전달함으로써 공유한다.

[참고자료]

• Win32 thread pool : http://www.codeproject.com/Articles/11976/Win32-Thread-Pool
• Operating System Concept / 홍릉과학 출판사

14_스레드 개념과 다중 스레드

스레드(thread)는 CPU 이용의 기본 단위다. 스레드는 스레드 ID, 프로그램 카운터, 레지스터 집합, 스택 으로 구성 된다. 스레드는 같은 프로세스에 속한 다른 스레드와 코드, 데이터 섹션, 열린 파일이나 신호와 같은 운영체제 자원들을 공유 한다.

프로세스에 하나의 제어 모델이 있으면 단일 스레드 이며, 프로세스가 다수의 제어 스레드를 가진다면 다중 스레드 모델이다.

[다중 스레드의 장점]

다중 스레드 프로그래밍을 장점을 크게 네 가지로 분류하면 다음과 같다.

• 응답성(Responsivness) : 응용 프로그램의 일부분이 봉쇄 되거나 긴 작업을 수행하는 경우에도 프로그램의 수행이 계속 되는 것을 허용 함으로써 사용자에 대한 응답성을 증가 시킨다.
• 자원 공유(Resource Sharing) : 스레드는 자동적으로 그들이 속한 프로세스의 자원들과 메모리를 공유 한다. 코드와 자료 공유의 이점은 한 응용 프로그램이 같은 주소 공간 내에 여러 개의 다른 작업을 하는 스레드를 가질 수 있다.
• 경제성(Economy) : 프로세스 생성을 위해 메모리와 자원을 할당하는 것은 비용이 많이 든다. 스레드는 자신이 속한 프로세스의 자원들을 공유하기 때문에 스레드를 생성하고 문맥맥 교환하는 것 보다 더 경제적이다.
• 다중 처리기 구조의 활용 (Utilization of multiprocessor architectures) : 다중 스레드의 이점은 다중 처리기 구조에서 더욱 증가 된다. 각각의 스레드가 다른 처리기에서 병렬로 수행 될 수 있기 떄문이다. 단일 스레드는 CPU가 많다고 하더라도 단지 한 CPU에서만 실행된다. 다중 CPU에서 다중 쓰레딩을 하면 병렬성이 증가 된다.

스레드를 위한 지원은 사용자 스레드(user thread)와 커널 스레드(kernel thread)가 있다

• 사용자 스레드 : 커널 위에서 지원되며 커널의 지원 없이 관리 된다.
• 커널 스레드 : 운영체제에 의해 직접 지원된고 관리 되며 대부분의 운영체제들은 커널 스레드를 지원 한다.

[다중 스레드 모델]

다대일 모델(Many-To-One Model) : 다대일 모델은 많은 사용자 수준 스레드를 하나의 커널 스레드로 매핑 한다. 스레드 관리는 사용자 공간의 스레드 라이브러리에 의해 행해 진다. 스레드 관리에는 효유율적이지만 한 스레드가 긴 작업을 실행 할 경우 나머지 작업들은 대기하게 된다. 다중 CPU환경에서도 병렬로 작업을 처리 할 수가 없다.

일대일 모델(One-To-One Model) : 일대일 모델은 각 사용자 스레드를 각각 하나의 커널 스레드로 매핑 한다. 이 모델은 하나의 스레드가 긴 작업을 처리하는 동안에도 다른 스레드가 실행 될 수 있기 때문에 다대일 모델보다 더 많은 병렬성을 제공 한다. 이 모델의 단점은 사용ㅈ 수준 스레드를 생성 할 때 그에 따른 커널 스레드를 생성해야 한다는 것이다. 커널 스레드를 생성하는 오버헤드로 응용프로그램의 성능저하가 발생 할 수도 있다.

다대다 모델(Many-To-Many Model) : 다대다 모델은 여러 개의 사용자 스레드를 그보다 작거나 같은 수의 커널 스레드로 다중화 한다. 커널 스레드의 수는 응용 프로그램이나 특정 기계에 따라 결정 된다. 응용프로그램은 단일 처리기보다 다중 처리기에 더 많은 커널 스레드를 할당 받을 수 있다. 개발자는 필요한 만큼 많은 사용자 수준 스레드를 생성 할 수 있으며 그에 상응하는 커널 스레드가 다중 처리기에서 병렬로 수행 된다. 스레드가 긴 작업등의 호출을 발생 시켰을 때 커널이 다른 스레드의 수행을 스케줄링 한다.

다대다 모델의 변형은 많은 사용자 스레드를 적거나 같은 수의 커널 스레드로 다중화 시키는 것을 유지하지만 하나의 사용자 스레드가 하나의 커널 스레드에 종속되도록 허용 한다. 이 변형은 두 수준 모델(Two-Level Model)이라고 불리며 HP-UX, UNiX Tru64 모델이 지원 하였다.

[참고자료]

Operating System Concept / 홍릉과학출판사

13_클라이언트 서버 환경에서 통신

클라이언트 서버 환경의 통신에서도 메시지 전달 기법을 이용하여 통신 한다. 통신 방식에서 3가지 유형에 대해서 살펴 보자.

[소캣(Socket)]

소켓(socket)은 통신의 극점(EndPoint)를 뜻한다. 두 프로세스가 네트워크 상에서 통신을 하려면 양 프로세스마다 하나씩 총 두 개의 소켓이 필요하다. 클라이언트 프로세스가 연결을 요청하면 호스트 컴퓨터가 포트 번호를 부여한다. 이때 포트 번호는 1024(0~1024는 시스템 예약)보다 큰 임의의 정수가 사용된다. 모든 연결은 유일 해야 한다.

소켓을 이용한 통신은 분산된 프로세스들 간에 널리 사용되고 효율적이기는 하지만 너무 저수준이다. 우선 소켓은 쓰레드들 간에 구조화되지 않은 바이트 스트림만을 통신하도록 하기 때문이다. 이러한 원시적인 바이트 스트림 자료를 구조화 하여 해석하는 것은 클아이언트와 서버의 주요 작업이 된다.

[원격 프로시저 호출(remote Procedure Call, RPC)]

RPC는 네트워크에 연결되어 있는 두 시스템 사이의 통신을 위해 프로시저 호출을 추상화 하기 위한 방편으로 설계 되었다.

IPC 방식과는 달리 RPC 통신에서는 전달되는 메시지는 구조화 되어 있고 따라서 데이터의 패킷 수준을 넘어서게 된다.

각 메시지에는 원격지 포트에서 listen 중인 RPC 데몬(daemon)의 주소가 지정되어 있고 수행되어야 할 함수의 식별자, 그리고 그 함수에게 전달 되어야 할 매개변수가 포함된다. 그리고 요청된 함수가 실행되고 어떤 출력이든지 별도의 메시지를 통해 요청자에게 반환 된다.

포트는 단순히 메시지 패킷의 시작 부분에 포함되는 정수이다. 시스템에서 지원되는 여러 서비스를 구별하기 위해 포트를 여러 개 가질 수 있으며 원격 프로세스가 어떤 서비스를 받고자 하면 그 서비스에 대응되는 적절한 포트 주소로 메시지를 보내야 한다.

RPC는 클라이언트가 원격 호스트의 프로시저를 호출하는 것을 마치 자기의 프로시저를 호출하는 것처럼 해 준다. 보통 프로시저마다 다른 스텁(Stub)이 존재 한다. 클라이언트가 원격 프로시저를 호출하면 RPC는 그 에 대응하는 스텁을 호출 하고 원격 프로시저가 필요로 하는 매개변수를 건네 준다. 그러면 스텁이 원격 서버의 포트를 찾고 매개변수를 정돈(marshall)한다. 그 후 스텁은 메시지 전달 기법을 사용하여 서버에게 메시지를 전송 한다. 이에 대응되는 스텁이 서버에도 존재하여 서버 측 스텁이 메시지를 수신한 후 적절한 서버의 프로시저를 호출한다. 필요한 경우 반환 값들도 동일한 방식으로 다시 되돌려 준다.

주의할 점은 클라이언트와 서버의 자료 표현 방식이 다를 경우와 호출의 의미에 관한 것이다. 지역 프로시저의 경우 극단적인 경우에만 실패 하지만 RPC 경우는 네트워크 오류 때문에 실패할 수 도 있으며 메시지가 중복되어 여러 번 호출 될 수도 있다. 이 문제의 해결은 운영체제가 메세지가 최대 한번 수행되는 것이 아니라 정확히 한번 처리 되도록 보장하는 것을 알 수 있도록 구현 하는 것이다.

또 하나의 문제는 클라이언트와 서버간의 통신 문제이다. 일반적인 프로시저의 경우 바인딩(binding)이라는 작업이 링크/적재/실행 시점에 행해진다. 이때 프로시저의 이름이 프로시저의 메모리 주소로 변환 된다. 이와 마찬가지로 RPC도 클라이언트와 서버 포트를 바인딩 해야 하는데 두 시스템에는 공유 메모리가 없기 때문에 상대방에 대한 완전한 정보가 없다. 클라이언트는 서버의 포트 번호를 어떻게 알 수 있을까? 두 가지 방법이 사용 된다.

• 고정 포트 방법 : 서버가 임의로 포트를 바꿀 수 없음으로 고정된 포트를 사용 할 수 있다.
• 동적 바인딩 방법 : 운영체제는 미리 정해져 있고 고정 RPC 포트를 통해 동적으로 바인딩 한다. 클라이언트가 자신이 수행하기를 원하는 RPC 이름을 담고 있는 메시지를 랑데부 데몬에게 보내서 RPC이름에 대응하는 포트 번호가 무엇인지 요청하여 알 수 있다.

[원격 메소드 호출(Remote Method Invocation)]

원격 메소드 호출(Remote Method Invocation)은 JAVA가 제공하는 RPC 기능이다. RMI는 쓰레드로 하여금 원격 객체에 있는 메소드를 호출 할 수 있게 해준다. 자신과 동일한 JVM(java Virtual Machine)에 있지 않는 객체를 원격이라고 정의 하기 때문에 실제 물리적인 다른 컴퓨터일 수도 있으며 같은 컴퓨터에 있으면서도 별도의 JVM에 속한 객체 일수도 있다.

RMI는 RPC와 크게 두 가지 다른 점이 있다.

• RPC는 절차적 프로그래밍을 지원하여 오직 원격 프로시저/ 함수만 호출 될 수 있지만 RMI는 객체 기반으로 원격 객체의 메소드 호출을 지원한다.
• RPC에서는 원격 프로시저에 전달되는 매개변수가 일반적인 자료구조 이지만 RMI에서는 매개변수로 객체 자체를 원격 메소드에게 전달 해 줄 수 있다. JAVA 프로그램이 매개변수로 객체 자체를 호출할 수 있도록 해준다면 네트워크에 분산되어 있는 JAVA 응용프로그램을 개발 할 수 있다.

[참고자료]

Operating System Concept / 홍릉과학출판사

12_프로세스간 통신

운영체제 내에서 수행되는 병행 프로세스가 시스템에서 실행중인 다른 프로세스들에 영향을 주거나 받지 않는다면 독립적인 프로세스라 하며 영향을 준다면 협력적인 프로세스라 한다.

프로세스 협력을 허용하는 이유는 다음과 같다.

• 정보 공유(Information Sharing) : 여러 사용자가 동일한 정보를 병행적으로 접근할 수 있는 환경을 제공해야 한다.(공유 파일 등)
• 계산 가속화(Computation Speed UP) : 특정 작업을 서브 태스크로 나누어 각각 다른 서브 태스크들과 병렬로 실행 되어야 한다.
• 모듈성(Modularity) : 시스템 기능을 별도의 프로세스들 또는 쓰레드 들로 나누어 모듈식 형태로 시스템을 구성하기를 원할 수 있다.
• 편의성(Convenience) : 개별 사용자들이 한순간에 작업할 많은 태스크를 가질 수도 있다.(컴파일 중 문서 편집, 인쇄 작업의 병행 등)

협력적 프로세스들은 자료와 정보를 공유하기 위해 공유 메모(Shared Memory)리 기법과 메시지 전달(Message Passing) 두 가지 모델을 기본적으로 사용 한다.

[공유 메모리 시스템(Shared Memory System)]

프로세스간 통신에서 공유 메모리 영역을 구축 해야 한다. 통상 공유 메모리 영역은 공유 메모리 세그먼트를 생성하는 프로세스의 주소 공간에 위치 한다. 이 공유 메모리 세그먼트를 이용하여 통신하고자 하는 다른 프로세스들은 이 세그먼트를 자신의 주소 공간에 추가 하여야 한다.

메모리 영역을 구축 할 때 시스템을 호출 하며 공유 메모리 시스템이 구축 되면 모든 접근은 일반적인 메모리 접근으로 처리 되며 커널의 도움은 필요 없다. 하나의 시스템 안에서 통신할 때 메모리 속도로 접근하기 때문에 최대 속도와 편의성을 제공한다.

일반적으로 운영체제는 한 프로세스가 다른 프로세스의 메모리가 접근하는 것을 금지 한다. 공유 메모리는 둘이 상의 프로세스가 접근을 허용해야 한다. 그런 후에 공유 메모리 영역을 읽고 쓰면서 정보를 공유 한다.

자료 형식과 이들의 위치는 운영체제가 관여하지 않으며 이들 프로세스에 의해 결정이 되며 프로세스들은 동시에 동일한 위치에 쓰지 않도록 설계되어야 한다.

협력하는 프로세스를 설명하기 위해 일반적으로 생산자-소비자 패러다임을 설명하는데 생산자 프로세스는 정보를 생산하고 소비자 프로세스는 정보를 소비한다. 생산자와 소비자는 프로세스들이 병행으로 실행 되도록 하려면 생산자가 채워놓고 소비자가 소비할 수 있는 항목들의 버퍼가 반드시 있어야 한다. 이 버퍼는 생산자와 소비자가 공유하는 메모리 영역에 위치 하게 되며 2가지 버퍼 유형이 있다.

• 무한 버퍼(Unbounded Buffer) : 생산자와 소비자 문제에서는 버퍼 크기에 실질적인 한계가 없다. 소비자는 새로운 항목을 기다려야만 할 수도 있지만 생산자는 항상 새로운 항목을 생산할 수 있다.
• 유한 버퍼(Bounded Buffer) : 버퍼 크기가 고정되어 있다고 가정하며 이 버퍼가 비어 있으면 소비자는 반드시 대기 해야 하며 모든 버퍼가 채워져 있으면 생산자가 대기 하여야 한다.

[메시지 전달 시스템(Message Passing System)]

동일한 주소 공간을 공유하지 않고도 프로세스들이 통신을 하고 그들의 동작을 동기화 할 수 있도록 허용 하는 기법이다. 통신하는 프로세스들이 네트워크에 의해 연결된 다른 컴퓨터들에 존재할 수 있는 분산 환경에서 특히 유용하다.

메시지 전달 모델은 충돌을 회피할 필요가 없기 때문에 적은 양의 자료를 교환하는데 유용하다. 또한 컴퓨터간 통신을 할 때 공유 메모리 모델보다 구현하기 쉽다. 하지만 시스템 호출을 사용하여 구현 되므로 커널 간섭 등의 부가적인 시간 소비 작업들을 필요로 한다.

메시지 전달 시스템은 최소한 두 가지 연산(Send Message, Receive Message)을 제공한다. 프로세스가 보낸 메시지는 고정 또는 가변일 수 있다. 고정의 경우 시스템 구현은 간단하지만 프로그래밍에 제약이 있으며 가변의 경우 고정보다 복잡하지만 프로그래밍 작업은 더욱 간단해 진다.

명명(Naming) : 통신을 원하는 프로세스들은 서로를 가리킬 수 있는 방법이 있어야 한다. 이들은 직접 또는 간접 통신을 사용 한다.

직접 통신에서 통신을 원하는 각 프로세스는 통신의 수신자 또는 송신자의 이름을 명시해야 한다. 이 기법의 단점으로는 프로세스 정의의 제한된 모듈성에 있다. 프로세스 이름을 바꾸면 모든 다른 프로세스의 정의를 검사할 필요가 있을 수 있다. Send(), Receive() 프리미티브들의 특성을 살펴 보자.

• 대칭성
  • Send(P, message) – 프로세스 P에게 메시지를 전송 한다.
  • Receive(Q, message) – 프로세스 Q로부터 메시지를 수신한다.
  • 통신을 원하는 각 프로세스 상들 사이에 연결이 자동적으로 구축 된다. 프로세스들은 통신하기 위해 서로 상대방의 Identity만 알면 된다.
  • 연결은 정확히 두 프로세스들 사이에만 연관 된다.
  • 통신하는 프로세스들의 각 쌍 사이에는 정확하게 하나의 연결이 존재해야 한다.

• 비대칭성
  • Send(P, message) – 프로세스 P에게 메시지를 전송 한다.
  • Receive(id, message) – 임의의 프로세스로부터 메시지를 수신한다. 변수 ID는 통신을 발생시킨 프로세스의 이름으로 설정 된다.

간접 통신은 메일박스(Mailbox) 또는 포트(port)로 송신되고 그것으로부터 수신 된다. 각 메일박스는 고유 ID를 가진다. Send(), Receive() 프리미티브 특성을 살펴보자.

• Send(A, message) – 메시지를 메일박스 A로 송신한다
• Receive(A, message) – 메시지를 메일박스 A로부터 수신한다.
• 한 쌍의 프로세스들 사이의 연결은 이들 프로세스가 공유 메일박스를 가질 때만 구축 된다.
• 연결은 두 개 이상의 프로세스들과 연관 될 수 있다.
• 통신하고 있는 가 프로세스들 사이에는 다수의 서로 다른 연결이 존재할 수 있고 각 연결은 하나의 메일 박스에 대응된다.

동기화(Synchronization) : 프로세스간 통신은 Send()와 Receive() 프리미티브에 대한 호출에 의해 발생한다, 메시지 전달 방식은 동기식(봉쇄형, Blocking) 또는 비동기식(비봉쇄형, nonblocking)이 있다.

• 동기식 보내기 : 송신하는 프로세스는 메시지가 수신 프로세스 또는 메일박스에 의해 수신될 때까지 봉쇄 된다.
• 비동기식 보내기 : 송신하는 프로세스가 메시지를 보내고 작업을 재시작 한다.
• 동기식 받기 : 메시지가 이용 가능할 때가지 수신 프로세스가 봉쇄 된다.
• 비동기식 받기 : 송신하는 프로세스가 유효한 메시지 또는 널(null)을 받는다.

Send()와 Receive()가 모두 봉쇄형일 때 우리는 송신자와 수신자간에 랑데부(Rendezvouns)를 갖게 된다.

버퍼링(Buffering) : 통신이 직접적이든 간접적이든 간에 통신하는 프로세스들에 의해 교환되는 메시지는 임시 큐에 들어 있다. 큐를 구현하는 방식은 세 가지가 있다.

• 무용량(Zero Capacity) : 큐의 최대 길이가 0이다. 즉 링크는 자체 안에 대기하는 메시지들을 가질 수 없다. 이 경우 손신자는 수신자가 메시지를 수신할 때 까지 기다려야 한다.
• 유한 용량(Bounded Capacity) : 큐는 유한 길이를 가지고 있으며 최대 큐 길이 메시지가 안에 들어올 수 있다. 새로운 메시지가 전송 될 때 큐가 가득 차 있지 않으면 큐에 저장되며 송신자는 대기하지 않고 실행을 계속 한다.
• 무한 용량(Unbounded Capacity) : 무한길이를 가진다. 메시지들이 얼마든지 큐 안에서 대기할 수 있다. 송신자는 결코 봉쇄되지 않는다.

무한 용량의 경우 버퍼가 없는 시스템이라고 부른다. 다른 경우들은 자동 버퍼링이라 부른다.

[참고자료]

Operating System Concept / 홍릉과학출판사

11_프로세스에 대한 연산

대부분 시스템 내의 프로세스들은 병행 수행 될 수 있으며 반드시 동적으로 생성되고 제거되어야 한다.

프로세스는 실행 도중에 프로세스 생성 시스템 호출을 통해서 여러 개의 새로운 프로세스들을 생성 할 수 있다. 생성하는 프로세스를 부모 프로세스라 하며 생성된 새로운 프로세스들은 자식 프로세스라 부른다. 새로운 프로세스들은 다시 새로운 프로세스들을 생성할 수 있으며 그 결과 트리 구조의 프로세스가 형성 된다.

대부분의 운영체제들은 프로세스 식별자(PID)에 의해 프로세스를 구분하며 식별자는 정수 이다.

프로세스가 새로운 프로세스를 생성할 때 실행과 관련하여 두 가지 가능성이 있다.

• 부모가 계속해서 자식과 병렬로 실행 된다.
• 부모가 모든 자식 또는 일부 자식이 끝날 때까지 기다린다.

새로운 프로세스들의 주소 공간 측면에서 볼 때 다음과 같은 두 가지 가능성이 있다.

• 자식 프로세스는 부모 프로세스의 복사본이다. (자식 프로세스는 부모와 똑 같은 프로그램과 자료를 가진다.)
• 자식 프로세스가 자신에게 적재될 새로운 프로그램을 갖고 있다.

프로세스 종료는 프로세스가 마지막 문장의 실행을 끝내고 exit() 시스템 호출을 사용하여 운영체제에게 자신의 삭제를 요청 한다. 이 시점에서 프로세스는 부모 프로세스에게 wait() 시스템 호출을 통해 상태 값을 반환할 수 있다. 이때 물리 메모리와 가상 메모리, 열린 파일, 입/츨력 버퍼를 포함한 모든 자원이 운영체제로 반납된다.

프로세스가 종료되는 다른 경우를 살펴 보자.

• 자식이 자신에게 할당된 자원을 초과하여 사용 할 때
• 자식에게 할당된 태스크가 더 이상 필요 없을 때
• 부조가 종료하는데 운영체제는 부모가 종료한 후에 자식이 수행되는 것을 허용하지 않는 경우

VMS를 비롯한 일부 시스템에서는 부모 프로세스가 종료된 이후 자식 프로세스가 존재할 수 없다. 그러한 시스템에서 프로세스가 종료되면 부모로부터 비롯된 모든 자식 프로세스들도 종료되어야 한다. 이것을 연속적 종료(Cascading Termination)이라 하며 운영체제가 직접 수행 한다.

10_프로세스 스케줄링

다중 프로그래밍의 목적은 CPU의 사용을 최대화 화기 위하여 항상 어떤 프로세스가 실행 되도록 하는데 있다.

시분할의 목적은 각 프로그램이 실행 되는 동안 사용자가 상호 작용할 수 있도록 프로세스들 사이에서 빈번하게 CPU를 교체하는 것이다.

위 두 개의 목적을 달성하기 위해 프로세스 스케줄러가 존재한다. 프로세스 스케줄러는 CPU에서 수행 가능한 여러 프로세스들 중에서 하나의 프로세스를 선택 한다. 단일 처리기 시스템에서는 실행 중인 프로세스가 한 개 이상 있을 수 없다. 만약 단일 처리기에 여러 프로세스들이 있다면 프로세스들은 CPU가 작업이 끝날 때까지 대기하여야 한다.

프로세스가 시스템에 들어오면 작업 큐에 놓여 진다.(메인 메모리 위치) 이 큐는 시스템 안의 모든 프로세스로 구성 된다. 준비 완료 상태에서 실행을 대기하는 프로세스를 준비 완료 큐(Ready Queue)라고 하며 리스트상에 유지 되며 연결 리스트로 저장 된다. 준비 완료 큐의 헤더는 리스트의 첫 번째와 마지막 PCB를 가리키는 포인터를 포함한다. 각 PCB는 준비 완료 큐에 있는 다음 프로세스를 가리키는 포인터 필드를 가진다.

시스템에는 다양한 큐들이 있다. 장치 큐(Device Queue)라고 불리는 특정 입/출력 장치를 대기하는 프로세스도 있다. 각 장치는 그 자신의 장치 큐를 가진다.

아래 그림을 보면 프로세스는 가장 먼저 큐에 넣어 진다. 프로세스가 새로운 서브 프로세스를 생성하고 그 프로세스 종료를 기다린다. 프로세스가 인터럽트 결과에 의해 강제로 CPU로부터 제거되고 준비 완료 큐에 다시 놓일 수 있다.

프로세스는 일생 동안(종료될 때 까지)에 다양한 상태의 스케줄링 큐로 변경 된다. 운영체제는 어떤 방식으로든지 스케줄링 목적을 위해 프로세스들을 이 큐에서 반드시 선택 해야 한다. 이때 선택 절차는 스케줄러에 의해 수행 된다.

시스템을 요청 작업을 수행 하는데 있어서 즉시 실행 할 수 있는 것보다 더 많은 프로세스들이 요청되기도 한다. 이때 프로세스들은 대용량 메모리(또는 디스크)에 저장되어 나중에 실행 될 때까지 대기하게 된다.

장기 스케줄러(작업 스케줄러)는 이 풀에서 프로세스들을 선택하여 실행하기 위해 메모리로 적재 한다. 단기 스케줄러(CPU 스케줄러)는 실행 준비가 완료되어 있는 프로세스들 중에서 선택하여 CPU에 할당 한다.

장기 스케줄러와 단기 스케줄러의 주요 차이점은 실행 빈도에 있다.

단기 스케줄러는 CPU를 위해 자주 새로운 프로세스를 선택 한다. 실행 간격이 짧기 때문에 반드시 빨라야 한다.

장기 스케줄러는 실행 빈도수가 훨씬 적다. 시스템에서 새로운 프로세스를 생성하는 간격이 수 분일 수도 있다. 장기 스케줄러는 다중 프로그래밍의 정도(메모리에 있는 프로세스들의 수)를 제어 한다. 장기 스케줄러는 실행간격이 크기 때문에 실행할 프로세스를 선택하는데 시간을 더 사용해도 된다.

대부분의 프로세스들은 입/출력 중심 또는 CPU 중심으로 묘사된다.

• 입/출력 중심 프로세스는 연산보다 입/출력 수행에 더 많은 시간을 소요하는 프로세스 이다.
• CPU 중심 프로세스는 입/출력 프로세스보다 연산에 시간을 더 소요하여 입/출력 요청을 드물게 발생시키는 프로세스이다.

장기 스케줄러는 입/출력 중심과 CPU 중심 프로세스들의 적절한 프로세스 혼합(mix)을 선택하는것이 중요하다.

입/출력 중심일 경우 준비 완료 큐는 항상 비게 되고 단기 스케줄러는 할 일이 없게 된다. 반면 CPU 중심으로만 이루어 진다면 입/출력 대기 큐는 항상 비어있는 상태가 되고 장치들은 사용되지 않으며 시스템 균형을 잃게 된다.

시분할 시스템과 같은 일부 운영체제들은 추가로 중간 수준의 스케줄링을 도입 한다. 스와핑(swapping)이라 불리는 이 방법은 메모리에서 프로세스들을 제거한 다음 차후 실행 시 다시 메모리에 프로세스를 불러와서 중단되었던 시점부터 실행을 재개 한다.

CPU를 다른 프로세스로 교환하려면 이전의 프로세스의 상태를 보관하고 새로운 프로세스의 보관된 상태를 복구하는 작업이 필요하다. 이 작업을 문맥 교환(Context Switch)이라 한다.

문맥 교환이 일어나면 커널은 과거 프로세스의 문맥을 PCB에 저장하고 새로운 프로세스의 저장된 문맥을 복구 한다. 문맥 교환이 일어날 동안 시스템은 아무런 일을 못하기 때문에 순수 오버헤드로 간주 된다. 또한 오버헤드는 메모리의 속도, 복사되어야 하는 레지스터의 수, 특수 명령어 등의 환경에 따라 달라진다.

[참고자료]

• Operating System Concept / 홍릉과학 출판사

• Multiprogrammed Batch systems :

http://www.transtutors.com/homework-help/computer-science/introduction-to-operating-system/multiprogrammed-batch-systems/

• 컨텍스트 전환 :

http://publib.boulder.ibm.com/infocenter/idshelp/v115/index.jsp?topic=%2Fcom.ibm.admin.doc%2Fids_admin_0273.htm

09_프로세스 개념

초기의 컴퓨터 시스템은 한 번에 하나의 프로그램만 수행 할 수 있었다. 현대의 컴퓨터 시스템은 메모리에 다수의 프로그램들이 적재되어 병행 수행되는 것을 허용 한다. 이러한 발전은 프로그램을 보다 견고하게 제어하고 보다 구획화 할 것이 필요 했다. 이러한 필요성으로 프로세스 라는 개념이 탄생 하였으며 프로세스는 수행중인 프로그램 이란 뜻을 가지게 되었다. 현대의 컴퓨터에서 프로세스란 시분할 시스템에서 작업의 단위이기도 하다.

프로세스는 일괄 처리 시스템 작업이나 시분할 시스템 사용자들의 태스크를 모두 지칭 한다. 또한 프로그램 카운터의 값과 처리기 레지스터의 내용으로 대표되는 현재 활동을 포함 한다.

프로세스는 일반 적으로 함수의 매개변수 복귀 주소와 지역 변수와 같은 임시적인 자료를 가지는 프로세스 스택과 전역 변수들을 수록하는 데이터 섹션을 포함한다. 또한 프로세스 실행 중에 동적으로 할당되는 메모리인 힙을 포함 한다.

프로그램 그 자체는 프로세스가 아니다. 프로그램은 명령어 리스트를 내용으로 가진 디스크에 저장된 파일(실행 파일)과 같은 수동적인 존재인 반면 프로세스는 다음에 실행할 명령어를 지정하는 프로그램 카운터와 연관된 자원의 집합을 가진 능동적인 존재이다. 실행 파일이 메모리에 적재 될 때 프로그램은 프로세스가 된다.

프로그램 ≠ 프로세스

실행 파일이 메모리에 적재되는 일반적인 방식은 실행 파일을 나타내는 아이콘을 더블 클릭하는 방법과 명령어 라인상에서 파일이름 입력하는 방법이다. 이 때 두 프로세스들이 동일한 프로그램에 연관 될 수 있지만 이들은 두 개의 별도의 실행 순서로 간주 된다.

예를 들어 동일한 워드 파일을 각각 실행 할 경우 이들은 각각 별도의 프로세스이며 텍스트 섹션이 동등하다 할지라도 자료, 힙 및 스택 섹션은 다를 수 있다.

프로세스는 실행이 되면 그 상태가 변한다. 프로세스의 상태는 현재의 그 상태는 프로세스의 현재 활동을 정의한다. 다음 그림을 통해 프로세스 상태 및 정의를 알아 보자.

• New : 프로세스가 생성
• Running : 명령어들이 실행
• Waiting : 프로시스가 어떤 사건(입/출력 등)이 일어나기를 기다림
• Ready : 프로세스가 처리기에 할당되기를 기다림
• Terminated : 프로세스의 실행이 종료

각 프로세스는 운영체제에서 프로세스 제어블록(Process Control Blcok : PCB)의 의해 표시 된다. 태스크 제어 블록이라고도 불린다.

• Process State : 상태는 New, Ready, Running, Waiting(Halted)상태 등이다.
• Program Counter : 프로그램 카운터는 이 프로세스가 다음에 실행할 명령어의 주소를 가리킨다.
• Registers : CPU 레지스터는 컴퓨터 구조에 따라 다양한 개수와 유형을 가진다. 레지스터에는 누산기, 색인 레지스터, 스택 레지스터, 범용 레지스터들과 상태코드 정보가 포함 된다/ 프로그램 카운터와 함께 이 상태 정보는 나중에 프로세스가 계속 올바르게 수행되도록 하기 위해서 인터럽트 발생시 저장되어야 한다.
• CU 스케줄링 정보 : 프로세스 우선순위, 스케줄 큐에 대한 포인터와 다른 스케줄 매개변수들을 포함
• Memory Limits : 운영체제에 의해 사용되는 메모리 시스템에 따라 베이스 레지스터와 한계 레지스터의 값, 운영체제가 사용하는 메모리 시스템에 따라 페이지 또는 테이블 또는 세그먼트 테이블 등과 같은 정보를 포함 한다.

• Accounting : CPU가 사용된 양과 시간, 시간 제한, 계정번호, 작업 또는 프로세스 번호 등을 포함
• 입/출력 상태 정보 : 프로세스에 할당된 입/출력 장치들과 열린 파일의 리스트 정보

[프로세스 제어 블록(PCB)]

[CPU 사이의 프로세스 Switch]

08_시스템 부트

하드웨어를 사용하려면 운영체제를 설치해야 한다. 하지만 운영체제가 설치 되었다고만 해서 하드웨어는 커널이 어디에 있는지, 어떻게 적재하고 사용 할까?

대부분의 컴퓨터 시스템에서는 부트스트랩 프로그램, 또는 부트스트랩 적재기로 알려져 있는 작은 크기의 코드가 커널을 찾고 그것을 메인 메모리에 적재하고 수행을 시작한다. 컴퓨터가 전원을 켜거나 재부팅 등의 명령을 받으면 명령 레지스터는 미리 지정된 메모리 위치를 가리키게 되고 그 곳에서부터 실행을 시작 한다. 그 위치에는 최초의 부트스트랩(bootstrap)이 존재한다. RAM은 시스템 시작 시에 알 수 없는 상태가 되기 때문에 이 프로그램은 ROM(Read only Memory) 안에 저장 된다.(흔히 BIOS라 불리는 영역) ROM은 초기화 할 필요가 없고 바이러스 등의 걱정도 없기 때문에 편리하다.

부트 프로그램은 다양한 작업을 수행하지만 가장 기본적인 작업으로는 시스템의 상태(기계적인 상태)를 진단하는 것이다. 진단 작업이 통과되면 프로그램은 부팅 절차를 계속 한다. CPU 레지스터, 장치 제어기, 주 메모리드의 내용 등 시스템 전반에 걸쳐 초기화 한다. 그리고 운영체제를 시작 시킨다.

[Mac OS X 시스템 상태 진단]

휴대 전화, PDA, 콘솔 게임기 등의 시스템은 운영체제 전체를 ROM에 저장 한다. 운영체제를 ROM에 저장하는 것은 운영체제의 크기가 작거나 간단한 하드웨어를 지원하거나 열악한 환경에서 사용되는 시스템에 적합하다. 하지만 이 방식의 단점은 부스트랩코드가 변경되면 ROM을 교체 해야 하는 이슈가 발생한다. 일부 시스템에서는 EPROM(Erasable Programmable Read Only Memory)을 사용하여 해결하기도 한다.

이처럼 ROM 성격을 가진 모든 형태를 펌웨어(Firmware)라 부른다. 펌웨어의 단점은 용량이 크지 않고 가격이 비싸다는 것이다. 또한 메모리보다 속도가 느리다. 따라서 메모리에서 실행 할 때 보다 성능이 떨어진다. ROM의 성능 문제를 개선하기 위하여 일부 시스템은 운영체제를 실행 할 때 RAM으로 복사하여 실행 한다.

Windows, Mac OS, Linux 같은 일반적인 운영체제를 포함하여 대용량의 운영체제 또는 자주 변경되는 시스템은 부스트랩 적재기는 펌웨어에 있고 운영체제는 디스크에 존재 한다. 이 경우 부트스트랩은 진단 절차를 수행하고 고정된 위치의 디스크 블록 하나를 읽어 메모리에 적재하고 그 위치로부터 실행 시킬 수 있는 코드를 가진다. 이 블록을 부트 블록이라 한다. 부트 파티션을 가지고 있는 디스크는 부트 디스크 또는 시스템 디스크라 한다.

[부트 블록]

[부트 파티션]

모든 부트 프로그램이 적재되면 파일 시스템을 탐색하여 운영체제 커널을 찾아내고 메모리로 적재한 후 실행을 시작한다. 시스템 실행 중 상태는 이 시점부터 이다.

[Windows 7 Boot Process]

07_가상 머신(Virtual Machine)

가상 머신(Virtual Machine)의 기본적인 개념은 한 컴퓨터의 하드웨어(CPU, 메모리, 디스크 드라이브, 네트워크 등)가 다수의 실행 환경을 제공하도록 추상화 하는 것이다. 각 개별적인 실행 환경이 자신만의 독립된 컴퓨터를 사용하는 환경을 제공 하는 것이다.

가상 머신을 구성하는 가장 큰 이유는 모두 동일한 하드웨어를 공유하면서 다수의 실행 환경(운영체제)을 동시에 수행 할 수 있다는 것이다. 또한 여러 가지 시스템 자원에 대해 완전한 보호가 이루어지므로 각 가상 머신은 강한 수준의 보안을 제공 한다. 그러나 동시에 가상 머신들은 자원을 직접적으로 공유 할 수 없어 가상 디스크를 공유하거나 네트워크 등을 통하여 공유 할 수 있다.

가상 머신의 접근 방법에서 가장 어려운 부분이 디스크이다. 실제 디스크는 3장밖에 없는데 가상 머신이 7개가 운용되고 있다고 가정 하였을 때 가상 머신에 드라이브를 하나씩 제공할 수가 없다. 가상 머신 소프트웨어는 자체가 가상 메모리와 스풀링을 제공하기 위해 대량의 디스크 공간이 필요 하다. 이것에 대한 해결책이 크기만 다르고 나머지는 모든 면이 동일한 가상 디스크를 제공 하는 것이다. IBM에서는 이것은 미니디스크(MiniDisk)라 부른다.

시스템은 물리 디스크에서 미니 디스크가 필요로 하는 만큼의 트랙들을 할당함으로써 각 미니 디스크를 구현한다. 당연히 모든 미니 디스크 크기의 합은 물리적인 디스크 크기보다 작아야 한다.

가상 머신 소프트웨어는 운영체제이기 때문에 커널 모드에서 수행 될 수 있다. 가상 머신 자체는 사용자 모드에서만 수행 될 수 있다. 물리적인 기계가 두 개의 모드를 갖는 것과 마찬가지로 가상 머신도 두 개의 모드를 가져야 한다. 실제 머신에서 사용자 모드로부터 커널 모드로 변환을 일으키는 행위는 가상 머신에서도 가상 사용자 모드로부터 가상 커널 모드로의 변환을 일으켜야 한다.

이러한 변화는 다음과 예제로 설명 할 수 있다. 가상 머신 상에서 가상 사용자 모드에서 수행중인 프로그램이 시스템 호출을 하면 이는 실제 기계 내의 가상 머신 모니터로 전달되게 된다. 가상 머신 모니터가 제어를 얻으면 시스템 호출의 효고를 흉내내기 위해 가상 머신의 레지스터의 내용와 프로그램 카운터를 변경할 수 있다. 그런 다음 가상 머신 모니터는 현재 가상 커널 모드에 있다는 것을 유의하면서 가상 머신을 재시작 시킬 수 있다.

[VMWare Architecture]

[Xen Architecture]

[Hypervisor Architecture]

[Java Virtual machine]

[.NET Framework]

06_운영체제 구조

운영체제와 같이 크고 복잡한 시스템은 적절하게 동작하고 쉽게 변경 될 수 신중히 제작되어야 한다. 일반 적인 접근 방법은 한 개의 일관된 시스템보다는 태스크를 작은 구성요소로 분리 하는 것이다.

[간단한 구조(Simple Structure)]

운영체제는 처음에는 소형이면서 간단하고 제한된 시스템으로 시작 되었다. 최소의 공간에 최대의 기능들을 제공하도록 작성되어 있어서 모듈들로 주의 깊게 분할 되지 않았다. MS-DOS와 UNIX를 예를 들어 보자.

• MS-DOS : 인터페이스와 기능 계층이 잘 분리되어 있지 않다. 예를 들면 응용 프로그램이 기본 입/출력 루틴을 통하여 디스플레이와 디스크 드라이브에 직접 쓰기가 가능 하다. 이런 자유는 프로그램을 취약하게 만들었다. 따라서 사용자 프로그램이 고장나면 시스템 전체가 고장나게 된다. MS-DOS는 시작부터 하드웨어의 기능에 제한적이었으며 Intel 8088이 이중 모드와 하드웨어 보호 기능을 제공하지 않기 때문에 MS-DOS의 설계자들은 기본 하드웨어를 접근하도록 하용 할 수 밖에 없었다.

• UNIX : 처음에는 하드웨어 기능에 의해 제한 받는 시스템 구조였다. UNIX는 커널과 시스템 프로그램으로 구성되어 있는데 커널은 여러 가지 인터페이스와 장치 드라이버로 다시 분리 되었다. 이는 발전 할수록 추가되고 확장 된 것이다. 시스템 인터페이스 아래와 물리적 하드웨어 위의 모든 것이 커널이다. 시스템 호출을 통해 파일 시스템, CPU 스케줄링, 메모리 관리 그리고 다른 운영체제의 기능을 제공 한다. 이 모노놀리딕(Monolithic)구조는 구현하기 어렵고 유지보수하기도 어렵다.

[계층적 접근(Layered Approach)]

하향식(top-down) 접근법에서는 전체적인 기능과 특징이 결정되고 구성 요소로부터 분리가 된다. 정보의 은폐 또한 중요하다. 저 수준의 루틴에서 외부 인터페이스가 변경되지 않고 루틴 자체가 공시된 일을 수행한다면 자유스럽게 구현할 수 있는 대신 보안에 취약하기 때문이다.

계층적 접근 방식은 운영체제가 여러 개의 계층으로 나누어 진다. 최하위 계층(계층0)은 하드웨어이고 최상위 계층(계층 N)은 사용자 인터페이스 이다.

계층적 접근 방식의 장점은 구현과 디버깅의 간단함에 있다. 계층들은 단지 자신의 하위 계층들의 서비스와 기능(연산)만 사용하도록 선택 된다. 첫 번째 계층은 정의에 의해 하드웨어(하드웨어는 오류가 없다고 가정함)만을 사용하여 이 계층의 기능을 구현하기 때문에 나머지 시스템에 아무런 신경을 쓰지 않고 디버깅 할 수 있다. 첫 번째 디버깅이 끝나고 두 번째 계층을 디버깅 하는 동안 그것이 정확하게 동작한다고 가정될 수 있으며 이러한 과정이 반복 된다. 만일 어느 계층의 디버깅 중 오류가 발견되면 그 하위의 계층은 이미 디버깅 되었기 때문에 오류는 반드시 그 계층에 있다. 각 계층은 자신보다 저 수준의 계층에 의해 제공된 연산만 사용해 구현한다. 한 계층은 이러한 연산들이 어떻게 구현되는지 알 필요가 없고 이러한 연산들이 무엇을 하는 지만 알면 된다. (객체지향의 캡슐화와 비슷하다.) 따라서 계층을 나누면 시스템의 설계나 구현이 간단해 진다.

단점으로는 여러 계층을 정의하는 것이 어렵다. 예를 들어 예비 저장 장소(Backing store :가상 메모리 알고리즘에 의해 사용되는 디스크 공간)를 위한 장치 드라이버는 메모리 관리가 예비 저장 장소를 사용할 수 있는 능력을 필요로 하기 때문에 메모리 관리 루틴들보다 저 수준에 있어야 한다.

계층적 구현의 문제점은 다른 유형의 구현 방법보다 효율성이 낮다는 것이다. 각 계층은 시스템 호출에 오버헤드를 추가하며 그 결과 계층적 구조가 아닌 시스템보다 시스템 호출의 수행 시간이 더 오래 걸린다.

[마이크로커널(Microkernel)]

이 방법은 중요치 않은 구성 요소를 커널로부터 제거하고 그들을 시스템 및 사용자 수준 프로그램으로 구현하여 운영체제를 구성 하였다. 마이크로커널의 주 기능은 클라이언트 프로그램과 사용자 공간에서 수행되는 다양한 서비스간에 통신 설비를 제공하는 것이다.

클라이언트 프로그램과 서비스는 직접 상호 작용을 하지 않고 마이크로커널과 메시지를 교환함으로써 통신 한다.

마이크로 커널의 장점은

• 운영체제의 확장이 용이하다 모든 새로운 서비스는 사용자 공간에 추가되며 커널 변경은 최소화 된다.
• 다른 하드웨어로 이식이 쉽다
• 높은 보안성과 신뢰성을 제공
• 서비스가 잘못되더라도 운영체제의 다른 부분은 영향을 받지 않는다.

단점으로는 가중된 시스템 기능 오버헤드 때문에 성능이 감소 된다.

[모듈(module)]

모듈화 커널을 만들기 위한 운영체제 설계의 가장 최근의 기술은 객체지향 프로그래밍 기법을 사용하는 것이다. 이 접근법은 커널은 핵심적인 구성 요소으 ㅣ집합을 가지고 있으고 부팅 때 또는 실행중에 부가적인 서비스들을 링크한다.

이러한 설계는 핵심 서비스를 제공할 수 있게 할 뿐 아니라 특정 기능들을 동적으로 구현할 수 있게 한다. 예를들어 특정 하드웨어를 위한 장치와 버스 드라이버는 커널에 추가 될 수 있고 다른 파일 시스템도 적재 가능 모듈을 이용하여 지원 될 수 있다. 전체적인 결과는 각 커널의 각 부분이 정의되고 보호된 인터페이스를 가진다는 점에서 계층적 구조를 닮았다. 그러나 모듈은 임의의 모듈을 호출 할 수 있다는 점에서 계층적 구조보다 유연하다. 또한 중심 모듈은 핵심 기능만을 가지고 있고 다른 모듈의 적재 방법과 모듈들과 어떻게 통신하는지 안다는 점에서 마이크로 커널과 유사하다. 그러나 통신하기 위하여 메시지 전달을 호출할 필요가 없기 때문에 더 효율적이다.

05_운영체제 구조_설계 및 구현

설계 및 구현에서는 운영체제를 설계하고 구현할 때 우리가 당면하는 문제점을 논의한다.

[설계 목표]

시스템을 설계하는데 있어 첫 번째 문제점은 시스템의 목표와 명세를 정의하는 일이다. 시스템 설계는 하드웨어와 시스템의 유형(일괄처리, 시분할 처리, 단일 사용 자 등)의 선택에 의해 영향을 받는다.

시스템 설계의 요구 조건들을 명세하는 것은 매우 어려운 일이지만 크게 사용자 목적과 시스템 목적 두 그룹으로 나눌 수 있다.

사용자 목적은 사용자들은 시스템이 사용하기 쉽고 편리하며 배우기 쉽고 안전해야 하는 등 요구사항이 있다. 이러한 명세는 어떻게 목적을 달성할 것인가에 대한 합의가 없기 때문에 시스템 설계에 있어 특별히 유용하지는 않다. 즉 운영체제는 설계, 구현, 유지보수가 쉬워야 하며 적응성, 선뢰성, 무오류, 효유율성을 가져야 한다.

[메커니즘과 정책(Mechanism and Policy)]

설계 시 중요한 원칙 중 하나가 메커니즘(Mechanism)으로부터 정책(Policy)을 분리 하는 것이다.

메커니즘은 어떤 일을 어떻게 할 것인가를 결정하는 것이고 정책은 무엇을 할 것인가를 결정하는 것이다. 정책은 장소가 바뀌거나 시간이 흐름에 따라 변경 될 수 있다. 최악의 경우 정책에 따라 메커니즘의 변경을 요구하게 된다.

정책 결정은 모든 자원 할당 문제에 있어 중요하다. 자원의 할당 여부를 결정할 필요가 있을 때마다 정책 결정을 해야 한다.

질문이 무엇(What)이 아니라 어떻게(How) 일 때마다 반드시 결정되어야 하는 것은 메커니즘이다.

[구현(Implementation)]

운영체제가 일단 설계 되면 구현하는데 운영체제는 어셈블리어로 작성 되었다. 그러나 지금은 C나 C++등의 고급언어로 작성 된다.

운영체제를 구현하기 위해 고급 언어나 최소한 시스템 구현 언어를 사용함으로써 얻어지는 장점이 있다.

• 코드를 빨리 작성 할 수 있으며
• 코드가 더욱 간결하고 이해하기 쉬우며
• 디버그도 쉽다.
• 더욱이 컴파일러 기술의 향상은 단순히 재컴파일만 하더라도 전체 운영체제 코드를 향상 시킬 것이다.
• 마지막으로 다른 하드웨어로 옮기는 이식이 쉽다. 예를 들면 MS-DOS는 intel8080 어셈블리어로 제작되어 Intel 계열의 CPU에서만 수행 된다. 대조적으로 Linux의 경우 대부분 C로 작성되었으며 따라서 Intel 80X86, Motorola 680X0, SPARC, MIS RX000 등 다수의 다른 CPU에 이용이 가능하다.

단점은 속도가 느리고 저장장치가 많이 소요된다. 하지만 이와 같은 문제는 현재의 시스템에서는 더 이상 주된 문제가 아니다. (하드웨어 성능의 발전으로 인한 효과)

어셈블리어 프로그래머는 효율적인 작은 루틴을 생산할 수 있지만 현대의 컴파일러는 대규모 프로그램을 위해 복잡한 분석을 수행하고고 그리고 정교환 최적화를 적용하여 우수한 코드를 생산 할 수 있다.

운영체제의 주요 성능 향상은 우수한 어셈블리어 코드보다 좋은 자료구조와 알고리즘의 결과일 가능성이 크다.

04_운영체제 구조_시스템 프로그램

시스템은 시스템 프로그램의 집합체이다. 최하위 수준은 하드웨어 이고 그 위에 운영체제와 시스템 프로그램, 마지막에 응용 프로그램의 집합으로 이루어져 있다.

시스템 프로그램은 프로그램 개발과 실행을 위해 보다 편리한 환경을 제공 한다. 일부는 단순한 호출에 대한 사용자 인터페이스 이며 나머지는 훨씬 복잡한 시스템 이다.

시스템 프로그램에 대해 6개의 범주로 구분하여 보자.

• 파일 관리 : 파일과 디렉토리를 생성, 삭제, 복사, 이름변경, 인쇄, 덤프, 리스트 등 파일의 조작과 디렉토리를 조작 한다.

• 상태 정보 : 날짜, 시간, 사용 가능한 메모리 정보 등 단순한 정보 외에 상세한 성능, 로깅, 디버깅 정보 등을 제공한다.
• 파일 변경 : 디스크나 다른 저장 장치에 저장된 파일의 내용을 생성하고 변경하기 위해 다수의 문장 편집기가 사용 가능하다. 파일의 내용을 검색하거나 변환하기 위한 특수 명령어가 제공 되기도 한다.
• 프로그래밍 언어 지원 : 일반적 프로그래밍 언어(C, C++, JAVA등)에 대한 컴파일러, 어셈블러, 해석기가 종종 운영체제와 함께 사용자에게 제공 된다.
• 프로그램 적재와 수행 : 프로그램이 어셈블되거나 컴파일 된 후 그것이 수행되려면 반드시 메모리에 적재(Load)되어야 한다. 시스템은 절대 적재기(absolute loader), 재배치 가능 적재기(relocatable loader), 링키지 에디터(linkage editor)와 중첩 적재기(overlay loader)등을 제공할 수 있다. 디버깅 시스템도 필요하다.

• 통신 : 프로세스 또는 다른 컴퓨터 시스템들 사이에 가상 접속을 이루기 위한 기법을 제공 한다.

대부분의 사용자가 보는 운영체제의 관점은 실제의 시스템 호출에 의해서 보다는 시스템 프로그램과 응용 프로그램에 의해 정의 된다.

03_운영체제 구조_시스템 호출의 유형

시스템 호출은 다섯 가지의 주요 범주로 묶을 수 있다.

[프로세스 제어]

• 끝내기(End), 중기(Abort)
• 적재(Load), 실행(Execute)
• 프로세스 생성, 프로세스 종료
• 프로세스 속성(Attribute) 획득, 프로세스 속성 설정
• 시간을 기다림
• 사건을 기다림(Wait Event), 사건을 알림(Signal Event)
• 메모리 할당 및 자유화

[파일 조작(File Manipulation)]

• 파일 생성(Create file), 파일 삭제(Delete File)
• 열기(Open), 닫기(Close)
• 읽기, 쓰기 위치변경(Reposition)
• 파일 속성 획득 및 설정

[장치 관리(Device Management)]

• 장치를 요청(Request Device), 장치를 방출(Release Device)
• 읽기, 쓰기, 위치 변경(Reposition)
• 장치 속성 획득, 장치 속성 설정
• 장치의 논리적 부착(Attach) 또는 분리(Detach)

[정보 유지(Information Maintenance)]

• 시간과 날짜의 설정과 획득
• 시스템 자료의 설정과 획득
• 프로세스, 파일, 장치 속성의 획득
• 프로세스, 파일, 장치 속성의 설정

[통신(Communication)]

• 통신 연결의 생성, 제거
• 메시지의 송신, 수신
• 상태 정보 전달
• 원격 장치의 부착 및 분리

[프로세스 제어(Process Control)]

실행 중인 프로그램은 수행을 정상(끝내기) 또는 비정상(중지)으로 끝낼 수 있어야 한다. 프로그램에 문제가 발생해 오류 트랩(trap)을 유발할 경우 때때로 메모리 덤프가 행해지고 오류 메시지가 생성된다. 이 덤프는 디스크에 기록되고 디버거(Bebugger)에 의해 검사될 수 있다. 운영체제는 명령어 해석기로 제어를 전달해야 한다. 명령어 해석기는 이어 다음 명령을 읽는다.

몇몇 시스템 에서는 오류가 발생할 경우 특별한 복구 행위를 지시하는 제어카드를 허용한다. 제어카드는 일괄처리의 개념이다. 만약 프로그램이 입력에서 오류를 발견하고 비정상으로 종료하기를 원한다면 프로그램은 오류 수준을 정의하기를 원할 수도 있다. 보다 높은 수준의 오류 매개변수가 보다 심각한 오류를 표시할 수 있다. 이렇게 함으로써 정상 종료를 수준 0의 오류로 정의하여 정상 종료와 비정상 종료를 결합시킬 수도 있다.

한 프로그램을 실행하고 있는 프로세스나 작업이 다른 프로그램을 적재(Load)하고 실행(Execute) 하기를 원할 수 있다. 이 기능은 명령어 해석기가 사용자 명령, 마우스의 클릭 혹은 일괄 처리 명령 등을 통하여 지시된 프로그램을 실행하는 것을 허용 한다. 이때 적재된 프로그램이 종료 될 때 어디로 제어를 되돌려 주느냐 하는 문제가 발생 한다.

만약 새로운 프로그램이 종료 되었을 때 제어가 기존 프로그램으로 되돌아 간다면 우리는 반드시 기존 프로그램의 메모리 이미지를 보관해야 한다. 따라서 우리는 실질적으로 한 프로그램이 다른 프로그램을 호출하는 기법을 만든 셈이 된다.

Ex) printf() 문을 호출 하는 C 프로그램에서 C 라이브러리는 이 함수 호출을 가로채고 운영체제의 필요한 시스템을 호출 한다. 예제에서는 write() 시스템 함수를 호출 하고 있다.

시스템 호출의 또 다른 집합은 프로그램을 디버깅하는데 유용하다. 많은 시스템들은 메모리를 덤프(Dump)하기 위한 시스템 호출을 제공하며 프로그램 추적(Trace)은 각 명령어가 실행될 때 이들을 하나씩 나열하며 이러한 시스템 호출은 보다 소수의 시스템에서만 제공 된다.

많은 운영체제는 프로그램의 시간 프로파일(Time Profile)을 제공한다. 시간 프로파일은 그 프로그램이 특정 위치 혹은 위치의 집합에서 수행한 시간의 양을 나타낸다. 시간 프로파일은 추적 설비(Tracing Facility)나 정규 타이머 인터럽트를 필요로 한다.

프로세스가 끝나면 종료하기 위해 exit() 시스템 호출을 수행하며 호출한 프로세스에게 상태 코드 0을 돌려주거나 0이 아닌 오류 코드를 돌려 준다. 이러한 상태 또는 오류코드는 쉘 또는 다른 프로그램들이 이용할 수 있게 된다.

[파일 관리(File Management)]

파일을 생성 삭제 할 수 있어야 한다. 이 시스템 호출은 파일 이름이나 파일 속성의 일부를 요구한다. 파일이 생성되면 그것을 열고, 읽고, 쓰고, 위치 변경을 할 수 있다. 파일을 더 이상 사용하지 않음을 나타내는 파일 닫기가 필요하다.

파일 시스템이 파일을 조직하기 위해 디렉토리 구조를 가진다면 우리는 디렉토리에 대해서도 파일과 같은 연산 집합이 필요 하다. 추가로 파일이나 디렉토리에 대해 여러 속성의 값을 결정할 수 있어야 하고 필요에 따라 재설정 할 수 있어야 한다. 파일 속성은 파일 이름, 파일 유형, 보호코드 등 정보를 포함한다. 이러한 기능을 위해서는 최소한 파일의 속성 획득과 파일 속성 설정의 두 시스템 호출이 필요하다. 일부 시스템들은 코드와 다른 시스템 호출을 이용하여 동일한 작업을 수행하는 API를 제공할 수도 있고 또 다른 시스템은 단순히 동일한 작업을 수행하는 시스템 프로그램을 제공하기도 한다. 이 시스템 프로그램이 다른 시스템 프로그램에 의해 호출 가능하다면 다른 프로그램의 입장에서는 이 시스템의 API가 된다.

[장치 관리(Device Management)]

프로세스는 작업을 계속 수행하기 위해서 CPU, 디스크, 파일의 접근 등에 대한 추가 자원이 필요 할 수 있다. 자원들이 사용할 수 있다면 이들 자원이 할당되고 제어가 사용자 프로그램으로 복귀 될 수 있다. 그렇지 않으면 프로그램은 충분한 자원을 할당 받을 때까지 기다려야 한다.

운영체제에 의해 제어되는 다양한 자원들은 장치로 간주 될 수 있다. 이 장치들은 물리장치 또는 추장적 혹은 가상적 장치로 생각할 수 있다. 다수의 사용자가 있다면 독점적인 장치 사용을 보장받기 위해 우선 그 장치를 요청(Request) 해야 한다. 그 장치의 사용이 끝나면 그것을 방출(release)해야 한다.

[정보의 유지(Information Maintenance)]

많은 시스템 호출은 단순히 사용자와 프로그램과 운영체제간의 정보 전달을 위해 존재 한다. 운영체제는 현재 운영되고 있는 프로세스들에 관한 정보를 가지고 있으며 이러한 정보에 접근하기 위한 시스템 호출들이 있다. 일반적으로 그 프로세스 정보를 재설정하기 위한 시스템 호출도 있다.(get process attributes, set process attributes)

[통신(Communication)]

통신 모델에서는 메시지 전달 방식과 공유 메모리의 두 가지 일반적인 모델이 있다.

메지시 전달 : 통신하는 두 프로세스가 정보를 교환하기 위하여 서로 메시지를 주고 받는다. 통신은 동일 CPU에 있는 프로세스이든지 또는 통신 네트워크에 의해 연결된 다른 컴퓨터에 있는 프로세스이든지 간에 그 이름을 반드시 알고 있어야 한다.

공유 메모리 모델 : 다른 프로세스가 소유한 메모리 영역에 대한 접근을 위해 shard memory create와 shared memory attach 시스템 호출을 사용한다. 정상적으로 운영체제는 한 프로세스가 다른 프로세스의 메모리 접근하는 것을 막으려고 한다. 공유 메모리는 두 개 이상의 프로세스가 이러한 제한을 제거하는 데 동의할 것을 필요로 한다. 그런 후 이들 프로세스들은 이러한 공유 영역에서 자료를 읽고 씀으로써 정보를 교환 할 수 있다. 소량의 자료를 교환할 때 유용하다.

자료의 형태와 위치는 운영체제의 제어가 아니라 프로세스들에 의해 결정 된다. 프로세스들은 동일한 위치에 동시에 쓰지 않도록 보장해야 한다. 한 컴퓨터 안에서 수행되기 때문에 최대 속도와 편리한 통신이 장점이지만 보호 영역 및 동기화 프로세스 등의 문제점을 가지고 있다.

[참고자료]

Operating System Concept