데이즈

안녕하세요? 허니입니다. 제 글을 읽은 분이라면 컴퓨터 워드 작업을 할때면 저장 불러오기 등은 모두 해 보셨을텐데요. 이때 운영체제에서는 사용자가 모르게 많은 일들을 진행합니다. 많은 작업들은 파일시스템이라는 운영체제의 기능으로 HDD나 SSD와 같은 2차 저장소에 저장을 하여 파일을 영구 보관하게 되는거지요. 그렇다면 파일 시스템의 자세한 작업에 대해서 포스팅 해 보겠습니다. 학생이나 연구원분들에게 많은 도움이 될 것이라고 생각하며 언제든지 질문은 환영입니다.

오늘의 주제

 파일이란 무엇인가.

 파일의 구조

 파일은 왜 필요한가.

 파일이름의 작성

 파일시스템은 왜 필요한가.

 Meta data란 무엇인가.

 디렉토리(Directory)란 무엇인가.

 버퍼 캐쉬(butter cache)

 파일 포인터의 역할...

 Memory map I/O

파일이란 무엇인가?

앞서 공부한 프로세스 관리나 메모리 관리에 비해 파일이라는 개념은 우리에게 좀더 익숙하게 느껴질 것이다. 그 이유는 컴퓨터 작업을 하는데 사용자에게 항상 파일이란 개념은 빠지지 않고 접할 수 있기 때문일 것이다. 그렇게 항상 익숙하게 느끼고 있는 파일이란 과연 무엇일까. 파일은 프로그램 또는 데이터 등과 같은 정보들의 집합을 말한다. 이러한 정보를 저장할 수 있는 기억장소 공간은 디스크에 할당되어 있으며 디스크에 존재하는 여러 파일들은 각자 고유한 이름을 가짐으로서 구별된다.

파일의 구조를 한번 들여다보자

파일은 ‘바이트의 연속적인 연결’이라고 정의된다. 파일의 특성을 살펴보면 파일은 바이트의 연속으로 구조가 없다. 그렇기 때문에 별다른 지정없이 파일의 시작에서 offset으로 주소지정이 가능하다. 이것은 데이터베이스의 레코드와의 구분되어지는 특성이기도한데 레코드는 필드라는 단위가 모여 이뤄지며 데이터베이스에서의 접근 단위가 되는 것이다.

잠깐, 상식! 필드: 데이터 항목을 의미한다. 즉 여러 개의 문자를 모아서 각 항목들의 속성을 표현하는데 사용된다. 예를 들면 이름 필드,나이필드,성별필드 등이 해당된다. 레코드: 특정한 대상과 관련된 필드들의 집합을 말한다.한 주민의 이름에 관한 필드, 나이에 관한 필드,생년월일에 관한 필드가 모여 주민들의 주민등록에 관한 레코드가 형성되는 것이다.

파일은 왜 필요한가?

보고서를 하나 작성했는데 파일이라는 개념이 없다면 어떨까. 그것의 결과는 사용자에게 매우 큰 불편을 가져다주게 된다. 보고서 작성 후 컴퓨터의 전원을 컸다면 처음부터 다시 입력작업을 하는 상황이 벌어질 것이다. 파일에 관하여 사용자가 알아야 하는 것은 매우 간단하다. 바로 파일 이름 하나만 제대로 알고 있으면 어느 장소에 저장되었는지를 모른다 하여도 작업을 위해 불러올 수가 있다. 그러나 실제로 파일 하나가 생성, 수정, 저장을 거쳐 다시 불러오기까지의 작업들을 위해선 우리가 알고 있는 것 보다 휠씬 복잡한 정보들이 필요하고 복잡한 과정이 얽혀있는 것이다. 그렇기에 OS를 공부하는 사람이라면 파일 시스템을 빼 놓을 수 없는 것이다.

파일이름의 작성

파일이름이란 특정한 파일을 지칭하기 위하여 사용되는 이름을 말한다. 일반적으로 영문자와 숫자. 그리고 _ 라는 문자로 구성된다. MS-DOS에서는 8자 이내의 숫자, 문자로 파일 이름이 작성되고 WINDOW 환경내에서는 무한대로 파일이름을 작성할 수 있다.

파일시스템은 왜 필요한가?

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

그림 53 파일과 디스크

Meta data

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

디렉토리(Directory)

디스크에 저장되어 있는 파일들을 보다 효율적으로 관리하기 위하여 파일 시스템에서 사용되는 하나의 방법이 바로 디렉토리(Directory)이다. 하나의 파일시스템에서 서로 연관된 파일들을 한곳에 체계적으로 저장 될 수 있도록 하는 방법인 것이다. 여러 개의 함을 갖고 있는 서류함처럼 관련된 파일들이 저장되는 장소를 제공한다.
 

그림 54 컴퓨터의 디렉토리 화면

 
디렉토리에 대하여 실행되는 조작들은 다음과 같다.
1.탐색 : 파일의 이름들은 상호관에 연관성을 갖고 있기 때문에 특정파일을 찾기 위하여 디렉토리를 탐색하게 된다.
2.파일의 생성 : 디렉토리에 새로운 파일을 만든다.
3.파일의 삭제 : 필요하지 않는 파일들을 디렉토리에서 지운다.
4.디렉토리 열람 : 디렉토리의 내용이 되는 파일들을 보여준다.
5.예비파일복사(backup):실수로 파일들이 지워지는 상황을 고려해 여분으로 파일을 복사해둔다.
 
바로 디렉토리는 메타데이터를 가지고 있기에 파일들에 대한 정보를 볼수 있는 것이다. 이러한 디렉토리는 디스크안에서 파일과는 따로 관리된다.

버퍼 캐쉬(buffer cache)

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

그림 55 버퍼 캐쉬
 
 

파일 포인터의 역할

파일을 read/wirte 할게 될 때 파일 포인터는 현재 사용되고 있는 데이터의 위치를 알려주게 된다. 바로 현재 사용되는 offset을 파일 포인터가 나타내는 것이다.

그림 56 파일 포인터

 
한 파일에 관한 사항은 A,B프로세스 모두가 공유할 수 있는 것이다. 그러나 offset만은 해당 프로세스가 그 파일을 현재 엑세스하고 있는 위치를 나타내고 있기 때문에 프로세스마다 다른 값을 가지게 된다. 파일을 바이트의 연속이라고 이미 설명하었다. 그렇기에 offset은 파일 처음부터 몇번째 바이트를 나타내는 정수가 된다. 

Memory map I/O

디스크에 저장되어있는 파일이 버퍼캐쉬를 통해 버퍼로 read 하는 대신 주소공간에 직접 load한다. 이러한 방법을  Memory map I/O라고 한다. 즉 파일이 주소공간의 일부가 되어 파일 I/O를 하지 않고 메모리 접근을 하듯이 읽거나 쓸 수 있게 된다. 이러한  Memory map I/O를 사용하게 되면 read/write 성능을 높일 수 있다.

그림 57 Memory Map I/O 와 버퍼 환경 비교

요점정리

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

파일의 구조는?
파일은 ‘바이트의 연속적인 연결’이라고 정의된다.

