THINK-PRO BLOG

내용 요약>

- 파일 관리기

- 물리 저장 매체의 분류

- 저장 장치 계층

- 자기 디스크 - (자기) 디스크의 성능, 성능 개선 방법: RAID

- 광 디스크

- 자기 테이프

- 저장 장치 액세스

- 버퍼 매니저 - 버퍼 대치전략

- 파일 구성

- 고정 길이 레코드 - 자유 리스트

- 가변 길이 레코드 - 바이트 스트링 표현법, 슬롯 페이지 구조, 공간예약, 포인터 방법

질문>

Q. 파일 관리기란 무엇인가? (File Manager)

 파일 관련 처리 과정 중에 레코드가 필요하면, 레코드는 디스크로부터 주기억 장치로 반입(Fetch) 된다. 파일 관리기는 레코드가 있는 페이지를 결정하는 역할을 한다. 원하는 레코드를 포함하는 페이지를 빨리 찾아내기 위해 보조적인 자료 구조를 사용할 수 있다. 파일 관리기가 원하는 페이지를 알아내면 버퍼 관리기에게 해당 페이지를 요청하는 방식으로 동작하며, 버퍼 관리기는 요청 페이지를 디스크에서 가져와 버퍼에 적재하고, 파일 관리기에 알린다.

Q. 저장 장치에서 블록이란?

 파일은 블록이라는 고정 길이 저장 단위로 분할되어 있다. 블록은 저장 장치 할당과 데이터 전송 단위의 역할을 한다. 데이터베이스는 기본적으로 블록의 크기로 4~8KB만큼을 가진다. 한 블록은 여러 레코드를 포함한다. 시스템은 디스크와 메모리 간의 데이터(파일) 전송에서 최소한의 블록 개수가 전송이 되도록 해야 한다. 가급적 많은 블록을 주 기억 장치, 즉 메인 메모리에 있도록 해야 디스크 액세스 수를 줄일 수 있다.

Q. 저장 장치에서 버퍼란?

 디스크 블록의 사본을 저장하는 데 사용되는 메인 메모리 부분이다. 버퍼 매니저는 메인 메모리에 버퍼 공간을 할당하는 서브 시스템으로 작동한다.

Q. 버퍼 매니저는 무엇이고, 버퍼 매니저의 동작 원리는 어떠한가? (Buffer Manager)

 프로그램은 디스크에서 블록이 필요할 때 버퍼 매니저를 호출한다. 필요한 블록이 버퍼(버퍼는 메인 메모리의 부분임)내에 이미 존재하면 메인 메모리 내의 블록 주소값을 요청하는 프로그램에게 전달한다. 블록이 버퍼 내에 없으면, 버퍼 매니저는 필요에 따라 새로운 블록을 위한 공간을 마련하기 위해 일부 블록을 내보내에 버퍼내어 공간을 확보하고 할당한다. 내보내진 블록은 디스크에 수록되고 읽혀진 최근 시점 이후 갱신되었을 때만 디스크에 다시 쓰이게 된다. 버퍼에 공간이 할당되면, 버퍼 매니저는 디스크에서 버퍼로 블록을 읽어 들이고 메인 메모리내 블록의 주소를 요청자(요청 프로그램)에게 전달한다.

Q. 버퍼 대치 전략에는 무엇이 있는가?

 LRU 버퍼 대치 전략과 MRU 버퍼 대치 전략이 있다.

Q. LRU 버퍼 대치 전략은 무엇인가?

 대부분 운영체제는 최근에 사용되지 않은 블록(LRU 블록)을 대치한다. LRU 대치 전략은 미래의 참조 지표로서 과거의 블록 참조 패턴을 사용한다는 특징을 가지고 있다. 질의는 잘 정의된 액세스 패턴(순차 스캔과 같은)을 가지며, 데이터베이스 시스템은 미래의 참조를 예측하는 데 사용자 질의 내의 정보를 사용할 수 있다. LRU는 데이터의 반복 스캔을 포함한 어떤 액세스 패턴에 대해서는 나쁜 전략일 수 있다.

