42구현 문제
FIFO 항목을 들어온 순서대로 꺼내기
1. 문제와 수정 범위
ByteQueue.deq는 가장 오래된 바이트를 반환하고, 바로 그 항목을 하나의 원자적 동작
안에서 제거해야 합니다. starter는 noAction을 실행하고 0을 반환합니다. 큐가 줄지
않으므로 공개 실행은 12와 34 대신 first = 00, second = 00을 출력합니다.
기존 FIFO의 method만 써서 deq의 본문을 완성하세요. 인터페이스, enq, 깊이 2,
mkTop은 그대로 둡니다. 큐 내용을 따로 복사해 두는 레지스터도 추가하지 않습니다.
2. starter 읽기와 실행 전 예측
ByteQueue인터페이스를 읽어 보세요.deq는ActionValue method이므로 한 번의 호출에서 상태를 바꾸고 값을 반환합니다.- 내부의
FIFO#(Bit#(8))을 읽어 보세요.FIFO인터페이스는 맨 앞 항목을 보는 동작과 제거하는 동작을 따로 제공합니다. mkTop을step별로 따라가 보세요. 서로 다른 사이클에 두 번 넣고 두 번 꺼냅니다.
실행 전에 수정된 설계를 기준으로 다음 표를 채워 보세요.
step | 동작 | 클록 에지 뒤 맨 앞 항목 |
|---|---|---|
| 0 | 12 넣기 | 12 |
| 1 | 34 넣기 | ? |
| 2 | 꺼내기 | ? |
| 3 | 꺼내기 | ? |
3. 최소 수정과 완료 조건
원자적 method 안의 모든 읽기는 동작이 시작될 때의 상태를 보고, 제거는 동작이 반영된
뒤에 효과를 냅니다. 이 규칙을 이용해 반환하는 값과 제거하는 항목이 같은 원소가 되게
하세요. 수정한 뒤 다시 실행하고, 첫 번째 꺼내기가 같은 동작 안에서 12를 제거하는데도
34를 반환하지 않는 이유를 설명해 보세요.
- 호출할 때마다 큐에 남은 가장 오래된 항목을 반환하고 그 항목만 제거합니다.
- 값이 둘보다 많거나 호출을 반복해도 들어온 순서대로 나갑니다.
- 빈 큐에서는
deq가 실행되지 않습니다. 큐 자체의 준비 조건을 그대로 이어받습니다. 12와34를 상수로 출력하면 다른 입력에서 실패합니다.
4. 단계형 힌트
힌트 1: 호출 한 번, 효과 두 개
ActionValue method는 원자적 동작 하나에서 상태 변경과 값 반환을 함께 수행할 수
있습니다. 이 문제에는 두 효과가 모두 필요합니다.
힌트 2: FIFO method 두 개
한 FIFO method는 아무것도 바꾸지 않고 맨 앞 항목을 읽고, 다른 method는 맨 앞 항목의
제거를 예약합니다. method 하나 안에서는 둘 다 반영 전 상태를 봅니다.
힌트 3: 본문 안의 순서
제거를 동작 문장으로 호출한 뒤, 읽은 맨 앞 항목을 반환하세요. 제거를 먼저 적어도 반환 식은 클록 에지에서 제거가 반영되기 전의 맨 앞 항목을 읽습니다.
5. 추가 실험
별도 사본에서 큐 깊이를 3으로 늘리고, 서로 다른 값 세 개를 넣은 뒤 모두 꺼내 보세요. 출력될 값을 실행 전에 모두 예측하고, 다음 사이클에 맨 앞 항목을 다시 읽으면 다른 항목이 보이는 이유를 설명해 보세요.