Minsoo's Studyroom

4) 파일 시스템 구현 (File System Implementation)

앞서 설명하였듯 파일을 사용하려면 파일이 반드시 열려야 하며 open() 호출은 파일 시스템에 파일 이름을 넘겨준다. open() 시스템 호출은 먼저 그 파일이 다른 프로세스에 사용 중인지 범 시스템 오픈 파일 테이블을 찾으며 이 알고리즘은 오버헤드를 줄이는데 도움이 된다. 또한 디렉토리 연산의 속도를 향상 시키기 위해 통상 디렉토리 구조의 일부는 메모리에 캐싱한다.

파일이 발견되면 FCB가 메모리 내의 범 시스템 오픈 파일 테이블에 복사된다. 테이블은 FCB와 프로세스의 수도 저장한다. 범 시스템 오픈 파일 테이블 안에는 테이블의 항목에 대한 포인터와 몇 개의 다른 필드를 갖는 프로세스 별 항목이 만들어진다. 이 필드들 파일 안의 현재 위치(다음 read() 또는 write() 연산이 시작되는 위치)를 가리키는 포인터와 파일이 열린 접근 모드 등을 포함한다.

Open() 호출은 프로세스 별 파일 시스템 테이블 내의 해당 항목에 대한 포인터를 찾아 돌려준다. 그 후 모든 파일 연산은 이 포인터를 통해 실행된다. 일단 해당 FCB를 디스크에서 찾으면 시스템은 파일 이름을 더 이상 사용하지 않기 때문에 파일 이름은 오픈 파일 테이블의 한 부분이 아니다. 그러나 같은 파일에 대한 차후 open() 연산을 빠르게 하기 위해 캐시될 수 있다. 유닉스에서는 파일 기술자라 부르고 Windows에서는 파일 핸들이라 부른다.

파일을 닫지 않는 이상 모든 파일 연산은 오픈 파일 테이블에서 이루어진다. 프로세스가 파일을 닫을 때 프로세스 별 테이블 항목이 삭제되며 범 시스템 항목의 오픈 계수는 감소 된다. 사용자가 열었던 모든 파일을 닫으면 갱신된 메타데이터 정보가 디스크 기반 디렉토리 구조에 복사되며 시스템 오픈 파일 테이블에서 그 항목이 삭제된다. 

이런 구조들은 캐싱 기법을 사용함으로써 실제 자료 블록을 제외한 오픈 파일에 대한 모든 정보는 메모리 내에 존재한다. 디스크 입/출력 작업을 줄일 수 있다.

사용자는 지역 디스크의 여러 파일 시스템이나 네트워크를 통하여 이용 가능한 파일 시스템에 접근할 수 있다. 구현 세부 사항으로부터 기본 시스템 호출 기능을 격리시키기 위해 자료 구조와 프로시저가 사용 된다. 일반적으로 파일 시스템 인터페이스, VFS 인터페이스, 지역 파일 시스템 으로 세 가지 주요한 계층으로 구성되어 있다.

파일 시스템 인터페이스는 open(), read(), write(), close() 호출과 파일 기술자에 기반을 둔 인터페이스이다. 가상 파일 시스템(VFS, Virtual File System)은 VFS 인터페이스를 명확하게 정의함으로써 파일 시스템의 일반적 연산을 구현과 분리 시킨다. VFS 인터페이스에 대한 다른 구현들이 같은 기계 상에 공존할 수 있으므로 다른 형태의 파일 시스템을 지역적으로 장착함으로써 투명한 접근을 가능하게 한다. 또한 전체 네트워크에 걸쳐 파일을 유일하게 표시할 수 있는 기법을 제공한다. vnode라는 전체 네트워크에서 파일을 유일하게 만들어주는 수치 지정자(designator)를 포함하고 있다. VFS는 특정 파일 시스템 고유의 연산을 활성화시킴으로써 파일 시스템 유형에 따른 지역 요청들을 처리하며 원격 요청에 대해서는 NFS 프로토콜 프로시저를 호출 한다. 파일 핸들은 연관된 vnode 들로부터 구성되며 이들 프로시저에 매개변수로 전달 된다.

5) 파일시스템(File System)의 종류

5-1) FAT (File Allocation Table)

Microsoft에서 빌게이츠가 만들었으며 전 세계적으로 가장 많이 사용되는 파일시스템이다. 최초 제작 시에는 저장장치의 크기가 매우 작았으며 여러 번의 발전을 거듭하여 제작하였다. 매우 단순한 구조와 최근에는 대용량을 위해서 FAT16, FAT32 등으로 발전되었다.

① FAT16 (File Allocation Table)

MS-DOS를 개발할 당시 사용하던 파일 시스템으로 윈도우 95, 윈도우 98, 윈도우 NT, 윈도우 2000 등에서 사용되며 대부분의 MS OS에서 호환이 된다는 장점이 있다.

그러나 하나의 파티션으로 최대 2GB 밖에 설정을 할 수 없고,  보안이나 암호화 및 압축 기능들을 지원하지 않는 단점이 있다. 또한, 한 클러스터에 1632KB를 할당하여 용량 낭비가 심하다.

② FAT32

FAT 파일 시스템을 보강한 파일시스템으로  FAT 파일시스템은 2GB 밖에 지원하지 않던 문제를 해결하여 2TB까지 지원한다. 영문 256문자 ( 한글 128 문자 ) 까지 파일 이름 지원한다. 뿐만아니라  클러스터당 4K 배정하여 용량 낭비가 줄어들었다는 장점이 있다. 하지만 FAT16 과 마찬가지로 보안, 암호, 압축 기능을 지원하지 않는다.

5-2) NTFS (New Technology File System)

MS에서 FAT가 서버용으로 부족하자 이를 보완하기 위해 만든 파일시스템으로 Window NT에서 사용되는 파일시스템으로 윈도우 NT 및 2000 이상부터 대표적인 파일시스템으로 자리 잡았다.  NTFS 는 대용량 하드 지원, 보안과 암호화 또한 지원.  별도의 압축 프로그램 없이도 파일과 폴더를 압축할 수 있다. 클러스터 크기는 512byte ~ 64KB까지 지원하며, 기본적으로 4KB를 지원한다. 뿐만 아니라 파일 접근 속도 최적화, 이론적으로 거의 무제한의 하드 디스크 공간 관리.  긴 파일 이름, 디스크 손실 방지, 자체적 오류 수정, 트랜잭션 로깅,  디렉토리 및 파일 수준의 보안, 충돌 보호, 실시간 압축 등을 지원한다.

5-3) HPFS (High Performance File System)

IBM의 OS/2 1.2부터 사용되던 파일시스템으로 NTFS가 나오기 전 많은 영향을 준 파일 시스템으로 제작당시 대용량에 적합한 구조로 효율적인 캐싱과 FAT에 비해 파일 손실과 단편화가 적기에 서버시스템에 많은 요구를 충족시키던 파일 시스템으로 알려져 있다. 하지만 대용량을 타겟으로 잡기에 200MB 이하의 저장장치에서는 성능 저하 문제가 발생한다.  

5-4) UFS (Unix File System)

UFS는 유닉스의 대표적인 파일시스템으로 많은 유닉스 계열의 OS들이 UFS를 각각의 OS에 맞게 변형해서 사용하고 있다. 빠른 속도와 안정성을 목표로 만들어졌다. 저장장치 그룹화를 통하여 관련된 데이터끼리 최대한 가까운 위치에 자리 잡아 헤드의 이동이 적다. 중요 데이터는 여러 그룹에 걸쳐 많은 백업을 저장하여 신뢰성을 높였다.

Berkeley대학의 FFS(Fast File System)을 근간으로 리눅스 파일시스템인 Ext2에 큰 영향을 주었다.

5-5) Ext2 (second Extended File System)

현재 리눅스의 기본 파일시스템인 Ext3에서 저널링 기능을 뺀 파일 시스템으로 UFS의 유명무실한 구조를 제거하고 전체 구조보다 간략히 하여 속도와 안정성을 고루 갖춘다.

1. Project Introduction

파일 시스템이란 파일의 실제 데이터와 메타데이터(파일의 위치, 크기, 소유자, 허가권 등, ls -al로 볼 수 있는 파일정보)를 유지/저장하는 체계로써 파일에 이름을 붙이고, 저장이나 검색을 위해 논리적으로 그것들이 어디에 위치시켜야 하는지 등을 나타내는 방법이다.

윈도우, OS/2, 매킨토시 및 유닉스 기반의 운영체계들은 모두 파일들이 어딘가에 계층적인 구조로 위치하는 파일 시스템을 가지고 있다. 파일은 계층구조 내의 올바른 디렉토리 또는 서브디렉토리 내에 놓여진다.

2. Project Goals

앞서 설명한 구조의 파일시스템을 구현하는 것으로, 모든 구현이 완료된 후에 disk.img 파일을 읽어와 마운트 시킨 후, 랜덤으로 10개의 파일 이름을 할당 받은 후 올바른 구조에 따라 해당 파일 이름의 데이터를 출력하는 것이다. 따라서 Mount 완료한 super block의 정보를 모두 출력하고, inode table에 들어있는 모든 정보를 파악하여 원하는 파일을 올바르게 읽어오는지 확인하고 출력하는 것이 이번 프로젝트의 목표이다. 뿐만 아니라 write기능을 추가하여 해당 파일의 데이터를 사용자가 원하는 데이터로 수정될 수 있도록 구현하는 것도 이번 프로젝트에서 해야 할 목표이다.

본 프로젝트를 구현함에 있어 파일시스템의 개념에 대해 이해하고, 구조, 특징 역할등을 파악하여 파일시스템이 필요한 이유에 대해서 생각하며, 각종 파일시스템의 종류를 알아보고 차이점을 찾아 파일시스템에 대한 이론을 숙지하는 것이 이번 프로젝트의 목적이다.