Q. MRU 버퍼 대치 전략은 무엇인가?

 MRU 버퍼 대치 전략은 시스템이 현재 처리중인 블록을 고정시키고, 블록의 마지막 레코드가 처리된 후 블록을 해제하는 대치 전략이다. 해제되는 블록은 가장 최근에 사용한 블록이 되며, 그 블록이 점유했던 공간이 해제된다.

Q. 파일이란 무엇인가?

 파일은 데이터베이스의 구성 단위이다. 즉, 데이터베이스는 파일의 모임이다. 각 파일은 레코드로 구성되며, 레코드는 필드로 구성된다. 각 레코드가 단일 블록 내에 완전하게 포함되도록 하는 것이 좋다. 하나의 레코드가 여러 블록에 걸쳐 저장되는 것을 제한함으로써 데이터 항목에 대한 접근을 단순화시키고 속도를 향상시킬 수 있다. 파일을 구성하는 가장 단순한 방법은 레코드의 크기를 고정길이로 지정하는 것이다.

Q. 스케줄러는 무엇이며, 스케줄링을 하는데 있어서 중요한 것은 무엇인가?

스케줄러는 레디 큐에 존재하는 프로세스들을 특정한 우선순위를 기반으로 CPU를 할당받게 해주는 역할을 한다. 스케줄러가 스케줄링을 하는데에는 2가지 중요한 요소가 있다. 첫 번째, 스케줄링의 최대 관심사는 무엇인가, 즉, 스케줄링의 기준은 무엇인가? 이다. 스케줄링의 기준이 될 수 있는 대표적인 예로는 대기 시간(waiting time), CPU 할당 시간(allocation time) 등이 있다. 두 번째, 스케줄링을 어떻게 구현할 것인가? 이다. 스케줄링을 구현할 때는 반드시 자료구조의 구현이 따른다. 어떠한 자료구조를 이용하여 스케줄링을 구현할 것인지를 결정하는 것이 스케줄링에 중요한 요소이다. 대표적으로, 링크드 리스트, 해쉬 리스트, 비트 맵, 레드 블랙 트리(리눅스) 등 다양한 자료구조를 사용하지만, 정밀하고 견고한 운영체제일 수록 스케줄링에 사용하는 자료구조의 실행시간을 최대한 줄여나가는 것이 중요하다. 최소한 O(log n) 수준으로 실행 시간을 낮춰야 한다.

Q. 스케줄링의 목표는 무엇인가?

스케줄링의 목표에는 3가지가 있다. CPU 활용을 최대화하자, 평균 대기 시간을 최소화하자. 처리량을 최대화하자. 스케줄링은 멀티 프로세싱 운영 체제를 디자인하는 일과 컴퓨터의 멀티태스킹 작업을 만들어내는 데에 있어서 핵심 개념이다.

Q.  스케줄링 알고리즘에는 무엇이 있나?

FCFS(First Come, First Served), SJF(Shortest Job First), Priority Scheduling, RR(Round Robin) Scheduling 등이 있다.

Q. FCFS(FIrst Come, First Served) 스케줄링은 무엇인가? 그리고 어떤 특징을 가지고 있고, 어떤 장단점을 가지고 있나?

  FCFS는 First Come, First Served 의 약자이다. 즉, 먼저 온 사람 먼저 대접한다는 뜻으로, CPU를 처음 요구한 프로세스가 CPU를 처음 사용한다는 의미의 스케줄링 알고리즘이다. 구현할 때는 FIFO (First In FIrst Out) 큐 자료구조를 사용한다. FCFS는 스케줄링 특성상 비선점 스케줄링 알고리즘이며, CPU를 사용하고 있는 프로세스 자기 자신이 CPU를 놓아줄 때까지 CPU를 다른 프로세스에게 양보하지 않는다. 이러한 특성은 콘보이 효과를 불러 일으킨다. 콘보이 효과란, CPU를 매우 오래 사용하는 프로세스가 도착하게 되면, 다른 프로세스가 CPU를 사용하는데 기다리는 대기 시간이 매우 커지는 현상을 말한다. 콘보이 효과는 비선점 스케줄링을 사용할 때만 발생한다. FCFS 스케줄링은 콘보이 효과때문에 평균 대기시간이 매우 형편없는 스케줄링 알고리즘이다. FCFS는 비선점 스케줄링 알고리즘의 장점을 그대로 가진다. 비선점 스케줄링 알고리즘은 모든 프로세스가 공평한 조건으로 CPU를 사용할 수 있게 해주며, 반응 시간을 예측할 수 있다.

