시행착오 기술 블로그

RAID 개념 및 종류

1. RAID (Redundant Array Of Inexpensive Disk 또는 Redundant Array Of Independent Disk)

디스크 드라이브가 소형화 되고, 저렴해지면서 현재 컴퓨터 시스템에 저렴하게 다수의 디스크를 부착할 수 있다.

시스템이 많은 수의 디스크를 가지고 있고, 그 시스템이 병렬적으로 운영된다면 데이터 읽기, 쓰기 비율을 향상시킬 수 있다. 더욱이 중복정보가 여러 디스크에 저장되기 때문에 데이터 저장의 신뢰성을 높일 수 있다. 그러므로 하나의 디스크 오류로 데이터가 분실되지 않는다. RAID 라고 불리는 다양한 디스크 구성 기술은 일반적으로 성능과 신뢰성 쟁점을 해결하는데 역점을 두고 있다.

(1) 중복을 통한 신뢰성 향상

신뢰성 측면에서, 데이터의 복사본이 1개만 있다면 각 디스크 오류는 엄청난 양의 데이터 손실을 발생시킬 수 있다.

신뢰성 문제를 해결하는 방안은 "중복을 허용하는 것"이다. 부가의 정보를 저장하는데 이 정보는 정상적인 경우에는 필요없지만, 디스크 고장이 발생했을 경우 분실된 정보를 재구축하기 위해 필요하다. 

(2) 병렬성을 통한 성능 향성

디스크 미러링을 사용하면 시스템에서 읽기요청의 경우 두 디스크 중 하나에서 처리할 수 있기 때문에 읽기 요청의 처리율은 2배가 될 것이다. 각 읽기 작업의 전송비율은 하나의 디스크 시스템과 같지만 단위 시간당 읽기 요청의 수는 2배가 된다.

- 비트 수준 스트라이핑 : 각 바이트의 비트가 여러 디스크에 스트라이핑 된다. 예를 들어 8개의 디스크가 포함된 경우 각 8비트 바이트는 별도의 디스크에 있는 8개의 헤드에 의해 병렬로 읽힌다. 단일 디스크 읽기는 일반적으로 512바이트를 읽는 데 필요한 시간 동안 8 * 512바이트 = 4K 가치의 데이터에 액세스한다. 유사하게 4개의 디스크가 관련된 경우 읽기 또는 쓰기 작업당 2K 가치의 디스크 액세스를 위해 각 바이트의 2비트를 각 디스크에 저장할 수 있다.

- 블록 수준 스트라이핑 : 블록 단위로 여러 디스크에 파일 시스템을 분산하므로 블록 N이 디스크 0에 있으면 블록 N + 1이 디스크 1에 있는 방식이0다. 이는 물리적 블록 클러스터 에서 파일 시스템에 액세스할 때 특히 유용하다. 

2. RAID 레벨

(1) RAID0 : 블록 레벨로 스트라이핑하는 디스크 구성. 미러링이나 패리티 비트 같은 어떤 중복 정보도 가지고 있지 않음.

(2) RAID1 : 디스크 미러링을 사용. 복사본을 만드는 것.

(3) RAID2 : 메모리 스타일 오류 정정 코드 구조. 패리티 비트를 이용해 error detection 및 error correction 가능.

(4) RAID3 : 성능을 향상시키는 스트라이핑, 하드웨어 수준의 패리티 계산과 NVRAM 캐시를 사용.

(5) RAID4 : 비트 레벨 스트라이핑 대신 블록 레벨 스트라이핑을 사용

(6) RAID5 : 패리티 블록이 모든 디스크에 분산되어 시스템의 로드 균형을 보다 고르게 분산한다는 점, 디스크의 주어진 블록에 대해 디스크 중 하나는 해당 블록에 대한 패리티 정보를 보유하고 다른 N-1 디스크는 데이터를 보유한다. 동일한 디스크는 동일한 블록에 대한 데이터와 패리티를 모두 보유할 수 없다. 디스크 충돌이 발생하면 둘 다 손실되기 때문.

(7) RAID6 : 단일 패리티 비트가 아닌 데이터의 각 비트 위치에 대해여러 비트의 오류 복구 코드 이용. 최대 2개의 동시 디스크 오류가 발생하더라도 데이터를 복구할 수 있다. 단일 디스크 오류만 허용할 수 있는 단순 미러링의 경우 100%와 달리 스토리지 요구 사항이 50%만 증가한다.

(8) RAID01 : 디스크가 먼저 스트라이프된 다음 스트라이프된 디스크가 다른 세트로 미러링된다. 이 수준은 일반적으로 RAID 수준 5보다 더 나은 성능을 제공한다.

(9) RAID10 : 디스크를 쌍으로 미러링한 다음 미러링된 쌍을 스트라이프한다. 저장 용량, 성능 등은 모두 동일하지만 아래 그림과 같이 여러 디스크 오류가 발생하는 경우 이 접근 방식에 이점이 있다.

파일시스템의 기능(목적) 및 종류

파일

운영체제에 의해서 물리장치들로 맵핑되며, 이들 저장장치들은 일반적으로 비휘발적 성질을 갖기 때문에 전원이 끊어지거나 시스템이 재부팅되어도 저장된 내용들은 영구히 존속된다.

파일 속성

사용자의 편의를 위해 파일에 이름을 부여하고 그 이름으로 파일을 참조한다. 파일은 다양한 속성을 가진다.

이름,  식별자, 타입, 위치, 크기, 보호(읽기, 쓰기, 실행 등을 할 수 있는지 권한), 시간, 날짜, 사용자 식별 등

파일시스템