파일 시스템은 왜 필요한가?
파일은 연속된 바이트로 이뤄져 있다. 그러나 디스크는 바이트 단위로 읽어들일 수 없는 구조로 되어 있기 때문에 파일 시스템이 파일과 디스크 블록간에 밀접한 연결작업을 해주어야 한다.

Meta data란?
파일 사용자 ID, 파일 형태, 크기, 저장장소, 정보의 장소(offset), 버퍼, 시간 정보(생성시간, 최근 읽기,쓰기된 시간)등의 정보들이 저장된 데이터를 의미한다.

디렉토리(Directory)란?디스크에 저장되어 있는 파일들을 보다 효율적으로 관리하기 위하여 파일 시스템에서 사용되는 하나의 방법이 바로 디렉토리(Directory)이다. 디렉토리에 대하여 실행되는 조작들은 탐색, 파일의 생성, 파일의 삭제, 디렉토리 열람, 예비파일복사등이다.

버퍼 캐쉬(butter cache)란?
버퍼 캐쉬는 파일 사용자와 디스크의 사이에 자리잡고 완충역할을 하게 되는 장치이다. 처음 한번 읽은 파일은 버퍼캐쉬에 내용을 카피해 둠으로서 이후 동일한 파일을 사용할 때 읽어오는 속도를 높일 수 있는 것이다.

파일 포인터의 역할은?
파일을 read/wirte 할게 될때 파일 포인터는 현재 사용되고 있는 데이터의 위치를 알려주게 된다. 바로 현재 사용되는 offset을 파일 포인터가 나타내는 것이다.

Memory map I/O란?
디스크에 저장되어있는 파일이 버퍼캐쉬를 통해 버퍼로 read 하는 대신 주소공간에 직접 load하는 방법을  Memory map I/O라고 한다.

퀴즈

 퀴즈1) 파일이란 프로그램 또는 데이터등과 같은 정보들의 집합을 말한다.  이러한 파일이 디스크에 할당될 때 구별되는 방법은 무엇인가.

 퀴즈2) 파일의 구조와 레코드의 구조를 구분해 설명해보시오..

 퀴즈3) 파일 시스템이 필요한 이유를 파일과 디스크를 연결시켜 설명해 보시오.

 퀴즈4) 버퍼 캐쉬(butter cache)를 사용하게 되면 파일을 읽어오는 속도를 높일 수 있다. 그 이유를 설명해 보시오.

 퀴즈5) Memory map I/O를 사용하게 되면 read/write 성능을 높일 수 있다. 그 이유는 무엇인가.

 정답1) 디스크에 할당되는 여러 파일들은 각자 고유한 이름을 가짐으로서 구별된다.

 정답2) 파일의 구조는 바이트의 연속으로 별다른 구조가 없으나 레코드는 필드라는 단위가 모여 이뤄진다.

 정답3) 연속적인 바이트로 구성된 파일이 512바이트로 나뉘어져 디스크 곳곳에 블록 단위로 저장되게 된다. 그런데 디스크는 바이트 단위로 읽어들일 수 없는 구조로 되어있기 때문에 파일과 디스크를 연결하는 파일 시스템이 필요한 것이다.

 정답4) 처음 한번 읽은 파일은 버퍼캐쉬에 내용을 카피해 둠으로서 이후 동일한 파일을 사용할 때 읽어오는 속도를 높일 수 있는 것이다.

 정답5) 디스크에 저장되어있는 파일이 버퍼 캐쉬를 통해 버퍼로 read 하는 대신 주소공간에 직접 load하기 때문에 파일이 주소공간의 일부가 되어 파일 I/O를 하지 않고 읽거나 쓸 수 있게 된다. 그렇기에 Memory map I/O를 사용하게 되면 read/write 성능을 높일 수 있다.

안녕하세요? 허니입니다. 오늘은 운영체제에서 페이지 대체 알고리즘이 무엇이 있는지 그리고 그것과 관련하여 알아야 할 개념들에 대해 포스팅 하겠습니다. 학생이나 연구원분들에게 많은 도움이 될 것이라고 생각하며 언제든지 질문은 환영입니다.

오늘의 주제

 Page replacement (페이지 대체) 알고리즘

 Page window

 Thrashing

 Inverted Page Table

 Segmentation

어떤 기준으로 page out의 순서를 정하게 될까?

 Page replacement (페이지 대체)
과거 메모리 용량이 적었을 때에는 페이지대체를 위해 많은 수고가 필요했지만 과거에 비해 실제메모리용량이 상당히 커진 지금에는 간단한 알고리즘으로 해결이 가능하다.
 
1) FIFO
FIFO는 먼저 쓰였던 페이지프레임을 먼저 page out 시키는 방법이다. 이 방법의 가장 큰 장점은 구현하기가 간단하다는 것이었으나 Locality(지역성)의 개념이 등장한 이후 환영받지 못했다. 현재 쓰이고 있는 페이지프레임은 당분간 계속해 쓰인다는 Locality(지역성)의 개념과는 FIFO가 반대되는 개념이었기 때문이다. 그러나 최근 멀티미디어는 또 다시 Locality(지역성)의 개념을 제외시키고 있다. 동영상지원이 가장 큰 관건인 멀티미디어는 영상이 지원되는 동안 한번 접근한 페이지프레임은 다시 접근하지 않기 때문이다. 계속해서 새로운 페이지 프레임을 접근하여 동영상을 완성해나가기 때문이다.

그림 50 FIFO

 
아이러니하게도 시스템이 발전해나가는 것은 항상 새로운 것을 받아들이는 것이 아니다. 과거에 쓸모없다고 버림받았던 개념들이 또다시 받아들여져 발전해 나가기도 한다. 그렇기에 우리는 현재 쓰이지 조차 않은 개념들을 배우는 게 아닐까. 여러분에 손에 의해 새롭게 환영받을 모습으로 태어날 그 날을 고대하며....
 
2) Optimal
이 방법은 앞으로 안 쓰일 페이지프레임을 page out 시키는 것이다. 그러나 이 방법은 이론상으로 존재할 뿐 실제로 적용되기는 불가능하다. 어떤 페이지프레임이 앞으로 쓰이지 않을지는 아무도 모르기 때문이다.
 
3) LRU (Least Recently Used)
LRU의 방법은 가장 오랫동안 사용되지 않았던 페이지 프레임을 page out 시키는 방법으로 Locality(지역성)를 전제로 현재 안 쓰이는 페이지프레임은 계속 안 쓰일 것이라는 생각을 바탕에 둔 것이다. 그렇다면 가장 최근에 안 쓰인 페이지프레임을 어떻게 확인할 것인가. LRU가 가능하기 위해선 이러한 문제가 해결되어야 한다. 가장 쉽게 생각할 수 있는 방법은 페이지프레임마다 시간을 기록하는 것이다.그러나 페이지프레임마다 최근 참조 시각을 기록하고 점검해 재정리하는 등의 작업을 하는데는 상당히 많은 시간이 필요하다. 초당 백 만 번 이상의 페이지프레임참조가 발생하는데 페이지프레임에 타임스태프를 찍어주는데 몇 천 분에 1초(ms)가 걸린다면 한마디로 배보다 배꼽이 더 큰 격이다. 이렇듯 페이지 프레임마다 시각을 찍는데 너무 많은 시간이 소요되는 것을 염려하던 시스템 설계자들은 리스트를 만드는 방법을 개발해 내었다. 바로 페이지 프레임마다 시각을 찍는 대신 리스트를 만들어 sorting을 함으로 최근 쓰인 페이지 프레임과 쓰이지 않은 페이지 프레임을 구분해 내는 것이다. 이러한 방법의 단점은 overhead가 발생한다는 것인데 최근 쓰였던 페이지 프레임을 빼내어 뒤로 올리는데 그리고 하나의 페이지 프레임이 빠진 앞뒤의 페이지 프레임을 붙이는 데에 대한 포인터 변화를 저장하기 위해 overhead가 쓰이는 것이다. 바로 포인터 갱신을 위한 overhead가 매우 심각하다는 것이 이 방법의 가장 큰 단점이다.