파일시스템의 이론을 확립하여 실제 파일시스템에서 작동하는 open, read, write를 구현하며, 추가 directory생성, 다수 사용자의 공유 파일사용 등 여러 명령을 어떻게 가능하도록 할지에 대해서 알아보도록한다.

3. Concepts used in CPU simulation

1) 파일시스템(File System)

1-1) 파일시스템이란?

컴퓨터에서 파일이나 자료를 쉽게 발견 및 접근할 수 있도록 보관 또는 조직하는 체제를 가리키는 말이다. 저장 매체의 크기가 증가 할수록 보관하는 파일의 수 또한 점점 증가하게 되어 별도의 관리 시스템이 필요하다. 따라서 개발된 것이 파일시스템이다. 파일시스템 종류에는 UFS, FAT16, FAT32, NTFS,  ext2, ext3, ext4, HFS+ 등이 있다. 

1-2) 파일이란?

파일은 프로그램 또는 데이터 등과 같은 정보들의 집합을 말한다. 이러한 정보를 저장할 수 있는 기억장소 공간은 디스크에 할당되어 있으며 디스크에 존재하는 여러 파일들은 각자 고유한 이름을 가짐으로서 구별된다.

1-3) 파일시스템 구조

파일시스템은 파일에 대한 메타데이터 즉, 파일 데이터의 데이터가 저장된 영역과 실제 데이터가 기록된 영역 2가지로 구분된다.

- 메타 영역(Meta Area) : 데이터 영역에 기록된 파일의 이름, 위치, 크기, 시간정보, 삭제유무 등 파일의 정보

- 데이터 영역(Data Area) : 파일의 데이터

1-4) 파일시스템 특징

⦁ 계층적(Hierarchical) 디렉터리 구조를 가진다.

⦁ 디스크 파티션 별로 하나씩 둘 수 있다.

1-5) 파일시스템 역할

⦁ 파일관리 : 파일 저장, 참조, 공유

⦁ 보조 저장소 관리 : 저장 공간 할당

⦁ 파일 무결성 메커니즘 : 파일이 의도한 정보만 포함하고 있음을 의미

⦁ 접근 방법 : 저장된 데이터에 접근할 수 있는 방법 제공

1-6) 파일시스템 목적

⦁ HDD와 메인 메모리 속도차 줄이기

⦁ 파일 관리 용이

⦁ HDD의 막대한 용량을 효율적으로 이용

1-7) 파일시스템은 왜 필요한가?

파일은 정보를 저장할 수 있는 기억장소공간이 디스크에 할당되어 있으며 디스크에 존재하는 다른 파일들과 구별할 수 있는 고유의 이름이 존재한다. 여기서 디스크란 소멸하지 않는 기억장치이다. 다시 말해 디스크에 저장된 데이터나 프로그램, 즉 파일은 프로세스가 수행을 완료하고 사라진 후에라도 여전히 남아있게 된다. 디스크는 고정된 블록단위로 데이터를 저장하게 된다. 모든 디스크의 입력과 출력은 섹터(물리적 레코드)단위로 이뤄진다. 연속적인 바이트로 구성된 파일이 일정 바이트로 나뉘어져 디스크 곳곳에 저장된다. 이때, 한 가지 문제점은 사용자는 블록에 관한 정보를 아무것도 모른다는 점이다. 메모리는 바이트 단위로 읽어 들일 수 있지만 디스크는 바이트 단위로 읽어 들일 수 없는 구조로 되어 있다. 그렇기에 파일 시스템이 파일과 디스크 블록 간에 밀접한 연결 작업을 해주어야 한다.

2) 파일시스템 마운팅

[파일 마운팅(File Mount)]

파일이 사용되기 전에 수행하는 작업으로 파일 시스템은 프로세스들에 의해 사용되기 전에 mount 되어야 한다.

즉, 운영체제(OS)에게 장치의 이름과 파일 위치가 주어진다. 일반적으로 마운트 포인트는 장착되는 파일 시스템이 부착될 비어있는 디렉토리이다. 운영체제(OS)는 장치가 유효한 파일 시스템을 포함하는지 확인한다. 그 과정은 장치 드라이버가 장치 디렉토리를 읽고 디렉토리가 유효한 포맷을 가지고 있는지 확인하도록 요청함으로써 이루어진다. 운영체제는 파일 시스템이 지정된 마운트 포인트에 장착되었음을 디렉토리 구조에 기록한다. 이 기법은 운영체제가 디렉토리 구조를 순회하고 파일 시스템을 적절히 교체할 수 있게 한다.

3) 파일시스템(File System) 모델

3-1) 슈퍼블록(Super Block)

UFS(Unix File System)에서 슈퍼블록은 수많은 정보들을 포함하고 있다. 이러한 값들로 파일시스템에 레이아웃을 정의 할 수 있는 것이다.

super block에 있는 filesystem 상태를 기술하는 여러 field를 보면,

- filesystem의 크기

- filesystem 내의 free block 수

- inode의 list 크기

- filesystem 내의 free inode 수

- filesystem 내의 free inode의 list

- free inode list의 다음 free inode의 index

- free block list와 free inode list를 위한 lock field들이 있다.

3-2) inode(Index node)

process가 disk의 file을 access하기 위한 도구로 'inode table = inode list'를 이용한다.

어느 한 file이나 directory가 만들어질 경우 그에 해당되는 하나의 inode가 만들어 지고 그 inode가 inode list에 등록되는데, 이 때 등록된 번호를 'inode number'라 한다.

inode 하나는 64 byte의 크기이고, 어떤 file이나 directory에 대한 모든 정보가 해당 inode에 담겨져 있어 file을 대표한다.

* 한 inode에 담겨진 내용을 보면 다음과 같다.

    - file type, access mode

    - link된 갯수

    - file의 크기(byte수)

    - file이 마지막으로 access, write되고 inode가 change된 시간

    - 'direct'로 data block을 가리키는 12 pointer의 array

    - 'indirect' pointer

    - file에 의해 사용된 physical block의 수

※ file의 크기와 'inode의 data block pointer'의 관계

- file의 최대 크기 : ① + ② + ③ 하면 된다.

① 'direct' pointer 12 개 : 8192 x 12 / 1024 = 96 Kbyte

② 'single indirect' pointer 1 개 : 8192 x 2048 / 1024 = 16 Mbyte

③ 'double indirect' pointer 1 개 : 8192 x 2048 x 2048 /1024 = 32 Gbyte

3-3) Data block

데이터블록은 inode 에 포함된다. inode 는 몇 개의 data block 을 포함하고 있으며, 각 데이터 블록은 파일들의 데이터를 실제로 저장하고 있다.

3-4) Indirection block

간접 블록은 추가적인 데이터 블록을 사용하기 위한 포인터들이 할당되는 공간이다. 실제로 inode 는 적은 수의 데이터블록을 갖고 있으며 더 많은 데이터블록이 필요할 경우 이를 동적으로 가리킬 포인터가 저장된다.

3-5) directory file

* directory는 file 이름들의 저장 창고와 같다.

* directory는 각 file의 이름과 그 file 자체를 서로 연결시켜 주는 역할을 하므로 file 시스템의 전체적 구조를 결정지어 준다.

* directory는 많은 file들을 포함하며 또한 마찬가지로 여러 file들을 갖는 sub directory를 가질 수 있다.

* directory는 ordinary file과 구별되는 개념이지만 읽힐 때는 ordinary file과 똑같이 행동한다.

* 모든 directory는 적어도 '.'와 '..'라는 file을 가지고 있어야 하는데, '.'은 directory file 자체를 지시하고 '..'은 그 directory의 상위 directory를 나타낸다. 이들 file들을 이용하여 전체 file 시스템을 루트에서부터 차례로 내려오면서 모든 file을 탐색할 수 있다.

* pathname(경로명)

모든 file은 자신이 속해 있는 directory가 있으므로 어느 한 file을 지정하기 위해서는 그 file명은 물론 그 File이 속해 있는 directory name도 지정해야 한다. 따라서 file을 지정하기 위해서는 관련 directory name과 file명 그리고 '/'로 이루어지는 pathname(경로명)이 필요하다.

- 절대 path

- 상대 path

3-6.1) 디렉토리 구조(Directory Structure)

 [1단계 디렉토리 (Single Level Directory)]

모든 파일이 한 개의 디렉토리 밑에 있는 개념으로 같은 디렉토리에 모든 파일이 존재 하므로 각 파일은 유일한 이름을 가져야 한다. 따라서 다수의 사용자에게 제약이 크다.

 [2단계 디렉토리(Two Level Derictory)]

각 사용자는 자신만의 사용자 파일 디렉토리(User File Directory, UFD)를 가지고 있으며 UFD는 비슷한 구조를 가지고 있지만 각 디렉토리에는 오직 한 사람의 파일 만을 저장한다.

사용자의 작업이 시작되거나 시스템에 사용자가 로그인을 통해 접속하면 시스템은 마스터 파일 디렉토리(Master File Directory, MFD)를 먼저 탐색한다. MFD는 사용자 이름이나 계정 번호로 색인되어 있으며 각 항목은 그 사용자의 UFD를 가리키고 있다.

2단계 디렉토리 구조에서 파일 이름이 충돌하는 문제는 어느 정도 해결하였으나 한 사용자의 UFD를 다른 사용자가 접근을 할 수 없기 때문에 파일을 공유해서 사용하는 경우는 공유가 불가능하다. 따라서 접근을 허용하려면 한 사용자가 다른 사용자의 디렉토리에 있는 파일을 지칭 할 수 있어야 한다.

 [트리 구조 디렉토리(Tree Structure Directory)]

여러 단계로 확장하는 일반적인 방법의 임의의 높이를 갖는 트리 구조이다. 일반 사용자들에게 자신의 서브디렉토리(subdirectory)를 얼마든지 만들 수 있게 해준다. 트리는 가장 일반적인 디렉토리 구조이다.

 [비순환 그래프 디렉토리(Acyclic Graph Directory)]

