Jump to content
Urch Forums

From Schaum's OS (2)


wood

Recommended Posts

5.14 Given the average size of a process is p, the page size is s, and the size of a page table entry is e, what page size minimizes wasted space due to internal and table fragmentation?

 

Highlight below to see the answer.

 

Since the average number of pages required per process will be p/s, the amount of space required by the page table will be pe/s. The amount of space lost to internal fragmentation is s/2, making the equation for total lost space

Waste = pe/s + s/2

To find the value of s that yields the minimal value, take the first derivative with respect to s and set the resulting equation to zero.

0 = - pe/s^2 + 1/2

Solving for s yields

pe/s^2 = 1/2

s = SQRT(2pe)

Can anyone explain to me why is he summing pe/s and s/2 and calling it the Waste?

Link to comment
Share on other sites

Hey Vinay... I understand that pe/s is the space required byt he page table (average [p/s] times the size of the page table entry [e])!! After that, the explanation lost me... It adds that to s/2 and calls it Waste. I might be missing something really stupid.

 

 

Link to comment
Share on other sites

The last block of every process would be half empty (wasted) on average (think of it as if p mod s has a uniform probability).

 

The "waste" due to the number of table entries occupied by the process is (on average) p/s * e (since the number of blocks = number of entries = p/s).

 

Thus the waste for the process is pe/s + s/2.

 

Wood, that was a good question to recall OS stuff... Thanks!

Link to comment
Share on other sites

Thanks to YOU rafi. I was getting confused with what the question meant by WASTE. Anyway, the book says "table fragmentation is the space lost to storing page table", so it makes perfect sense now. For each process, you'll have pe/s for table fragmentation plus s/2 (average for the last page the process uses).
Link to comment
Share on other sites

the difference: similar to space taken by a single page in a book and space taken by its entry on the the index page.

 

No s/2 is half filled block/page as pointed out by rafi. like galvin says "if process size is independent of page size, we expect internal fragmntation to average one-half page per process", so s/2 is not counted twice.

 

so even if the page in a book occupies half space, it is listed in index and takes space thr leading to wastage.

 

Thanks rafi :-)

 

Thanks wood, this was real good question, forced me to open my book again :-)

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...