Q. SJF 알고리즘은 무엇인가? 그리고 어떤 특징을 가지고 있고, 어떤 장단점을 가지고 있나?

  SJF는 Shortest Job First 의 약자이다. 가장 시간이 적게 걸리는 작업을 먼저한다는 뜻으로, SJF의 정의는 CPU가 릴리즈되어 있을 때, 가장 시간이 적게 걸리는 프로세스가 선택되어 실행된다는 것이다. SJF는 비선점 스케줄링과 선점 스케줄링 두가지 종류가 있고, 선점형 SJF는 SRTF(Shortest Remaining Time First)라고도 한다. SJF는 스케줄링 알고리즘 중에서 최소의 평균 대기 시간을 위해 최적화된 스케줄링 알고리즘이다. (즉, 스케줄링 알고리즘 중에서 평균 대기 시간을 가장 적게 가지는 스케줄링 알고리즘이다.) 

 SJF의 단점도 있다. SJF에서 최소의 오버헤드로 최적의 성능을 보장하도록 알고리즘을 구현하는 것이 힘들다는 것이 SJF의 단점이다. 선점형 SJF에서는 프로세스들끼리 서로 끼어들기 때문에, 다음 CPU 점유 시간을 예측하는 것이 매우 힘들다. (SJF는 CPU 점유 시간 자체를 예측해야만 구현할 수 있는 스케줄링 알고리즘이다. 즉, 미래를 예측해야 한다는 특성 자체가 SJF 알고리즘을 구현하는 것을 어렵게 만드는 것이다.) 이러한 특성은 제대로 성능을 발휘하는 선점형 SJF를 구현하는 것이 힘들게 한다. 

Q. Priority Scheduling 은 무엇인가? 어떤 특징을 가지고 있고, 어떤 장단점을 가지고 있나?

  높은 우선순위를 가진 프로세스가 항상 먼저 CPU를 사용할 수 있도록 구현한다. 우선순위 기반 스케줄링에는 치명적인 단점 이슈가 있다. 바로 Starvation(굶주림)이다. 우선순위가 낮은 프로세스는 영원히 작동하지 않을 수 있다. (우선순위가 낮은 프로세스의 대기 시간이 무한정 늘어날 수 있다.) Starvation의 해결책은 바로 Aging-method이다.   레디 큐에서 오랜 시간을 기다린 프로세스는 계속해서 우선순위를 높히게 하는 기법이다. 이러한 에이징 메서드 기법을 통해서 우선순위가 낮은 프로세스도 최대 한도의 대기 시간을 가질 수 있다. 참고로, 우선순위 스케줄링은 선점형 SJF와 비슷한 경향을 가지고 있다. 우선순위 스케줄링에서의 각 프로세스의 우선순위가 선점형 SJF 스케줄링에서의 예측 CPU 점유 시간과 동일한 역할을 한다. 우선순위가 높을 수록, 먼저 CPU를 사용할 수 있게 해주듯이, 예측 CPU 점유 시간이 짧을 수록 먼저 CPU를 사용할 수 있게 해준다는  것이 매우 흡사하다.

