A certain computer system has the segmented paging architecture for virtual memory. The memory is byte addressable. Both virtual and physical address spaces contain $${2^{16}}$$ bytes each. The virtual address space is divided into $$8$$ non-overlapping equal size segments. The memory management unit $$(MMU)$$ has a hardware segment table, each entry of which contains the physical address of the page table for the segment. Page table are stored in the main memory and consists of $$2$$ byte page table entries.

(a)$$\,\,\,\,\,$$ What is the minimum page size in bytes so that the page table for a segment requires at most one page to store it? Assume that the page size can only be a power of $$2.$$

(b)$$\,\,\,\,\,$$ Now suppose that the pages size is $$512$$ bytes. It is proposed to provide a $$TLB$$ (Translation look-aside buffer) for speeding up address translation. The proposed $$TLB$$ will be capable of storing page table entries for $$16$$ recently referenced virtual pages, in a fast cache that will use the direct mapping scheme. What is the number of tag bits that will need to be associated with each cache entry

(c)$$\,\,\,\,\,$$ Assume that each page table entry contains (besides other information) $$1$$ valid bit, $$3$$ bits for page protection and $$1$$ dirty bit. How many bits are available in page table entry for storing the aging information for the page? Assume that the page size is $$512$$ bytes.

In a computer system where the ‘best-fit’ algorithm is used for allocating ‘jobs’ to ‘memory partitions’, the following situation was encountered:

When will the $$20$$ $$K$$ job complete?

A demand paged virtual memory system uses $$16$$ bit virtual address, page size of $$256$$ bytes, and has $$1$$ Kbyte of main memory. $$LRU$$ page replacement is implemented using a list, whose current status (page numbers in decimal ) is
$$\eqalign{ & \,\, \uparrow \cr & LRU\,Page \cr} $$
For each hexa decimal address in the address sequence given below,
$$00FF,$$ $$010D,$$ $$10FF,$$ $$11B0$$
Indicate,
i) The new status of the list
ii) Page faults, if any, and
iii) Page replacements, if any

A computer installation has 1000K of main memory. The jobs arrive and finish in the following sequence.
Job 1 requiring 200k arrives
Job 2 requiring 350k arrives
Job 3 requiring 300k arrives
Job 1 finishes
Job 4 requiring 120k arrives
Job 5 requiring 150k arrives
Job 6 requiring 80k arrives

(a) Draw the memory allocation table using Best Fit and First fit algorithm.
(b) Which algorithm performs better for this sequence?