트리 구조는 파일 또는 디렉토리의 공유를 허용하지 않는다. 비순환 그래프는 디렉토리들이 서브디렉토리들과 파일 들을 공유할 수 있도록 허용하는 구조로 똑같은 파일이나 서브디렉토리가 서로 다른 서브디렉토리에 있을 수 있다. 비순환 그래프는 트리 구조 디렉토리 방식을 일반화한 것이다.

파일을 공유하는 방법으로는 링크(link)라 불리는 새로운 디렉토리 항목을 만드는 것과 디렉토리들이 동일한 항목 내용을 복사해서 가지고 있는 방법이 있다. 후자의 경우에는 일관성에 문제가 발생한다. 링크의 경우는 다른 파일이나 서브디렉토리를 가리키는 포인터를 가지고 참조한다. 디렉토리를 검색할 때 디렉토리 항목이 링크로 표시되어 있다면 실제 파일 이름을 링크 정보에 포함되어 있다. 실제 파일에 대한 경로 이름을 사용함으로써 링크를 해석(resolve) 한다.

 일반 그래프 디렉토리(General Graph Directory)]

비순환 그래프 트리 구조에 있어서 중요한 문제점은 순환이 발생하지 않도록 어떻게 보장하느냐는 것이다. 2단계 디렉토리부터 시작해서 사용자가 서브디렉토리를 생성하면 트리 구조가 형성된다. 단순히 새로운 파일이나 디렉토리를 기존의 트리 구조 디렉토리에 추가하는 것은 트리 구조의 성질을 유지 하지만 기존의 트리에 새로운 링크를 추가하면 트리 구조는 파괴되고 일반적인 그래프 구조가 될 수 있다.

비순환 그래프의 장점은 파일을 검색하고 파일에 대한 참조의 존재 여부를 결정하는 알고리즘이 비교적 간단하다는 것이다. 하지만 성능적인 측면에서 비순환 그래프의 공유 부분을 두 번 순회하는 것은 좋지 않다. 잘못 설계된 알고리즘은 계속 탐색하고 종료하지 못하는 무한 루프에 빠질 수도 있다. 한 가지 해결책은 한 번에 검색 할 수 있는 디렉토리의 숫자를 임의로 제한하는 것이다.

3-7) Meta data

파일 사용자 ID, 파일 형태, 크기, 저장장소, 정보의 장소(offset), 버퍼, 시간 정보(생성시간, 최근 읽기,쓰기된 시간)등의 정보들이 저장된 데이터를 의미한다. 파일에 접근하는데 필요한 정보를 가진 Meta data가 있어야 파일이 제대로 관리될 수 있으며 이들은 디스크 내부에 파일과 별도로 저장된다.
 

3-8) 버퍼 캐쉬(buffer cache)

파일 사용자와 디스크의 사이에 자리 잡고 완충 역할을 하게 되는 장치이다. 파일을 사용할 때마다 디스크에서 일일이 읽어오려면 속도가 상당히 느리다. 따라서 처음 읽은 파일은 버퍼 캐쉬에 내용을 저장해 둠으로써 이후 사용자가 동일한 파일을 사용하길 원할 때 읽어오는 속도를 높일 수 있는 것이다. 바로 파일에 접근하는 것도 지역적 성격을 갖고 있기 때문에 버퍼 캐쉬를 사용할 수 있는 것이다. 그러나 버퍼 캐쉬가 무한정의 메모리를 사용할 수는 없다. 그러므로 용량의 제한으로 버퍼 캐쉬에 저장된 목록을 교체해야 한다. 이때 앞서 메모리 관리에서 배운 LRU Policy가 일반적으로 쓰인다. 이러한 버퍼 캐쉬는 시스템에 하나만 존재한다. 이유는 버퍼 캐쉬 상에 변화가 생기면 해당 변화를 다른 장치들도 알고 있어야 하기 때문이다.

4) 가상 메모리의 부가 장점

가상 메모리를 사용하면서 생기는 부가 장점으로 다음과 같은 것들이 있다.

º 공유 메모리 사용

º Copy-on-write 메커니즘

º Memory mapped file

4-1) 공유 메모리 사용

여러 프로세스 간의 communication의 한 가지 방법으로 공유 메모리를 사용할 수 있는데, demand-paging 기법을 사용할 경우 다른 프로세스의 각각의 페이지가 같은 프레임을 가리키도록 하면 공유 메모리를 사용할 수 있다.

윈도우의 dll이나 리눅스의 so 역시 이 방식으로 물리 메모리 프레임을 같이 가리키게 하여, 전체 메모리를 절약하게 된다. 아래 그림에서 프로세스 A의 1번 페이지, 프로세스 B의 7번 페이지가 물리 메모리 5번 프레임을 같이 가리키는 것을 볼 수 있다.

4-2) Copy-on-write 메커니즘

부모 프로세스를 clone하여 자식 프로세스를 생성하였을 때, 처음에는 같은 메모리를 사용하도록 하다가 그곳에 Write가 발생하였을 때 메모리를 copy하는 것으로 이것 또한 공유 메모리처럼 같은 프레임을 가리키도록 하였다가 복사가 되었을 때 새로운 프레임을 할당하면 된다.

Linux에서는 자식 프로세스(child process)를 생성(fork)하면 같은 메모리 공간을 공유하게 된다. 그런데 부모 프로세스가 데이터를 새로 넣거나, 수정하거나, 지우게 되면 같은 메모리 공간을 공유할 수 없게 된다. 따라서 부모 프로세스는 해당 페이지를 복사한 다음 수정한다. 이것을 Copy-on-Write(COW)라고 한다. 만약 자식 프로세스가 없었다면 페이지를 복사하지 않고 바로 수정했을 것이다. 따라서 자식 프로세스가 생성되어 작업을 하는 동안 데이터 입력/수정/삭제가 발생하면 해당 메모리 페이지를 복사해야 되기 때문에 평소보다 더 많은 메모리가 필요해진다.

5) MMU(Memory Management Unit)

5-1) MMU란?

가. MMU(Memory Management Unit)의 개념

CPU와 Cache 사이 불연속적 메모리 주소를 논리적 연속된 가상 주소로 Mapping 관리 장치

나. MMU 역할

5-2) MMU 주요 기능 및 주소 변환 과정

가. MMU 주요 기능

나. MMU 주소 변환 과정

Memory Mapping 절차	절차 설명
	① MMU에 가상주소 전달
	② Page Table 탐색
	③ 물리주소 MMU에 전달
	④ 주소신호(RAS,CAS)발생
	⑤ Data를 CPU에 전달

6) TLB (Translation Look-aside Buffer)

6-1) TLB란?

가. TLB(Translation Look-aside Buffer)의 정의

자주 참조되는 가상 메모리 주소를 실제 메모리 주소로 매핑 시 성능 개선 위해 MMU(Memory Management Unit)에서 사용하는 고속 캐시.

나. TLB의 특징

6-2) TLB의 개념도 및 동작원리

가. TLB의 개념도

나. TLB의 동작원리

다. 직접사상 방식과 TLB의 비교

6-3) TLB 성능 개선 위한 고려사항

3) 페이징과 세그먼트(Paging and Segment)

3-1) 페이징 (Paging)

프로세스가 사용하는 주소 공간을 여러 개로 분할하여 비연속적인 물리 메모리 공간에 할당, 가상 메모리를 모두 같은 크기의 블록으로 나누어 메모리를 관리하는 방식.

 단위

 프레임 : 실제 메모리 공간 (4KB)

 페이지 : 프로세스의 메모리 공간 (4KB)

 프레임 사이즈 = 페이지 사이즈

★ 페이지 테이블 내에 프레임과 페이지가 서로 매핑이 되어 있어서 페이지 테이블을 참조하여 실제 메모리에 접근하게 된다.

★ 문제 : 매번 메모리의 페이지 테이블을 먼저 읽어야 하므로 메모리 접근 시간이 두 배가 된다. => 페이지 테이블의 캐시 사용

3-2) 세그먼테이션 (Segmentation)

프로세스가 필요로 하는 메모리 공간을 분할하여 비연속적인 물리 메모리 공간에 할당하는 방식. 즉, 각 영역들의 기능, 권한, 필요한 공간의 크기가 모두 다르기에 세그먼테이션 기술로 각각 다른 크기로 분할하여 효율적인 메모리 관리가 가능하도록 한 것이다.

 단위 : 세그먼트(서로 다른 크기)

 페이징과의 차이

논리적 의미에 부합하도록 세그먼트들의 크기가 서로 다름.

크기가 다 다르기 때문에 메모리를 페이징 기법에서처럼 미리 분할해 둘 수 없고, 메모리에 적재될 때 빈 공간을 찾아 할당.

 논리 주소 공간을 세그먼트 집합으로 정의.

 세그먼트 테이블

사용자가 정의한 주소를 실제 주소로 맵핑하는 정보를 저장.

개별 세그먼트는 항목별로 Base(세그먼트 시작 주소) + Limit(세그먼트 길이)의 정보를 갖는다.

3-3) 요구 페이징 (Demand Paging)

- Demanding-page는 실제로 필요한 page만 물리 메모리로 가져오는 방식을 말한다. 필요 page에 접근하기 위해선 가상 메모리 주소에 대응하는 물리 메모리 주소를 찾아내야 한다. 이 때 필요한 것이 페이지 테이블(page table)이다.

페이지 테이블에 valid bit를 두고, 해당 page가 물리 메모리에 있으면 1, 그렇지 않으면 0로 설정한다.

ex) Page fault의 경우

1) 페이징 하드웨어는 page table entry의 valid bit를 보고 invalid인 것을 확인한 후 OS에게 trap으로 알린다.

2) OS는 정말로 메모리에 없는 것인지 아니면 잘못된 접근인지 확인한 후 잘못된 접근이었으면 종료시킨다.

3) Empty frame (free page)을 얻는다.