- 사용자가 이용하기 편리하도록 인터페이스(UI) 제공

- 사용자가 파일을 생성, 수정, 제거(CRUD) 기능 제공

- 타인과 파일을 공유할 수 있는 기능 제공

- 사용자가 임의대로 파일을 구성할 수 있는 기능 제공

- 파일 간에 정보 전송을 할 수 있는 기능 제공

- 파일의 백업과 복구, 암호화와 복호화 기능 제공

- 디렉토리를 생성하고 제공

파일 시스템 종류

FAT : 어느 영역에 파일이 속해 있는지, 공간에 여유가 있는지, 또 어디에 각 파일이 디스크에 저장되어 있는지에 대한 정보

NTFS: FAT의 단점을 보완하기 위해 개발된 파일 시스템, 윈도우에 최적화 되어있는 파일시스템

EXT : 리눅스용 파일 시스템, 리눅스 배포판에서 주로 쓰이는 파일시스템

HFS : 계층적 파일 시스템, 맥OS를 구동하는 컴퓨터 시스템에 서 쓰이는 파일 시스템

APFS : 애플파일 시스템, 애플 관련 OS들에서 범용으로 사용하는 파일 시스템

1. 요구 페이징

요구 페이징 (Demand paging)

가상 메모리는 요구 페이징 방식으로 구현되며, 또한 세그멘테이션이나 페이지된 세그멘테이션 기법을 사용하기도 한다.

요구 페이징은 초기에 필요한 것들만 메모리에 적재하는 전략으로, 요구 페이징을 사용하는 가상메모리에서는 페이지들이 실행과정에서 실제로 필요해질 때 적재되는 방식이다. 즉, 한번도 접근되지 않는 페이지는 물리메모리에 전혀 적재되지 않는다.

요구 페이징 시스템의 중요사안

- 프레임 할당: 한정된 메모리에 어떤 프레임(프로세스의 단위, 페이지)을 올려야 좋을까?

- 페이지 교체 알고리즘: 모든 메모리에 프레임이 꽉 찼을 때, 어떤 프레임을 빼서 다른 프레임을 넣을까?

페이저(Pager)

프로세스 내의 개별 페이지를 관리한다. 그리고 실제로 어떤 페이지들이 사용될 것인지 추측한다.

프로세스 전체를 스왑인(swap-in: 메모리로 읽어들인다)하는 대신에 실제 필요한 페이지들만 메모리로 읽어 온다.

사용되지 않을 페이지는 메모리로 가져오지 않음으로써 시간낭비와 메모리 공간의 낭비를 줄일 수 있다.

유효-무효 비트(valid-invalid bit)

어느 페이지가 디스크에 있고, 어느 페이지가 메모리에 올라와 있는지 구별할 필요가 있는데, 이를 유효-무표 비트를 통해 알 수 있다. 이 비트가 유효하다고 설정되면, 해당 페이지가 메모리에 있다는 의미이고, 무효하다고 설정되면 해당 페이지가 유효하지 않거나 유효해도 디스크에 존재한다는 의미이다.

즉, 메모리에 올라오는 페이지에 대해서는 유효로 설정하며, 현재 메모리에 올라와 있지 않은 페이지의 페이지테이블 항목은 무효로 설정하거나, 그 페이지가 저장되어 있는 디스크 주소를 기록해둔다.

2. 페이지 부재

페이지 부재(Page Fault)

프로세스가 메모리에 올라와 있지 않는 페이지에 접근하려고 하면 페이지 부재 트랩(Page-Fault Trap)이 발생한다. 페이징 하드웨어는 페이지 테이블을 이용한 주소 변환 과정에서 무효 비트를 발견하고, 운영체제에게 트랩을 건ㄴ다. 이 트랩은 운영체제가 적재하지 않은 페이지 중에 필요한 페이지가 있기 때문이다. 

페이지 부재 처리 과정

1. 프로세스에 대한 내부 테이블을 검사해서 그 메모리가 유효인지 무효인지 파악한다.

2. 만약 무효한 페이지라면 그 프로세스는 중단된다. 만약 유효한 참조인데 페이지가 아직 메모리에 올라오지 않았다면 디스크에 접근하여 해당 페이지를 메모리로 가져온다.

3. 빈공간 (Free Frame)을 찾는다.

4. 디스크에 새로이 할당된 프레임으로 해당 페이지를 읽어들이도록 요청한다.

5. 디스크 읽기가 끝나면 이 페이지가 이제는 메모리에 있다는 것을 알리기 위해 페이지 테이블을 갱신하며, 프로세스가 유지하고 있는 내부 테이블을 수정한다.

5. 트랩에 의해 중단되었던 명령어를 다시 실행한다. 프로세스는 마치 그 페이지가 항상 메모리에 있었던 것처럼 해당 페이지에 접근할 수 있다.

3. 페이지 교체 알고리즘

페이지 교체 (Page Replacement)

운영체제는 사용자 프로세스가 실행 중에 페이지 부재가 발생한다. 운영체제가 필요한 페이지가 디스크 어디에 위치하고 있는지 알아내지만, 빈 프레임이 없을 수 있다. 즉 모든 메모리가 사용 중인 경우가 있을 수 있다.

이때 페이지 교체가 발생한다. 즉 기존에 메모리에 올라가 있는 페이지를 빼고, 새롭게 필요로하는 페이지를 저장한다.

페이지 교체 과정

1. 디스크에서 필요한 페이지의 위치를 찾아낸다.