그림 51 LRU
 

4) Random
Locality(지역성)이 존재하지 않은 채, 전혀 예측할 수 없이 불규칙적으로 수행되는 프로그램의 경우 페이지프레임을 아무런 규칙없이 page out 시키는 것을 말한다.

하드웨어를 사용한 page out

앞서 page out 시킬 페이지 프레임을 검색하는 데는 많은 어려움이 존재하는 것을 배웠다. 바로 이러한 어려움의 해결을 하드웨어의 도움을 얻음으로써 더 이상 시간과 메모리를 낭비하지 않을 방법이 고안되었다. 하드웨어를 사용해 page out 시킬 때는 앞서 배운 PTE에 참조비트(reference bit)와 수정비트(modify bit)를 셋팅해 bit 값의 변화를 관찰해 page out이 실행되게 된다. 참조비트가 0이라는 것은 해당 페이지 프레임이 참조되지 않았다는 것을, 또한 참조비트가 1이라는 것은 해당 페이지프레임이 참조되었다는 것을 의미한다. 바로 PTE에 이러한 참조비트를 두고 MMU가 페이지프레임을 참조할 때마다 0인 참조비트를 1로 셋팅 시키는 것이다. 참조비트를 통해 해당 페이지프레임이 최근 사용되었는지 사용되지 않았는지에 관한 정보가 제공되므로 page out daemon은 PTE를 검사해 참조비트가 0인 페이지프레임을 page out 시키게 되는 것이다. page out daemon을 통해 계속해 페이지들을 돌며 레퍼런스가 0인 페이지를 스왑으로 내보내게 되는 것이다. 그렇다면 수정비트(dirty bit)가 의미하는 것은 무엇일까. 만약 수정비트가 0일 경우는 해당 페이지프레임의 내용이 수정된 적이 없음을 의미하고 또한 수정비트가 1일 경우 이것은 해당 페이지 프레임의 내용이 수정된 적이 있음을 의미한다. 참조비트가 0인 두 개의 페이지프레임이 존재할 때는 수정비트를 확인하여 수정비트가 0인 페이지프레임을 먼저 page out 하게 되는 것이다. 그 이유는 수정된 페이지프레임을 대체 시키려면 수정된 내용을 다시 저장해야하는 번거로움이 있기 때문이다. 정리해보면 참조비트 0, 수정비트 0인 페이지 프레임이 page out 1순위가 되고 그 다음은 참조비트 0, 수정비트 1인 페이지프레임, 그리고 참조비트 1, 수정비트 0인 페이지프레임의 순서로 page out이 되는 것이다. 참조비트 1, 수정비트 1인 페이지프레임은 최후의 순간까지 남게 되는 것이다.

Page window

그렇다면 과연 page out daemon은 실제 메모리 안에 페이지프레임들을 전부 다 검사하는 걸까. 그렇지는 않다. 바로 Page window의 범위 내에 존재하는 페이지 프레임을 검사하게 되는 것이다. 현재 사용중인 PTE가 차곡차곡 모이게 되면 page out daemon은 Page window 영역 내에 PTE을 스캔하게 되는 것이다.

Thrashing

만약 페이지 공간이 부족해 페이지프레임상에 A프로그램을 page out 시켰는데 바로 그 A프로그램을 다시 접근해야 하는 상황이 발생됐다고 생각해보자. 그래서 A프로그램을 page in 시키기 위해 또 다른 B프로그램을 page out 시켰는데 안타깝게도 B프로그램을 다시 접근해야 한다면 어떨까. 말로 표현하기도 복잡한 이런 상황이 발생하면 프로그램을 처리해야 하는 CPU는 자신의 본분을 다하지 못하고 page out, page in만을 시키다 말게 된다. 다시 말해 컴퓨터 시스템 성능에 심각한 저하를 가져오게 되는 것이다. 이렇듯 페이지 교환이 너무 자주 일어나는 상황을 Thrashing이라고 한다.

그림 52 Thrashing
 

Thrashing이 발생하는 원인은 메모리 부족과 swap space의 부족을 들 수 있다. 이렇듯 페이지교체전략이 효율적이지 못할 때는 Working set을 수정하여 page in이 발생하는 페이지들을 메모리에 유지될 수 있도록 해야 한다. 이러한 Thrashing을 방지하기 위해선 프로그램을 실행을 위한 메모리용량을 확보할 때 swap space도 함께 잡아주는 것이다. 보통 메모리 용량의 2-3배를 잡아 놓으면 swap space의 부족으로 시스템이 돌아가지 않는 어려움이 방지될 수 있다. 일반적인 경우 CPU의 이용률은 50%를 넘기가 어렵다. 그런데 컴퓨터 시스템상의 어느 부문에선가 병목 현상이 발생했다면 Thrashing을 점검해볼 필요가 있다. 메모리용량에 비해 사용자가 많을 때 메모리를 늘리거나 디스크를 늘리거나 스왑을 높이거나 사용자의 수를 줄이는 등의 판단도 이제부턴 여러분의 몫인 것이다.

Segmentation

우리는 앞서 메모리를 페이징 방식으로 나누는 것에 대하여 상세히 공부해 보았다. 기계적으로 페이지를 나누었던 것에 비해 세그먼테이션은 이미 프로그램이 논리적으로 나뉘어져 있는 3개의 Stack, Data segment, Text segment의 영역을 기본으로 메모리를 할당하는 것이다. 그렇게 되면 가상주소는 세그먼테이션과 내부주소(offset)을 통해 실제주소와 매핑되게 된다. 그러나 이런 방법이 크게 환영받지 못한 이유는 페이징방식에 비해 단편화가 크고 세그먼트가 지원되는 시스템에서만 사용이 가능하다는 점이었다. 또한 세그먼테이션과 페이징 방식의 혼합은 각각의 세그먼트를 4Kbyte의 페이지로 나누어 사용하게 된다. 보통 하나의 세그먼트가 64Kbyte의 크기를 갖게 되므로 16개의 페이지가
생기게 되는 것이다. 그러나 이 방법 또한 페이징방식에 비해 별다른 효과가 없는 것으로 알려지고 있다.

요점정리

 Page replacement의 방법
