2025/06/04 [LAB3] FTL 구현 추가 설명

[kbskbs1102]

안녕하세요 운영체제 조교입니다.

FTL 구현시 고려해야할 사항에 대한 추가 안내입니다.

• Greedy 정책은 invalid 페이지 수가 가장 많은 블록을 victim으로 선택합니다. 만약 invalid 페이지 수가 동일한 블록이 여러 개일 경우, 블록 번호가 가장 작은 블록을 선택합니다.

• GC 수행 시, 새로운 free block을 active block으로 할당한 뒤, victim block에 존재하는 valid 페이지들을 해당 active block으로 먼저 복사합니다. 이후 사용자 요청에 따른 데이터를 그 위치에 이어서 기록합니다.

• 새로 할당된 active block은, write가 실제로 발생하기 전까지는 is_free = true 상태로 유지되며, write가 이루어지는 시점에 is_free = false로 전환됩니다.

• active block이 가득 찬 경우에는 0번 블록부터 순차적으로 탐색하여 가장 먼저 발견되는 free block을 새로운 active block으로 할당합니다.

• 모든 페이지가 valid하여 GC를 수행하더라도 유효하지 않은 페이지가 없어 공간을 회수할 수 없는 경우에는, 오류 메시지를 출력하도록 처리하시기 바랍니다. 단, 과제에 제공된 워크로드에서는 해당 상황이 발생하지 않을 수 있습니다.

• GC 중 새로 할당된 active block에 남은 공간이 존재할 경우, 해당 블록은 이후 write 시에 계속해서 사용할 수 있습니다. 별도의 처리는 필요하지 않습니다.

• GC 수행 시에는 현재 active block도 victim block 탐색 대상에 포함됩니다. 단, GC 도중 active block이 변경되기 전까지는 기존 active block 상태를 유지해야 합니다.

구현하시는데 참고가 되기를 바라며, 추가적인 문의가 있을 경우 언제든지 연락주시기 바랍니다.
감사합니다.

[psmsq4]

조교님, 이 명세대로면

만약 현재 free block이 A, B, C가 있고 그 중 A가 active block이라고 가정하고,
A block에 page 하나를 write하면 not free 상태가 되며, 다음 write일 때 free block이 2개 이하이므로 gc가 trigger 됩니다.
(A에는 현재 1 VALID | 3 FREE)
gc에서 victim block을 찾은 다음 A block이 아닌 새로운 free block을(B라고 가정) active block으로 할당하고 복사하는게 맞나요? 현재 A block에는 한 개의 page 밖에 쓰지 않은 상태인데 free block을 새로 할당한다는게 맞는지 모르겠습니다. A에 아직 3개의 FREE 공간이 남아있으니 여기에 복사해야 하는 것이 아닌가요?

그리고 active block이 가득 찬 경우 0번 블록부터 순차적으로 탐색하여 가장 먼저 발견되는 free block이 active block이 된다고 하셨는데, 하필이면 직전에 GC된 Free Block이 선택되어 active block으로 할당해도 문제가 없는건가요?
그리고 이 탐색 방법이 GC에서 새로운 free block을 할당할 때에도 동일하게 적용되는지도 궁금합니다.

저번에 설명해주실 때에는 "ftl 낸드 랜드플래시의 특성상 write 포인터는 계속 뒤로 가기 때문에 끝번을 찍고 다시 앞으로 갑니다."라고 하셔서 0번 부터 탐색한다는게 조금 혼동이 됩니다. free block 탐색은 현재 active block에서 9번 block을 찍은 후 0번 block부터 재 탐색하는 원형큐 처럼 탐색해야 하는 것 아닌가요?

[yeojin5]

@psmsq4

GC를 실행할지 조건을 검색하는 시간은 새로운 free 블록을 할당 받을 때 입니다. 따라서 예시로 들어주신 시나리오로 설명을 드리자면 A 블록에 1번의 write 후 GC가 트리거 되는 것이 아닌 A 블록의 모든 페이지가 write 된 이후 새로운 free 블록을 할당 받으려 할때 남은 블록이 B, C 2개 이므로 이때 GC가 트리거 됩니다.

