1. Numpy란?

numpy는 Numerical Python의 약자로 행렬이나 일반적으로 대규모 다차원 배열을 쉽게 처리 할 수 있도록 지원하는 파이썬의 라이브러리이다. NumPy는 데이터 구조 외에도 수치 계산을 위해 효율적으로 구현된 기능을 제공한다.

 

2. Numpy 특징

  • 일반 List에 비해 빠르고, 메모리를 효율적으로 사용한다.
  • 반복문 없이 데이터 배열에 대한 처리를 지원하여 빠르고 편리하다.
  • C, C++, 포트란 등의 언어와 통합이 가능하다.
  • 선형대수와 관련된 다양한 기능을 제공한다.

3. Numpy Array

  • numpy는 np.array 함수를 활용하여 배열을 생성합니다.
  • numpy는 하나의 데이터 타입만 정의가 가능하며 배열에 넣을 수 있습니다.
  • List와 가장 큰 차이점은 다이나믹 타이핑을 지원하지 않습니다.
  • C의 Array를 사용하여 배열을 생성하여 속도가 빠릅니다.

 

예제1) 1차원 배열의 경우

import numpy
array = numpy.array([1, 2, 3, 4, 5, 6, 7, 8, 9])
array #출력: array([1, 2, 3, 4, 5, 6, 7, 8, 9])
array.shape #출력: (9,)
type(array) #출력: numpy.ndarray

예제2) 2차원 배열의 경우

array = numpy.array([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]])
array #출력: array([[ 1,  2,  3,  4],
      #             [ 5,  6,  7,  8],
      #             [ 9, 10, 11, 12]])
array.shape #출력: (3, 4)

4. Numpy Array 생성 방법

◎ 리스트

numpy 모듈의 array 메소드에 파라미터로 리스트를 넘겨주면 numpy array가 리턴된다.

import numpy
array = numpy.array([1, 2, 3, 4, 5, 6, 7, 8, 9])
print(array)

#출력: [1 2 3 4 5 6 7 8 9]

◎ 동일 값으로 생성

full 메소드를 사용하면, 모든 값이 같은 numpy array를 생성할 수 있다.

import numpy
array = numpy.full(5, 9) 
print(array)

#출력: [9 9 9 9 9]

모든 값이 0인 array 생성

import numpy
array = numpy.zeros(6, dtype=int) 
print(array)

#출력: [0 0 0 0 0 0]

모든 값이 1인 numpy array 생성

import numpy
array = numpy.ones(6, dtype=int) 
print(array)

#출력: [1 1 1 1 1 1]

연속된 값들이 담긴 numpy array 생성

arange 함수를 사용하면 연속된 값들이 담겨 있는 numpy array를 생성할 수 있다.

 

⊙ 파라미터 1개

import numpy
array1 = numpy.arange(6)
print(array1)

#출력: [0 1 2 3 4 5]

파라미터 2개

arange(n, m)을 하면 n부터 m-1까지의 값들이 담긴 numpy array가 리턴된다.

import numpy
array1 = numpy.arange(2, 7)
print(array1)

#출력: [2 3 4 5 6]

파라미터 3개

arange(n, m, s)를 하면 n부터 m-1까지의 값들 중 간격이 s인 값들이 담긴 numpy array가 리턴된다.

import numpy
array1 = numpy.arange(3, 17, 3) 
print(array1)  

#출력: [3 6 9 12 15]

 

 

 

'Study > Data Science' 카테고리의 다른 글

Data Science 시작하기  (0) 2020.05.25

데이터 과학(Data science)이란, 위키피디아에 따르면 데이터 마이닝(Data Mining)과 유사하게 정형, 비정형 형태를 포함한 다양한 데이터로부터 지식과 인사이트를 추출하는데 과학적 방법론, 프로세스, 알고리즘, 시스템을 동원하는 융합분야라고 한다. 즉, 데이터와 관련된 모든 일을 데이터 과학이라고 한다.

 

해당 분야를 전문으로 하는 사람을 데이터 사이언티스트(Data Scientist)라고 부른다. 이들은 가치를 더할 수 있는 일을 찾고, 데이터를 이용해서 문제를 해결하는 역할을 한다.

 

데이터 사이언스의 순서는 대략적으로 이렇다.

  1. 문제 정의하기
  2. 데이터 모으기
  3. 데이터 다듬기
  4. 데이터 분석하기
  5. 데이터 시각화 및 커뮤니케이션

문제 정의하기

해결하고자 하는 게 무엇인지, 언제까지 어떤 결과물을 얻을 것인지, 어떤 방식으로 데이터를 활용할 것인지 등을 설정한다.

  • 목표 설정
  • 기간 설정
  • 평가 방법 설정
  • 필요한 데이터 설정

데이터 모으기

이미 모아 놓은 데이터를 그대로 사용할 수도 있고, 공공 기관 등에서 배포한 자료를 찾아 볼 수도 있고, 웹사이트에서 직접 데이터를 수집할 수도 있다.

  • 웹 크롤링
  • 자료 모으기
  • 파일 읽고 쓰기