1) FIFO: FIFO는 먼저 쓰였던 페이지프레임을 먼저 page out 시키는 방법이다.
2) Optimal: 이 방법은 앞으로 안 쓰일 페이지프레임을 page out 시키는 것을 말한다.
3) LRU (Least Recently Used): LRU의 방법은 가장 오랫동안 사용되지 않았던 페이지 프레임을 page out 시키는 방법으로 Locality(지역성)를 전제로 현재 안 쓰이는 페이지프레임은 계속 안 쓰일 것이라는 생각을 바탕에 둔 것이다.
4) Random: Locality(지역성)이 존재하지 않은 채 전혀 예측할 수 없이 불규칙적으로 수행되는 프로그램의 경우 아무런 규칙없이 page out 시키는 것을 말한다.

 하드웨어를 사용한 page out
PTE에 참조비트를 두고 MMU가 페이지 프레임을 참조할 때마다 참조비트를 셋팅 시킨 후 page out daemon이 PTE를 검사해서 참조비트가 0인 페이지프레임을 page out 시키게 되는 것이다.

 Thrashing이란
페이지 공간이 부족해 A프로그램을 page out 시켰는데 바로 그 A프로그램을 다시 접근해야 하는 상황이 발생했다. 그래서 A프로그램을 page in 시키기 위해 또 다른 B 프로그램을 page out 시켰는데 B프로그램에 다시 접근해야 하는 상황을 말한다.

안녕하세요? 허니입니다. 오늘은 운영체제에서 메모리 관련하여 알아야 개념들을 포스팅 하도록 하겠습니다. 학생이나 연구원분들에게 많은 도움이 될 것이라고 생각하며 언제든지 질문은 환영입니다.

오늘의 주제

TLB(Translation Lookaside Buffer)

Locality

Working set

Swapping과 Paging의 관리 방법

Overlay

TLB(Translation Lookaside Buffer)

앞서 우리는 테이블이 메모리를 너무 많이 차지하는 문제를 해결하기 위해 페이지 디렉토리와 레벨2 페이지테이블이라는 두 개의 테이블을 구성한다는 것을 공부해보았다. 그렇다면 우리가 자주 쓰는 프로그램을 항상 두 개의 테이블을 뒤져 찾아낸다는 것은 효율적이지 못한 것 아닐까. 그렇기에 하드웨어의 지원으로 자주 쓰는 프로그램의 매핑관계를 TLB에 저장하는 MMU가 고려된 것이다. 이러한 방법은 캐쉬라는 고속의 기억장치가 만들어져 가능하게 된 것으로 프로그램에서 자주 사용되는 데이터와 명령어들을 메모리에서 읽어와 캐쉬에 저장함으로써 이후 CPU의 요구가 있을 때 보다 빠른 시간 안에 처리가 가능한 것처럼 PTE를 TLB에 캐쉬하여 보다 빠른 메모리접근에 사용하는 것이다. 컴퓨터를 사용할 때 자주 쓰는 프로그램은 초기화면에 아이콘을 만들어 놓으면 사용하기 위해 프로그램을 찾는데 걸리는 시간을 휠씬 줄일 수 있는 것처럼 말이다.

그림 46 TLB (Table Lookaside Buffer)

최근 출시되는 프로그램들은 처음 메모리에 접근할 때 페이지 폴트가 일어나지만 그 다음 사용할 때에는 무조건 TLB안에 저장되게 설계되어 있다. TLB를 사용하게 되면 일반적인 Page Table Lookup보다 빠르지만 TLB에 담을 수 있는 항목은 보통 16개 정도에 불과하다.

IPT(Inverted Page Table)

앞서 우리는 페이지 테이블에 관해 상세히 공부해 보았다. 간략히 다시 한번 페이지 테이블의 개념을 설명하자면 가상페이지넘버를 가지고 그것과 매핑되는 물리적인 페이지프레임 넘버를 찾는 것이었다. 그러나 IPT는 페이지테이블의 이용방법을 완전히 뒤바꾸어 물리적인 페이지프레임넘버를 가지고 가상메모리내부의 페이지를 찾는 것이다. 과연 IPT의 장점은 무엇인가. 바로 현재 실제로 쓰이게 될 페이지프레임인덱스를 기준으로 가상메모리페이지를 찾게 되므로 기존의 페이지테이블에 비해 훨씬 적은 메모리를 차지한다는 것이다. 그렇다면 메모리도 적게 차지되는 IPT는 왜 널리 사용되지 못하는 것일까. 바로 공유의 문제와 페이지테이블 접근 시간이 더디다는 문제가 발생하기 때문이다. 페이지 테이블상에서 하나의 가상페이지는 여러 페이지프레임을 공유할 수가 있다.다시 말해 가상페이지 넘버 1번과 36번이 똑같은 12번 페이지프레임넘버를 지정했다면 12번 페이지 프레임 하나를 1번과 36번 의 가상페이지넘버를 사용하는 프로세스가 각각 공유하는 것이다. 그러나 IPT에는 12번의 페이지 프레임넘버가 1번과 36번의 가상페이지넘버를 지정 할 경우 (12, 1), (12,36)등과 같이 일일이 표기해줘야 하는 것이다.바로 페이지를 공유하기 위해서는 별도의 정보가 필요한 것이다. 페이지 테이블 접근 시간에서 문제가 발생하는 원인은 바로 프로세스가 수행하면서 만들어내는 주소가 가상주소이기 때문이다. 그런데 IPT는 물리적인 페이지프레임이 인덱스이기 때문에 맨 처음 주소부터 찾아 프로그램이 가상메모리의 임의의 주소가 어디에 자리잡고 있는지를 알아내게 되는 것이다. 그렇기에 페이지테이블을 통해 주소를 알아내는데 너무 긴 시간이 소요된다.

Locality(지역성)

프로세스가 실행되는 것을 계속 관찰하던 어느 시스템 설계자는 실행과정에서 공통된 특성을 한가지 발견하게 된다. 바로 프로세스가 메모리 레퍼런스(메모리를 참조하기 위해 접근하는 것을 메모리 레퍼런스라고 한다.)를 할 때는 메모리의 전 부분을 골고루 참조하는 것이 아니라 일부 페이지 프레임에 대해서 집중적으로 레퍼런스 한다는 것이다. 바로 지역적 특성을 갖는다는 것이었다. 예를 들어 For loop을 사용하게 되면 인접 주소들을 계속 참조하게 된다.

그림 47 지역성 (Locality)

잠깐 상식! For loop란 프로그래밍 언어에서 일정한 횟수 동안 같은 동작을 반복하여 수행하도록 하는 작업을 말한다.

Working set

가상메모리시스템에서 주어진 시간에 프로세스가 참조하는 페이지 프레임의 집합을 Working set이라고 말한다. TLB가 Working set에 속한 페이지 프레임을 다 가지고 있다면 메모리 참조 속도가 엄청나게 빨라지게 될 것이다. 또한 Working set을 통해 어떤 페이지프레임을 page out 시킬 것인가 하는 기준이 마련되게 된다. 다시 말해 메모리가 부족해 page out 시킬 것을 찾아야 한다면 바로 Working set안에 있는 프로그램을 제외시키면 되는 것이다. Working set에 속한 메모리를 고정시켜주면 page out으로 인하여 프로그램 운영에 미치는 영향을 최소화할 수 있다. 내가 사용하는 프로그램에 별다른 지장을 주지 않도록 내부적으로 page out이 진행된다면 이보다 더 좋을 순 없을 것이다.

