2. (40 points) You have a large collection of images, image, image,, mage that y

Question

2. (40 points) You have a large collection of images, image, image,, mage that you wish to store on 100GB USB flash drives. You are given an array size, where size[i] is the size of the image, in GB. The goal is to use as few flash drives as possible, while storing the images in order. In other words, image1 through image, must be stored on drive 1, image-1 through imagej on drive 2, image#1 through imagek on drive 3, etc. a. Provide an efficient and correct algorithm to allocate images to drives b. What is the time complexity of your algorithm? Use asymptotic notation. Justify your answer. c. Prove that your algorithm is correct

Explanation / Answer

1) As per in the given in the question, There is a large collection of images image1, image2,...,imageN that we require to store on 100GB USB flash drives
2) We have been given an array size, where size[i] is the size of the imagei in GB.
3) Now, the goal of ours is to use as few flash drives as possible, whike storing the images in order.
4) That is, image1 through imagei must be stored on drive 1, imagei+1 through imagei on drive 2, and likewise others also.
5)We need to write the algorithm to allocate images to drive.
6) Now what is Flash memory, It is a type of electrically-erasable programmable read-only memory (EEPROM). Because flash memories are nonvolatile and relatively dense, they are now used to store files and other persistent objects in handheld computers, mobile phones, digital cameras, portable music players, and many other computer systems in which magnetic disks are inappropriate. Flash, like earlier EEPROM devices, suffers from two limitations. First, bits can only be cleared by erasing a large block of memory. Second, each block can only sustain a limited number of erasures, after which it can no longer reliably store data. Due to these limitations, sophisticated data structures and algorithms are required to effectively use flash memories.
7) One approach to using flash memory is to treat it as a block device that allows
fixed-size data blocks to be read and written, much like disk sectors. This allows
standard file systems designed for magnetic disks, such as fat, to utilize flash
devices. In this setup, the file system code calls a device driver, requesting block
read or write operations. The device driver stores and retrieves blocks from the
flash device.
8) However, mapping the blocks onto flash addresses in a simple linear fashion
presents two problems. First, some data blocks may be written to much more than
others. The second problem that the identity mapping poses is the inability to write
data blocks smaller than a flash erase unit.
9) The basic idea behind all the wear-leveling techniques is to map the block number
presented by the host, called a virtual block number, to a physical flash address
called a sector. Typically, sectors have a fixed size and occupy a fraction of an erase unit. In
nand devices, sectors usually occupy one flash page. But in nor devices, it is also
possible to use variable-length sectors.
This mapping serves several purposes:
a) First, writing frequently-modified blocks to a different sectors in every modification
evens out the wear of different erase units.
b) Second, the mapping allows writing a single block to flash without erasing and rewriting an entire erase unit [Assar et al. 1995a; 1995b; 1996].
c) Third, the mapping allows block writes to be implemented atomically, so that
if power is lost during a write operation, the block reverts to its pre-write state
when flash is used again.
10) Each sector is associated with a small header, which may be adjacent to the sector or elsewhere in the erase unit.
When a block is to be written, the software searches for an free and erased sector. In
that state, all the bits in both the sector and its header are all 1. Then a free/used
bit in the header of the sector is cleared, to mark that the sector is no longer free.
Then the virtual block number is written to its header, and the new data is written
to the chosen sector . Next, the pre-valid/valid bit in the header is cleared, to mark
the sector is ready for reading. Finally, the valid/obsolete bit in the header of the
old sector is cleared, to mark that it is no longer contains the most recent copy of
the virtual block.
11) Fundamentally,
there are two kinds of data structures that represent such mappings. Direct maps
are essentially arrays that store in the ith location the index of the sector that
currently contains block i. Inverse maps store in the ith location the identity of the
block stored in the ith sector. In other words, direct maps allow efficient mapping
of blocks to sectors, and inverse maps allow efficient mapping of sectors to blocks.
12) The Flash Translation Layer (ftl) is a technique to store some of the direct map
within the flash device itself while trying to reduce the cost of updating the map
on the flash device.
13) The ftl uses a combination of mechanisms, illustrated in Figure 2,to perform
the block-to-sector mapping.
(a) Block numbers are first mapped to logical block numbers, which consist of a
logical erase unit number (specified by the most significant bits of the logical
block number) and a sector index within the erase unit. This mechanism allows
the valid sectors of an erase unit to be copied to a newly erased erase unit
without changing the block-to-logical-block map, since each sector is copied to
the same location in the new erase unit.
(b) This block-to-logical-block map can be stored partially in ram and partially
within the flash itself. The mapping of the first blocks, which in fat-formatted
devices change frequently, can be stored in ram, while the rest is stored in the
flash device. The transition point can be configured when the flash is formatted,
and is stored in a header in the beginning of the flash device.
(c) The flash portion of the block-to-logical-block map is not stored contiguously
in the flash, but is scattered throughout the device, along with an inverse map.
A direct map in ram, which is reconstructed during initialization, points to
the sectors of the map. To look up a the logical number of a block, the system
first finds the sector containing the mapping in the top-level ram map, and then retrieves the mapping itself. In short, the map is stored in a two-level
hierarchical structure.
(d) When a block is rewritten and moved to a new sector, its mapping must be
changed. To allow this to happen at least some of the time without rewriting
the relevant mapping block, a backup map is used. If the relevant entry in
the backup map, which is also stored on flash, is available (all 1s), the original
entry in the main map is cleared, and the new location is written to the backup
map. Otherwise, the mapping sector must be rewritten. During lookup, if the
mapping entry is all 0s, the system looks up the mapping in the backup map.
This mechanism favors sequential modification of blocks, since in such cases
multiple mappings are moved from the main map to the backup map before
a new mapping sector must be written. The backup map can be sparse; not
every mapping sector must have a backup sector.
(e) Finally, logical erase units are mapped to physical erase units using a small
direct map in ram. Because it is small (one entry per erase unit, not per
sector), the ram overhead is small. It is constructed during initialization from
an inverse map; each physical erase unit stores its logical number. This direct
map is updated whenever an erase unit is reclaimed.
13) the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to differ by at most a constant factor.
14) the time complexity is commonly expressed using big O notation, typically {displaystyle O(n),} O(n), {displaystyle O(nlog n),} {displaystyle O(nlog n),} {displaystyle O(n^{lpha }),} {displaystyle O(n^{lpha }),} {displaystyle O(2^{n}),} {displaystyle O(2^{n}),} etc., where n is the input size in units of bits needed to represent the input.

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

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