관리자 입니다...

 

해설을 통한 토론이 길어져서 이곳으로 복사해 두겠습니다. ㅎㅎ

 

***************************************************************************

 

7

70

701

201

/

231

230

430

420

423

023

/

/

013

012

/

/

712

702

 

총 14개 / 가장 오래있는 것 자리 교체 

[해설작성자 : 거상 주작섭]

 

7

70

701

012

/

123

230

304

042

423

230

/

/

301

012

/

/

127

270

 

FIFO식으로 다시 작성해봤습니다. 자리교체식으로 보니까 조금 헷갈려서요.

(관리자 입니다. FIFO식으로다시 작성했다는 말은 좀 의미가 안맞는거 같네요. 자리 교체식도 아니구요. 그냥 표현 방식의 차이거나 적용한 자료구조에 따른 알고리즘적 차리 같습니다.

대신에 위에 작성해 주신 숫자들은 일관성 있게 맞기는 합니다.)

 

[추가 해설]

FIFO : 가장 오래 있는 페이지 교체이지 페이지를 밀어버리진 않습니다.

큐와 똑같다고 생각해서 실기 때 그렇게 적으면 틀립니다.

7 70 701 012 / 123 230 304 이렇게 될 수가 없어요

 

+ 자리(페이지)를 교체한다는 거지 자리교체식이 아니고 FIFO 입니다. 이상하게 설명해서 그런가 전혀 다르게 적어놓으셨네요

[해설작성자 : 거상 주작섭]

 

[관리자 입니다.

전공자로써 한말씀 드리자면.

거상 주작섭 님 말씀이 맞습니다.

그리고 해설작성자 이름 없이 올리신 분 설명도 맞습니다.

 

문제에서 FIFO라고 했으므로 선입선출만 정확하게 지키면 페이지 교체 횟수는 정확하게 나옵니다.

다만 어떤 알고리즘으로 FIFO 즉 선입선출을 구성하느냐의 문제일 뿐입니다.

실제로 프로그래밍을 한다면

저는 거상 주작섭님의 알고리즘을 택할꺼 같네요.

페이지 교체 지점을 가르키는 포인터를 P라고 한다면

다음 포인터를 가르킬때

P=P+1

P=P%3 <-- 여기서 %는 몫(MOD) 연산자와 같습니다. 그리고 방번호는 0,1,2 즉 C언어 기준입니다.

이렇게 하면 간단하게 환상형 큐에 가까워 지니깐요.(관점에 따라 다를수 있음)

두개의 해설이 공존하면 어느게 맞는건지 헷깔리실분들이 계실까봐.

 

더 직접적으로 간단하게 설명하면

거상 주작섭님 해설의 숫자 표기 방법은

방번호순입니다.

배열로 보면

a[0], a[2], a[3] 이렇게 무조건 0번부터 출력하는 방식으로 표현된거구요

 

해설작성자 이름 없는 분은

start, end 또는 rear, front를 별도로 구성해서

 

출력순서를 오래된것부터 최근에 들어온 데이터 순서대로 출력해서 보여준것 뿐입니다.

 

결론 

거상 주작섭님 출력방식은 절대적인 방번호 0, 1, 2 번 순으로 출력

해설작성자 이름 없는분은 오래된 데이터 부터 최근 데이터 순서 이렇게 생각하고 보시면

두분 해설이 모두 이해가 가실껍니다.

 

일단 두 해설이 모두 맞다는걸 알려 드리고자 주저리 주저리 적어 봤습니다.

열공하세요.]

 

자유게시판에 글 적었었는데 안보셔서 제가 궁금해서 여기다가 질문하는점 죄송합니다.

관리자님 해석 보고 제 생각이 틀렸다는 점은 어느정도 알겠으나 완전하지가 않아 질문드립니다.

 

필기의 경우 부재 횟수를 맞춰라는 문제가 나올 시 위 방법을 써도 된다는 점은 알고 있습니다.

출력 순서를 오래된 것부터 최근에 들어온 데이터 순서대로 출력해서 보여준 것 뿐이라고 하셨는데

앞서 추가해석에 적었다시피 만약 실기 문제에서 페이지 프레임을 모두 적어라라고 했을 경우