2. 빈 페이지 프레임을 찾는다.

     2-1. 만약 빈 프레임이 있다면 그것을 사용한다.

     2-2. 없다면 희생 프레임 victim frame을 선정하기 위해 페이지 교체 알고리즘을 가동시킨다.

     2-3. 희생될 페이지를 디스크에 기록하고, 관련 테이블을 수정한다.

3. 새롭게 비워진 프레임에 새 페이지를 읽어오고 프레임 테이블을 수정한다.

4. 사용자 프로세스를 재시작한다.

페이지 교체 알고리즘 (Page Replacement Algorithms)

운영체제는 페이지 부재율(page-fault rate)가 가장 낮은 교체 알고리즘을 선정한다.

1. FIFO 페이지 교체: 메모리가 적재된 시간을 기록한 뒤, 메모리에 올라온 기간이 가장 오래된 페이지를 제거한다.

2. 최적 페이지 교체: 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체한다. 하지만 예측이 어렵다는 단점이 있다.

3. LRU 페이지 교체: 페이지 별 마지막 사용시간을 기록한 뒤, 최근에 가장 사용되지 않은 페이지를 교체한다. 

4. LRU 근사 페이지 교체: LRU 페이지 교체를 지원하지 못하는 시스템이 있을 수 있다. 이때 참조비트 하나를 설정하여 어떤 페이지가 사용된 적이 있는지(1) 없는지(0) 정도는 파악하게 하는 알고리즘이다.

5. LFU 페이지 교체: Least Frequently Used, 참조 횟수가 가장 작은 페이지를 교체하는 방법.

6. MFU 페이지 교체: Most Frequently Used, 가장 작은 참조횟수를 가진 페이지는 최근에 적재된 페이지이므로, 앞으로 계속 사용될 것이라 판단한다.

4.  프레임 할당

프레임의 할당 (Allocation of Frames)

128KB 메모리 내에 1KB의 프레임이 128개 있다. 이 중 운영체제가 35KB를 차지하므로 가용 프레임은 총 93개이다.

처음부터 93번까지는 페이지 부재가 발생하면 빈 가용프레임을 사용한다. 94번째 페이지부재부터는 이미 사용한 93개의 프레임 중에서 하나를 선택해 페이지를 교체해야 한다. 프로세스가 종료되면 93개의 프레임은 가용프레임으로 반환된다.

"93개의 가용 프레임이 있고 프로세스는 2개가 있다. 각 프로세스에게 몇 프레임씩 할당할 것인가?"

최소로 할당해야 할 프레임의 수 (Minimum Number of Frames)

최소한의 프레임을 할당해야 하는 이유는 성능과 관계가 있다. 할당되는 프레임의 수가 적으면 페이지 부재가 빈번하고 그러면 프로세스 실행이 늦어지기 때문이다. 또한 하나의 명령을 실행 중에 페이지 부재가 발생하면 그 명령은 처음부터 다시 시작되어야 하기 때문에 적어도 하나의 명령어가 참조하는 모든 페이지를 적재할 수 있는 최소의 프레임은 필수다.

할당 알고리즘 (Allocation Algorithms)

1. 균등 할당(equal allocation)

m개의 프레임을 n개의 프로세스에게 할당하는 가장 쉬운 방법으로, m/n개씩 똑같이 할당해 주는 것이다.

2. 비례 할당 (proportional allocation)

프로세스마다 요구하는 메모리 크기가 다르다는 점을 감안하여, 가용 메모리를 각 프로세스의 크기에 비례하여 할당하는 방법이다.

3. 전역교체/지역교체:

전역 교체란, 페이지 부재가 발생해서 victim page를 찾을 때 다른 프로세스에게 할당되었던 페이지까지 찾는 경우다. 우선순위가 낮은 프로세스를 희생시켜 우선순위가 높은 프로세스가 더 많은 프레임을 할당 받을 수 있게 해준다.

지역 교체에서는 프로세스에 할당된 프레임의 수는 변하지 않는다. 

5. 쓰레싱 (Thrashing)

쓰레싱 (Thrashing)

할당된 프레임이 적은 프로세스는 페이지 부재가 빈번하게 발생한다.

페이지 교체가 필요하지만 이미 활발하게 사용되는 페이지들로만 이루어져 있어서 어떤 페이지가 교체되든 바로 다시 교체가 필요해진다. 과도한 페이징 작업을 쓰레싱이라고 부른다. 즉, 어떤 프로세스가 실행보다 페이징 작업에 더 많은 시간을 쓰고 있는 경우 쓰레싱이 발생했다고 한다.

쓰레싱 발생하는 과정

- 운영체제는 CPU 이용률을 감시하며, CPU이용률이 낮아지면 새로운 프로세스를 추가해 다중 프로그래밍 정도를 늘린다.

- 한정된 프레임을 여러 프로세스들이 사용하며 페이지 부재가 빈번해진다.

- 따라서 프로세스들은 페이징 장치를 기다리고, 그동안 CPU 이용률은 점차 떨어진다.

- 이를 본 운영체제는 CPU 이용률을 늘리기 위해 프로세스를 더 늘린다.

- 시스템 처리율은 매우 낮아지고 페이지 부재는 엄청 늘어나, 쓰레싱이 발행하게 된다.

쓰레싱 해결책

쓰레싱 현상을 방지하기 위해서는 각 프로세스가 필요로 하는 개수만큼 프레임을 할당해야 한다. 그너라 각 프로세스가 필요로 하는 프레임 수를 어떻게 알 수 있는가? 작업 집합 모델을 이용해 실제로 사용하고 있는 프레임의 수가 몇개인지 알아보는 방법이 있다.

작업 집합 모델 (Workin-Set Model)

