Anonymous
Anonymous asked in 電腦與網際網路程式設計 · 2 decades ago

演算法的問題

比較2個程式的取頁失敗次數

假設可用頁框數為2,整數陣列A[1024,1024]分頁大小為1024BYTE一個整數為

4BYTE欄先儲存每欄占4頁

演算法一

for j :=1 to 1024 do

for i :=1 to 1024 do

A[ij] :=0;

演算法二

for i :=1 to 1024 do

for j :=1 to 1024 do

A[ij] :=0;

2 Answers

Rating
  • 2 decades ago
    Favorite Answer

    "取頁失敗" 是 page fault 的意思吧?

    "欄先儲存" 是 column-major 的意思? 這表示同一欄的陣列元素會被放在一起, 像這樣: a[0, 0], a[0, 1], a[0, 2] ... a[0,1023], a[1,0], a[1,1] ... 每欄占 4 頁沒錯。

    演算法一: 最內層迴圏變動的是 row, 因此存取順序是 a[0,0] = 0; a[1,0] = 0; a[2,0] ... 每一次存取都會產生 page fault, 總共要 1024 x 1024 次

    演算法二: 最內層迴圏變動的是 column, 且依序存取, 內層迴圏每跑完一次只會 page fault 4 次, 總共要 1024 x 4 次

    希望沒猜錯。

  • Lv 7
    2 decades ago

    若是column major的話那答案應反過來才對吧?

Still have questions? Get your answers by asking now.