4) Page를 frame으로 swap한다.

5) 프로세스의 page table과 TLB를 page-in/page-out 된 것을 토대로 재설정한다.

6) Page fault를 야기했던 인스트럭션부터 다시 수행한다.

=> 3)과정에서 empty frame(free page)을 얻어 와야 하는 상황에서 물리 메모리가 모두 사용 중이라면, 사용 중인 frame 중 하나를 선택해서 page-out (disk로 이동) 시키고, 그 frame을 사용해야 한다.

이처럼 victim frame을 선택하는 과정에서 Page Replacement Algorithm을 사용한다.

3-4) 페이지 교체 정책 (Page Replacement Algorithm)

메모리 공간이 부족하면 특정 페이지를 스왑 하여 교체한다.

※교체 알고리즘

◎ FIFO (First-In-First-Out)

º 메모리에 적재된 시간이 가장 오래된 페이지를 교체 (프레임 개수가 많아지면 페이지 부재 율이 높아지는 현상, Belady의 모순이 된다.)

◎ Optimal Page Replace

º 앞으로 가장 오래 사용되지 않을 페이지를 교체, 들어온 데이터를 쭉 읽어서 앞으로 사용하지 않을 걸 교체

º 다른 모든 알고리즘보다 페이지 부재 율이 낮으면서 Belady의 모순이 발생하지 않는 페이지 교체 알고리즘

º 실제 구현이 불가능하다 : 미래의 페이지 참조를 미리 알아야 함.

º 제안된 알고리즘의 성능을 비교하기 위한 목적으로 사용

◎ LRU (Least-Recent-Used)

º 가장 오랫동안 사용되지 않은 페이지를 교체.

º 최적 페이지 교체 알고리즘에 근사하는 방법, 과거 참조를 기반으로 미래 참조 형태의 근사치를 결정

º 거의 최적 알고리즘에 가까움

º linked-list로 관리

º 고려사항

    - 페이지들을 최근에 사용한 시간 순서대로 나열할 수 있어야 함

    - 하드웨어의 지원이 필요 : 모든 메모리 참조에 대해 참조 정보를 갱신

◎ LFU (Least-Frequently-Used)

º 참조 횟수가 가장 적은 페이지를 교체

º 참조 횟수가 적은건 앞으로도 안쓸것이다.

º 참조 빈도와 참조 시간은 정확히 일치하지 않습니다.

◎ MFU (Most-Frequently-Used)

º 참조 횟수가 가장 많은 페이지를 교체

º 최근에 참조가 된 페이지는 앞으로 덜 쓸것이다.

º 참조 횟수가 적은 페이지는 최근에 적재되었고 앞으로 참조될 가능성이 높을 것이라는 직관에 의존

※ 자세히 설명하자면 Demand Paging을 가능하게 하는 것은 Locality의 개념이다.

Temporal Locality는 시간적 지역성이라 하며 최근에 접근된 것이 다시 접근되는 것을 말하며, Spatial Locality는 공간적 지역성이며 최근에 접근된 것에 가까운 것이 접근되는 것을 말한다. 따라서 Locality에 의하면 접근되었던 것은 접근될 가능성이 크므로 메모리에 남아있게 되고 그것이 Demand paging의 근본이 된다.

위의 3-3)에서 Page Fault 처리 과정에서 empty frame(free page)을 얻는다고 되어 있다.
물론 empty frame이 있으면 그냥 얻으면 되겠지만 멀티프로세싱 환경에서 실행하다 보면 메모리가 꽉 차있을 경우가 있을 것이다.
이 경우에 앞서 말했듯 어떠한 기준에 의해 페이지 하나를 swap out하고 그 프레임을 할당할 것인지를 정하는 것이 Paging Replacement Algorithm이다.

첫째로 FIFO(First in First out)알고리즘은 가장 오래된 페이지를 없애는 기법으로 공평하기는 하지만 locality가 적용되지 않은 방법이므로 비효율적이다.

다음으로 Optimal 알고리즘이다. 가장 오랫동안 사용되지 않을 것을 victim으로 선정하는 것이 당연히도 가장 합리적이며 효율적이다. 하지만 가장 오랫동안 사용되지 않을 것을 정하는 것은 불가능하므로 이론적인 알고리즘이라 볼 수 있다.

그래서 Optimal 알고리즘과 원리는 유사하지만 반대로 생각한 것이 LRU 알고리즘이다. 가장 오랫동안 사용되지 않았던 페이지는 앞으로도 사용되지 않을 것이라는 가정 하에 victim으로 선정한다.

LRU 방식에는 첫째로 counter를 두어 구현할 수 있다. 카운터에 접근횟수를 기록하는 것이다.
둘째로 더블 링크드 리스트의 스택으로 구현한 뒤 어떠한 페이지가 접근되면 그 페이지를 top으로 올린다. 그리고 만약 victim을 선정해야 하면 bottom에 있는 페이지를 victim으로 선정하게 된다.

하지만 이러한 방식을 쓰면 많은 페이지 엔트리가 존재하는 페이지 테이블에서는 연산이 많아지고 각 엔트리마다 두개의 링크만큼의 공간을 필요로 하므로 비효율적이다.

따라서 Page Table에서는 LRU-approximation 알고리즘을 사용한다. 이 알고리즘은 하드웨어의 도움을 받아 하나의 bit를 두고 이용한다.

페이지들을 queue형태로 나타내고 만약 reference가 일어나면 이 bit를 set한다. 그리고 victim 페이지를 선정할 때는 하나씩 접근하여 bit를 확인한다. 만약 bit가 clear하면 그 페이지를 victim으로 선정하며, set 되어 있으면 그 bit를 clear시키고 다음 페이지를 확인한다. 해당 페이지에 Second-chance를 주는 것이므로 Second-chance algorithm이라고도 한다.

그리고 카운팅을 기반으로 한 MFU, LFU알고리즘이 있다.(설명은 위 참조)

이렇게 Virtual Memory를 사용하면 실제 존재하는 물리적 메모리 공간보다 논리적 메모리 공간이 큰 것처럼 사용될 수 있기 때문에 효율적이다. 그런데 효율적이라는 이유로 멀티프로세싱의 degree를 계속 늘리다 보면 실제 실행하는 시간보다 page replacement를 하는 시간이 더 많아지는 순간이 오게 된다. 이는 CPU Utilization을 떨어뜨리는 원인이 된다.

만약 CPU는 CPU사용률만 보고 이것을 올리기 위하여 멀티프로세싱의 degree를 더 증가시키고 이에 따라서 효율은 극악으로 나빠지게 되는데 이때, 실행 시간보다 페이지 교체 시간이 많아지는 현상을 Thrashing이라 한다. 

 
Thrashing이 발생하는 이유는 locality크기의 합이 실제 메모리의 크기보다 커졌기 때문이다. 따라서 이 Thrashing을 해결하기 위해 Working set model을 적용한다.
Working set model은 locality를 approximate한 것으로 페이지 넘버로 관리한다.
그러다 working set의 크기가 실제 메모리보다 커지면 하나의 프로세스를 종료하는 방식으로 Thrashing이 생기지 않도록 조절할 수 있다.

따라서 Thrashing이 생겼다는 것은 즉 Page Fault가 많아졌다는 것이기 때문에 그것의 정도를 지정하고 Page Fault의 횟수가 어느 한계점을 넘어가면 프로세스를 종료하는 방식으로 구현한다.

                                                                           <working set model 특징>

Virtual Memory를 사용하게 되면 생기는 부가적인 장점으로 공유 메모리 사용, Copy on write 메커니즘, Memory mapped file이 있다. 
여러 프로세스간의 communication의 한 가지 방법으로 공유 메모리를 사용할 수 있는데 demand paging 기법을 사용할 경우 다른 프로세스의 각각의 페이지가 같은 프레임을 가리키도록 하면 공유 메모리를 사용할 수 있다.

또한 COW(Copy-On-Write) 메커니즘은 부모 프로세스를 clone하여 자식 프로세스를 생성하였을 때 처음에는 같은 메모리를 사용하도록 하다가 그곳에 Write가 발생하였을 때 메모리를 copy하는 것으로 이것 또한 공유 메모리처럼 같은 프레임을 가리키도록 하였다가 복사가 되었을때 새로운 프레임을 할당하면 된다.

그리고 Memory mapped file은 file을 접근하는 것을 메모리 접근하듯이 페이지를 할당하여 할 수 있도록 하는 것이며 메모리 접근 속도가 더 빠르므로 효율적이다.


Paging은 동일한 크기를 가지는 page  단위로 메모리를 나누는 것이라 하였다.
반면에 Segmentation은 가변 크기의 단위인 segment로 메모리 영역을 나눈다. 이것은 사용자가 바라보는 관점에서 메모리를 나눈 것이며 일반적인 사용자는 페이지 단위로 메모리를 바라보지 않고 큰 단위단위로 바라보게 된다.
따라서 최근의 컴퓨터는 세그멘테이션 기법과 페이징 기법을 동시에 적용하여 메모리를 접근하게 된다.

1. Project Introduction

본 프로젝트는 실제 메모리의 크기에 비해 프로그램들의 메모리 요구량이 더욱 크기 때문에 프로그램 수행 시 모든 명령어와 데이터가 메모리에 할당될 수 없기 때문에 메모리 상황에 따라 필요한 부분만 메모리에 할당해서 수행해야 한다. 이를 가능하게 해주는 개념이 가상 메모리 (Virtual Memory)이다.

따라서 이번 프로젝트에서는 라운드로빈 스케줄링을 기반으로 하여 프로세스가 10개의 가상메모리 주소(Virtual address)를 할당받아 MMU(Memory Management Unit)을 통해 실제 메모리의 주소로 변환해서 매핑 및 데이터에 접근한다. 이때, 메인 메모리는 하드디스크의 Cache 역할을 수행하게 된다.

