2013년도 운영체제 1학기 텀 프로젝트 2

<버퍼 캐쉬 구현>

버퍼 캐쉬의 정의
커널은 모든 파일을 직접 디스크에서 읽고 쓸 수 있으나, 디스크의 느린 데이터 전송 송고 때문에 시스템의 응답시간과 처리능력이 나빠진다. 따라서 커널은 최근 사용된 디스크 블록의 데이터를 유지하는 공통의 내부 데이터 버퍼(이것을 버퍼 캐쉬라 한다)를 관리하여 디스크 액세스를 최소화한다. 커널의 버퍼 캐쉬 모듈은 파일 서브시스템과 블록단위의 장치 드라이버 사이에 위치하고 있다.
커널이 디스크에서 데이터를 읽으려 할 때 우선 버퍼캐쉬에서 읽으려고 시도하고, 만일 데이터가 캐쉬 속에 있으면 그대로 읽게 되고, 없을 경우 커널은 디스크에서 데이터를 읽어 될 수 있는 대로 유익한 데이터를 보관하려는 알고리즘에 따라 캐쉬에 저장한다. 디스크에 쓰려고 하는 데이터의 경우도 나중에 커널이 그것을 이용할 경우를 대비하여 캐쉬에 저장해 둔다.

목적
커널이 어떻게 버퍼 캐쉬를 관리하고 접근하는지 제시된 구현 시나리오(XI번 항목 참조)를 구현하여 버퍼 캐쉬에 대한 내용을 이해하고 숙지한다.

버퍼 할당 알고리즘
다음은 버퍼 할당 알고리즘인 getblk 알고리즘이다.
- 입력 : 파일 시스템 번호, 블록 번호
- 출력 : 블록에 사용할 수 있는 락된(locked) 버퍼
while (버퍼를 찾지 못한다)
{
if (블록이 해쉬대기행렬에 있다)
{

if (버퍼를 사용 중)  // 시나리오 5
{

sleep (해당 버퍼가 빌 때까지);

continue;     // while 루프로 돌아간다.

}

버퍼에 사용중이라는 표시를 한다.   // 시나리오 1

프리 리스트에서 버퍼를 삭제한다.;

return (버퍼);

}

else   // 블록이 해쉬대기행렬에 없다

{

if (프리 리스트상에 버퍼가 없다)  // 시나리오 4

sleep (어떠한 버퍼가 빌 때까지);

continue;  // while 루프로 돌아간다.

}

자유리스트에서 버퍼를 지운다.;

if (버퍼에 delayed write의 표시가 붙어있다)  // 시나리오 3

{

디스크의 버퍼의 내용을 비동기로 출력한다.;

continue;  // while 루프로 돌아간다.

}

// 시나리오 2 - 빈 버퍼의 검출

옛날 해쉬대기 행렬에서 버퍼를 삭제한다.;

새로운 해쉬대기 행렬에 버퍼를 삽입한다.;

return (버퍼);

}

}

}

버퍼 반환 알고리즘
다음은 버퍼 반환 알고리즘인 brelse 알고리즘이다.
- 입력 : 락된(locked) 버퍼
- 출력 : 없음
{

어떤 버퍼가 비기를 기다리던 모든 프로세스를 깨운다.;

이 버퍼가 비기를 기다리던 모든 프로세스를 깨운다;

인터럽트를 막기 위하여 프로세서의 실행레벨을 올린다;

if (버퍼의 내용이 유효이며 버퍼가 오래된 것이 아니다)

버퍼를 프리 리스트의 맨 뒤에 넣는다.;

else

버퍼를 프리 리스트의 맨 앞에 넣는다.;

인터럽트를 허가하기 위하여 프로세서의 실행레벨을 낮춘다;

unlock(버퍼);
}

버퍼헤드의 구조

버퍼는 실제 데이터 영역과 버퍼 헤더로 구성되어 있다.

장치 번호와 블록 번호로 고유한 버퍼를 식별한다.

버퍼 헤드의 자료구조는 다음과 같다.

struct Buffer{

int deviceNum;             // 장치번호

int blkno;	// 블록번호

char* data;	// 데이터 영역의 포인터

int stateFree;	// 버퍼 상태

int stateBusy;	// 버퍼 상태

int stateDelay;	// 버퍼 상태

int stateWrite;	// 버퍼 상태

Buffer* queuePrev;	// 해쉬큐의 다음 버퍼 포인터

Buffer* queueNext;	// 해쉬큐의 앞 버퍼 포인터

Buffer* freeListPrev;      // 프리리스트의 앞 버퍼 포인터

Buffer* freeListNext;      // 프리리스트의 다음 버퍼 포인터

};

