2011년도 운영체제 1학기 프로그램 과제 #1

- 버퍼캐쉬 구현 -

1. 프로그램의 목적

커널이 어떻게 버퍼캐쉬에 접근하고 관리하는지에 대한 시나리오를 구현함으로써 버퍼 캐쉬에 대한 내용을 이해하고 숙지한다.

2. 버퍼캐쉬 기본개념

커널은 모든 파일을 직접 디스크에서 읽고 쓸 수 있으나, 디스크의 느린 데이터 전송 속도 때문에 시스템의 응답시간과 처리능력이 나빠진다. 따라서, 커널은 최근 사용된 디스크ㅡ 블록의 데이터를 유지하는 공통의 내부 데이터 버퍼(이것을 버퍼캐쉬라 한다)를 관리하여 디스크 액세스를 최소화한다. 커널의 버퍼캐쉬 모듈은 파일 서브시스템과 블록단위의 장치 드라이버 사이에 위치하고 있다.

커널이 디스크에서 데이터를 읽으려 할 때 우선 버퍼캐쉬에서 읽으려고 시도하고, 만일 데이터가 캐쉬 속에 있으면 그대로 읽게 되고, 없을 경우 커널은 디스크에서 데이터를 읽어 될 수 있는 대로 유익한 데이터를 보관하려는 알고리즘에 따라 캐쉬에 저장한다. 디스크에 쓰려고 하는 데이터의 경우도 나중에 커널이 그것을 이용할 경우를 대비하여 캐쉬에 저장해 둔다.

3. 버퍼 할당 알고리즘 (getblk)

- 입력 : 파일 시스템 번호, 블록 번호

- 출력 : 블록에 사용할 수 있는 로크된 버퍼

while (버퍼를 찾지 못한다)

{

if (블록이 해쉬대기행렬에 있다)

{

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

{

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

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

}

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

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

return (버퍼);

}

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

{

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

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

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

}

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

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

{

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

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

}

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

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

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

return (버퍼);

}

}

}

4. 버퍼 반환 알고리즘 (brelse)

- 입력 : 로크된 버퍼

- 출력 : 없음

{

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

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

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

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

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

else

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

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

unlock(버퍼);

}

5. 버퍼헤드의 구조

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

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

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

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;

};

6. 버퍼의 프리 리스트

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

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

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

7. 해쉬큐의 버퍼

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

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

#1) 시나리오 1

- 커널이 해쉬큐에서 그 블록을 찾아내고 해당 버퍼는 미사용 중이다 (예: 커널이 해쉬큐에도 있고, 프리리스트에도 있는 블록 4를 요구).

#2) 시나리오 2

- 커널이 해쉬큐에서 그 블록을 찾을 수가 없어 프리 리스트에서 버퍼를 할당한다 (예: 커널이 버퍼캐쉬에 없는 블록 18을 요구, 이 경우 프리리스트는 empty가 아니다)

#3) 시나리오 3

- 커널이 해쉬큐에서 그 블록을 찾을 수 없어 프리 리스트에서 버퍼를(시나리오 2와 같이) 할당하려고 한다. 그러나 그 버퍼가 “지연쓰기 (delay writing)”라고 표시되어 있음을 알게 된다.이 경우 커널은 그 “지연쓰기” 버퍼를 디스크에 저장해야 하고 다른 버퍼를 할당해야 한다 (예: 커널이 버퍼캐쉬에 없는 블록 18을 요구, 이 경우 프리리스트는 empty가 아니지만, 프리리스트의 블록 3과 블록 5가 지연쓰기를 하고 있는 경우)

#4) 시나리오 4

- 커널은 해쉬큐에서 그 블록을 찾을 수 없고 프리버퍼가 없다(예: 커널이 버퍼캐쉬에 없는 블록 18을 요구, 이 경우 프리리스트는 empty 이다. 이때 임의의 프로세스가 사용이 끝난 블록을 프리리스트에 연결(버퍼 반환 알고리즘 (brelse) 구현)하면 다시 구동 된다)

