memmult.html

关于ARM汇编的非常好的教程

It gets better. <i>Every single memory reference</i> will be passed through the MMU. So we'll
want it to operate in nanaseconds. Faster, if possible.<br>
In reality, it is somewhat easier as most typical machines don't have enough memory to fill the
entire addressing space, indeed many are unlikely to get close on technical reasons (the RiscPC
can have 258Mb maximum RAM, or 514Mb with Kinetic - the extra 2Mb is the VRAM). Even so, the page
tables will get large.
<p>

So there are three options:
<ul>
  <li> Have a huge array of fast registers in the MMU. Costly. Very.
  <li> Hold the page tables in main memory. Slow. Very.
  <li> Compromise. Cache the active pages in the MMU, and store the rest on disc.
</ul>

An example. A RiscPC, 64Mb of RAM, 2Mb of VRAM, 4Mb of ROM and hardware I/O (double mapped).
That's 734000320 bytes, or 17920 pages. It would take 71680 bytes to store each address. But an
address on it's own isn't much use. Seven words comprise an entry in the ARM's MMU. So our 17920
pages would require 501760 bytes in order to fully index the memory.<br>
You just can't store that lot in the MMU. So you'll store a snippet, say 16K worth?, and keep the
rest in RAM.
<p>&nbsp;<p>


<h2>The TLB</h2>

The Translation Lookaside Buffer is a way to make paging even more responsive. Typically, a
program will make heavy use of a few pages and barely touch the rest. Even if you plan to byte
read the entire memory map, you will be making four thousand hits in one page before going to
the next.<br>
A solution to this is to fit a little bit in the MMU that can map virtual addresses to their
physical counterparts without traversing the page table. This is the TLB. It lives within the MMU
and contains details of a small number of pages (usually between four and sixty four - the ARM610
MMU TLB has thirty two entries).<br>
Now, when we have a page lookup, we first pass our virtual address to the TLB which will check
all of the addresses stored, and the protection level. If a match is found, the TLB will spit
out the physical address and the page table isn't touched.<br>
If a miss is encountered, then the TLB will evict one of it's entries and load in the page
information looked up in the page table, so the TLB will know the new page requested, so it can
quickly satisfy the result for the next memory access, as chances are the next access will be in
the page just requested.
<p>

So far we have figured on the hardware doing all of this, as in the ARM processor. Some RISC
processors (such as the Alpha and the MIPS) will pass the TLB miss problem to the operating
system. This may allow the OS to use some intelligence to preload certain pages into the TLB.
<p>&nbsp;<p>


<h2>Page size</h2>

Users of an RISC OS 3.5 system running on an ARM610 with two or more large (say, 20Mb)
applications running will know the value of a 4K page. Because it's bloody slow. To be fair, this
isn't the fault of the hardware, but more the WIMP doing stuff the kernel should do (as happens
in RISC OS 3.7) and doing it slower!
<p>

Like with harddisc LFAUs, what you need is a sensible trade-off between page granulity and page
size. You could reduce the wastage in memory by making pages small, say 256 bytes. But then you
would need a lot of memory to store the page table. A bigger page table, slower to scan through
it. Or you could have 64K pages, which make the page table small, but can waste huge amounts of
memory.<br>
To consider, a 32K program would require eight 4K pages, or <i>sixty four</i> 512 byte pages. If
your system remaps memory when shuffling pages around, it is quicker to move a smaller number of
large pages than a larger number of small pages.
<p>

The MEMC in older RISC OS machines had a fixed page table. So the size of page depended upon how
much memory was utilised.
<center>
<table border="1" cellspacing="1" cellpadding="1">
  <tr> <td><b>MEMORY</b><br> <td><b>PAGE SIZE</b><br>

  <tr> <td>0.5Mb<br> <td>8K<br>

  <tr> <td>1Mb<br> <td>8K<br>

  <tr> <td>2Mb<br> <td>16K<br>

  <tr> <td>4Mb<br> <td>32K
</table>
</center>
<br>
3Mb wasn't a valid option, and 4Mb is the limit. You can increase this by fitting a slave MEMC,
in which case you are looking at 2 lots of 4Mb (invisible to the OS/user).<br>
In a RiscPC, the MMU accesses a number of 4K pages. The limits are due, I suspect, to the system
bus or memory system, not the MMU itself.
<p>

Most commercial systems use page sizes in the order 512 bytes to 64K.<br>
The later ARM processors (ARM6 onwards) and the Intel Pentium both use page sizes of 4K.
<p>&nbsp;<p>


<h2>Page replacement algorithms</h2>

When a page fault occurs, the operating system has to pick a page to dump, to allow the required
page to be loaded. There are several ways that this may be achieved. None of these are perfect,
they are a compromise of efficiency.
<p>

<b>Not Recently Used</b><br>
This requires two bits to be reserved in the page table, a bit for read/write and a bit for
page reference. Upon each access, the paging hardware (and it must be done in hardware for
speed) will set the bits as necessary. Then on a fixed interval the operating system will clear
these bits - either when idling or upon clock interrupt? This then allows you to track the
recent page accesses, so when flushing out a page you can spot those that have not recently been
read/written or referenced. NRU would remove a page at random. While it is not the best way of
sorting out which pages to remove, it is simple and gives reasonably good results.
<p>

<b>First-In First-Out</b><br>
It is hoped you are familiar with the concept of FIFO, from buffering and the like. If you are
not, consider the lame analogy of the hose pipe in which the first water in will be the first
water to come out the other end. It is rarely used, I'll leave the whys and wherefores as an
exercise for the bemused reader. <tt>:-)</tt>
<p>