그림 48 Working Set

그렇다면 앞서 설명한 swapping과 paging는 어떤 방법으로 관리될까. 그것들은 별도의 커널 스레드에 의해 관리된다. 이 커널 스레드는 보통의 상황에서는 활동을 하지 않지만 메모리와 free page의 부족을 나타내는 임계치에 다달으면 활동을 시작하게 된다. 이러한 커널 스레드를 page out daemon이라 한다. 이 daemon이 활동하는 동안 작업 중이던 프로세스들은 동작을 중단하고 있을까. 그것은 아니다. 작업은 작업대로 메모리 확보를 위한 page out은 out대로 함께 동작하는 것이다. 우리가 가끔 컴퓨터 작업을 할 때 본체의 디스크 불빛이 깜빡이며 삑삑 소리를 내는 것은 어떠한 문제가 발생해서가 아니라 바로 시스템 내부에서 메모리 확보를 위한 page out이 진행중인 것이다.

Overlay

가상메모리가 존재하지 않았을 당시에 8kbyte의 메모리에 32kbyte의 프로그램을 읽어드려야 하는 경우가 발생했다면 어떻게 될까. 프로그램 용량이 너무 커 실행시킬 수 없다면 모든 프로그램들은 메모리 크기로밖에 만들어질 수밖에 없을 것이다. 이러한 문제를 overlay를 통해 해결될 수 있는 것이다. 프로그램의 운영상 관련이 깊은 구조끼리 묶어 메모리가 감당할 수 있는 크기의 모듈로 나누어 수행하는 것이다. 90년대 초반까지만 하더라도 초등학교 시설에 비해 학생수가 많아 오전반 오후반으로 나누어 교실을 활용했던 것처럼 말이다. 그러나 프로그램을 제어하는 기능은 어느 모듈에나 속해 있어야 한다는 것을 잊어선 안되겠다. 바로 overlay는 가상 메모리의 전신인 격이다.

그림 49 Overlay
 

그렇다면 overlay와 가상메모리의 차이점은 무엇일까. overlay는 프로그램 사용자 스스로가 프로그램의 영역을 나누고 통제해야만 했다. 그러나 가상메모리는 사용자의 짐을 덜어주기 위해 영역을 나누고 통제하는 모든 것은 시스템 스스로가 도맡아 처리하게 되는 것이다.

요점정리

 TLB(Translation Lookaside Buffer)란?
하드웨어의 지원으로 자주 쓰는 프로그램의 PTE를 MMU의  TLB에 저장한다. 이러한 방법은 캐쉬라는 고속의 기억장치가 만들어져 가능하게 되었다.

 IPT(Inverted Page Table)란?
IPT는 페이지테이블의 이용방법을 완전히 뒤바꾸어 페이지프레임넘버를 갖고 가상메모리내부의 페이지를 찾는 것이다.

 Locality(지역성)이란?
프로세스가 메모리 레퍼런스(메모리를 참조하기 위해 접근하는 것을 메모리 레퍼런스라고 한다.)를 할 때는 메모리의 전 부분을 골고루 참조하는 것이 아니라 일부 페이지프레임에 대해서 집중적으로 레퍼런스 한다는 것이 바로 지역적 특성이다.

 Working set이란?
가상메모리시스템에서 주어진 시간에 프로세스가 참조하는 페이지프레임의 집합을  Working set이라고 말한다. 메모리가 부족해 page out 시킬 것을 찾아야 한다면 바로  Working set안에 있는 프로그램을 제외시키면 되는 것이다.

 Swapping과 Paging의 관리란?
swapping과 paging은  page out daemon이라는 별도의 커널 스레드에 의해 관리된다. 이 커널 스레드는 보통의 상황에서는 활동을 하지 않지만 메모리 부족을 나타내는 임계치에 다달으면 활동을 시작하게 된다.

 Overlay란?
프로그램 용량이 메모리 용량보다 클 경우 프로그램의 운영상 관련이 깊은 구조끼리 묶어 메모리가 감당할 수 있는 크기의 모듈로 나누어 수행하는 것이다.

안녕하세요? 허니입니다. 운영체제에서 많이 쓰이는 동기화 기법으로 세마포어를 많이 씁니다. 세마포어는 프로세스의 순차적인 처리를 위해 만든 기법으로 프로세스들끼리 경쟁을 막아 원할한 자원 공유를 가능하게 합니다. 운영체제에서는 매우 중요하기 때문에 세마포어에 대해 자세하게 포스팅 하려고 합니다. 학생이나 연구원분들에게 많은 도움이 될 것이라고 생각하며 언제든지 질문은 환영입니다.

오늘의 주제

 SEMAPHORE

 Monitor

세마포어(SEMAPHORE)

프로세스의 순차적인 처리로 데이터의 값을 보장하는 방법에 대해 자세히 모르신다면 제 블러그에서 프로세스 동기화를 주제로 한 포스트를 읽어보시고 세마포어에 대해 읽어보는 것이 좋다. 프로세스를 단순히 2개라고 가정한 채 critical section을 한 프로세스만을 접근시켜보았는데 프로세스가 10개, 20개, 30개라고 가정한다면 대단히 복잡한 문제로 발전할 수밖에 없다.  그렇기에 시스템 설계자들은 발상의 전환을 하기 시작했다. 바로 신호체계를 만든 것이다. 하나의 프로세스가 critical section내에서 수행되고 sleeping하는 것을 신호에 따라 조절될 수 있도록 말이다. 그러한 발상에서 semaphore가 고안되었다. 바로 wait(약어P)와 signal(약어V)의 함수를 적절히 호출함으로 여러 프로세스를 수행하게 되는 것이다.

Semaphore의 동작을 간단히 살펴보면, S라는 변수를 두고 critical section내에 들어가기 전에 wait(S)함수를 수행하여 critical section 내에 다른 프로세스가 없는 상태를 기다린다. 이는 (S > 0)의 조건을 기다리는 것인데, 이 조건은 다른 프로세스가 signal(S)을 호출하거나 초기 상태에만 가능하다. 즉, 프로세스가 critical section에서 나올 때 signal(S)를 호출함으로써 (S > 0)의 조건이 만족되고, wait(S) 함수로 기다리던 프로세스들이 그것을 감지하여 critical section으로 진입하게 되는 것이다. 단 여기서 하나의 프로세스만이 critical section으로 진입하여야 하므로 while 구문을 가장 먼저 통과한 프로세스가 S를 다시 감소시켜 (S > 0)의 조건을 파괴하는 것이다. 그렇다면 critical section이 5개일 경우 1개의 semaphore를 구성하는 것이 효과적일까. 아니면 5개의 semaphore를 구성하는 것이 효과적일까. 각각의 critical section마다 semaphore를 둘 경우 동시수행이 가능해지기 때문에 처리능력이 향상된다. 그러나 교착상태(deadlock)의 위험이 도사리고 있는 것이 문제점으로 지적될 수 있다. 다음과 같은 경우를 한번 생각해 보자. 철학자 5명이 국수를 먹는다. 그러나 얄궂게도 젓가락이 5쌍이 아닌 5개밖에 없다. 여기에서 젓가락이 바로 critical section이 되는 것이다.