#5) 시나리오 5

- 커널이 해쉬큐에서 그 블록을 찾는다. 그러나, 그 버퍼를 누군가 현재 액세스하고 있다. (예: 커널이 누군가가 현재 사용중인 블록 99를 요구하였는데, 이 경우 프리리스트는 empty가 아니다. 시나라오 5는 여러 가지 복잡한 상황을 고려해야 되나, 본 프로그램 숙제에서는 구현의 단순화를 위하여 일정시간 Sleep한 뒤 액세스 하고 있던 프로세스가 종료되었다고 가정하고, 블록 99를 재사용 한다)

9. 프로그램 요구사항

- 버퍼 할당 알고리즘 (getblk)을 구현한다. 요청되는 블록 번호는 랜덤으로 한다.

- 버퍼 반환 알고리즘 (brelse)은 본 과제에서는 실제 구현은 안한다. 그러나 brelse 알고리즘이 호출되어 사용이 종료된 블록은 프리리스트로 반환된다고 가정한다.

- Busy, Sleep, Delay writing에 소요되는 시간은 5초 미만으로 가정하고, 구현 시 시스템 timer를 사용한다.

- 버퍼캐쉬내에 총 가용 블록의 갯수는 20개 이상 200개 미만으로, 블록번호는 1부터 500번을 사용하며, 해쉬함수는 (블록 번호 MOD 5) 또는 (블록 번호 MOD 7)을 사용한다

- 기타사항은 구현 시 합리적인 내용으로 명시적 가정하고 구현을 하면 이를 허용한다.

10. 개발 환경

a. Platform : Windows

b. 개발언어 : C, C++(MFC 사용 권장-Console도 무방함) 또는 Java

11. 제출 마감 기한 및 방식

- Term Project 각 팀 단위로 4월 27일 (수) 13:00 까지

- 소스와 실행 파일, 문서 파일을 압축하여 “HW1_몇조”으로 ftp://163.180.116.80

(ID :　os, PW : ospw)의 "OS_Homework 1" 폴더에 업로드

2011 OS Homework #1

- Buffer Cache -

1. Goal

Understand about buffer cache that how kernel access to it and manage it by implementing the scenarios.

2. Basic concept of Buffer Cache

Kernel can read and write all the files directly into the disk. But because of the slow data transfer speed, the system's response time and throughput may deteriorate. So, kernel manages a common internal buffer(this is called a Buffer Cache) which maintains recently used disk block's data to minimize the disk access. Kernel's Buffer Cache module is located between file subsystem and device driver composed of blocks.

Kernel first tries to read the data on buffer cache, and if the data is in the cache, it just reads it. But if there isn't, kernel reads the data from the disk and uses a best algorithm to store useful data in the cache. Data which will be written to disk will also be stored in the cache to prepare for the kernel to read it.

3. Buffer allocation algorithm (getblk)

- input : file system number, block number

- output : locked buffer which could be used for block

while (buffer is not found)

{

if (block in hash queue)

{

if (buffer is busy)  // scenario 5

{

sleep (event buffer becomes free);

continue;     // go back to while loop

}

mark the buffer as busy   // scenario 1

remove the buffer from free list;

return (buffer);

}

else   // block not in the hash waiting lin

{

if (buffer is not in the free list)  // scenario 4

sleep (event any buffer becomes free);

continue;  // go back to while loop

}

remove the buffer from free list;

if (buffer marked for delayed write)  // scenario 3

{

asynchronous write buffer to disk;

continue;  // go back to while loop

}

// scenario 2 - found a free buffer

remove buffer from old hash queue;

put buffer onto new hash queue;

return (buffer);

}

}

}

4. buffer return algorithm (brelse)

- input : locked buffer

- output : none

{

wakeup all processes: event, waiting for any buffer to become free;

wakeup all processes: event, waiting for this buffer to become free;

raise processor execution level to block interrupts;

if (buffer contents valid and buffer not old)

enqueue buffer at end of free list;

else

enqueue buffer at beginning of free list;

lower processor execution level to allow interrupts;

unlock(buffer);

}