구간을 정하여 최근 x번의 페이지 참조를 관찰한다. 한 프로세스가 x번 페이지를 참조했다면 그 안에 들어있는 서로 다른 페이지들의 집합을 작업집합(working set)이라고 부른다. 이 안에는 활발하게 사용되던 페이지들이 들어있다.

더이상 사용되지 않는 페이지들은 마지막 참조로부터 x번의 페이지 참조 후에는 이 집합에서 제외된다. 

이로 인해 작업집합은 프로그램의 지역성에 근사하게 된다.

작업집합의 정확도는 x의 선택에 따라 좌우된다. x가 너무 작으면 전체 지역을 포함하지 못할 것이고, 너무 크면 여러 지역성을 과도하게 포함할 것이다. 

가상 메모리 개념

가상메모리

11에서 학습한 관리방법들(메모리 오버레이, 스왑, 메모리분할시스템, 버디 등)은 메모리에 많은 프로세스들을 동시에 유지하며 다중프로그래밍을 실현하기 위한 방법이다. 메모리가 실제 메모리보다 많아 보이게 하는 기술로, 가상 메모리는 프로세스 전체가 메모리에 올라오지 않더라도 실행이 가능하도록 하는 기법이다. 

장점

- 메모리 용량부족 이슈 발생 감소: 사용자 프로그램의 크기가 물리 메모리 보다 커도 문제되지 않는다. 왜냐하면 가상 메모리는 물리메모리와 논리메모리를 분리시켜, 메인 메모리를 규일한 크기의 저장공간으로 구성된 큰 배열로 추상화시켜주기 때문이다.

- 가상 메모리는 파일의 공유를 쉽게 해주고 공유 메모리 구현을 가능하게 한다.

- 프로세스 생성을 효율적으로 처리할 수 있는 매커니즘이 있다. 즉, fork() 시스템 호출 중에 프로세스 페이지를 공유할 수 있으므로 원래 부모 프로세스의 모든 페이지를 복사할 필요가 없어진다.

단점

- 가상 메모리 구현이 어렵다.

- 만약 잘못 사용하게 된다면 성능이 현저히 저하될 수 있다.

가상 메모리의 크기

가상 메모리 시스템의 모든 프로세스는 물리 메모리와 별개로 자신이 메모리의 어느 위치에 있는지 상관없이 0번지부터 시작하는 연속된 메모리 공간을 가진다. 실제 물리 메모리 공간이 아닌 가상의 메모리 공간에서의 주소를 가상 주소라고 한다.

예를 들어 4GB 메모리를 갖는 CPU가 있다고 했을 때, 하나의 프로세스는 4GB의 주소공간을 차지한다.

다중 프로그래밍을 하기 위해 10개의 프로세스를 동시에 메모리에 올리려면 필요한 메모리는 40GB이다.

이러한 경우 가상 메모리 시스템을 사용하여, 프로세스가 지금 당장 필요하지 않은 페이지는 메모리에 적재하지 않음으로써 4GB 메모리를 40GB인 것처럼 사용이 가능해진다.

페이징 기법과 페이지 테이블 매핑 방식

요구 페이징 (Demand paging)

초기에 필요한 것들만 메모리에 적재하는 전략. 요구 페이징을 사용하는 가상메모리에서는 페이지들이 실행과정에서 실제로 필요해질때 적재된다. 즉, 한번도 접근되지 않는 페이지는 물리메모리에 전혀 적재되지 않는다.

페이징 기법

- 고정 분할 방식을 이용한 가상 메모리 관리 기법

- 물리 주소 공간을 같은 크기로 나눠 사용

- 가상 메모리에서 분할된 각 영역은 페이지, 물리 메모리의 각 영역은 프레임이라고 한다.

페이지 테이블 매핑 방식 4가지

매핑 테이블은 가상 주소가 물리 메모리의 어느 위치에 맵핑되어 있는지 알 수 있도록 정리한 표이다.  

- 직접 매핑 (direct mapping):

직접 매핑은 모든 페이지 테이블을 물리 메모리에 가지고 있는 가장 단순한 방식이다. 물리 메모리가 충분할 때 사용할 수 있으며, 모든 페이지를 물리 메모리에 가지고 있기 때문에 주소 변환 속도가 빠르다.

- 연관 매핑 (associative mapping):

물리 메모리의 여유 공간이 작을 때 사용하는 방식으로 모든 페이지 테이블을 저장장치의 스왑 영역에 저장하고 그 중 일부만 물리 메모리에 가지고 있다. 작동 방식은 캐시처럼 원하는 페이지가 있으면 hit, 없으면 miss이다. 단점은 모든 매핑을 확인해야 하므로 성능이 떨어진다는 점이다.

- 집합-연관 매핑 (set-associative mapping)  또는 디렉터리 매핑(directory mapping)이라고도 함:

연관 매핑의 성능 문제를 개선한 방식으로, 집합-연관 매핑에서는 페이지 테이블을 일정한 집합으로 자른다. 그리고 이를 관리하는 페이지 테이블인 집합 테이블(set table)에는 일정하게 자른 페이지 테이블이 물리 메모리에 있는지, 스왑 영역에 있는지에 대한 위치 정보가 저장되어 있다.

- 역매핑(invert mapping):

위의 세가지 매핑(직접 매핑, 연관 매핑, 집합-연관 매핑)에서는 페이지 번호를 기준으로 테이블을 구성하지만, 

역매핑에서는 물리 메모리의 프레임 번호를 기준으로 테이블을 구성한다.

세그멘테이션 기법과 주소 변환 방식

세그멘테이션(Segmentation)

가변 분할 방식을 이용한 가상 메모리 관리 기법으로, 물리 메모리를 프로세스의 크기에 따라 가변적으로 나누어 사용한다.

