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

<Implementation of MVT Memory Management>

프로그램 설명

이 과제는 MVT(Multiprogramming with Variable number of Tasks) 모델을 기반으로 두 개의 메모리 할당 전략(Best Fit와 Worst Fit)을 시뮬레이션 하는 프로그램이다.

이 프로그램은 두 가지의 기능을 갖고 있어야 한다.

첫째로, 두 개의 메모리 블록이 free 상태일 때 서로 인접한 메모리를 병합할 수 있어야 한다.

둘째로, 메모리 요청이 있을 때 비어있는 메모리 블록이 없을 경우, 띄엄띄엄 떨어져 있는 비어 있는 메모리 블록을 합칠 수 있어야 한다.

2. 입력

이 프로그램의 입력은 간단하다. 첫 번째 줄은 실제 메모리 크기를 KB 단위의 정수로 입력하는 것이다. 그 다음의 입력값들은 메모리 요청에 따른 정수의 2개 묶음이다. 2개 묶음 중 첫 번째 정수는 요청 id이고, 두 번째는 요청된 메모리(KB단위)이다. 만약 요청된 메모리 크기가 0이라면, 이전에 같은 id에 할당되었던 메모리를 해제하라는 뜻이다. 하나의 id에 이미 메모리 요청을 하였다면, 또 다시 똑같은 id에 메모리 요청을 할 수 없다. 즉, 먼저 해제를 해야 다시 요청이 가능하다. 이 과제에서는 Best Fit만 구현한다.

<예제 1>

간단한 예로, 다음과 같이 입력을 한다:

256

1 64 2 64 3 32 4 16 1 0 3 0 5 32 2 0

이 프로그램은 아래와 같은 출력을 나타내야 한다.

3. 출력

Memory size : 256K

Request 1 : 64K

Best Fit : Allocated at address 0K

192K free, 1 block(s), average size = 192K

Worst Fit : Allocated at address 0K

192K free, 1 block(s), average size = 192K

Request 2 : 64K

Best Fit : Allocated at address 64K

128K free, 1 block(s), average size = 128K

Worst Fit : Allocated at address 64K

128K free, 1 block(s), average size = 128K

Request 3 : 32K

Best Fit : Allocated at address 128K

96K free, 1 block(s), average size = 96K

Worst Fit : Allocated at address 128K

96K free, 1 block(s), average size = 96K

Request 4 : 16K

Best Fit : Allocated at address 160K

80K free, 1 block(s), average size = 80K

Worst Fit : Allocated at address 160K

80K free, 1 block(s), average size = 80K

Free Request 1 (64K)

Best Fit : Freed at address 0K

144K free, 2 block(s), average size = 72K

Worst Fit : Freed at address 0K

144K free, 2 block(s), average size = 72K

Free Request 3 (32K)

Best Fit : Freed at address 128K

176K free, 3 block(s), average size = 59K

Worst Fit : Freed at address 128K

176K free, 3 block(s), average size = 59K

Request 5 : 32K

Best Fit : Allocated at address 128K

144K free, 2 block(s), average size = 72K

Worst Fit : Allocated at address 176K

144K free, 3 block(s), average size = 48K

Free Request 2 (64K)

Best Fit : Freed at address 64K

Coalescing blocks at address 0K and 64K

208K free, 2 block(s), average size = 104K

Worst Fit : Freed at address 64K

Coalescing blocks at address 64K and 128K

Coalescing blocks at address 0K and 64K

208K free, 2 block(s), average size = 104K

4. 개발 환경

a. Platform : Windows

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

5. 제출 마감 기한

- 6월 14일 (화) 13:00까지

6. 인원

- 개인별

7. 제출 방식

- 소스와 실행 파일, 문서 파일을 압축하여 “Homework4_학번_이름”으로 ftp://163.180.116.80 (ID :　os, PW : ospw)의 "Homework 4" 폴더에 업로드

2011 Spring OS Homework #4

<Implementation of MVT Memory Management>

Program explanation

For this assignment, you are to write a program which simulate two memory allocation strategies under the MVT (Multiprogramming with Variable number of Tasks) model : Best Fit and Worst Fit. These are described briefly in the textbook and references. This assignment is intended to give you more insight and understanding in two particular ares : First, the operation of storage placement algorithms; Second, the implementation of Operating System’s software. In addition, of course, this assignment should sharpen your valuable programming skills.

In addition to the straight-forward implementation of these algorithms, your program implement coalescence of adjacent free memory blocks (which is possible whenever a memory block is freed) and compaction of fragmented memory (which is done whenever no free block is of sufficient size to fulfill a request). Of course, there may be occasions when a request cannot be fulfilled, even memory if has been compacted.

Finally, your program must print a nicely formatted, readable summary of the memory allocation activity for each strategy at the time of each request. In particular, your program must report the address of each memory allocation, the address of each memory block freed, the coalescing activity, the compaction activity, and the result of each memory request. At the conclusion of each memory allocation/free request, you must also print a summary consisting of the total number of bytes free, the number of contiguous blocks free, and the average size of these blocks (this is easy : just divide the number of free bytes the number of free blocks).

2. Input

The input to this program is simple : the first line contains an integer giving the size of real memory in kilobytes. Following this are pairs of integers describing memory requests. The first integer in the pair is a request id, the second is the amount (in kilobytes) of memory requested. If that amount is zero, then the request is to free memory previously requested under the same request id. No request id will request additional memory (i.e. a request id N for S kilobytes cannot be followed later by a request id N for any non-zero kilobytes). For simple implementation, we just implement Best bit only in this assignment.

<Example 1>

As a short example, consider the following input:

256

1 64 2 64 3 32 4 16 1 0 3 0 5 32 2 0

This should produce output similar to the following

3. Output

Memory size : 256K

Request 1 : 64K

Best Fit : Allocated at address 0K

192K free, 1 block(s), average size = 192K

Request 2 : 64K

Best Fit : Allocated at address 64K

128K free, 1 block(s), average size = 128K

Request 3 : 32K

Best Fit : Allocated at address 128K

96K free, 1 block(s), average size = 96K

Request 4 : 16K

Best Fit : Allocated at address 160K

80K free, 1 block(s), average size = 80K

Free Request 1 (64K)

Best Fit : Freed at address 0K

144K free, 2 block(s), average size = 72K

Worst Fit : Freed at address 0K

144K free, 2 block(s), average size = 72K

Free Request 3 (32K)

Best Fit : Freed at address 128K

176K free, 3 block(s), average size = 59K

Request 5 : 32K

Best Fit : Allocated at address 128K

144K free, 2 block(s), average size = 72K

Free Request 2 (64K)

Best Fit : Freed at address 64K

Coalescing blocks at address 0K and 64K

208K free, 2 block(s), average size = 104K

4. Developing environment

a. Platform : Windows

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

5. Due date

- June 14th (TUE) 13:00

6. The number of people

- by individual

7. How to submit

- Compress the source file and the execution file like "Homework4_studentID_Name" and upload it to folder “Homework 4” in ftp://163.180.116.80 (ID :　os, PW : ospw)