데이터 다듬기

우리가 수집한 데이터에는 수많은 문제점들이 있다. 이런 문제점들로 인해 분석 자체가 불가능할 수도 있고, 혹은 분석을 하더라도 잘못된 결론으로 이어질 수 있다. 따라서 데이터를 올바르게 다듬어 활용 가능한 데이터로 만드는 것이다.

  • 데이터 관찰하기
  • 데이터 오류 제거
  • 데이터 정리하기

데이터 분석하기

통계를 이용해 수치적으로도 할 수도 있고, 수십 가지의 그래프를 그려보면서 탐색할 수도 있다. 처음 설계했던 방식대로 데이터를 활용해서 원하는 결과를 도출해 내야 한다.

  • 데이터 파악하기
  • 데이터 변형하기
  • 통계 분석
  • 인사이트 발견
  • 의미 도출

커뮤니케이션

어떤 문제를 해결하려 했는지, 어떻게 데이터를 모았는지, 어떤 방식으로 어떤 인사이트를 얻었는지 등을 다른 사람들에게 전달해야 한다. 적절한 시각화를 통해 소통을 원활히 할 수 있다.

  • 다양한 시각화
  • 커뮤니케이션
  • 리포트

출처: 코드잇(Codeit) https://www.codeit.kr/dashboard

'Study > Data Science' 카테고리의 다른 글

Data Science(Numpy 사용하기)  (0) 2020.05.25

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)

IBMOS/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의 예시>

* 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 역시 이 방식으로 물리 메모리 프레임을 같이 가리키게 하여, 전체 메모리를 절약하게 된다. 아래 그림에서 프로세스 A1번 페이지, 프로세스 B7번 페이지가 물리 메모리 5번 프레임을 같이 가리키는 것을 볼 수 있다.

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

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

 

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

 

<자식 프로세스를 생성(fork)한 직후 프로세스와 메모리 모습>

 

< 부모 프로세스가  Page C 를 수정한 후 프로세스와 메모리 모습 >

5) MMU(Memory Management Unit)

5-1) MMU?

. MMU(Memory Management Unit)의 개념

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

 

. MMU 역할

주소 변환

 실제 메모리와 가상 메모리의 주소 변환

메모리 보호

 각 영역 간 읽기/쓰기 침범 차단 역할

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

. MMU 주요 기능

주요 기능

설명

주소 변환

 가상메모리 주소를 물리 주소로 변환

특권 통제

 사용자 프로그램에서 커널 영역 침범 차단

캐시 통제

 캐시 가능 영역과 불가 영역 설정

읽기/쓰기보호

Read / Write 불가 영역 생성 기능

메모리 보호

 각 프로세스 별 영역만 접근하도록 통제

 

. 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 동작

TLB Hit

가상주소에 해당 항목이 TLB에 있음

CPUTLB 통해 즉시 물리주소 생성

TLB Miss

가상주소에 해당 항목이 TLB에 없음

주기억장치 페이지테이블 참조, TLB 갱신

페이지 Fault

가상주소에 해당 항목이 주기억장치에 없음

디스크에서 페이지 반입, 페이지테이블 갱신

 

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

항목

직접 사상의 주소 변환

TLB에 의한 주소 변환

사상 방식

Direct Mapping

Association Mapping

페이지 테이블 위치

주기억장치 내

고속의 특수 캐시 내 (TLB)

장단점

데이터 접근시 주기억장치 두 번 접근 필요

TLB 병렬 고속탐색
고비용, 적용 한계

 

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

고려사항

상세 내용

Entry 수 증가

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의 횟수가 어느 한계점을 넘어가면 프로세스를 종료하는 방식으로 구현한다.

구분

설명

특징

원리

– 지역성 가정을 기반으로 동작

– 지역성 기반

특징

– 과도기, 안정기가 주기적 반복

– 프로세스 변화

장점

– Multi-Programming 정도 높임

– Page Hit rate증가

– CPU 활용률 최적화

– 임계치 극대화

단점

– Working Set 추적관리 복잡

– 크기/구성 변화

– Window 사이즈 설정이 모호함

– 최적값 모름

– 참조 페이지 Queue 유지관리

– 메모리관리 복잡

                                                                           <working set model 특징>


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


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


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


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 PIPEPIPE의 또 다른 단점인 읽기/쓰기가 동시에 가능하지 않으며, 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 운영체제의 특성상 프로세스의 메모리 영역은 반드시 보호되어져야 한다. 하지만 메모리 영역에 있는 데이터를 다른 프로세스들도 사용할 수 있도록 해야 하는 경우도 발생할 수 있다. PIPEMessage Queue등을 이용해서 데이터 통신을 이용하여 데이터를 전달하는 방법도 있지만, Thread에서처럼 메모리 영역을 공유한다면 더 편하게 데이터를 함께 사용할 수 있다.

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

 

Memory Map

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

 

Socket

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

 

Semaphore

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

 

+ Recent posts