세그먼테이션-페이징 혼용 기법

- 사용자 입장에서 세그먼테이션 기법을 사용, 메모리 관리자 입장에서는 페이징 기법을 사용하는 가상 메모리 관리 기법

- 메모리 보호 및 중복 정보를 세그먼테이션 테이블에서 관리함으로써 메모리 관리를 효율적으로 할 수 있다.

주소 변환 방식

세그먼테이션 기법에서 가상 논리주소를 물리 주소로 변환하는 방법과 매핑 테이블 관리 방법이 있다.

세그멘트 테이블 내 base(시작점)와 limit(한계값) 인자가 있다.

변환된물리주소 = base[s] + d 이고, 만약 이 값이 base[s] + limit[s] 를 넘기면 인터럽트가 발생한다.

s는 세그멘트 테이블 인덱스 값으로 s=2라면 base[2] = 500이다. 즉 물리주소는 500+100 = 600 이다.

base[2] + 100 < base[2]+limit[2] 이므로 인터럽트 발생 안함.

주기억장치 할당 방법

1. 연속 할당 방법

- 단일분할 할당

- 오버레이

- 스와핑

- 메모리 분할 할당

2. 분산 할당 방법

- 페이징

- 세그멘테이션

메모리 오버레이 Memory Overlay

오버레이(Overlay)
프로그램의 메모리가 주기억장치보다 클 때, 하나의 프로그램을 여러 개의 조각으로 분할한 후 필요한 조각을 순서대로 주기억장치에 적재하여 프로그램을 실행. 주기억장치의 메모리가 부족하면 불필요한 조각이 있는 곳에 새로운 조각을 중첩하여 적재한다

스왑 Swap

스와핑(Swapping)
주기억장치에 적재한 하나의 프로그램과 보조기억장치에 적재한 다른 프로그램의 메모리를 교체함. 더 나아가 가상 메모리 페이징 기능으로 발전됨.
Swap Out: 주기억장치에 있는 프로그램 -> 보조기억장치로 이동
Swap In: 보조기억장치에 있는 프로그램 -> 주기억장치로 이동

메모리 분할 방식(가변 분할, 고정 분할)

가변 분할 할당
프로그램을 주기억장치에 적재할 때 필요한 크기로 영역을 분할하는 기법. 고정 분할 기법의 단편화를 줄일 수 있음.

장점) 주기억장치 효율 증가, 다중프로그래밍 정도 증가

고정 분할 할당 (정적 할당 기법)
주기억장치의 USER 영역을 여러 개의 고정 크기로 분할하여 사용하는 기법.
프로그램 전체가 주기억장치에 적재되고, 프로그램이 분할 영역보다 크면 분할 영역을 사용할 수 없어서 빈 공간으로 남은 전체 영역을 사용하는 외부 단편화가 발생한다. 반대로 분할 영역보다 크기가 작은 프로그램을 적재하였을 때 내부 단편화가 발생한다

장점) 초기에 다중프로그래밍을 위해 사용

단편화(Fragmentation)
할당하고 반납하는 과정에서 발생하는 사용하지 않는 작은 조각
내부 단편화: 분할 영역보다 적재한 크기가 작을 때 사용하지 않는 작은 조각
외부 단편화: 프로그램 크기가 분할 영역보다 커서 사용하지 않는 분할 영역

버디 시스템 Buddy System

버디 시스템

외부단편화를 해결하기 위한 방법으로, 버디는 버퍼가 나누어 질 때 각각의 공간을 가리킨다.

큰 버퍼들을 반복적으로 반으로 나우어 작은 버퍼들을 만들며, 가능할 때마다 인접한 자유로운 버퍼들을 합치는 과정을 반복한다.

외부단편화를 해결하는 방법

특히 외부단편화는 큰 크기의 페이지 프레임을 할당해 달라는 요청을 받았을 때, 자잘한 프레임만 많이 남아있어 큰 크기의 연속적인 프레임을 할당해줄 수 없는 문제를 말한다. 이 문제를 해결하기 위한 방법이 버디시스템이다.

1. 페이징 회로를 활용하여 불연속적인 여유 페이지 프레임의 그룹을 연속된 가상 주소 구간에 매핑한다.

2. 남아있는 연속된 여유 페이지 프레임 블록을 관리하는 적절한 기법을 개발하여, 작은 블록을 요청할 때 큰 여유 블록을 쪼개서 할당하는 경우를 가능한 한 줄인다.

프로세스 간 통신의 종류(전역변수, 파일, 파이프, 소켓)

프로세스 간 통신의 개념
프로세스가 다른 프로세스와 데이터를 주고 받는 것을 의미하며 프로세스 내부 데이터 통신, 프로세스 간 데이터 통신, 네트워크를 이용한 데이터 통신이 있다.

프로세스 간 통신의 종류
- 전역 변수를 이용한 통신: 공동으로 관리하는 메모리를 사용하여 데이터를 주고받는 것이다.
- 파일을 이용한 통신: 저장장치에 파일을 읽고 쓰는 방법으로 데이털르 주고 받는 것이다.
- 파이프를 이용한 통신: 운영체제가 제공하는 동기화 통신 방법으로, 파이프에 쓰기 연산을 하면 데이터가 전송되고 읽기 연산을 하면 데이터를 받는다.
- 소켓을 이용한 통신: 여러 컴퓨터에 있는 프로세스와 프로세스를 소켓으로 연결하여 데이터를 주고 받는 것이다. 소켓에 쓰기 연산을 하면 데이터가 전송되고 읽기 연산을 하면 데이터를 받는다.