이전에 erase 된 블록이 active 블록으로 선택될 수 있습니다. 하지만 GC하는 동안 valid 한 페이지를 동일한 블록으로 옮기는 것은 적절하지 않은 것 같습니다.(A 블록이 GC되고 valid 한 페이지 1개를 옮겨야하는데, A 블록을 지우고 다시 쓰는건 안된다는 의미)

네, GC시 valid 한 페이지를 옮기기 위해 Free 블록을 찾을 때도 동일하게 찾을 수 있습니다.

또한 실제 SSD에서는 write pointer가 계속 뒤로가는 (append 형식)이므로 끝번을 찍고 다시 앞으로 가는것이 맞습니다. 하지만 저희 시뮬레이터에서는 학생분들의 구현의 편의성을 위해 0번 블록부터 순차적으로 free block을 선택하는 것으로 Issue에 안내드렸습니다.

저희 1분반에서는 실제 SSD의 write pointer처럼 구현하셔도 정답처리하도록 하겠습니다. (tester의 패스 유무에 관계 없이)

감사합니다.

[KANG8369]

조교님 ppt의 조건에 따르면 valid한 block이 2개 이하일 때와 free block이 2개 이하일 때 GC가 발생한다고 나와있는데 valid page가 2개 이하일 때가 아니라 valid한 block이 2개 이하일 때가 맞는 걸까요?

[yeojin5]

조교님 ppt의 조건에 따르면 valid한 block이 2개 이하일 때와 free block이 2개 이하일 때 GC가 발생한다고 나와있는데 valid page가 2개 이하일 때가 아니라 valid한 block이 2개 이하일 때가 맞는 걸까요?

GC 조건은 Free Block이 2개 이하일때입니다. page는 GC 조건과 무관합니다.

[KANG8369]

• Valid한 block이 2개 이하면, Garbage Collection을 실행한다.
  ppt의 요구 사항에는 이렇게 적혀있는데 맞는걸까요.

[yeojin5]

• Valid한 block이 2개 이하면, Garbage Collection을 실행한다.
  ppt의 요구 사항에는 이렇게 적혀있는데 맞는걸까요.

혹시 PPT의 어느 부분에 적혀있는지 알 수 있을까요?
PPT의 Project Requirement에 Free block 이 2개 이하면 GC를 실행한다고 설명되어있습니다.

이 페이지를 기준으로 구현하시면 됩니다.
즉, Valid 한 block이 2개 이하 -> 틀린 조건
Free block (모든 page가 비어있는)이 2개 이하 -> 옳은 조건
입니다.

감사합니다.

[KANG8369]

같은 페이지인데 제가 다운 받은 Lab3 안내 파일이 수정되기 이전의 파일이였던 거 같습니다.

[yeojin5]

같은 페이지인데 제가 다운 받은 Lab3 안내 파일이 수정되기 이전의 파일이였던 거 같습니다.

죄송합니다. 재차 확인해보니, github 공개 버전 pdf에 Free block으로 안내되어있지 않았습니다.
따라서 Lab3 PPT를 수정하여 다시 올려드리겠습니다.

알려주어 감사합니다.

[KANG8369]

넵 알겠습니다.
그리고 추가적으로 문제 풀이 같은 경우에 GC가 일어나는 과정을 그림으로 설명하시오인데 이 문제 같은 경우에는 처음 GC가 일어날 때 발생하는 상황을 설명하면 되는 것이 맞을까요.

[yeojin5]

넵 알겠습니다.
그리고 추가적으로 문제 풀이 같은 경우에 GC가 일어나는 과정을 그림으로 설명하시오인데 이 문제 같은 경우에는 처음 GC가 일어날 때 발생하는 상황을 설명하면 되는 것이 맞을까요.

네 맞습니다.