모든 프로그램은 프로세서에서 제공하는 최대 주소 공간만큼의 논리적 가상 메모리가 있고 프로그램이 전체 메모리를 다 사용 할 수 있다고 가정한다. (32bit 주소 => 4 GB 메모리)

2. Project Goals

이번 프로젝트에서는 가상메모리를 사용하는 이유에 대해 알아보고, 가상 접근 주소로부터 물리 메모리를 매핑 하는 방법에 대해 살펴보는 것을 목표로 한다.

또한, 각종 페이징 기법의 개념을 이해하고, 직접 물리 메모리 주소를 계산하고 매핑 함으로써 올바른 값을 도출하는지를 확인한다. 마지막으로 페이징 기법에 따른 전체 flow와 구조를 파악하여 Logic에 맞게 프로젝트를 구현하는 것이 본 프로젝트의 목적이다.

3. Concepts used in CPU simulation

1) 가상메모리(Virtual Memory)

1-1) 가상메모리란?

모든 프로세스는 자신만의 가상 주소 공간을 가진다. 32비트/64비트 프로세스는 각 비트 수에 맞게 최대 4GB/16GB의 주소 공간을 가진다. 따라서 특정 프로세스 내에서 쓰레드가 수행될 때 해당 쓰레드는 프로세스가 소유하고 있는 메모리에 대해서만 접근이 가능하다. 즉, 가상 메모리는 프로세스의 logical memory와 physical memory를 분리하기 위해 생겨난 것이라 할 수 있다. 이를 이용하여, logical memory가 physical memory보다 커지는 것을 가능하도록 할 수 있다.

1-2) 왜 가상메모리를 사용할까?

1-3) 프로세스 가상 주소 공간의 분할

각 프로세스의 가상 주소 공간은 분할되어 있으며, 각각의 분할 공간을 파티션(partition) 이라 한다. 32비트 프로세스는 4GB의 가상 주소 공간을 가질 수 있다.

하지만, 사용자는 가상의 주소 공간 4GB를 모두 사용할 수 있는 것은 아니고, 약 2GB밖에 사용하지 못 한다.

이유는 32비트 주소 공간이 다음과 같이 분할되어 있기 때문이다.

 Null 포인터 할당 파티션 : 0x00000000 ~ 0x0000FFFF

 유저 모드 파티션 : 0x00010000 ~ 0x7FFEFFFF

 64KB 접근 금지 파티션 : 0x7FFF0000 ~ 0x7FFFFFF

 커널 모드 파티션 : 0x80000000 ~ 0xFFFFFFFF

 Null 포인터 할당 파티션

프로그래머가 NULL 포인터 할당 연산을 수행할 경우를 대비하기 위해 준비된 영역이다. 만일 프로세스의 특정 쓰레드가 이 파티션에 대해 읽거나 쓰기를 시도하게 되면 접근 위반(access violation)이 발생한다.

 유저모드 파티션

프로세스의 주소 공간 내에서 유일하게 자유롭게 활용될 수 있는 파티션이다.

0x00010000 ~ 0x7FFEFFFF의 범위이므로, 2047MB의 크기이다.

2) 페이지 테이블과 엔트리(Page table & Entry)

2-1) 페이지 테이블(Page Table)

가상 메모리를 사용하는 운영 체제에서 개별 프로세스는 자신만의 가상 주소 공간을 가지고 있다. 32비트 프로세스는 0x0000:0000에서 0xFFFF:FFFF까지 표현될 수 있기에 4GB 크기의 주소 공간을, 각 프로세스들의 가상 메모리는 물리 메모리의 각기 다른 영역에 분산되어 로드되거나, page-out 되어 disk에만 저장될 수 있다.

프로세스가 특정 메모리에 접근하기 위해서 OS는 프로세스의 가상 주소를 시스템의 물리 메모리 주소로 변환해 주어야 한다. 페이지 테이블은 가상 주소와 물리 메모리 주소의 매핑 테이블이며, 개별 매핑 데이터는 Page-Table-Entry(PTE)라 한다.

페이지 테이블은 프로세스마다 하나씩 존재하게 되며, 메인 메모리 (RAM)에 상주하게 된다. 즉, 많은 프로세스가 구동될수록, 페이지 테이블로 인한 메인 메모리 사용이 커짐을 의미한다.

2-2) 페이지 테이블 엔트리(Page Table Entry)

프레임 테이블은 어느 프레임이 매핑 되어 있는지에 대한 정보를 들고 있다.

페이지 테이블의 엔트리는 가상 주소의 페이지와 물리 메모리 프레임간의 매핑 정보를 들고 있다. 다음과 같은 부가 정보들을 포함한다.

 valid bit (present bit)

 access bit

 dirty bit (modified bit)

 process ID information

① Valid bit

Page 단위의 메모리는 페이징 파일(디스크 파일)에서 물리 메모리로 page-in 될 수 있고, 물리 메모리로부터 페이징 파일(디스크 파일)로 page-out 될 수 있다.

위 페이지 테이블의 정보 중 valid bit는 이 page가 물리 메모리에 있는지 여부를 나타내는데 사용된다.

② Access bit

Page replacement alogorithm에 사용되며, 해당 페이지에 대한 접근이 있었는지에 대해 기록한다.

③ Dirty bit

Dirty bit는 가상 메모리 관리 시스템의 성능을 향상시키는 데 중요한 역할을 수행한다. 어떤 page가 물리 메모리로 page-in 된 이후, 내용이 전혀 달라진 게 없다면 이 page가 추후 paging file로 page-out 될 때, 달라진 게 없으므로 내용을 다시 복사하지 않아도 되게 된다. 그와 반대로 page-in 된 이후 내용이 달라진 것이 있다면, page-out 될 때 반드시 해당 내용을 paging file에 써야 할 것이다. 이 과정에서 page-out 되기까지 해당 page의 내용이 변경 되었는지를 기록하는 것이 dirty bit 이다. 만약, 이 dirty bit 이 없었다면, 모든 page-out 과정에서 page data copy가 발생할 것이고, 이는 불필요한 성능 하락을 발생시킨다.

④ Process ID information

가상 메모리 관리 시스템은 어떤 페이지가 어느 프로세스와 연관이 있는지 알고 있어야 한다. 가상 주소는 프로세스별로 독립적이므로, 주소가 같다고 해서 같은 메모리를 가리키는 것은 아니다.

페이지 테이블은 여러 프로세스가 요청한 가상 메모리 주소에 대해 정보를 각기 저장시킬 수 있어야 한다.

2-3) 페이지 테이블 종류 

페이지 테이블은 다음과 같은 종류가 있다.

 Inverted

 Multi-level

 Virtualized

 Nested

이 중 x86 이 사용하는 것은 Multi-level 방식이라고 한다. 만약 Single-level 즉, 하나의 page table로 4GB의 주소 공간을 표현하기 위해선 2 ^ 20개의 Page Table Entry(PTE)가 필요하다. (4GB / 4KB(1 page size) = 2 ^ 32 / 2 ^ 12 = 2 ^ 20)

2 ^ 20개면 1024 * 1024개의 PTE 정보를 가져야 하는데, 이 때의 페이지 테이블의 크기가 너무 커져서, 2 or 3 level paging을 하게 된다.

2-4) 페이지 테이블 구조(Page Table Structure)

 Hierarchical paging

 Hash Page Tables

 Inverted Page Table

① 계층적 페이징(Hierarchical paging)

- 32비트 컴퓨터에선 페이지 테이블은 4MB정도로 크다.

- 페이지 테이블을 작은 조각으로 나눈다. 페이지 테이블 자체가 다시 페이지 화 되는 것.

◉ p1은 Outer Page Table의 Index, p2는 Inner Page Table의 변위, d는 페이지의 Offeset

◉ 페이지의 접근 시간이 늘어나는 단점이 있다.

② 해시 페이지 테이블(Hash Page Tables)

- 해시 테이블에 각 항목은 연결리스트를 가지고 있으며, 충돌을 일으켜서 이곳으로 해시되는 원소들이 연결된다. 각 원소는 가상 페이지번호, 사상되는 페이지 프레임 번호, 연결 리스트 상의 다음 원소 포인터를 가진다.

◉ 알고리즘 :

가상 주소 공간에서 페이지 번호가 오면 그것을 해싱함수에 의해 해싱 한다.

-> 페이지 테이블에서 연결리스트를 따라가며 첫 번째 원소와 가상 페이지 번호를 비교 한다.

-> 일치하면 그에 대응하는 페이지 프레임 번호를 가져와 물리주소를 얻고, 일치하지 않으면 다음 원소로 이동하여 반복.

③ 역 페이지 테이블(Inverted Page Table)

- 보통 프로세스 마다 각자 하나씩 페이지 테이블을 가짐 -> 프로세스 전체가 공통으로 사용하는 페이지 테이블, 가상 주소에는 프로세스ID와 페이지 주소를 가지고 있다.

- 메모리공간을 작게 사용한다.

- 주소변환 시간이 더 오래 걸린다.

2) IPC(Inter Process Communication)

위 그림처럼 Process는 완전히 독립된 실행객체이다. 서로 독립되어 있다는 것은 다른 프로세스의 영향을 받지 않는다는 장점이 있다. 하지만 독립되어 있는 만큼 별도의 설비가 없이는 서로 간에 통신이 어렵다는 문제가 생긴다. 이를 위해서 커널 영역에서 IPC라는 내부 프로세스 간 통신(nter Process Communication)을 제공하게 되고, 프로세스는 커널이 제공하는 IPC설비를 이용해서 프로세스 간 통신을 할 수 있게 된다.

2-1) IPC의 종류

① PIPE

PIPE는 두 개의 프로세스만을 연결하게 되고, 하나의 프로세스는 데이터를 쓰기만, 다른 하나는 데이터를 읽기만 할 수 있다. 한쪽 방향으로만 통신이 가능한 파이프의 특징 때문에 Half-Duplex(반이중) 통신이라고 부르기도 한다.