그림 22 Dining Philosophers

철학자들이 국수를 먹기 위해선 자신의 좌측 우측에 있는 젓가락을 잡아야 하는데, 이럴 경우 발생할 경우란 2사람의 철학자가 먹을 수 있는 경우와 아무도 먹을 수 없는 경우가 될 것이다. 다섯 명의 철학자가 젓가락을 하나씩 쥐고 계속 기다린다면 어떨까. 시간이 흘러도 그 상황은 계속 유지되어 철학자들은 계속 굶고 있을 수밖에 없는 것이다. 바로 교착상태(deadlock)이 발생하는 것이다. 바로 P와 V를 어떻게 사용해야 철학자들이 굶지 않을까 하는 것이 semaphore의 최대 관심거리인 것이다. 이러한 교착상태(deadlock)가 발생한 경우는 얼마간의 시간이 지나면 하나의 젓가락을 포기한 채 Synchronization을 다시 시도해야 한다. 교착상태(deadlock)가 발생하지 않기 위해서는 순서를 정해 양쪽 젓가락을 잡을 수 있도록 설계되어야 한다. 젓가락을 쓰는데 순서를 정해주면 2명씩의 철학자가 돌아가면서 국수를 먹을 수 있도록 말이다. 모자라는 자원의 최대 활용이라고나 할까....

잠깐, 상식! 교착상태(deadlock)란? 프로세스들이 서로 작업을 진행하지 못하고 영원히 대기 상태로 빠지는 현상을 교착상태라고 한다. 이러한 교착상태가 발생하는 원인은 프로세스 사이에 할당된 자원의 충돌로 인하여 발생하게 된다. 예를 들어 A와 B라는 2개의 프로세스가 동작을 한다고 하자. 그리고 이들은 각각 a와 b라는 자원을 할당 받아 사용하고 있다고 가정하자. 이때 프로세스 A 에서는 작업을 계속 진행하기 위해서 b라는 자원을 요청하고 프로세스B에서는 a라는 자원을 요청하게 되면 각각의 프로세스가 요청한 자원이 이미 다른 프로세스에 할당되어 있기 때문에 할당이 풀릴 때까지 대기 상태에 들어가게 된다. 그런데 A와 B 프로세스 모두 상대방이 자원을 내놓기를 기다리면서 대기 상태로 들어가기 때문에 이들은 영원히 대기 상태에 머무는 교착상태에 빠지게 되는 것이다.

또 다른 semaphore의 쓰임새를 살펴보자. 앞서 예로 들었던 은행 잔고가 잘못 기록되는 문제점에 대한 해결 열쇠 또한 semaphore가 쥐고 있는 것이다. 은행 잔고를 처리하는 부분을 semaphore로 관리하면 되는 것이다. 지금까지 살펴보았듯 semaphore를 사용하게 되면 Synchronization을 보다 효율적으로 구현할 수 있다. 그러나 앞에서도 잠깐 언급했듯이 Synchronization을 구현하는 것은 사용자의 필요성에 의해 각자에게 맡겨진 것이다. 어떠한 1명이 고의적으로 또한 P와 V의 구조를 잘못 이해해서 실수를 범하게 된다면 그 결과는 아무도 예측하지 못하게 된다. 바로 미꾸라지 하나가 Synchronization를 엉망으로 만들 수 있는 것이다. 그렇기에 이러한 문제점의 해결방안으로 Monitor가 구성되었다. Monitor는 P, V와 같은 함수의 정의가 언어로 표현되어 사용자들이 보다 쉽게 Synchronization을 구현 할 수 있도록 한 것이다.

요점정리

 세마포어(Semaphore)란?

wait(약어P)와 signal(약어V)의 함수를 적절히 호출함으로 여러 프로세스를 수행하는 방법이다.

안녕하세요? 허니입니다. 운영체제에서 프로세스끼리 자원경쟁을 한다거나 서로 자원을 쓰지 못하는 기아현상을 해결하기 위해 동기화 기법을 활용합니다. 즉, 자원을 효과적으로 활용하기 위한 정책으로 프로세스 동기화에 자세히 포스팅 하려고 합니다. 학생이나 연구원분들에게 많은 도움이 될 것이라고 생각하며 언제든지 질문은 환영입니다.

오늘의 주제

 프로세스 동기화(Process Synchronization)

Process Synchronization

 동기화(Synchronization)