5. Structure of buffer head

- Buffer is composed of genuine data field and buffer header

- Distinguish inherent buffer by device number and block number

- Buffer head data structure.

struct Buffer{

int DeviceNum;             // Device number

int blkno;	// Block number

char* data;	// Pointer of data field

int stateFree;	// Buffer status

int stateBusy;	// Buffer status

int stateDelay;	// Buffer status

int stateWrite;	// Buffer status

Buffer* queuePrev;	// Front buffer of hash queue

Buffer* queueNext;	// Next buffer of hash queue

Buffer* freeListPrev;      // Front buffer of free list

Buffer* freeListNext;      // Next buffer of free list

};

- Hash queue data structure.

class CQueue{

public:

CQueue();

~CQueue();

void MakeEmpty();       // Delete all queue

bool IsEmpty();	// Check queue is empty

bool IsFull();	// Check quqeue is full

void Enqueue(Buffer* newbuf);  // Insert queue

void Dequeue();	// Delete queue

Buffer* GetFront();	// Retrun fisrt block of queue

private:

Buffer* front;

};

- Free list data structure.

class FreeList{

public:

FreeList(void);

~FreeList(void);

void MakeEmpty();	// Delete all list

bool IsEmpty();	// Check list is empty

bool IsFull();	// Check list is full

int GetLength();	// Return list length

Buffer* GetHead();	// Return head of list

void Insert(Buffer* newBuffer);  // Insert list

void Delete(int delNum);         // Delete list

private:

Buffer* Head;

int Length;

};

6. Free list of buffer

- Kernel uses LRU (Least Recently Used) algorithm to link the buffers maintaining in the free list

- Free list uses the buffer in the front and delete it. It inserts a buffer from the back.

- Free list is made up of double linked circuit list.

7. Buffer of hash queue

- Hashing buffer's device number and block number separately in queue.

8. 5 Scenarios getting buffer

#1) Scenario 1

- Kernel finds the block in the hash queue and it is free. (Ex: Kernel requests  block 4 which is in both hash queue and free list).

#2) Scenario 2

- Kernel allocates the buffer from the free list because of the kernel cannot find the block in the hash queue (Ex: Kernel requests block 18 which is not in the buffer cache. Free list is not empty)

#3) Scenario 3

- Kernel is trying to use the buffer from free list because the requested block is not in the hash queue. (Just like scenario 2). But the buffer is marked for delay writing. In this case, kernel should store this buffer to a disk and allocate another buffer. (Ex : Kernel requests block 18 which is not in the buffer cache. In this case, free buffer is not empty, but block 3 and 5 are marked as delay writing.

#4) Scenario 4

- Kernel cannot find the block in hash queue and there is no buffer in the free list. (Ex: Kernel requests the block 18 which is not the buffer cache. And the free list is empty. If one process terminates and return the buffer to the free list, it will work on.

#5) Scenario 5

- Kernel searches a block in hash queue. But the buffer is busy. (Ex: Kernel requests block 99 which is busy, and the free list is no empty. For simplification, sleep for a while and then let the process using block 99 is finished. And then use the block 99 when released)

9. Program requirement

- Realize buffer allocation algorithm (getblk). Set the block number as random.

- Buffer return algorithm (brelse) is not actually realized in this homework. Assume the brelse algorithm is called and the block which is finished using will be returned to free list.

- The time spent in Busy, Sleep, Delay writing should be under 5 sec. Use the timer to program.

- Total number of block should be minimum from 20 to maximum 200. Block number should be 1 to 500. Hash function should have 5 or 7 blocks.

- Other elements are up to you. Data structure suggested is not the correct answer. You may change as you wish.

10. Developing environment

a. Platform : Windows

b. Language : C, C++(MFC , Console) or Java

11. Due date and submission

- Term Project team April 27th (WED) 13:00

- Zip the Source file, execution file, and document file like “HW1_which team” and upload it to foler "OS_Homework 1" ftp://163.180.116.80 (ID :　os, PW : ospw)