PIPE와 같은 반이중 통신의 경우 하나의 통신선로는 읽기나 쓰기 중 하나만 가능하므로 읽기와 쓰기, 즉 양방향 송/수신을 원한다면 두개의 파이프를 만들어야만 가능해진다.

이때, PIPE는 매우 간단하게 사용할 수 있다는 장점이 있다. 만약 한쪽 프로세스가 단지 읽기만 하고 다른 쪽 프로세스는 단지 쓰기만 하는 데이터 흐름을 가진다면 PIPE를 사용하는 것이 편하다. 하지만 단점으로는 반이중 통신이라는 점으로 프로세스가 읽기와 쓰기 통신 모두를 해야 한다면 PIPE를 두개 만들어야 하는데, 구현이 꽤나 복잡해 질 수 있다. 만약 전이중 통신을 고려해야 될 상황이라면 PIPE는 좋은 선택이 아니라고 보여 진다.

② Named PIPE(FIFO)

명명 파이프(Named Pipe)는 통신을 할 프로세스를 명확하게 알 수 있는 경우 사용한다. 예를 들어 자식과 부모 프로세스 간 통신의 경우에 사용될 수 있다. 또한, Named PIPE는 ①의 PIPE 단점 중 하나인 같은 PPID(같은 부모 프로세스)를 가지는 프로세스들 사이에서만 통신이 가능한 점을 보안한 PIPE의 확장이라고 할 수 있다. Named PIPE는 부모 프로세스와 무관하게 전혀 다른 모든 프로세스들 사이에서 통신이 가능한데 그 이유는 프로세스 통신을 위해 이름이 있는 파일을 사용하기 때문이다. Named PIPE의 생성은 mkfifo를 통해 이뤄지며, mkfifo가 성공하면 명명된 파일이 생성된다.

단점으로는, Named PIPE도 PIPE의 또 다른 단점인 읽기/쓰기가 동시에 가능하지 않으며, read-only, write-only만 가능합니다. 하지만 통신선로가 파일로 존재하므로 하나를 읽기 전용으로 열고 다른 하나를 쓰기전용으로 영어서 이러한 read/write문제를 해결 할 수 있습니다. 호스트 영역의 서버 클라이언트 간에 전이중 통신을 위해서는 결국 PIPE와 같이 두개의 FIFO파일이 필요하게 됩니다.

③ Message Queue

Queue는 선입선출의 자료구조를 가지는 통신설비로 커널에서 관리한다. 입출력 방식으로 보면 Named PIPE와 동일하다고 볼 수 있다. 하지만 Name PIPE가 데이터의 흐름이라면 메시지 큐는 메모리 공간이라는 점이 다르다. 파이프가 아닌, 어디에서나 물건을 꺼낼 수 있는 컨테이너 벨트라고 생각해도 좋다.

메시지 큐의 장점은 컨테이너 벨트가 가지는 장점을 그대로 가지게 된다. 컨테이너 벨트에 올라올 물건에 라벨을 붙이면 동시에 다양한 물건을 다룰 수 있는 것과 같이, 메시지 큐에 쓸 데이터에 번호를 붙임으로써 여러 개의 프로세스가 동시에 데이터를 쉽게 다룰 수 있다.

④ Shared Memory(공유 메모리)

데이터를 공유하는 방법에는 크게 두 가지가 있다. 하나는 통신을 이용해서 데이터를 주고받는 것이고 다른 하나는 데이터를 아예 공유, 즉 함께 사용하는 것이다. PIPE, Named PIPE, Message Queue가 통신을 이용한 설비라면, Shared Memory는 공유메모리가 데이터 자체를 공유하도록 지원하는 설비이다.

프로세스는 자신만의 메모리 영역을 가지고 있다. 이 메모리 영역은 다른 프로세스가 접근해서 함부로 데이터를 읽거나 쓰지 못하도록 커널에 의해서 보호가 되는데, 만약 다른 프로세스의 메모리 영역을 침범하려고 하면 커널은 침범 프로세스에 SIGSEGV 시그널을 보내 보호한다.

다수의 프로세스가 동시에 작동하는 Linux 운영체제의 특성상 프로세스의 메모리 영역은 반드시 보호되어져야 한다. 하지만 메모리 영역에 있는 데이터를 다른 프로세스들도 사용할 수 있도록 해야 하는 경우도 발생할 수 있다. PIPE와 Message Queue등을 이용해서 데이터 통신을 이용하여 데이터를 전달하는 방법도 있지만, Thread에서처럼 메모리 영역을 공유한다면 더 편하게 데이터를 함께 사용할 수 있다.

따라서 Shared Memory는 프로세스 간에 메모리 영역을 공유하여 사용할 수 있도록 한다. 프로세스가 공유 메모리 할당을 커널에 요청하게 되면 커널은 해당 프로세스에 메모리 공간을 할당해주게 되고, 이후 어떤 프로세스이던 간에 해당 메모리영역에 접근할 수 있다. 공유메모리는 중개자가 없이 곧바로 메모리에 접근할 수 있기 때문에 다른 모든 IPC들 중에서 가장 빠르게 작동할 수 있다는 장점도 가지고 있다.

⑤ Memory Map

Memory Map도 Shared Memory와 마찬가지로 메모리를 공유한다는 측면에 있어서는 비슷한 측면이 있다. 차이점으로는 Memory Map의 경우 열린 파일을 메모리에 Mapping시켜 공유한다는 점이다. 파일은 시스템의 모두 공유할 수 있는 자원이므로 서로 다른 프로세스들끼리 데이터를 공유하는데 문제가 없을 것임을 예상할 수 있다.

⑥ Socket

Socket은 프로세스와 시스템의 basic한 부분으로, 프로세스 들 사이의 통신을 가능하게 한다. 소켓을 사용하기 위해서는 소켓을 생성해주고, 이름을 지정해주어야 한다. 또한 domain과 type, Protocol을 지정해 주어야 한다. 서버 부분에서는 bind, listen, accept를 해주어 소켓 연결을 위한 준비를 하고, 클라이언트 부분에서는 connect를 통해 서버에 요청하며, 연결이 수립 된 이후에는 Socket을 send함으로써 데이터를 주고받게 된다. 연결이 끝난 후에는 반드시 Socket을 close()해야 한다.

⑦ Semaphore

Semaphore는 Named PIPE, PIPE, Message Queue와 같은 다른 IPC설비들이 대부분 프로세스 간 메시지 전송을 목적으로 하는데 반해, Semaphore는 프로세스 간 데이터를 동기화 하고 보호하는데 그 목적을 두게 된다. PIPE와 Message Queue와 같이 프로세스 간 메시지 전송을 하거나, Shared Memory를 통해서 특정 데이터를 공유하게 될 경우 공유된 자원에 여러 개의 프로세스가 동시에 접근하면 안 되며, 단지 한 번에 하나의 프로세스만 접근 가능하도록 만들어주는 것이 Semaphore이다.

1. Project Introduction

프로세스는 실행하며 CPU burst와 I/O burst의 사이클을 가지게 된다. 다른 표현으로는 CPU execution과 I/O waiting의 사이클을 가진다고도 한다. (CPU burst : CPU 할당 받아서 실제 처리되는 부분, I/O burst : I/O 작업 처리하는 시간)

왼쪽의 사진처럼 모든 프로세스는 CPU burst로 시작하고, 그 뒤에는 I/O burst, 그 뒤에 다시 CPU burst의 순환을 갖고, 가장 마지막에 다시 CPU burst로 끝이 나게 된다.

만약 A 프로세스의 I/O 작업을 기다리는 상황에(wait for I/O) 다른 프로세스를 실행시키지 못한다면 분명 굉장한 시간 낭비가 될 것이다. 이처럼 어떤 프로세스의 I/O 작업을 기다리는 상황에서 다른 프로세스에게 올바른 기준에 의해 CPU를 할당하는 것이 CPU 스케줄링이다.

2. Project Goals

이번 프로젝트는 Ready Queue에 있는 프로세스들 중 어떤 프로세스를 어떤 기준에 의해 CPU를 할당해야 하는지를 결정하는 것이다. 스케줄링이 필요한 이유는 CPU 이용율(CPU Utilization)을 최대화하기 위해서 이다. 만약 하나의 프로세스가 CPU를 점유하여 실행하다가

특정 I/O처리를 기다려야 한다면, 나머지 프로세스는 Ready Queue에 머무르게 되고 I/O처리를 하는 시간(I/O Burst)동안 CPU는 쉬게 될 것이다. 이는 CPU 이용률을 떨어뜨리게 된다. 따라서 적절한 스케줄링 방법을 사용하여 CPU Burst Time을 최대로 하는 것이 스케줄링의 목적이며 이번 프로젝트의 목적이다. 또한, 각종 스케줄링 정책을 활용하여 CPU burst와 I/O burst에 따른 성능 비교를 통해 프로세스 상태에 따른 효율적인 스케줄링 정책을 찾는 것 또한 목표로 한다.

3. Concepts used in CPU simulation

1) 스케줄링이란?

스케줄링이란 현재 실행 중인 프로세스로부터 다른 프로세스로 CPU를 넘겨주어야 할 때, 기다리고 있는 여러 프로세스 중에 OS가 누구를 선택해야 할지에 대한 방식이나 기준을 설정하는 것이다. 따라서 한정된 자원으로 최대한의 성능을 이끌어내기 위해서는 CPU를 적절하고 효율적으로 사용해야 한다. 따라서 OS는 실행 대기 중인 프로세스들에게 자원 배정을 적절히 하여 시스템의 성능을 끌어올리는 역할을 한다.

스케줄링은 다음과 같은 때에 일어난다.

⦁Running → Waiting 상태 : ( ex. I/O 요청, 자식프로세스 종료 - wait() 요청을 통해 종료)

⦁Running → Terminate 상태 : ( ex. 부모프로세스의 종료 )