해쉬큐의 버퍼 자료구조는 다음과 같다.

class CQueue{

public:

CQueue();

~CQueue();

void makeEmpty();       // 큐를 모두 삭제

bool isEmpty();	// 큐가 비었나 확인

bool isFull();	// 큐가 가득 찼나 확인

void enqueue(Buffer* newbuf);  // 큐의 블록 삽입

void dequeue();	// 큐의 블록 삭제

Buffer* getFront();	// 큐의 첫 블록 리턴

private:

Buffer* front;

};

프리 리스트의 자료 구조는 다음과 같다.

class FreeList{

public:

FreeList(void);

~FreeList(void);

void makeEmpty();	// 리스트를 모두 삭제

bool isEmpty();	// 리스트가 비었나 확인

bool isFull();	// 리스트가 가득 찼나 확인

int getLength();	// 리스트의 길이 리턴

Buffer* getHead();	// 리스트의 헤드 리턴

void insert(Buffer* newBuffer);  // 리스트 추가

void delete(int delNum);         // 리스트 삭제

private:

Buffer* head;

int length;

};

버퍼의 프리 리스트

커널은 LRU(Least Recently Used) 알고리즘에 의해 버퍼들을 연결한 프리 리스트를 보관한다.

프리 리스트는 앞부분에서 버퍼를 취하고 리스트에서 제거 후 사용한 버퍼는 끝에 삽입한다.

프리 리스트는 이중 링크드 원형 리스트로 구성된다.

해쉬큐의 버퍼

버퍼의 장치번호와 블록번호를 해슁하여 별도의 큐로 구성되어 있다.

버퍼를 가져오는 5가지 시나리오

커널이 해쉬큐에서 그 블록을 찾아내고 해당 버퍼는 미사용 중이다.

커널이 해쉬큐에서 그 블록을 찾을 수가 없어 프리 리스트에서 버퍼를 할당한다.

커널이 해쉬큐에서 그 블록을 찾을 수 없어 프리 리스트에서 버퍼를(시나리오 2와 같이) 할당하려고 한다. 그러나 그 버퍼가 “지연쓰기”라고 표시되어 있음을 알게 된다. 이 경우 커널은 그 “지연쓰기” 버퍼를 디스크에 저장해야 하고 다른 버퍼를 할당해야 한다.

커널은 해쉬큐에서 그 블록을 찾을 수 없고 프리버퍼가 없다.

커널이 해쉬큐에서 그 블록을 찾는다. 그러나, 그 버퍼를 누군가 현재 액세스하고 있다.

프로그램 요구사항

1. 해쉬큐를 나눌 때 해쉬큐의 크기는 4개 이상이여야 한다.

2. 버퍼해더의 구조는 앞에서 이야기 한 것과 똑 같이 구성할 필요는 없지만 해쉬큐의 다음 버퍼, 해쉬큐의 앞 버퍼, 프리리스트의 앞 그리고 뒤 그리고 프로세스의 상태를 나타내는 부분은 꼭 구성 되어야 함

3. 위의 5가지 시나리오를 테스트 할 것이며 프로세스의 갯 수는 최대 1 ~ 100을 가지고 테스트 할 것이며 해쉬큐의 구조를 보여 줄 것

4. 해쉬큐 해더를 제외한 블록의 최대 크기는 30 이며 프리리스트 해더 또한 30에 포함 된다.

5. 프로세스의 크기는 1로 모두 동일 하며 프로세스의 번호 가 같으면 같은 프로세스로 취급 한다.

6. 출력 화면은 프로세스를 하나 입력 받을 때 마다 해쉬 블록의 상태를 전부 보여 주어야 함 (프리리스트 헤더 및 프리리스트 블록 포함)

7. 프로세스가 죽는 것(프리리스트 헤더로 들어가는 것)은 프로세스를 입력 받은 후 블록 안에 있는 프로세스를 죽일지 말지를 선택 한다.

8. 블록안의 프로세스를 죽일 경우에는 랜덤으로 죽게 된다.

9. 죽은 프로세스는 스스로 살아 나지는 않으며 만약 프리 리스트 헤더에 있는 값을 입력을 받는다면 프로세스가 살아남

개발 환경

Platform : Windows

Dev. Language : C/C++(MFC 사용 권장-Console도 무방함)

제출 마감 기한
05월 14일 (화) 23:59 까지

텀 프로젝트 구성 인원
개인 별

제출 방식
소스와 실행 파일, 문서 파일을 압축하여 “Term02_학번_이름”으로 메일(bkgo@oslab.khu.ac.kr) 로 보냄