Q. Round Robin(RR) 스케줄링은 무엇인가? 어떤 특징과 장단점을 가지는가?

  Round Robin 스케줄링은 각각의 프로세스가 공평하게 시간 간격 동안 CPU를 활용할 수 있도록 하는 스케줄링 알고리즘이다. 정해진 시간 간격이 끝나면, CPU를 사용하고 있던 프로세스는 선점적으로 추방당한다. (레디 큐에 다시 들어가게 된다.) 여기서 정해진 시간 간격을 Time Quantum 이라고 한다. 

만약 레디 큐에 n개의 프로세스와 q의 time qunatum을 가지고 있다고 가정하면, 모든 프로세스는 최대한 (n-1)q 시간 안에 CPU 사용을 시작하게 됨을 보장할 수 있다. 따라서, 라운드 로빈은 SJF 스케줄링 보다 반응 시간 최적화에 있어서는 더 탁월한 스케줄링 알고리즘이다. (하지만 대기 시간의 최적화는 SJF가 더 좋은 편이다.)

쓰레드

(프로젝트 개요)

현재 pintos는 시스템 콜 핸들러가 제대로 구현되어 있지 않다. 시스템 콜이 발생해도 system call!! 이라는 출력문 하나만 달랑 뿌리고, 그대로 스레드가 종료된다.(thread_exit()) 따라서, 이번 프로젝트 2는 핀토스의 시스템 콜 핸들러 함수를 구현하고, 간단한 시스템 콜(halt, exit, create, remove)를 구현해본다.

| 시스템 콜?

사용자 모드 수준에서의 프로그램이 커널 기능을 사용할 수 있도록 해주는 인터페이스.

시스템 콜의 기능들은 커널 모드에서 실행되고, 처리 후 사용자 모드로 복귀됨.

(프로젝트 해결 방법 개요)

우선, 2가지 함수를 구현해야 함. 

1. 유저 영역은 0x08048000 에서 0xc0000000 사이에 (경계값 제외) 존재하는 주소값이면 유저 영역인 것이다. check_address를 구현할 때 이 바깥 범위의 값이면 exit (-1)을 호출해 프로그램을 종료시켜야 한다. (유저 영역이 아닌 커널 영역을 건드리는 프로그램은 프로그램을 종료시키는 것이 적절한 운영체제의 반응이다.)

2. get_argument 의 함수는 esp 인자에서 인자들을 4바이트씩 긁어온 후, arg라는 변수에 저장하는 행동을 한다. 참고로, arg에 저장하는 값들은 인자의 주소값이다. (이 부분을 정확히 이해하라.) arg에 주소값을 저장하지 않고 인자값 자체를 저장하면 안된다. 왜냐하면, 시스템 콜의 인자들이 전부 4바이트로 표현할 수 있다는 보장이 없기 떄문이다. (가령 문자열이 전달되어 온다면 어떻게 할것인가..? 해결방법은 문자열 자체의 주소값을 저장하는 것이다.)

따라서, arg에는 반드시 인자의 주.소.값이 저장되어야 함을 무한 강조!!

f->esp 의 첫 4바이트는 시스템 콜 넘버이므로, 그 다음 4바이트씩 count 횟수만큼 긁어와서 arg에 저장하면 된다.

============

시스템 콜 핸들러 함수

static void syscall_handler (struct intr_frame *f UNUSED)
{
/* 유저 스택에 저장되어 있는 시스템 콜 넘버를 이용해 시스템 콜 핸들러 구현 */
/* 스택 포인터가 유저 영역인지 확인 */
/* 저장된 인자 값이 포인터일 경우 유저 영역의 주소인지 확인*/
}

f->esp (유저 스택)에는 4바이트씩 인자들이 저장되어 있다. f->esp의 첫 번째 4바이트에는 시스템 콜의 넘버가 저장되어 있고, 그 뒤로 4바이트씩 시스템 콜의 인자가 저장되어 있다.