⦁Running → Ready 상태 : ( ex. 인터럽트 발생 )

⦁Waiting → Ready 상태 : ( ex. I/O 완료 )

1-1) 스케줄링 단계

▷장기 스케줄링

어느 작업을 커널에 등록시켜 프로세스로 만들어 줄 것 인가를 결정하는 단계로서 시분할 스케줄링의 경우 사용자의 접속 시도를 허용할지 말지 결정하는 것을 예로 들 수 있다. 장기 스케줄러의 경우 수행 횟수가 적으며, 대부분 FIFO(First in First out)형태로 사용하게 된다.

▷중기 스케줄링

보류 상태의 프로세스들 중에서 어느 프로세스에게 메모리를 할당해 줄 것인가를 결정한다. 어떤 프로세스를 다시 Swap in을 할 것인가를 결정하는 것으로 장기와 단기 사이의 중간단계에 속한다.

▷단기 스케줄링

준비상태에 있는 프로세스들 중에서 어느 프로세스에게 CPU를 할당할지를 결정하는 단계로서, 프로세스 스케줄러 또는 디스패처에 의해 수행된다.

인터럽트가 발생 혹은 실행 중인 프로세스에 의해 System Call이 발생하는 경우 수행되는 단계이다.

1-2) 스케줄링 정책

멀티 프로세스 운영체제에서 하나의 CPU가 여러 프로세스를 실행하기 위해선 스케줄링 정책이 중요하다.

● Non-Preemptive Scheduling(비 선점 스케줄링) ( ex) FIFO, SJF, HRN )

비 선점형 OS는 현재 실행 중인 프로세스보다 높은 우선순위를 가지는 프로세스가 실행된다고 해서 실행 대상을 바로 변경하지 않는다.

새로 실행된 높은 우선순위의 프로세스가 실행되기 위해서는 현재 실행 중인 프로세스가 명시적으로 CPU를 양보할 때까지, 혹은 I/O 작업 등으로 block 상태가 될 때까지 기다려야만 한다.

● Preemptive Scheduling(선점 스케줄링) ( ex) RR, SRT, MFQ )

선점형 OS는 실행 중인 프로세스보다 높은 우선순위의 프로세스가 실행되면, 스케줄러에 의해 실행 순서가 적극 조정되는 OS를 뜻한다.

또한, 비 선점형 OS에 비해 훨씬 더 스케줄링이 복잡하게 처리가 되어 있는데, 우선순위가 같은 프로세스들 간 실행 배분에도 관여하기 때문이다.

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

각각의 프로세스마다 우선순위를 부여해서 우선순위가 높은 프로세스를 먼저 실행시키는 알고리즘이다.

1-3) 스케줄링 기법

1. FIFO(First In First Out)

FIFO 스케줄링은 프로세스들이 대기 큐에 도착한 순서에 따라 CPU를 할당받는 방식이다. FIFO 방식은 하나의 프로세스가 CPU를 할당받게 되면 프로세스가 모두 완료될 때까지 CPU를 점유하게 된다. 따라서 다른 스케줄링 방식에 비해 작업 완료 시간을 예측하기가 쉽다. 하지만 선점이 불가능하기 때문에 수행시간이 긴 프로세스가 할당받은 상태라면 수행시간이 짧은 프로그램이 오랜 시간 대기할 경우가 생기고 중요한 작업이 대기 하는 상황이 발생할 수 있다.

2. SRT (Shortest Remaining Time)

SRT 방식은 대기 큐에서 기다리는 작업 중 수행시간이 가장 짧다고 판단되는 것을 가장 먼저 수행하는 스케줄링 방법이다. FIFO방식 보다 평균대기 시간을 감소시키지만 큰 작업일수록 FIFO에 비해 예측이 어렵다. 긴 작업보다 짧은 작업 일 수록 오버헤드 면에서 볼 때 유리하다. 하지만 이 방법은 수행할 작업이 얼마나 긴지를 정확히 판단해서 수행해야 하는데 수행시간을 정확히 얻는 것이 어렵다.

3. HRN(Highest Responce ratio Next)

대기 시간과 실행 시간을 적절하게 혼합하여 어느 작업에 CPU를 먼저 할당할지 결정하는 방법 (HRN 값 = (대기 시간 + 실행 시간) / 실행 시간)

4. Round-Robin (순환 처리)

라운드 로빈 스케줄링은 FIFO 방식으로 각 프로세스는 같은 크기의 타임 퀀텀을 할당받는다.

만약 프로세스가 할당받은 시간 동안 작업을 완료하지 못하면 다음 프로세스로 넘어가고 실행 중이던 프로세스는 준비 완료 리스트의 가장 뒤로 보내진다.

5. Multi-level-Queue (다단계 큐)

Multi Level Queue는 대기 큐가 여러 개 존재한다. 이때, 프로세스는 생성될 때 정해지는 우선순위에 따라 해당 우선순위에 해당하는 대기 큐에 등록된다. 각 큐는 별도의 스케줄링 알고리즘을 가지고 있으며 큐 사이에도 스케줄링이 존재한다. 즉, 각 큐는 절대적인 우선순위를 가진다. 우선순위가 높은 큐에 존재하는 프로세스부터 실행되며 상위 우선순위 큐가 비어야만 다음 우선순위의 대기 큐를 실행할 수 있다. 작업은 한 큐에서 다른 큐로 옮겨지지 않기 때문에 스케줄링 부담이 적지만 융통성이 떨어진다.

우선순위가 낮은 프로세스가 오랫동안 CPU 할당을 기다리는 기아현상이 발생할 수도 있다.

6. Multi-level Feedback Queue (다단계 피드백 큐)

Multi-level-Queue의 공평성 문제를 완화하기 위해 나온 알고리즘이다. 이 알고리즘에서는 우선순위가 변동되기 때문에 큐 사이의 이동이 가능하다. 즉, 여러 개의 ready queue를 사용하여 각 queue마다 priority(우선순위) 와 time quantum을 다르게 할당하고 프로세스가 들어오면 가장 상위 queue에 넣었다가, 해당 queue의 time quantum이 지나도 프로세스가 종료되지 않았다면 하위의 queue로 끌어내리는 스케줄링 방식이다. 일정 시간동안 수행되지 못하고 남아있는 프로세스(기아상태)는 다시 상위 큐로 끌어올려주는 에이징 기법을 사용하여 상위 큐로 끌어올리기도 한다.

1-4) 스케줄링의 목적

⦁ No starvation : 각각의 프로세스들이 오랜 시간동안 CPU를 할당받지 못하는 상황이 없도록 한다.

⦁ Fairness : 각각의 프로세스에 공평하게 CPU를 할당해준다.

⦁ Balance : Keeping all parts of the system busy

⦁ Batch System : 일에 대한 요청이 발생했을 때, 즉각적으로 처리하는 것이 아닌 일정기간 또는 일정량을 모아뒀다가 한 번에 처리하는 방식

⦁ Throughput : 시간당 최대의 작업량을 낸다.

⦁ Turnaround time : 프로세스의 생성부터 소멸까지의 시간을 최소화한다.

⦁ CPU utilization : CPU가 쉬는 시간이 없도록 한다.

⦁ Interactive System : 일에 대한 요청에 대해 즉각적으로 처리하여 응답을 받을 수 있는 시스템

⦁ Response time : 즉각적으로 처리해야하는 시스템이므로 요청에 대해 응답시간을 줄이는 게 중요하다.

⦁ Time Sharing System : 각 프로세스에 CPU에 대한 일정시간을 할당하여 주어진 시간동안 프로그램을 수행할 수 있게 하는 시스템

⦁ Meeting deadlines : 데이터의 손실을 피하며, 끝내야하는 시간 안에 도달해야한다.

⦁ Predictability : 멀티미디어 시스템에서의 품질이 저하되는 부분을 방지해야한다.

1. Project Introduction

이번 프로젝트는 Producer-Consumer 패턴으로 상당히 널리 알려져 있는 패턴이기에, 대부분의 개발자들이 기본적으로 이해하고 있는 내용이다. 따라서 이번 프로젝트에서는 생산자와 소비자 스레드 사이에서 발생하는 문제들을 해결하고 멀티스레딩이 가능하도록 하는 것이 목적이다.

이번 프로젝트에서 사용되는 기본 코드에서의 생산자 스레드는 파일에서 라인을 읽어 공유 버퍼에 저장을 한다. 소비자 스레드는 공유 버퍼에서 문자열을 가져와 화면에 라인을 출력한다. 이후, 다수의 소비자 스레드를 이용해 파일에 있는 알파벳의 수를 계산하여 최종적으로 출력하는 것이 이번 프로젝트의 목표이다.

2. Project Goals

이번 프로젝트의 목표는 두 개 이상의 concurrent한 스레드들이 공유된 자원에 접근하려고 할 때 동기화 메커니즘이 없이 접근하려는 현상인 race condition을 해결하여 멀티 스레딩이 가능하도록 하는 것이다. 따라서 다수의 스레드들이 명령을 수행함에 있어 생기는 동기화 문제와 임계영역 문제 등을 파악하고, 해당 문제를 해결할 수 있는 소프트웨어적인 방법을 알아보고 고안하여, 구현하는 것을 이번 프로젝트의 목표로 한다.

3. Concepts used in CPU simulation

프로세스란, 운영체제에서 실행되는 프로그램의 최소 단위라고 보면 된다. 즉, 1개의 프로그램을 가리킬 때 보통 1개의 프로세스를 의미하는 경우가 많다.

그렇다면 이 프로세스들은 어디에서 실행될까? 바로 CPU의 코어에서 실행되며 한 번에 한 개의 연산을 수행한다.

근데 CPU가 한 번에 한 가지 연산 밖에 못한다면, 도대체 어떻게 웹서핑을 하면서 음악을 듣고, 게임을 하는 등 여러 가지 일들을 한 번에 할 수 있었을까? 방법은 바로 컨텍스트 스위칭(Context switching) 이라는 기술에 숨어 있다.

