플래시 메모리를 기반으로 한 SSD(Solid State Drive)는 반도체를 이용하여 정보를 저장하는 장치이다.
SSD에 파일을 쓰기, 삭제, 읽기, 수정하는 프로그램을 구현하고자 한다.
주어지는 SSD는 N개(9 ≤ N ≤ 256)의 block으로 구성되며 하나의 블록은 M개(6 ≤ M ≤ 256)의 page로 구성된다.
SSD는 기록하는 경우 page 단위로 기록되지만, 지우고자 하는 경우 block 단위로 삭제된다.
따라서 한 블록에 A, B 두 종류의 데이터가 있을 때 A를 삭제하려면 B를 다른 block에 복사하고 A를 포함하는 block을 삭제해야 한다.
그런데 block을 삭제하는 것은 SSD의 수명을 단축시킨다고 한다.
이로 인해 A를 삭제할 때 바로 삭제하는 것이 아니라 삭제된 데이터라고 분류만 하고(이를 garbage화 라고 한다)
빈 공간이 부족해지는 경우에 garbage화 된 것이 많은 block의 내용을 삭제하여 초기화 한 후에 재사용한다.
[제약사항]
1. 함수의 호출은 최대 12,800번까지 가능하다.
2. 파일은 fid(파일 id)로 구분되어 주어지며 한 파일의 크기는 2 * M을 넘지 않는다. (두 block보다 크지 않다)
3. fid는 최대 10,000이다.
4. 9 ≤ N ≤ 256, 6 ≤ M ≤ 256
5. 1 <= file_ID <= 10000, 0 <= block_ID <= 255, 0 <= page_ID <= 255
6. 파일의 기록 또는 변경으로 기록되는 유효한 페이지의 개수는 전제 페이지의 2/3를 넘지 않도록 주어진다.
[아래 API설명을 참조하여 각 함수를 완성하시오]
1. void init(int blocks, int pages): 초기화 하기
: SSD의 페이지 크기와 블럭의 크기가 주어진다.
2. void writeFile(int fid, int len, int arr[]): 기록하기
: fid-파일의 고유 ID, len-파일을 구성하는 페이지 수, arr[]에 len개의 수가 들어있다.
: 위 파일을 SSD의 비어있는 공간에 할당한다.(garbage 공간에 할당 할 수 없다.)
3. void modifyFile(int fid, int len, int arr[]): 수정하기
: fid파일이 없다면 아무일도 하지 않는다.
: 기존의 fid공간을 garbage화 해준다.
: free(비어있는)인 공간에 새롭게 주어진 len길이의 arr[]을 기록한다.
4. void removeFile(int fid): 삭제하기
: fid파일이 없다면 아무일도 하지 않는다.
: fid에 해당하는 공간을 garbage화 해준다.
5. int readFile(int fid, int bid[], int pid[]): 검색하여 읽기
: fid파일이 없다면 아무일도 하지 않는다.
: fid파일이 기록되어 있는 각 block위치를 bid[]에, 각 page위치를 pid[]에 기록한다.
입력이나 수정에서 주어진 순서대로 위치를 기록한다.
: bid[], pid[]에 기록한 길이를 반환한다.
ex) fid==1, len==5 인 파일이 (0,0), (0,1), (0,2),(0,3),(0,4) (블록,페이지) 일때
bid[] = [0,0,0,0,0], pid[]=[0,1,2,3,4] 가 된다.
※ 주의사항 ※
: 이 함수가 호출된 상태에서는 main.cpp의 writePage()함수를 호출할 수 없음에 유의한다.
: 그렇지 않은 경우 0점 처리된다.
[main 코드의 함수]
//*** main.cpp을 분석하여 main.cpp의 함수를 적절히 사용해야 한다.
1. int readPage(int blockid, int pageid)
: main.cpp의 ssd[blockid][pageid]에 저장해놓은 값을 반환한다.
2. void writeFile(int blockid, int pageid, int data)
: main.cpp의 ssd[blockid][pageid]에 값을 저장한다.
3. void removeBlock(int blockid)
: main.cpp의 ssd[blockid]의 내용을 삭제하고 초기화 하여 free한 상태로 만든다.
※ 주의사항 ※
: user.cpp의 함수가 한 번 호출될 때 user는 removeBlock(int) 함수를 16번 이하로만 호출할 수 있다.
: main.cpp의 removeBlock(int)정의를 참조한다.
★ template code는 아래 힌트란에 주어져 있다. ★
[입력형식]
첫 행에 테스트 케이스의 수와 초기 점수가 입력된다.
이후 자세한 입출력은 아래에 제시된 main.cpp를 참조한다.
[출력형식]
사용자는 user.cpp의 api함수를 완성하여 제출한다.
[입력예]
1 100
111 9 6 14 100 256
100 1 3 272
100 2 5 213
100 3 8 462
100 4 4 49
300 4
200 2 4 72
100 5 7 257
200 1 5 138
300 1
100 6 6 492
400 5 7
200 6 6 77
100 7 7 392
400 3 8
[출력 예]
#1 100
[Hint]
//*** user.cpp ***
const int FILESIZE = 512;
extern int readPage(int blockid, int pageid);
extern void writePage(int blockid, int pageid, int data);
extern int removeBlock(int blockid);
void init(int blocks, int pages){
}
void writeFile(int fid, int len, int arr[FILESIZE]){
}
void removeFile(int fileid){
}
void modifyFile(int fileid, int len, int arr[FILESIZE]){
}
int readFile(int id, int bids[FILESIZE], int pids[FILESIZE]){
return 0;
}
//*** main.cpp ***
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <stdio.h>
#define WRITE 100
#define MODIFY 200
#define DELETE 300
#define READ 400
#define POOL_SIZE 100000
#define MAX_FILE_ID 10000
#define MAX_BLOCK 256
#define MAX_PAGE 256
#define MAX_FILE_SIZE 512
extern void init(int blocks, int pages);
extern void writeFile(int fid, int len, int arr[MAX_FILE_SIZE]);
extern void removeFile(int fileid);
extern void modifyFile(int fileid, int len, int arr[MAX_FILE_SIZE]);
extern int readFile(int id, int bids[MAX_FILE_SIZE], int pids[MAX_FILE_SIZE]);
static int ssd[MAX_BLOCK][MAX_PAGE];
static int written[MAX_BLOCK][MAX_PAGE];
static int erase_cnt = 0;
static int ing_read_file = 0;
static int score;
static int poolsize = POOL_SIZE;
static int filepool[POOL_SIZE];
static int file[MAX_FILE_ID + 1][MAX_FILE_SIZE];
static int nblock, npage, maxcall;
int readPage(int blockid, int pageid)
{
if (blockid < 0 || blockid >= nblock || pageid < 0 || pageid >= npage) {
score = 0;
return 0;
}
return ssd[blockid][pageid];
}
void writePage(int blockid, int pageid, int data)
{
if (blockid < 0 || blockid >= nblock || pageid < 0 || pageid >= npage
|| written[blockid][pageid] == 1 || ing_read_file > 0) {
score = 0;
return;
}
written[blockid][pageid] = 1;
ssd[blockid][pageid] = data;
}
int removeBlock(int blockid)
{
++erase_cnt;
if (blockid < 0 || blockid >= nblock || erase_cnt > 16) {
score = 0;
return erase_cnt;
}
for (register int i = 0; i < npage; ++i)
ssd[blockid][i] = written[blockid][i] = 0;
return erase_cnt;
}
static unsigned int seed = 1;
static int pseudo_rand(void)
{
seed = seed * 0x343fd + 0x269ec3;
return (seed / 16) & 0x00ffffff;
}
static void makeFilePool(int poolopt, int mod)
{
if (poolopt == 0)
return;
poolsize = poolopt == 100 ? 500 : POOL_SIZE;
if (mod > 0) {
for (register int i = 0; i < poolsize; ++i)
filepool[i] = pseudo_rand() % mod;
} else {
for (register int i = 0; i < poolsize; ++i)
filepool[i] = pseudo_rand();
}
}
static void makeFileData(int *data, int size, int offset)
{
for (register int i = 0; i < size; ++i)
data[i] = filepool[offset + i];
}
static void run()
{
for (int i = 0; i < nblock; ++i)
for (int j = 0; j < npage; ++j)
ssd[i][j] = written[i][j] = 0;
int poolopt, mod;
if (scanf("%d %d %d %d %d %d", &seed, &nblock, &npage, &maxcall, &poolopt, &mod) != 6) {
score = 0;
return;
}
init(nblock, npage);
makeFilePool(poolopt, mod);
int cmd, id, size, offset;
int usize;
int data[MAX_FILE_SIZE] = { 0, };
int blockids[MAX_FILE_SIZE] = { 0, };
int pageids[MAX_FILE_SIZE] = { 0, };
for (int call = 0; call < maxcall; ++call) {
erase_cnt = 0;
scanf("%d %d", &cmd, &id);
switch (cmd) {
case WRITE:
scanf("%d %d", &size, &offset);
makeFileData(file[id], size, offset);
for (int idx = 0; idx < size; ++idx)
data[idx] = file[id][idx];
writeFile(id, size, data);
break;
case MODIFY:
scanf("%d %d", &size, &offset);
makeFileData(file[id], size, offset);
for (int idx = 0; idx < size; ++idx)
data[idx] = file[id][idx];
modifyFile(id, size, data);
break;
case DELETE:
removeFile(id);
break;
case READ:
for (register int i = 0; i < npage * 2; i++)
blockids[i] = pageids[i] = 0;
ing_read_file = 1;
usize = readFile(id, blockids, pageids);
ing_read_file = 0;
scanf("%d", &size);
if (size != usize) {
score = 0;
}
else {
for (int i = 0; i < size; ++i)
if (blockids[i] < 0 || blockids[i] >= nblock
|| pageids[i] < 0 || pageids[i] >= npage
|| file[id][i] != ssd[blockids[i]][pageids[i]]) {
score = 0;
break;
}
}
break;
}
}
}
int main()
{
setbuf(stdout, NULL);
freopen("input.txt", "r", stdin);
int T, MARK;
scanf("%d %d", &T, &MARK);
for (int tc = 1; tc <= T; ++tc) {
score = MARK;
run();
printf("#%d %d\n", tc, score);
}
return 0;
}
[풀이]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
|
/** user.cpp***/
const int FILESIZE = 512;
extern int readPage(int blockid, int pageid); //main의 ssd[bi][pi]에 저장해놓은 값을 반환
extern void writePage(int blockid, int pageid, int data); //main의 ssd[bi][pi]에 값을 저장
extern int removeBlock(int blockid); //main의 ssd[bi]의 내용을 삭제하고 초기화하여 free한 상태로 만든다
const int MAXB = 256 + 2;
const int MAXP = 256 + 2;
int N, M;
struct Node
{
int bid, pid;
Node* next;
}buf[FILESIZE * 12800], * ftbl[10005];
int bcnt = 0;
Node* myalloc(int _bid, int _pid, Node* _next)
{
Node* n = &buf[bcnt++];
n->bid = _bid;
n->pid = _pid;
n->next = _next;
return n;
}
struct Page;
struct Block
{
Page* usepage[MAXP + 5];
int uCnt; //유효페이지개수
int gbCnt; //가비지페이지개수
void Addusepage(Page* p)
{
usepage[uCnt++] = p;
}
void Init()
{
uCnt = 0;
gbCnt = 0;
}
}block[MAXB];
struct Page {
int pid;
int bid;
Node* file;
bool isgb;
void Init(int _bid, int _pid) {
file = 0;
bid = _bid;
pid = _pid;
isgb = false;
}
void SetGB() {
isgb = true;
block[bid].gbCnt++;
}
}page[MAXB][MAXP];
int MAXQ = MAXB * MAXP;
Page* queue[MAXB * MAXP + 3];
int sp, ep;
void push(Page* p)
{
queue[ep % MAXQ] = p;
ep++;
}
Page* pop()
{
Page* p = queue[sp % MAXQ];
sp++;
return p;
}
int getUsePageSize() { return ep - sp; }
void init(int pages, int blocks)
{ //초기화하기
N = pages;
M = blocks;
MAXQ = N * M;
bcnt = sp = ep = 0;
for (int i = 1; i <= 10000; i++) ftbl[i] = 0;
for (int i = 0; i < N; i++)
{
block[i].Init();
for (int j = 0; j < M; j++)
{
page[i][j].Init(i, j);
push(&page[i][j]); //유효페이지 푸쉬
}
}
}
void garbageCollect()
{
int maxidx = 0;
for (int i = 0; i < N; i++)
{
if (block[i].gbCnt > block[maxidx].gbCnt) maxidx = i;
}
//유효한 블록에 복사
Block* b = &block[maxidx];
for (int i = 0; i < b->uCnt; i++)
{
Page* p = b->usepage[i];
if (p->isgb) continue;
Page* newPage = pop();
while (newPage->bid == p->bid)
{
push(newPage);
newPage = pop();
}
block[newPage->bid].Addusepage(newPage);
writePage(newPage->bid, newPage->pid, readPage(p->bid, p->pid)); //main api
p->file->bid = newPage->bid;
p->file->pid = newPage->pid;
newPage->file = p->file;
}
//삭제
removeBlock(maxidx);
block[maxidx].Init();
for (int j = 0; j < M; j++)
{
page[maxidx][j].Init(maxidx, j);
push(&page[maxidx][j]);
}
}
void writeFile(int fid, int len, int arr[FILESIZE])
{ //기록하기 , 파일을 ssd의 비어있는 공간에 할당한다. garbage공간에 할당할 수 없다.
for (int i = len - 1; i >= 0; i--) { //파일을 구성하는 페이지 수
Page* p = pop(); //유효페이지 가져오기
block[p->bid].Addusepage(p);
writePage(p->bid, p->pid, arr[i]); //main
ftbl[fid] = myalloc(p->bid, p->pid, ftbl[fid]);
p->file = ftbl[fid];
}
if (getUsePageSize() <= 2 * M) {
garbageCollect();
}
}
void removeFile(int fileid) { //삭제하기
for (Node* n = ftbl[fileid]; n != 0; n = n->next) page[n->bid][n->pid].SetGB(); //fid에 해당하는 공간을 garbage화 해준다.
ftbl[fileid] = 0;
}
void modifyFile(int fileid, int len, int arr[FILESIZE]) { //수정하기
removeFile(fileid);
writeFile(fileid, len, arr);
}
int readFile(int id, int bids[FILESIZE], int pids[FILESIZE])
{
//검색하며 읽기
//fid파일이 기록되어 있는 각 block위치를 bid[]에, 각 page위치를 pid[]에 기록한 길이를 반환
int i = 0;
for (Node* n = ftbl[id]; n != 0; i++, n = n->next)
{
bids[i] = n->bid;
pids[i] = n->pid;
}
return i;
}
|
cs |
'알고리즘 문제풀이' 카테고리의 다른 글
| [Heap]중앙값관련 Problem Solving (0) | 2020.10.08 |
|---|---|
| [CS] Merge Sort (0) | 2020.10.07 |
| [CS] Quick Sort (0) | 2020.10.07 |
| [CS] Stack, Queue (Heap기반) (0) | 2020.10.07 |
| [CS] Stack, Queue(Linear, Circular) (0) | 2020.10.07 |