공유자원과 임계구역

공유 자원
여러 프로세스가 공동으로 이용하는 변수, 메모리, 파일 등을 말한다. 공유 자원은 공동으로 이용되기 때문에 누가 언제 데이터를 읽거나 쓰느냐에 따라 그 결과가 달라질 수 있다.

임계구역
공유 자원 접근 순서에 따라 실행 결과가 달리지는 프로그램의 영역을 말한다.

임계구역과 관련한 문제와 해결 방법

임계구역 해결 조건
상호 배제: 한 프로세스가 임계구역에 들어가면 다른 프로세스는 임계구역에 들어갈 수 없다.
한정 대기: 어떤 프로세스도 무한 대기하지 않아야 한다.
진행의 융통성: 한 프로세스가 다른 프로세스의 진행을 방해해서는 안된다.

임계구역 해결 방법
피터슨 알고리즘, 데커 알고리즘: 임계구역 해결 조건을 모두 만족하는 소프트웨어적인 해결 방법이다.
세마포어: 임계구역에 진입하기 전에 스위치를 사용 중으로 놓고 임계구역으로 들어가는 방법으로, 피터슨 알고리즘이나 데커 알고리즘보다 간단하고 사용하기가 쉽다.
모니터: 세마포어 알고리즘을 자동으로 처리하도록 설계한 코드이다. 보호할 자원을 임계구역으로 숨기고 임계구역ㄷ에서 작업할 수 있는 인터페이스만 제공하여 자원을 보호한다.a

교착 상태와 해결 방법

교착상태

2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만을 기다리며 작업을 진행하지 못하는 상태

교착상태의 특징, 필요조건 4가지

1. 상호배제: 최소한 하나의 자원이 비공유 모드로 점유되어야 한다. 다른 프로세스가 그 자원을 요청하면, 요청프로세스는 자원이 방출될 때까지 반드시 지연되어야 한다.

2. 점유하며 대기: 프로세스는 최소한 하나의 자원을 점유한 채, 현재 다른 프로세스에 의해 점유된 자원을 추가로 얻기 위해 반드시 대기해야 한다.

3. 비선점: 자원들을 선점할 수 없어야 한다. 즉, 자원이 강제적으로 방출될 수 없고, 점유하고 있는 프로세스가 태스크를 종료한 후 그 프로세스에 의해 자발적으로만 방출될 수 있다.

4. 순환대기: 대기하고 있는 프로세스의 집합에서 꼬리에 꼬리를 물어 자원을 대기하고 있는 상태이다.

교착상태 처리방법 3가지

1. 시스템이 결코 교착상태가 되지 않도록 보장하기 위해 교착상태를 예방하거나 회피하는 프로토콜을 사용한다.

2. 시스템이 교착상태가 되도록 허용한 다음에 회복시키는 방법. (운영체제 과목에서 배워야할 내용)

3. 문제를 무시하고, 교착상태가 시스템에서 결코 발생하지 않는 척 한다. (현실에서 가장 많이 쓰임)

프로세스의 CPU -  I/O 사이클

단일 처리 시스템에서는 하나의 CPU를 이용해 한 순간에 오직 하나의 프로세스만이 실행될 수 있다.

프로세스는 CPU를 사용하다가, I/O 요청 후 I/O작업이 완료되기를 기다렸다가, CPU를 다시 사용하는 과정의 반복이다. 

따라서 I/O를 기다리는 대기시간 동안 CPU는 시간을 낭비하게 된다.

- CPU Burst: 프로세스가 CPU를 사용할 때

- I/O Burst: I/O를 기다릴 때

CPU 스케줄링

CPU 스케줄러

CPU가 유휴상태가 될 때마다 운영체제는 1.준비완료큐에 있는 프로세스들 중 실행될 프로세스를 선택한다.

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

CPU 스케줄링의 목적

CPU 자원을 효율적으로 사용하고자

다수의 프로세스들을 메모리에 내에 올려놓은 뒤, 프로세스 하나가 대기해야하는 경우 운영체제는 CPU를 회수한 후 다른 프로세스에게 할당해주는 다중 프로그래밍이 등장하였다.

따라서 '어떻게 하면 효율적으로 CPU를 회수하고 할당해줄지' 고민하다가 고안된 것이 CPU 스케줄링이다.

* 준비완료 큐

큐를 구현할 때 선입선출 큐, 우선순위 큐, 트리, 연결리스트 등으로 구현할 수 있다. 이 큐 안에는 CPU를 할당받을 기회를 기다리며 대기하고 있다. (구체적으로 말하자면 큐에 저장된 데이터는 프로세스 전체가 아니라 PCB가 들어있음)

CPU 스케줄링 종류

CPU 스케줄링 발생 상황 네가지

[필수] 1. 한 프로세스가 실행 상태에서 대기 상태로 전환될 때 (입출력을 위한 wait 상태로 전환시)

* [선택] 2. 프로세스가 실행 상태에서 준비완료 상태로 전환될 때 (인터럽트 발생시)

* [선택] 3. 프로세스가 대기 상태에서 준비완료 상태로 전환될 때 (입출력 종료시)

[필수] 4. 프로세스 종료시

1과 4의 경우, 스케줄링 측면에서 선택의 여지가 없다. 실행을 위해 새로운 프로세스가 반드시 선택되어야 한다.

하지만 2와 3의 경우, 프로세스에게 CPU를 뺏어서 다른 프로세스에게 줄지 말지는 선택의 여지가 있다. 

1. 선점(Preemptive Scheduling)