컴퓨터에서 프로그램이 실행될 때, 사용자가 보기에는 프로그램이 연속적으로 작동하는 것처럼 보이지만 실제로는 그렇지 않다. 아래 그림을 보면 CPU 코어 하나에서 프로그램들이 어떻게 실행되는지 알 수 있다.

보다시피, 프로그램 하나가 연속적으로 작동하는 것이 아니라, 프로그램 하나가 잠시 실행되었다가, 다른 프로그램으로 스위칭 되는 것을 볼 수 있다. 즉, CPU 는 한 프로그램을 통째로 실행시키는 것이 아니라, 이 프로그램 조금, 저 프로그램 조금씩 골라서 차례를 돌며 실행시킨다는 것을 알 수 있다.

정확히 말하면, CPU는 명령어들을 실행할 뿐, 어떤 프로그램을 실행시키고, 얼마 동안 실행 시키고, 또 다음에 무슨 프로그램으로 스위칭할지는 운영체제의 스케쥴러(scheduler)가 알아서 결정하게 된다.

※ Thread

CPU 코어에서 돌아가는 프로그램 단위를 쓰레드 (thread) 라고 부른다. 즉, CPU 의 코어 하나에서는 한 번에 한 개의 쓰레드의 명령을 실행시키게 된다.

한 개의 프로세스는 최소 한 개 쓰레드로 이루어져 있으며, 여러 개의 쓰레드로도 구성될 수 있다. 이렇게 여러 개의 쓰레드로 구성된 프로그램을 멀티 쓰레드 (multithread) 프로그램이라 한다.

쓰레드와 프로세스의 가장 큰 차이점은 프로세스들은 서로 메모리를 공유하지 않는다. 다시 말해, 프로세스1 과 프로세스2 가 있을 때, 프로세스1 은 프로세스2 의 메모리에 접근할 수 없고, 마찬가지로 프로세스2 도 프로세스1 의 메모리에 접근할 수 없다.

프로세스는 서로의 메모리를 접근할 수 없지만, 같은 프로세스 내에 Thread끼리는 메모리를 공유한다.

하지만 쓰레드의 경우는 다르다. 만일 한 프로세스 안에 쓰레드1 과 쓰레드2 가 있다면, 서로 같은 메모리를 공유하게 된다. 따라서 Thread1 과 Thread2는 같은 변수에 접근할 수 있다.

※ 멀티 프로세싱(Multi-processing)

멀티 프로세싱은 한마디로 말해 '두개 이상, 다수의 프로세서가 협력적으로 작업을 동시에 처리하는 것'이다.

프로세서는 대략적으로 CPU라고 생각하면 된다.

각각의 프로세서가 하나의 작업만을 처리하는 것이 아니라 다수의 작업을 처리하며, 하나의 작업은 하나의 프로세서에 의해 처리되는 것이 아니라 다수의 프로세서에 의해 처리된다.

멀티 포르세싱의 장점으로는 여러 개의 프로세스가 처리되어야 할 때 동일한 데이터를 사용한다면 이러한 데이터를 하나의 디스크에 두고 모든 프로세서가 이를 공유하도록 한다면 비용적으로 저렴하다.

또한, 만약 하나의 프로세서가 하나의 작업만을 처리한다면 특정 프로세서가 고장이 났을 때 해당 작업은 정지된다. 하지만 멀티 프로세싱을 할 경우 특정 프로세서가 고장나도 다른 프로세서들은 자신의 일을 수행할 수 있다.

※멀티 프로그래밍(Multi-programming)

멀티 프로그래밍이란, 특정 프로세스 A에 대해서 프로세서가 작업을 처리할 때 낭비되는 시간동안 다른 프로세스를 처리하도록 하는 것 입니다.

예를 들어 A라는 프로세스를 처리 중에 있을 때 입출력 이벤트가 발생했는데 프로세서가 입출력 이벤트에 대한 응답을 위해 무작정 대기하고 있다면 프로세서의 자원을 낭비하는 결과를 초래한다. 프로세서, CPU는 한 번에 하나의 프로세스만 처리하도록 되어있기 때문에 A 프로세스에 대한 입출력 이벤트에 대한 응답을 대기하는 동안 아무 일도 하지 않기 때문이다.

멀티 프로그래밍은 이렇게 낭비되는 시간동안 프로세서가 다른 프로세스를 수행할 수 있도록 하는 것이다.

※멀티 태스킹(Multi-tasking)

멀티 태스킹이란 다수의 Task를 운영체제의 스케줄링에 의해 번갈아 가면서 수행하는 것이다. 프로세서가 각각의 Task를 조금씩 자주 번갈아가면서 처리하기 때문에 사용자는 마치 동시에 여러 Task가 수행되는 것처럼 보게 된다. 위에서 말한 멀티프로그래밍과의 차이점으로는, 멀티프로그래밍은 프로세서의 자원이 낭비되는 것을 최소화하기 위한 것이며 멀티 태스킹은 일정하게 정해진 시간동안 번갈아가면서 각각의 Task를 처리하는 것이다.

※멀티 스레딩(Multi-threading)

일반적으로 하나의 프로세스는 하나의 스레드를 가지고 작업을 수행하게 된다.

하지만 멀티 스레드(multi thread)란 하나의 프로세스 내에서 둘 이상의 스레드가 동시에 작업을 수행하는 것을 의미한다.

또한, 멀티 프로세스(multi process)는 여러 개의 CPU를 사용하여 여러 프로세스를 동시에 수행하는 것을 의미한다.

멀티 스레드와 멀티 프로세스 모두 여러 흐름을 동시에 수행하다는 공통점을 가지고 있지만 멀티 프로세스는 각 프로세스가 독립적인 메모리를 가지고 별도로 실행되지만, 멀티 스레드는 각 스레드가 자신이 속한 프로세스의 메모리를 공유한다는 점이 다르다.

멀티 스레드는 각 스레드가 자신이 속한 프로세스의 메모리를 공유하므로, 시스템 자원의 낭비가 적으며 하나의 스레드가 작업을 할 때 다른 스레드가 별도의 작업을 할 수 있어 사용자와의 응답성도 좋아진다.

※상호배제(Mutual Exclusion)

상호 배제는 동시에 실행되는 프로세스들이 임계 영역(Critical Section)에 동시에 들어가지 않도록 하는 것이다. 임계 영역(Critical Section)은 공유 자원에 접근하는 프로세스의 영역으로 즉, 프로그램 코드 중에서 공유 자원에 접근하는 부분의 코드를 의미한다.

예를 들면, 어떤 프로그램이 파일의 이름을 변경하는 기능이 있을 때, 파일의 이름을 변경하는 코드가 있는 곳이 임계 영역이다. 파일은 여러 프로그램이 사용할 수 있는 공유 자원이다. 2개의 프로그램이 동시에 한 파일의 이름을 변경하려고 하면 예측할 수 없는 결과가 생길 수 있다. 2개의 프로그램이 동시에 파일의 이름을 변경하는 임계 영역에 들어가지 못하도록 하는 기법이 상호 배제이다.

⦁상호 배제(Mutual Exclusion)는 다음과 같은 방법들이 있다.

- Lock

- Semaphore

- Monitor

- Message Passing

- Tuple Space

⦁ 상호 배제는 하드웨어로 구현될 수도 있고 소프트웨어로 구현될 수도 있다. 하드웨어에 의한 방법은 주로 CPU 명령어에서 지원한다.

⦁ 상호 배제를 순수하게 소프트웨어만으로 구현하기 위해서는 조금 복잡한 알고리즘이 필요하다. 소프트웨어로 구현할 수 있는 상호 배제 알고리즘은 다음과 같다.

- Dekker 알고리즘

- Peterson 알고리즘

- Lamport's bakery 알고리즘

- Szymanski 알고리즘

- Taubenfeld's black-white bakery 알고리즘

⦁ 상호 배제가 제대로 동작하지 않을 때 다음과 같은 문제가 생길 수 있다.

- Deadlock : 2개의 프로세스가 동시에 공유 자원을 얻기 위해 2개의 프로세스가 모두대기하는 상태

- Starvation : 프로세스가 공유 자원을 절대 얻을 수 없는 상태

- Priority Inversion : 우선 순위가 높은 프로세스가 공유 자원을 얻는데 우선 순위가 낮아지는 것

※ 피터슨(Peterson) 알고리즘

peterson algorithm이란 상호 배제를 위한 병렬 프로그래밍 알고리즘으로서, 공유 메모리를 활용하여 여러 개의 프로세스가 하나의 자원을 함께 사용할 때 문제가 발생하지 않도록 해준다. 코드를 살펴보면 결국 마지막에 결정된 turn의 값이 두 개의 프로세스 중에 어떤 게 공유된 자원을 먼저 사용할지 결정시키는 알고리즘이다.

※데커(Dekker) 알고리즘

※ 결정성과 경쟁 조건

1) 병행 프로세스(Concurrent Process)

두 개 이상의 실행 중인 프로그램이라는 의미로 서로 관련 없이 독립적으로 수행하는 독립적 병행 프로세스와 상호 관련성으로 갖고 비동기적으로 수행 하는 비동기적 병행 프로세스로 나뉨

2) 결정성

두 프로세스 간에 선행관계가 없으면 독립적이고 병행 실행 가능

순서를 어떻게 조합하는 가에 의해 시스템의 활동 순열이 결정

결정성 : 상대적인 실행 순서에 관계없이 항상 주어진 입력에 대해서 같은 결과를 내는 것.

3)경쟁 조건(race condition)

두 개 이상의 프로세스들이 공유 기억장치를 공유하고, 어떤 프로세스가 언제 실행하느냐에 따라 결과가 달라질 수 있는 상황. 경쟁 조건이 있는 프로그램은 다른 순서로 실행하게 되면 그 결과를 예측할 수 없다.