<b>Second Chance</b><br>
A simple modification to the FIFO arrangement is to look at the access bit, and if it is zero
then we know the page is not in current use and can be thrown. If the bit is set, then the page
is shifted to the end of the page list as if it was a new access, and the page search continues.
<br>
What we are doing here is looking for a page unused since the last period (clock tick?). If by
some miracle ALL the pages are current and active, then Second Change will revert to FIFO.
<p>

<b>Clock</b>
Although Second Chance is good, all that page shuffling is inefficient so the pages are instead
referenced in a circular list (ie, clock). If the page being examined in in use, we move on and
look at the next page. With no concept of the start and end of the list, we just keep going until
we come to a usable page.
<p>

<b>Least Recently Used</b><br>
LRU is possible, but it isn't cheap. You maintain a list of all the pages, sorted by the most
recently used at the front of the list, to the least recently used at the back. When you need a
page, you pull the last entry and use it. Because of speed, this is only really possible in
hardware as the list should be updated each memory access.
<p>

<b>Not Frequently Used</b><br>
In an attempt to simulate LRU in software, we can maintain something vaguely similar to LRU in
a software implementation, in which the OS scans the available pages on each clock tick and
incrememnts a counter (held in memory, one for each page) depending on the read/written bit.<br>
Unfortunately, it doesn't forget. So code heavily used then no longer necessary (such as a
rendering core) will have a high count for quite a while. Then, code that is not called often but
should be all the more responsive, such as redraw code, will have a lower count and thus stand
the possibility of being kicked out, even though the higher-rated renderer is no longer needed
but not kicked out as it's count is higher.<br>
But this can be fixed, and the fix emulates LRU quite well. It is called aging. Just before the
count is incremented, it is shifted one bit to the right. So after a number of shifts the count
will be zero unless the bit is added. Here you might be wondering how adding a bit can work, if
you've just shifted a bit off. The answer is simple. The added bit is added to the leftmost
position, ie most significant.<br>
The make this clearer...
<pre>   Once upon a time:     0 0 1 0 1 1
   Clock tick      :     0 0 0 1 0 1
   Clock tick      :     0 0 0 0 1 0
   Memory accessed :     1 0 0 0 0 1
   Clock tick      :     0 1 0 0 0 0
   Memory accessed :     1 0 1 0 0 0
</pre>
<p>&nbsp;<p>


<h2>Multitasking</h2>

There is no such thing as <i>true</i> multitasking (despite what they may claim in the advocacy
newsgroups). To multitask properly, you need a processor per process, with all the relevant bits
so processes are not kept waiting. Effectively, a seperate computer for each task.
<p>

However, it is possible to provide the illusion of running several things at once. In the old
days, things happened in the background under interrupt control. Keyboards were scanned, clocks
were updated. As computers became more powerful, more stuff happened in the background. Hugo
Fiennes wrote a soundtracker player that runs on interrupts, so works in the background. You set
it going, it carries on independent of your code.
<p>

So people began to think of the ability to apply this to applications. After all, most of the
time an application is spent waiting for user input. In fact, the application may easily so sweet
sod all for almost 100% of the time - measured by an event counter in Emily's polling loop, I
type ~1 character a second, the RiscPC polls a few hundred times a second. That was measured in
a multitasking application, using polling speed as a yardstick. Imagine if we were to record
loops in a single-tasking program. So the idea was arrived at. We can load several programs into
memory, provide them some standard facilities and messaging systems, and then let them run for a
predefined duration. When the duration is up, we pass control to the next program. When that has
used its time, we go to the next program, and so on.<br>
As a brief aside, I wish to point out Schr&ouml;dinger's cat. A rather cute little moggy, but an
extremely important one. It is physically impossible to measure system polling speed in software,
and pretty difficult to measure it in hardware. You see, the very act of performing your
measurement will affect the results. And you cannot easily 'account' for the time taken to make
your measurements because measuring yourself is subject to the same artefacts as when measuring
other things. You can only say 'to hell with it', and have your program report your polling rate
as being 379 polls/sec, knowing that your measuring code may be eating around 20% of the
available time, and use the figures in a relative form rather than trying to state &quot;My
computer achieves 379 polls every second&quot;. While there is no untruth in that, your computer
might do 450 if you weren't so busy watching! You simply can't be JAFO.
<p>&nbsp;<p>


<h2>Co-operative multitasking</h2>

One such way of multitasking is relatively clean and simple. The application, once control has
passed to it, has full control for as long as it needs. When it has finished, control is
explicitly passed back to the operating system.<br>
This is the multitasking scheme used in RISC OS.
<p>&nbsp;<p>


<h2>Pre-emptive multitasking</h2>

Seen as the cure to all the world's ills by many advocates who have seen Linux (not Windows!),
this works differently. Your application is given a timeslice. You can process whatever you want
in your timeslice. When your timeslice is up, control is wrested away and given to another
process. You have no say in the matter, peon.
<p>&nbsp;<p>&nbsp;<p>



I don't wish to get into an advocacy war here. My personal preference is co-operative, however I
don't feel that either is the answer. Rather, a hybrid using both technologies could make for a
clean system. The major drawback of CMT is that if an application dies and goes into a
never-ending loop, control won't come back. The application needs to be forceably killed off.<br>
Niall Douglas wrote a <a href="http://www.armature.net.au/~tornado">pre-emption system</a> <font color = "red" size = "-1">[EXTERNAL LINK]</font> for
RISC OS applications. Surprisingly, you didn't really notice anything much until an application
entered some heavy processing (say, ChangeFSI) at which point life carried right on as normal
while the task which would have stalled the machine for a while chugged away in the background.
<p>

<hr size = 3>

<a href="index.html#03">Return to assembler index</a>

<hr size = 3>
<address>Copyright &copy; 2001 Richard Murray</address>
</body>
</html>