"출력순서를 오래된것부터 최근에 들어온 데이터 순서대로 출력해서 보여준것 뿐입니다."

이 말씀처럼 작성자 이름 없으신 분처럼 적는 경우에도 선입선출로 맞다고 인정이 되는지 궁금합니다.

제가 지식이 깊지 못해 페이지 교체 알고리즘에서 선입선출(FIFO) 방식은 가장 오래 있었던 페이지를 교체하는 것으로 알고 있어,

작성자 이름 없으신 분처럼 페이지를 교체하는 것과 동시에 페이지를 모두 앞당기는 것은 아예 다른 방식이라고 생각하여 이렇게 질문합니다.

[해설작성자 : 거상 주작섭]

 

[관리자 입니다. 자유게시판 확인했는데 글을 지우셨는지 안보이네요. ㅎㅎㅎ

그래서 저도 여기다 글을 남기겠습니다.

 

질문 주신 요지는

 

"만약 실기 문제에서 페이지 프레임을 모두 적어라라고 했을 경우" 둘다 맞는건지 질문 주셨는데요..

실기에서 FIFO방식의 페이지 교체 알고리즘이라고만 나왔다면 좀 곤란한 일이 벌어 집니다.

실기는 채점 하는 사람 맘대로라서요 ㅎㅎ

그럼 어느 방식을 따라야 하느냐? 그건 결론에서 말씀 드릴께요.

 

앞서 말씀 드릴때 제가 구분을 정확하게 해드렸어야 하는데 두리뭉실하게 설명을 드려서 혼돈이 있으신가 봅니다.

우선 본 문제는 두분의 해설이 모두 정확하구요... 어차피 답만 나오면 되니깐..

 

근데 왜 제가 두분 답이 다 맞다고 했냐 하면요

 

문제에서 FIFO라고 주어졌을뿐 다른 단서가 없습니다.

 

자료구조를 이야기 할때 큰틀에서는

FIFO, LIFO(FILO) 두가지 정도로 구분을 합니다.

 

근데 FIFO 처리를 위한 알고리즘이 여러가지 존재합니다.

대표적으로 큐, 환상형 큐등이 되겠구요

 

LIFO의 경우는 스택이 되겠네요.

 

문제에서 FIFO만 주여 졌을뿐, 이걸 큐로 하라거나, 환상형 규로 하라거나 하지 않았다는 겁니다.

 

다만!!!!!

 

학문적으로 배우는 일반적인 페이지 교체 알고리즘으로 놓고 본다면 거상 주작섭님 표현이 100% 옳습니다.

 

왜냐하면 페이지 교체 알고리즘이라고만 하면 교체를 위해서 삭제와 삽입 두가지 일을 해야 합니다.

 

근데 학문적으로 배우는 FIFO 페이지 교체 알고리즘이라고 하면 삽입이 곧 삭제의 역할을 하게 됩니다.

실제로는 삭제 동작 자체가 필요 없습니다.

 

왜냐?

 

교체할 페이지를 지우지 말고 교체할 페이지에 최신 데이터를 덮어 써버리면 되니깐요.

 

이게 본 글의 핵심입니다.

 

거상 주작섭님의 표현방식은 아주 아주 아주 정확하게

문제에서 요구하는 FIFO 페이지 교체 알고리즘을 표현하신거구요.(보통 책은 저렇게 설명합니다. 제일 쉬운방법이라서)

 

작성자 이름이 없는 분의 해설은 큐, 환상형 큐 내용을 차용한것으로 생각이 됩니다.(보는 관점에 따라 다름)

 

따라서 실기에서 FIFO라는 단서만 나왔다면

 

저라면 거상 주작섭님의 표현방식을 따를 껍니다.

 

왜냐하면.... 실기는 사람이 채점합니다. 학문적으로 일반적으로 배우는 방식이 아니면

틀렸다고 해버릴 확률이 증가 합니다. 나만 손해죠 ㅎㅎ

 

다만 여기는.... 필기인데다. 교체 횟수만 물었으므로

이 문제에서는 두가지 방식다 유용하지만..

 

다른 변형문제나 실기까지 고려 한다면

거상 주작섭님 해설을 추천 드립니다.

이정도면 답변이 되었을듯 합니다.

추가 의견은 자유게시판으로 부탁 드립니다.]