여러 프로세스의 접근이 가능한「공유된 데이터」에 여러 프로세스들이 동시에 접근했을 경우 과연 어떠한 문제가 발생하게 될까. 체계적인 접근방법을 만들어 놓지 않는다면 예측하지 못했던 결과가 나올 가능성이 있다. 이러한 가능성을 배제하기 위해 Synchronization의 개념이 도입되었다. 예를 들어 은행에 1000원의 잔고가 남아 있다고 하자. 통장의 주인이 500원을 찾는 순간 동시에 고향 어머니께서 500원을 송금해 오셨다면 어떤 결과가 발생할까. 우리가 바라는 결과값은 두말할 나위 없이 바로 1000원인데 말이다. 그러나 그 결과값이 500원이 나왔다면 또는 1500원이 나왔다면 이것은 엄청난 문제가 아닐 수 없다. 어떻게 이런 결과값이 나올 수 있었을까. 바로 공유 데이터, 은행 잔고 1000원에 A프로세스(500원 인출)와, B프로세스(500원 송금이 동시에 접근해 각각의 프로세스가 서로 다른 결과를 갖고 있기 때문이다.

그림 18 Synchronization의 필요성

위의 그림과 같이 A프로세스는 500원의 결과를 B프로세스는 1500원의 결과를 갖고 있을 경우 마감 처리되는 프로세스의 결과가 최종 은행잔고로 남게 되는 것이다. 어떠한 데이터에 대해 동시 작업이 일어났을 경우 처리순서에 상관없이 원하는 결과값을 얻기 위해 바로 Synchronization이 필요한 것이다. 즉, Synchronization의 목적은 data consistency을 보장해 주는 것이다. 하나의 작업을 처리하는데 100개의 시그널이 동시에 날아와 제 각각의 처리를 마쳐도 데이터는 항상 시종일관 자신이 갖고 있어야 할 결과값을 담고 있어야 하는 것이다. data consistency을 보장해 주기 위한 방법은 다음과 같다.

 상호배제(Mutual exclusion)

공유 데이터에 동시에 여러 개의 프로세스가 임의로 접근하게 되면 앞서 살펴본 예와 같이 데이터의 상태가 부정확하게 되는 문제가 발생된다. 그렇기에 공유데이터가 하나의 프로세스에 의해 독점적으로 사용되는 원칙을 상호배제라 한다. 여기서 잠깐 critical section이라는 코딩 용어를 알아두자. 바로 상호배제의 원리가 지켜져야 하는 영역이 critical section인 것이다. 자칫 잘못하면 위험한 결과가 초래될지도 모르기에 위험한 세션이라 이름을 붙인 것일까....

예를 들어 프로그래머가 다음과 같이 코딩을 하였다.

프로세스는 critical section안으로 들어가기 이전 entry section 단계에서 출입을 허가 받아야 한다. 이러한 허가절차를 받는 이유는 critical section안에 오직 하나의 프로세스만이 존재하도록 하기 위해서다. 프로세스를 이렇게 순차적으로 접근시킨다면 동시에 2개 이상의 프로세스가 접근해 서로 다른 결과치를 갖게 되는 문제가 해결되는 것이다. 다시 말해 A프로세스가 최종결과로 시스템 내부에서 처리되면 통장에는 500원의 잔고가 남을 것이고 B프로세스가 최종결과로 시스템 내부에서 처리되면 통장에는 1500원의 잔고가 남을 것이다. 이러한 문제의 발생을 막기 위해 A프로세스가 -500을 수행하는 동안 +500을 수행하는 B프로세스의 접근을 차단시키는 것이다. 그 역할을 바로 entry section이 맡고 있는 것이다. 이러한 상호배제(Mutual exclusion)는 DB의 프로그램에서는 자동적인 부가기능으로 지원되지만 OS의 경우는 사용자의 요구에 따라 지원된다. DB프로그램은 공유된 데이터의 보장이 프로그램의 가장 중요한 요소이다. 모든 프로그램이 수행될 때 공유된 데이터를 바탕으로 사용되기 때문이다. 그러나 OS는 사용자의 요구에 따라 상호배제(Mutual exclusion)가 지원된다. 바로 그 필요성이 DB만큼 막대하지 않기에 사용자의 필요성에 맡기는 것이다. 은행을 운영하는데 있어 CCTV등의 보안장치는 필수불가결하기 때문에 전국 어느 은행이나 설치를 했겠지만 보통의 가정집은 집주인이 필요하다고 판단되면 설치되는 것처럼 말이다.

상호배제(Mutual exclusion)의 장점은 무엇보다도 혼란이 없고 간단하다는 점이다. 그러나 매우 커다란 문제점이 내재되어 있었다. 바로 read와 write의 처리에 관한 문제였다. 「공유 데이터」에 read라는 명령어를 수행하기 위해 접근하는 프로세스는 100개나 1000개가 동시에 critical section안으로 들어와도 아무런 문제가 없다. 그 프로세스들을 공유된 데이터를 다만 참조할 뿐 더 이상의 어떤 변화도 가져오지 않기 때문이다. 그러나 write라는 명령어를 수행하기 위해 접근하는 프로세스의 경우는 1개만이 critical section 안에서 처리되어야 한다. write는 공유 데이터를 변화시키기 때문이다.

그러나 상호배제(Mutual exclusion)의 방법에서는 바로 이러한 read와 write의 처리를 구분 짓지 않는다. 무조건 「공유 데이터」에 접근하기 위해선 1000개가 동시 처리되어도 좋을 read마저도 오랜 기다림을 가져야 했다. 그렇기에 시스템 설계자는 새로운 무엇을 찾아내려 했다. 그 방법은 바로 kernel 자체가 하나의 커다란 critical section의 역할을 하는 것이다.

그림 19 kernel 자체의 critical section

여기서 가장 핵심이 되는 것은 lock이란 개념이다. 우리말로 표현한다면 잠금장치, 즉 자물쇠인 것이다. 바로 lock이라는 용어는 남이 접근하지 못하도록 잠궈 놓는다는 의미를 갖고 있는데 하나의 프로세스가 공유데이터에 접근하는 동안 다른 프로세스가 공유데이터에 접근하지 못하도록 입구를 잠궈 두는 것이다. lock에는 spin lock과 sleep lock이 있는데 spin lock이 0일 때는 critical section에 프로세스가 들어와도 된다는 것을 의미하고 spin lock이 1일 때는 critical section안에 다른 프로세스가 들어와 있다는 것을 의미한다. spin lock이 1일 경우 다음 수행을 기다리는 프로세스는 1이 언제 0이 될까를 관찰하며 Lock을 계속 돌게 된다. 바로 exit section에 의해 critical section내에서 프로세스가 처리되었다는 것이 인식되어 spin lock을 0으로 만드는 것이다.

그림 20 spin lock

sleep lock은 lock이 1일 경우 기다리던 프로세스는 sleep을 하게 되는 것이다. critical section내에 프로세스가 언제 처리가 끝날지 모르기 때문이다. critical section내에 프로세스의 작업이 끝나게 되면 sleep중인 프로세스를 깨워 처리하게 된다.

그림 21 Sleep Lock

그러나 이러한 방법 또한 완벽한 것은 아니었다. 또 다시 발생한 문제점은 동시에 2개 이상의 프로세스가 접근해 0을 1로 바꿀 가능성이 있다는 것이었다. 이러한 상황은 하나 이상의 프로세스가 동시에 lock=1에서 lock=0으로 바뀐 변수를 확인한 경우 발생하게 된다. 바로 프로세스가 처리될 때 0을 read해 1로 write하는 작업이 따로 수행되기 때문이다. 예를 들어 프로세스A와 프로세스B가 동시에 lock=0인 것을 read했다. 그러나 프로세스B가 먼저 lock=1을 write하고 프로세스B는 read만을 한 채 더 이상 작업이 진행되지 않았다. 이럴 경우 프로세스B는 context switching이 일어나게 되고 그 다음 작업이 수행될 때는 read작업을 다시 하지 않는다. 그렇기에 context switching이 발생하기 이전 lock=0이었던 것만을 기억한 채 작업을 수행하기 때문에 현재 lock=1이 라도 프로세스는 데이터에 접근하게 되는 것이다. 바로 또다시 동시에 2개 이상의 프로세스가 접근해 서로 다른 결과값을 갖게 되는 근본적인 문제가 다시 발생되는 것이다. 이러한 문제의 가장 간단한 해결책은 read/write를 하나의 명령어로 만들어 놓는 것이다. 이렇게 되면 동시에 2개의 프로세스가 lock을 0으로 볼 리는 없는 것이다.

요점정리

 Synchronization은 왜 필요한가

여러 프로세스의 접근이 가능한「공유된 데이터」에 동시에 여러 프로세스들이 접근했을 경우 어떠한 접근체계를 만들어놓지 않는다면 예측하지 못했던 결과가 나올 가능성이 있다. 이러한 가능성을 배제하기 위해 Synchronization의 개념이 도입되었다.

 바로 Synchronization의 목적은 data consistency을 보장해 주는 것이다.

하나의 작업을 처리하는데 100개의 시그널이 동시에 날아와 제 각각의 처리를 마쳐도 데이터는 항상 시종일관 자신이 갖고 있어야할 결과값을 담고 있어야 하는 것이다. 

 data consistency을 보장해 주기 위한 방법

1)상호배제(Mutual exclusion) - 공유데이터가 하나의 프로세스에 의해 독점적으로 사용되는 원칙을 상호배제라 한다.

2)kernel을 이용 - spin lock과 sleep lock을 이용하여 kernel 자체가 critical section 역할을 하게 된다.

안녕하세요? 허니입니다. 많은 스케줄링 알고리즘이 존재하기 때문에 어떤 스케줄링 기법을 활용하냐에 따라 성능차이가 많이 납니다. 때문에 비교 기준이 필요합니다. 때문에 저는 스케줄링 알고리즘을 어떻게 비교할 수 있을까에 대해 포스팅을 하려고 합니다. 학생이나 연구원분들에게 많은 도움이 될 것이라고 생각하며 언제든지 질문은 환영입니다.

