I'm revising for my BSc exam in "OS and computer architecture".
There's a question from a previous year's exam which I'm not sure how
to solve and it might come this year in some variation. As I'm aiming
for a 80% score, I want to be able to answer this one. Please explain
step-by-step how you solved question (b). To give an idea of the
scope: it's a 2-hour exam and this question represented 25% of the
total exam mark when it occured.

Note that I have consulted my university's code of conduct and
guidelines on academic honesty and don't see anything preventing me
from seeking tutor help on past papers.


(a) State the aims of memory management. Discuss how the processor and
operating system contribute to memory management. [10 Marks]

(b) A particular 32-bit computer has 256 MB of main memory, split into
4 MB pages. Segmentation is not being used. A paged, byte addressable
virtual memory is being used. The processor is executing a program of
size 32 MB, split into 8 pages.
(i) How many bits are required to store the frame number in the page
translation table? [1 mark]

(ii) Pages 1, 3, 6 and 7 of the program are in virtual memory, and
pages 0, 2, 4 and 5 are loaded into frames 2, 12, 8 and 16
respectively. Copy and complete the following page translation table
to reflect the current state of this program.

[2*8 table follows. Left column labelled "V" (for Valid, I presume),
right column labelled "Frame number (in binary)"]

[6 Marks]


(iii) Using your completed table, or otherwise, compute the physical
addresses (in hex) that correspond to the linear addresses 002F5044
(hex) and 01760042 (hex). [5 Marks]

(iv) Describe what will happen when the processor fetches an item with
linear addresses 00FFFF02 (hex). [3 Marks]

Hello Lovkraft,

[a1] State the aims of memory management.
In brief:
 - to effectively utilize memory and secondary storage of a computer system
 - to protect the operating system and other user applications from an
erroneous or damaging application
 - to ensure applications run within time constraints (e.g., real time
tasks are locked into physical memory)
 - to fairly share resources
Some of these are at opposition with other aims - the results will
vary by operating system or tuning values within an operating system.

See also:
  http://www.cs.toronto.edu/~demke/468F.02/Lectures/lecture7_2up.pdf
  http://www.cs.toronto.edu/~demke/369F.03/Lectures/lecture8_4up_bw.pdf
parts of a lecture series on Operating System design, describing
memory management goals, page replacement policies, etc.

[a2] Discuss how the processor and operating system contribute to
memory management.
An example of this is at
  http://www.deas.harvard.edu/courses/cs261/reviews/levy-1982.html
which focuses mostly on the hardware support but also describes some
of the techniques used by the operating system to manage pages. For
example - the page replacement section near the bottom describe
methods used by the operating system to minimize the amount of paging
/ swapping done by the OS.

There is also a relatively recent (February 2004) description of the
memory management in Linux by Mel Gorman at
  http://www.csn.ul.ie/~mel/projects/vm/guide/html/understand/
and will be available in complete form (in a few months) at
  http://www.phptr.com/perens
[or some page it redirects to[

For example, a good illustration of the constraints of real hardware
and how it is mapped by Linux is at
  http://www.csn.ul.ie/~mel/projects/vm/guide/html/understand/node16.html
which introduces the concepts of nodes (for Non Uniform Memory Access
systems), as well as the three major regions - DMA, Normal, and
Highmem used on x86 processors.

Note that for Linux in particular - a lot of effort was put into
writing the code once (or with minor tailoring) and using on a number
of different hardware platforms. You will see references to a three
layer page table in
  http://www.csn.ul.ie/~mel/projects/vm/guide/html/understand/node21.html
and how one layer is optimized away on most x86 systems.

In summary - the operating system will impose a set of memory
management policies using the capabilities of the hardware.

Search phrases used to help prepare this part of the answer:
  goals memory management
  "memory management goals"
  vax/vms memory management

[b] A particular 32-bit computer has 256 MB of main memory, split into 4 MB pages.

OK. 256/4 = 64, so you have frames from 0 to 63.

[b] Segmentation is not being used.

OK. That means there won't be address bits reserved for segment
numbers (like the two bits reserved on a VAX).

[b] A paged, byte addressable virtual memory is being used.

OK. Combined with the first statement - you have 22 bit byte offsets
within an address to cover the 4 Mbyte page. This also implies a
virtual to physical mapping will be used for address translation.

[b] The processor is executing a program of size 32 MB, split into 8 pages.

OK. 32/4 = 8; that appears good.

[b1] How many bits are required to store the frame number in the page
translation table?

At least 6 bits to cover the 64 pages of physical memory.

NOTE: If this is in a family of processors with a larger maximum
memory limit - there would be more bits in the PTT.

[b2] Pages 1, 3, 6 and 7 of the program are in virtual memory, and
pages 0, 2, 4 and 5 are loaded into frames 2, 12, 8 and 16
respectively. Copy and complete the following page translation table
to reflect the current state of this program.

Valid Frame Number
V     02
NV    --
V     12
NV    --
V     08
V     16
NV    --
NV    --

Let's explain why...
The first entry - page 0 reflects a valid page at frame 2.
The second entry - page 1 reflects an invalid page, its location is
ignored by the hardware until loaded into a frame and the valid bit is
set.
The third entry - page 2 reflects a valid page at frame 12.
and so on.

NOTE: an operating system such as VAX/VMS can store information in
invalid page table entries to tell the OS where the page is on disk.

[B3] Compute the physical addresses (in hex) corresponding to addresses:

  002F5044
We said before we have a 22 bit offset - this address has a page
number of zero and offset of 2F5044.
 VA in binary 0000 0000 00,10 1111 0101 0000 0100 0100
[comma added here and below to show page / offset portions of the address]

Page 0 is at frame 2, starting at physical address 00800000. So
virtual address 002F5044 is at physical address 00AF5044.
  PA in binary 0000 0000 10,10 1111 0101 0000 0100 0100

  01760042
This address has a page number of 5 and offset 360042.
  VA in binary 0000 0001 01,11 0110 0000 0000 0100 0010
Page 5 is at frame 16, starting at physical address 04000000, so the
virtual address 01760042 is at physical address 04360042
  PA in binary 0000 0100 00,11 0110 0000 0000 0100 0010

[B4] What will happen when the processor fetches address 00FFFF02?

Decoding that address
  0000 0000 11,11 1111 1111 1111 0000 0010
we note that the page number is three (3). According to the PTT, three
is not a valid page at this time. The hardware should generate a fault
(or trap or exception) and enter the OS at the page fault handler. The
page fault handler determines that page 3 is within the 8 pages of the
application, frees up a physical page [may have to write that page to
memory - don't have enough data to determine the exact method], loads
page 3 into that physical page - let's say frame 9, then sets the
frame number for page 3, sets the valid bit, and retries the
instruction which should now succeed.

NOTE: a real OS would also run some other task while the page is being
brought into memory so you have one or more task switches plus other
applications running as well.

That gives you an answer to all parts of your two questions. If some
part of the answer is not understandable - especially [b], please use
a clarification request so I can explain more fully.

Good luck with your studies.

  --Maniac

I cannot answer all of your questions but the first part is as below:

An OS manages many process, the code and data for a process must be in
RAM before it can run. There is usually not enough RAM to hold the
code and data for all the currently running processes in RAM. Memory
management is about sharing memory so that the largest number of
processes can run simultaneously in the most efficient way.

Memory Management is usually divided into three areas: hardware,
operating system and application.  In most computer systems, all three
are present to some extent, forming layers between the user's program
and the actual memory hardware.

Memory management at the hardware level is concerned with the
electronic devices in the computer. e.g. processor and RAM

Operating system usually deals with virtual memory.