Information Technology Reference
In-Depth Information
index into the table, while the block table covers
disk space in the unit of block, and block disk
location is an index into the table. (2) The page
table is used to translate a virtual address into its
physical address, while the block table is used to
provide the times of recent accesses for a given
disk block. (3) The requirement on the page table
lookup efficiency is much more demanding and
performance-critical than that on the block table
lookup efficiency because the former supports
instruction execution while the latter facilitates
I/O operations. That is the reason why a hardware
TLB has to be used to expedite page table lookup,
but there is no such a need for block table. (4)
Each process owns a page table, while each disk
drive owns a block table in memory.
In the system we set a global variable called
disk access clock
, which ticks each time a block
is fetched into memory. The block being fetched
takes the current clock time. We then record the
timestamp in an entry at the leaf level of the block
table corresponding to the block disk location,
which we called BTE (
Block Table Entry
). When
the block is being released, we reset the informa-
tion recorded for that block to prevent new blocks
allocated to the same location inheriting stale
information. Each BTE allows at most two most
recent access times recorded in it. Whenever a new
time is added, the oldest time is replaced if the
BTE is full. In addition, to manage efficiently the
memory space held by block table(s), a timestamp
is set in each table entry at directory levels. Each
time the block table is looked up in a hierarchical
way to record a new access time, the time is also
recorded as a timestamp in each directory entry
that has been passed. In this way, each directory
entry keeps the most recent timestamp among those
of all its direct/indirect children entries when the
table is viewed as a tree. The entries of the table
are allocated in an on-demand fashion.
The memory consumption of the block table
can be flexibly controlled. When system memory
pressure is too high and the system needs to reclaim
memory held by the table, it traverses the table
with a specified clock time threshold for recla-
mation. Because the most recent access times are
recorded in the directories, the system will remove
a directory once it finds its timestamp is smaller
than the threshold, and all the subdirectories and
BTEs under it will be removed.
forming Sequences
When the bank is full, it is the time to traverse all
the blocks in the bank to collect all the sequences.
To ensure the sequentiality and the stability re-
quirement of a sequence, the algorithm determines
that the last block (
A
) of a developing sequence
should not be coalesced with the closest block (
B
)
in the bank if the two blocks belong to one of the
following cases:
•
Block B is not close enough to block A. This
includes the case that the LBN (
Logical
Block Number
) of block B is less than that
of block A, where a long rotation time is
involved to move the disk head from block
A to block B. Currently, DULO uses 4 as
the distance threshold. The reason is that,
if the distance between block B and block
A is within the threshold, the read-ahead
mechanism in most hard drives, which is
enabled by default, can fetch block B into
disk caches automatically after it fetches
block A. So the cost of reading of block B
is very cheap.
Block B and block A are not sequentially
•
fetched from disk this time. If the most re-
cent time stamp of block B is not greater
than the most recent time stamp of block
A by 1, the accesses of block A and block
B are intersected by the access of the third
block, and high cost disk head seeks are
involved.
Block B and block A were not sequentially
•
fetched from disk last time. This includes
the case where one and only one of the two
blocks was not accessed before the current
Search WWH ::
Custom Search