오늘의 주제

 스케줄링 알고리즘의 비교기준

스케줄링 알고리즘의 비교기준

무엇인가를 평가하는 것은 분명 나름대로의 기준이 있기 마련이다. 무조건 공부 잘하는 학생을 최고의 학생으로 평가하는 선생님도 있을 것이고 공부보다는 친구들과의 관계, 여러 활동 상황 등의 사회성을 보다 높게 평가하는 선생님도 있기 마련이다. 가치있는 삶을 돈이란 기준으로 평가하는 이들도 있고 인간관계라고 평가하는 이들도 권력이라고 평가하는 이들도 있다. 그 어느 것이 보다 좋다는 것을 말하려는 것이 아니다. 바로 각자가 가진 평가기준에 따라 최고라는 기준은 달라지게 마련이다. 그렇기에 보다 다양한 사람들이 모인 사회가 되는 것일 테지만 말이다. 이와 같이 시스템 설계자 또한 스스로가 선택한 한가지의 기준에 따라 최적의 스케줄링 알고리즘을 설계하는 것이다. 여기서 말하는 기준이란 바로 다음과 같다..

 CPU utilization

이 경우의 기준은 사용자가 컴퓨터를 이용한 전체시간 중에 작업처리를 위해 실제 CPU가 이용된 시간의 비율을 말한다. 바로 CPU의 낭비가 가장 적은 것에 초점을 두고 스케줄링하는 것이다. 다시 말해 CPU utilization는 ‘몇%의 일이 처리되었나’가 관심사이다.  예를 들어 은행에 A직원은 3명의 손님을 처리하였고 B직원은 30명의 손님을 처리했다면 어느 직원이 열심히 일한 것일까. 별다른 고려없이 표면적인 수치로만 이해한다면 분명 B직원이 열심히 작업을 수행했다고 생각할 수 있다. 그러나 만일 A직원이 처리한 3명 손님의 작업은 시간이 오래 소요돼 잠시도 쉴 틈이 없었고 B직원이 처리한 30명의 작업은 1분씩의 시간이 소요돼 30분만에 마치고 나머지 시간은 사적인 일을 처리했다면 어떨까. 그렇다면 단순히 처리된 손님수로만 직원의 성실도를 체크할 수는 없는 것이다. 이와 같이 은행직원이(CPU) 얼마나 쉼 없이 일을 처리했느냐는 것이 바로 CPU utilization의 관점인 것이다. CPU utilization의 관점에서 가장 효율적인 스케줄링은 FCFS(First Come First Served) 이다. FCFS의 경우는 프로세스에 대한 별도의 처리없이 (예를 들어 타임퀀텀이 다 되어 수행하던 프로세스를 저장하고 다음 프로세스를 처리) 계속해서 작업이 수행됨으로 overhead가 적어진다. 따라서 CPU의 낭비가 가장 적은 스케줄링인 것이다. Priority의 경우에는 하나의 프로세스를 처리하던 중 우선순위가 높은 프로세스가 처리되어야 할 경우 앞서 수행되던 프로세스를 저장하고 이후 제자리를 찾아주는 등의 작업에 overhead가 소요되는 것이다. 또한 Round Robin의 경우 타임퀀텀 내에 완료되지 않은 프로세스들을 관리하는 작업에 overhead가 소요되는 것이다 

Response time

이 경우의 기준은 하나의 프로세스가 일을 시작해서 끝날 때까지 걸리는 시간에 초점을 맞춘 것으로 작업처리 평균시간이 가장 적게 걸리도록 스케줄링하는 것이다. 은행에 한손님이 들어서 은행을 나설 때까지 걸리는 시간을 최대한 줄이는 것이 바로 Response time을 기준으로 설계된 것이다. 여러 방법 중 Round Robin으로 설계했을 때 Response time이 가장 적게 걸린다. 스케줄링 알고리즘에서도 언급했듯이 FCFS의 경우 긴 시간을 필요로 하는 작업이 앞에 놓였을 때 작업처리평균시간은 길어지게 마련이다. 바로 짧은 타임퀀텀을 갖고 있는 Round Robin이 Response time을 가장 적게 해주는 설계방법인 것이다.

 Throughput

처리량을 기준으로 할 경우 기준시간당 얼마나 많이 일을 처리했느냐 하는 것이 관건이다. 바로 한 명의 은행직원이 몇 명의 손님을 처리 했는냐 하는 것인데 빨리 빨리라는 개념이 최상의 서비스란 생각을 갖고 있는 은행장이라면 처리량을 기준으로 은행시스템을 설계할 것이다. 은행직원의 관심은 오직 ‘한 시간 동안-기준시간을 한 시간이라 한다면-몇 명의 일을 처리 했나’일 것이다. 은행은 1시간당 100명의 손님이 오는데 직원 1명은 1시간당 평균 25명을 처리하니까 창구직원을 4명을 두어야겠다 라는 생각을 분명 갖고 있을 것이다.

 Waiting time

프로세스가 준비상태의 큐로부터 얼마나 빨리 나오게 할 수 있느냐에 초점을 맞춘 것이 Waiting time이다. 은행에 들어서 번호표를 빼어 든 다음 자신의 번호가 표시되어 처리가 시작될 때까지 기다리는 시간을 최소로 하는 것이 바로 Waiting time의 관점에서의 설계기준인 것이다. 최근 어느 은행에서는 손님이 10분 이상 Waiting time을 가졌을 경우 1000원을 보상해주는 제도가 도입되었었다. 바로 그 은행은 최고의 서비스란 손님들의 Waiting time을 최소화하는 것이란 생각이 분명 내재되어 있었을 것이다.

질문) throughput의 관점이 결국 CPU utilization의 관점과 유사한 개념이 아닐까요?

답) throughput의 관점에서는 CPU, memory, I/O를 다 보는 것이다. throughput는 보다 넓게 시스템의 균형을 중심으로 보는 것이다.              

질문) CPU 스케줄링이 시스템의 균형과 무슨 관계가 있는 것입니까. (앞서 우리는 CPU가 프로세스의 처리속도와는 별다른 관계가 없다고 하었다)

답) CPU 스케줄링을 잘하면 시스템이 효율적이게 된다. 결국 CPU 스케줄링이 시스템 전체에 어떤 영향을 미치는 것인가를 주목하는 것이다.

요점정리

 Scheduling의 비교기준

1. CPU utilization

이 경우의 기준은 바로 CPU의 낭비가 가장 적은 것에 초점을 두고 스케줄링하는 것이다. 다시 말해 ‘몇%의 일이 처리되었나’가 관심사이다.

2. Response time

이 경우의 기준은 하나의 프로세스가 일을 시작해서 끝날 때까지 걸리는 시간에 초점을 맞춘 것으로 작업처리평균시간이 가장 적게 걸리도록 스케줄링하는 것이다.

3. Throughput

처리량을 기준으로 할 경우 기준시간당 얼마나 많은 일을 처리했느냐 하는 것이 관건이다.

4. Waiting time

프로세스가 준비상태의 큐로부터 얼마나 빨리 나오게 할 수 있느냐에 초점을 맞춘 것이 Waiting time이다.