Worksheet 10/30/2017 1) Given five memory partitions of 100 KB, 500 KB, 200 KB,

Question

Worksheet 10/30/2017 1) Given five memory partitions of 100 KB, 500 KB, 200 KB, 300 KB, and 600 KB (in order), how would each of the first-fit, best-fit, and worst-fit algorithms place processes of 212 KB, 417 KB, 112 KB, and 426 KB (in order)? Which algorithm makes the most effictent use of memory? 2) p. 332. Consider a simple paging system with the following parameters: 2432 bytes of physical memory: page size of 2410 bytes; 2416 pages of logical address space. a. How many bits are in a logical address? b. How many bytes in a frame? c. How many bits in the physical address specify the frame? d. How many entries in the page table?

Explanation / Answer

1) Given, five memory partitions of 100 KB,500 KB,200 KB,300 KB and 600 KB(in order)

First fit

Check for first free partition that is larger to accomodate the request.

212 KB --> Allocates 500 KB partition (since, it is next largest) first,leaving 288 KB.
417 KB --> Allocates 600 KB partition leaving 183 KB
112 KB --> Allocates 288 KB partition leaving 176 KB (allocates 200 KB in our case)
426 KB --> Remaining partition of memory is < 426 KB. No partition is large. So it can't be allocate.

In total 1700 KB used memory is 841 KB (212+417+112). Usage rate = 841/1700 = 0.49

Best fit

Select the nearest size to allocate.

212 KB --> Allocates 300 KB (since it is closest) partition first,leaving 88 KB.
417 KB --> Allocates 500 KB partition leaving 83 KB
112 KB --> Allocates 200 KB partition leaving 88 KB
426 KB --> Allocates 600 KB partition leaving 174 KB

In total 1700 KB used memory is 1267 KB(212+417+112+426). Usage rate = 1267/1700 = 0.74.

Worst fit

It Selects the largest size first to allocate.

212 KB --> Allocates 600 KB (since it is largest) partition first,leaving 388 KB.
417 KB --> Allocates 500 KB partition leaving 83 KB
112 KB --> Allocates 388 KB partition leaving 276 KB (allocates 300 KB in our case)
426 KB --> Remaining partition of memory is < 426 KB. No partition is large. So it can't be allocate.

In total 1700 KB used memory is 841 KB (212+417+112). Usage rate = 841/1700 = 0.49.

So, Based on usage rate Best fit algorithm performance is most efficient.

2) Given,
Physical memory = 2^32 bytes
Page size = 2^10 bytes
Logical address space = 2^16 pages

a) Number of pages = Logical address space / Page size = 2^16 / 2^10 = 2^6

pages = 6
Offset (based on page size) = 10

Number of bits in logical address = 6+10 = 16 bits.

b) Given, Physical memory = 2^32 bytes in which page size is 2^10.
Number of bytes in a frame = 10 bytes and it is same as page size.

c) Number of bits in physical address = 32 (Total physical bits) - offset bits = 32 - 10 = 22 bits.

d) Entries in page table = Number of pages.

Number of pages = Logical address space / Page size = 2^16 / 2^10 = 2^6. i.e, Number of pages = 6.

So, Entries in page table = 6

(16 -10) bits 10 bits Page Number Offset

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.