예를 들어, create 시스템 콜은 인자로 파일 이름과 파일의 첫 크기를 인자로 받는다. 그러면, create 시스템 콜이 발생할 때 유저 스택 포인터는

다음과 같은 구조를 띈다.

f->esp

(4바이트) 4

(4바이트) 0x100

(4바이트) 0x104

....

0x100은 파일 이름 문자열의 주소값이고, 0x104는 파일의 첫 크기의 주소값이다. 물론, 파일의 첫 크기값은 정수일테지만, 정수값 자체를 유저 스택에 저장하지 않는다. 유저 스택에는 '주소값'이 저장되어 있음을 무조건 기억하라. 따라서, 나중에 시스템 콜 핸들러에서 create 시스템 콜을 처리할 때 다음과 같이 처리해야 한다.

    case SYS_CREATE:/* 4 */
      f->eax = create((char *)*(int *)arg[0], (unsigned)*(int *)arg[1]);
    break;

pintos 운영체제에는 자체 내장되어 있는 테스트 프로그램이 있습니다. 

src/userprog/ 디렉토리에서 'make check' 쉘 명령어를 입력하면, 76개의 테스트를 실행하며, 마지막에 테스트의 결과를 알려줍니다.

76개의 테스트 중 (제가 봤을 때) 제일 디버깅이 어려운 테스트는 'multi-oom'테스트입니다.

multi-oom테스트의 목적은 pintos운영체제의 메모리 누수가 존재하는지를 확인합니다.

메모리 누수가 일어나는 곳을 찾아야 하는데 쉽지 않습니다. 

multi-oom 테스트를 해결해나가는 약간의 팁을 제공하자면,

1) malloc - free를 정확하게 사용해라. 

malloc함수는 힙영역에 새로운 메모리를 할당하는 함수입니다. 만약에 어떤 함수에서 메모리를 새로 할당한 이후, 그 함수가 종료되기 전까지 할당한 메모리가 사라지지 않는다면, 계속해서 쓸모없는 메모리가 남게 되어 메모리 누수가 발생합니다. 따라서, 함수 루틴 안에서 반드시 malloc을 사용한 경우에는 그에 대응하는 free를 해주기 바랍니다. 참고로, malloc을 한 이후, 그 메모리를 가리키는 포인터를 다음에도 계속 가지고 있다면, 즉시 free를 해줄 필요는 없습니다. 최종적으로 그 메모리가 필요없게 되었을 때 정확히 free를 해주는 것이 관건인 것이지요.

간단히 말하자면, 함수 내에서 임시적으로 사용하기 위해 할당한 메모리는 그 함수가 끝나는 시점에서 즉시 free로 메모리 해제를 해주어야 하고, 스레드 내에서 파일 디스크립터 테이블과 같이 스레드가 죽을 때까지 가지고 있어야 하는 정보에 대한 메모리는 스레드가 죽을 때, 메모리 해제를 해주면 되는 것이지요.

2) 1)과 같은 이유로, palloc_get_page에 대응하는 palloc_free_page를 철저하게 사용하라.

1)과 동일한 이유입니다. palloc_get_page도 메모리를 할당하는 함수이고, palloc_free_page도 메모리를 해제하는 함수입니다.

3) 문자열에 대한 메모리 누수를 정확하게 계산하라.

운영체제를 건축하는 일은 C언어의 메모리 사용을 '정확히' 알아야 합니다.

하지만, 제가 학부생으로서 다른 친구들을 보았을 때 C언어의 메모리(포인터) 사용을 정확하게 아는 사람은 정말 드물어요.

아마 4학년 졸업한 후에도 10명 중 1명이 채 안될 겁니다. 정말 세밀한 부분까지 완벽하게 이해한 사람은 거의 없습니다.

물론 저도 아직 부족한 부분이 많고, 운영체제를 건축해보면서 더더욱 부족한 부분을 알게 되고 수정해나가네요.

그런 부분에서 큰 성장을 하는 것 같아 기분이 좋습니다. :)