상황 1-4에 스케줄링이 발생하는 경우로, 인터럽트가 발생하면 현재 CPU를 사용하던 프로세스는 동작을 멈추고, CPU를 반납한다.

차순위의 다른 프로세스는 CPU를 할당받아 사용한다. 이러한 인터럽트는 어느 시점에서건 일어날 수 있고, 이때 공유자원을 사용하고 있었다면 공유자원의 일관성에 해를 끼칠 수 있다는 단점이 있다.

이를 해결하기 위해 등장한 것이 임계 뮤텍스 등이 있다. 추후 포스팅 예정.

2. 비선점형

상황 1과 4에서만 스케줄링이 발생하는 경우로,비선점형 스케줄링이라고 한다.

비선점 스케줄링 하에서는 일단 CPU가 한 프로세스에 할당되면, 프로세스가 종료하든지 또는 대기 상태로 전환해 CPU를 반환할 때까지 CPU를 점유한다.

CPU 스케줄링 알고리즘

스케줄링 기준

1. CPU 이용률: CPU를 가능한 최대한 바쁘게 유지하기 위함.

2. 처리량(throughput) : 단위시간당 완료된 프로세스의 개수임. CPU가 프로세스를 실행하느라 바쁘다면, 작업이 완료되고 있는 중이다. 

3. 총처리시간(turnaround time) : 하나의 프로세스를 실행하는데 소요된 시간. 메모리에 적재되기 위해 기다리며 소비한 시간과 준비완료에서 대기한 시간, CPU에서 실행하는 시간, 그리고 입출력 시간을 합한 시간을 말한다.

4. 응답시간(response time) : 하나의 요청을 한 이후, 첫 응답이 나올 때까지의 시간. 응답이 시작되는 데 까지 걸리는 시간을 말하는 것이며 응답을 출력하는데 걸리는 시간은 아니다.

CPU 이용률, 처리량은 높을 수록 좋으며, 총 처리시간과 응답시간은 짧을수록 좋다.

스케줄링 알고리즘 종류

1.선입 선처리 (FCFS, First Come First Scheduling) 알고리즘

CPU를 먼저 요청한 프로세스가 CPU를 먼저 할당받는다. 이는 준비완료 큐를 FIFO 큐 형태로 구현하면 쉽다.

단점) 최악의 경우 평균대기시간이 길수도 있음.

2. 최단 작업 우선순위 (SJF, Short Job First Scheduling) 알고리즘

CPU가 이용가능해지면, 다음 CPU버스트가 가장 작은 프로세스에게 할당한다. 만약 버스트가 동일한 두 프로세스가 있다면 순위를 정하기 위해 선입 선처리 스케줄링을 이용한다.

-선점형 SJF: 최소 잔여시간을 기준으로 가장 짧은 프로세스가 있으면 스케줄링을 함.

-비선점형 SJF : 현재 실행하고 있는 프로세스가 자신의 CPU버스트를 끝낼 때까지 기다려준다.

단점) 다음 CPU요청의 길이를 예상하는 것이 어려움. (일괄처리시스템에선 가능)

3. 우선순위 (Priority Scheduling) 알고리즘

CPU는 우선순위가 가장 높은 프로세스에게 할당된다. 우선순위가 같은 프로세스들이 있다면 선입 선처리 순서로 스케줄된다. 우선순위는 CPU버스트가 클수록 우선순위가 낮다. 

단점) 우선순위가 낮은 프로세스들은 무기한 봉쇄(indefinite blocking) 또는 기아상태(starvation)에 처한다. 이를 해결하기 위해 ageing(대기시간이 길어진 프로세스들에게 우선순위를 높임)을 도입한다. 

4.라운드 로빈 (Round-Robin Scheduling) 알고리즘

시분할 시스템을 위해 설계된 알고리즘으로, 선입선처리 알고리즘에 시스템이 프로세스들 사이를 옮겨 다닐 수 있도록 선점을 추가한 기법이다.

준비완료큐는 원형 큐를 이용하여 동작하며, CPU스케줄러는 준비완료큐를 돌면서 한번에 한 프로세스에게 한번의 시간할당량 동안 CPU를 할당한다. 여기서 시간할당량이란, 10~100 ms이다.

5. 다단계 큐 (Multi-level Queue Scheduling) 알고리즘

준비완료 큐를 다수의 큐로 구현하여 level을 여러개로 나눈다. 그리고 각 level의 큐들은 각자의 스케줄링 알고리즘을 갖고 있으며, 우선순위도 정해져있다. 또한 큐와 큐 사이에 스케줄링도 존재한다.

6. 다단계 피드백 큐 (Multi-level Feedback Queue Scheduling) 알고리즘

다단계큐 스케줄링 알고리즘(5)에서는 프로세스들을 한 큐에서 다른 큐로 이동하지 않는 반면, 다단계 피드백 큐 스케줄링 알고리즘에서는 프로세스가 큐 사이를 이동하는 것을 허용한다. 예를 들면 CPU버스트가 높으면 낮은 우선순위의 큐로 이동하는 것이 가능하다. 또한 낮은 우선순위의 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위의 큐로 이동할 수 있다. 

참고 링크) 공룡책 9판 CH6 https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/6_CPU_Scheduling.html

참고 도서) 공룡책 8판 CH5

프로세스의 메모리 영역

프로세스 메모리는 4개의 섹션으로 나뉜다.

1. text 영역

프로그램이 시작될 때, 비휘발성 저장소(ROM)에서 읽어온 컴파일 된 프로그램 코드로 구성되어 있다.

2. data 영역

main 코드를 실행하기 전, 할당되거나 초기화된 전역변수, 정적변수를 저장하는 공간이다.

3. heap 영역

동적메모리 할당에 사용되며, 자바나 파이썬에서 new, delete 또는 C계열 언어에서 malloc, free 등 호출로 관리된다.

4. stack 영역

지역변수가 선언될 때, 지역변수를 위해 예약되고 변수가 범위를 벗어나면 공간이 해제된다. 예를 들면 메서드 내에서만 쓰이는 변수 등

* 여기서 스택과 힙은 메모리의 반대편 끝에서 시작하며, 서로의 방향으로 메모리가 할당된다. 만약 중간에서 만나게 되면 스택쪽에는 스택오버플로우 오류가 발생하거나, 힙쪽에서는 메모리 부족으로 new 또는 malloc 호출에 실패한다.

프로세스의 생성, 복사 - fork()와 exec() 시스템 호출

부모 프로세스와 자식프로세스

프로세스는 fork 또는 spawn과 같은 시스템 호출을 통해 다른 프로세스를 생성할 수 있다.

각 프로세스에는 프로세스 식별자 또는 PID라고 하는 정수 식별자가 있다. 부모의 PID (PPID)도 각 프로세스에 저장된다.

유닉스 시스템에서 시스템을 init 하면서 시작되는데, 이때 모든 시스템 데몬과 사용자 로그인이 시작된다.

프로세스 스케줄러는 PID 0으로 지정되고, init 프로세스가 PID 1이다.

1.프로세스 생성 (분기라고도 함)

자식은 메모리에서 동일한 프로그램 및 데이터 세그먼트를 공유하는 부모의 복제본이다. 자식 프로세스는 프로그램 카운터, PID, 레지스터 를 포함한 자체 PCB를 갖는다. 유닉스 시스템에서는 fork 시스템 호출을 사용.

2.프로세스 실행

자식프로세스는 코드역역, 데이터 영역과 함께 새 프로그램을 갖는다. 유닉스 시스템에서는  exec 시스템 호출을 사용.

3.프로세스 대기

부모프로세스는 자식 프로세스를 만든 후, 자식프로세스가 종료될 때까지 기다린다. wait 시스템 호출을 사용.

병렬처리 작업을 하게 되면 부모 프로세스는 이때 기다리는 동안 다른 자식 프로세스들을 분기시킬 수 있다.

4.프로세스 종료

프로세스는 int를 반환하는 exit() 시스템 호출을 통해 종료를 요청할 수 있다. 반환되는 int 값은 부모 프로세스로 전달되며 부모는 대기상태에서 해제된다. 자식 프로세스가 성공적으로 종료되면 부모프로세스에세 int값 0을 전달하고, 만약 오류가 발생하면 그외 값 전달한다. 

* 프로세스 종료시 발생할 수 있는 오류에는

- 시스템이 해당 프로세스에게 할당해줄 자원이 부족한 경우

- kill 명령 또는 인터럽트에 대한 응답이 발생한 경우

- 부모프로세스가 자식 프로세스를 죽이는 경우

-부모프로세스가 없는 고아 프로세스가 된 경우

참고 링크) https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/3_Processes.html

참고 도서) 공룡책 8판 ch3

프로세스 제어 블록 PCB Process Control Block

각 프로세스는 운영체제에서 프로세스 제어블록에 기록된다. 특정 프로세스에 관련된 여러 정보가 담겨 있다.

1. 프로세스 상태

생성, 준비, 실행, 대기, 정지 상태 등

2. 프로그램 카운터

프로세스가 다음에 실행할 명령어의 주소를 가리킨다.

3. CPU레지스터들

CPU 레지스터에는 누산기(Accumulate), 인덱스 레지스터, 스택 레지스터, 범용레지스터들과 상태코드 정보가 포함된다.

* 상태코드는 인터럽트 발생시 프로그램 카운터와 함께 저장되어야 인터럽트 처리 완료 후 중단된 지점부터 실행 가능함.

4. CPU스케줄링정보

프로세스 우선순위, 스케줄 큐에 대한 포인터와 다른 스케줄 매개변수들이 들어있다.

5. 메모리 관리정보

운영체제가 지원하는 메모리 시스템에 따라 기준(base)레지스터와 한계(limit)레지스터, 페이지 테이블 또는 세그먼트 테이블 등과 같은 정보를 포함한다.

6. 회계(Accounting)정보

CPU가 사용된 양과 시간, 시간제한, 계정번호, 프로세스 번호 등을 포함한다.

7. 입출력 상태정보

프로세스에 할당된 입출력장치들과 파일목록 등을 포함한다.

문맥교환 Context Switch

문맥교환 Context Switching 필요한 이유

인터럽트는 운영체제가 CPU를 현재 작업에서 뺏어 커널 루틴을 실행할 수 있게 한다.

인터럽트가 발생하면 시스템은 인터럽트 처리가 끝난 후에 문맥을 복구할 수 있도록 현재 실행중인 프로세스의 현재 문맥을 저장할 필요가 있다.

문맥교환 Context Switch

문맥 context는 CPU의 레지스터의 값, 프로세스 상태, 메모리 관리 정보 등을 포함한다. 이 정보들은 PCB에 기록된다.

따라서 State Save(CPU의 현재상태 저장 작업)과 State Restore(연산을 재개하기 위한 상태복구작업)이 수행된다.

이 작업을 문맥교환 Contect Switch라고 한다. 문맥교환 시간 동안은 시스템은 아무런 일도 하지 못하기 때문에 순수한 오버헤드가 된다. 문맥교환을 효율적으로 하기 위한 메모리 관리기법에 좌우된다. (메모리 관리 기법은 따로 포스팅 예정)

참고도서) 공룡책 8판