Method and apparatus for performing force unit access writes on a disk

Description

BACKGROUND

Disk drives are commonly used to store data in computers, databases, digital video records, and other devices. A disk drive comprises a rotating magnetic disk and a head actuated over the disk to magnetically write data to and read data from the disk. The disk drive may write data to and read data from the disk in response to write/read commands from a host that used the disk drive for data storage. When the disk drive receives a force unit access write command it writes force unit access write data directly to the disk instead of just a cache before it completes the command to the host. In the case of shingled magnetic recording, metadata corresponding to the force unit access write data will also typically be written to the disk. This can cause a large accumulation of metadata in the disk. This can be undesirable because the metadata can take up space which could be used for storage of valid data.

BRIEF DESCRIPTION OF THE DRAWINGS

The features and advantages of the present embodiments of the present invention will become more apparent from the detailed description set forth below when taken in conjunction with the drawings, wherein:

FIG. 1 is a block diagram of a disk drive according to an embodiment of the present invention;

FIG. 2 depicts various shingled zones in a disk according to an embodiment of the present invention;

FIG. 3 depicts multiple disks in a disk drive according to an embodiment of the present invention;

FIG. 4 depicts force unit access write data stored in a cache as part of cache data according to an embodiment of the present invention;

FIG. 5 depicts a disk storing force unit access write data according to an embodiment of the present invention;

FIG. 6 depicts force unit access write data and other data stored in a cache as part of cache data according to an embodiment of the present invention;

FIG. 7 depicts cache data written on a disk according to an embodiment of the present invention;

FIG. 8 depicts tables of valid data counters corresponding to various zones in a disk according to an embodiment of the present invention;

FIG. 9 depicts force unit access write data stored in a cache as part of cache data according to an embodiment of the present invention;

FIG. 10 depicts a disk storing force unit access write data according to an embodiment of the present invention;

FIG. 11 depicts force unit access write data and other data stored in a cache as part of cache data according to an embodiment of the present invention;

FIG. 12 depicts cache data written on a disk according to an embodiment of the present invention;

FIG. 13 depicts tables of valid data counter corresponding to various zones in a disk according to an embodiment of the present invention;

FIG. 14 depicts a disk storing force unit access write data according to an embodiment of the present invention;

FIG. 15 depicts cache data written on a disk according to an embodiment of the present invention;

FIG. 16 depicts tables of valid data counter corresponding to various zones in a disk according to an embodiment of the present invention; and

FIG. 17 depicts a process according to an embodiment of the present invention.

DETAILED DESCRIPTION

In the following detailed description, numerous specific details are set forth to provide a full understanding of the present invention. It will be apparent, however, to one ordinarily skilled in the art that the present invention may be practiced without some of these specific details. In other instances, well-known structures and techniques have not been shown in detail to avoid unnecessarily obscuring the present invention.

FIG. 1 shows a disk drive 100 according to an embodiment of the present invention. The disk drive 100 comprises a rotating magnetic disk 60 and a head 50 connected to the distal end of an actuator arm 25. The actuator arm 25 is rotated about a pivot by a voice coil motor (VCM) 20 to position the head 50 radially over the disk 60. The disk drive 100 also includes a spindle motor (not shown) for rotating the disk during read/write operations.

The disk drive 100 also comprises a controller 10 that performs various operations of the disk drive 100 described herein. The controller 10 may be implemented using one or more processors for executing instructions and may further include memory, such as a volatile or non-volatile memory, for storing data (e.g., data being processed) and/or instructions. The instructions may be executed by the one or more processors to perform the various functions of the controller 10 described herein. The one or more processors may include a microcontroller, a Digital Signal Processor (DSP), an Application Specific Integrated Circuit (ASIC), a Field Programmable Gate Array (FPGA), hard-wired logic, analog circuitry and/or a combination thereof.

The disk 60 comprises a number of radially spaced, concentric tracks 4. The tracks 4 can overlap, and thus can be shingled. Each track 4 may be divided into a number of sectors (shown in FIG. 5) that are spaced circumferentially along the track 4. The sectors may be used to store user data and/or other information. The disk 60 may also comprise a plurality of angularly spaced servo wedges 22₀-22_N, each of which may include embedded servo information that can be read from the disk 60 by the head 50 to determine the position of the head 50 over the disk 60. For example, each servo wedge 22₀-22_N may include a pattern of alternating magnetic transitions (servo burst), which may be read from the disk 60 by the head 50 and processed by the controller 10 to estimate the position of the head 50 relative to the disk 60. The angular spacing between the servo wedges 22₀-22_N may be uniform, as shown in the example in FIG. 1.

To write data to the disk 60, the controller 10 may first position the head 50 at a desired track 4 on the disk 60 by sending a control signal input 28 (e.g., control current) to the VCM 20. The controller 10 may include a servo control system that positions the head 50 using the VCM 20 based on position information read from one or more servo wedges 22₀-22_N. The controller 10 processes data to be written to the disk 60 into a write signal 26, which is outputted to the head 50. The head 50 converts the write signal 26 into a magnetic field that magnetizes the surface of the disk 60 based on the write signal, thereby magnetically writing the data to the disk 60.

To read data from the disk 60, the controller 10 positions the head 50 at a desired track 4 on the disk 60. The head 50 generates a read signal based on the magnetization of the disk surface under the head 50. The controller 10 receives and processes the read signal 26 into data, thereby reading the data from the disk 60.

The controller 10 may write data to and read data from the disk 60 in response to write/read commands from a host (e.g., host processor). When the controller 10 receives a host write command including data to be written to the disk 60, the controller 10 may temporarily hold the data from the host in a cache 128 (e.g., DRAM) and write the data from the cache 128 to the disk 60 using the head 50. When the controller 10 receives a host read command requesting data stored on the disk 60, the controller 10 may read the requested data from the disk 60, temporarily hold the read data in the cache and send the read data from the cache to the host.

However, when the controller 10 receives a force unit access command from a host, the controller 10 writes force unit access write data to the cache 128 as part of the cache data. The controller 10 then writes the force unit access write data and also a metadata corresponding to the force unit access write data to a first location in the disk 60. The metadata can be, for example, a header in front of the write data, a footer after the write data, and/or a write log that is many sectors before or after the write data containing metadata for nearby sectors. The metadata can include logical-to-physical mapping information, such as what Logical Block Address (LBA) is found in Physical Block Addresses (PBA) near the metadata. Wherever it is located, the metadata can be used to update a mapping table in case a power loss is encountered before the mapping table is updated and stored in non-volatile memory. The first location can be part of, for example, a first shingled zone.

As seen in FIG. 2, the disk 60 can include a plurality of shingled zones 150 and the first location can be located in one of the plurality of shingled zones 150 according to an embodiment of the present invention. Each of the shingled zones 150 can comprise portions of one or more of the track 4. Furthermore, one or more of the shingled zones 150 can be a shingled zone allocated for force unit access write data such as the shingled zone 150₁ and the shingled zone 150₂. In one embodiment, a shingled zone allocated for force unit access write data can be smaller than the shingled zones used for other data. This can be done because the data in the shingled zone allocated for force unit access write data can constantly be invalidated and overwritten, thus conserving space on the disk 60 for the shingled zones used for other data.

In one embodiment, when writing to a shingled zone allocated for force unit access write data, the controller 10 can determine which shingled zone allocated for force unit access write data is closest to the head 50 when the controller 10 receives a force unit access write command from the host. The controller 10 can then control the head 50 to write the force unit access write data and its corresponding metadata onto that shingled zone allocated for force unit access write data which is closest to the head 50. For example, in FIG. 2, the shingled zone 150₁ is closest to the head 50. Thus, the controller 10 will write the force unit access write data and its corresponding metadata to the shingled zone 150₁.

The controller 10 can also repeat the above process for additional force unit access write commands and write, for example, a subsequent force unit access write data to a second location. The second location can be located, for example, in the first shingled zone, or in a shingled zone different from the first shingled zone. The second shingled zone can also be a shingled zone allocated for force unit access write data.

Furthermore, although in FIGS. 1 and 2, the disk 60 includes single disk with a single surface, the disk 60 can include multiple disks, and comprise multiple surfaces as seen in FIG. 3. In FIG. 3, the disk 60 can include multiples disks with the disk surfaces 60₁, 60₂, 60₃, and 60₄. The disk surfaces 60₁ and 60₂ can be formed on opposite sides of one disk, while the disk surfaces 60₃ and 60₄ can be formed on opposite sides of another disk. Each of the disk surfaces 60₁, 60₂, 60₃, and 60₄ can also have a corresponding head from the heads 50₁, 50₂, 50₃, and 50₄ to perform read/write operations on each of the disks. Furthermore, actuator arms 25₁, 25₂, and 25₃ can be used to move the heads 50₁, 50₂, 50₃, and 50₄. Since there are multiple disks, the shingled zones allocated for force unit access write data could be spread out over various disks. The controller 10 can determine which shingled zone allocated for force unit access write data is closest to one of the heads 50₁, 50₂, 50₃, and 50₄, even if such shingled zone is on a different disk.

In one embodiment, after the metadata is written on the disk 60, the controller 10 can transmit a write complete status to the host. Instead of erasing or overwriting the force unit access write data in the cache 128, the controller 10 maintains the force unit access write data in the cache. When the cache 128 is full or when a cache flush should be performed, the controller 10 writes the cache data including the force unit access write data to the disk 60 at a third location. The third location can be located in a different location than the first location, and the second location. The third location can be selected, for example, to be located sequentially after a location in the plurality of the tracks that the head 50 was performing a write operation on before the cache flush. Alternatively, the force unit access write data can be written at a time separate from a cache flush.

When the first location and the second location are part of the first shingled zone, the third location can be part of a second shingled zone. However, when the first location is part of the first shingled zone, and the second location is part of the second shingled zone, the third location can be part of a third shingled zone. The controller 10 can also write a metadata corresponding to the cache data in the third location.

After the cache data and the metadata corresponding to the cache data has been written to the third location, the controller 10 can optionally update the mapping table entry for the force unit access write data to point to the new physical location. Also, in one embodiment, when the first location and the second location are part of the first shingled zone, the controller 10 can decrement a first valid data counter corresponding to the first shingled zone and increment a second valid data counter corresponding to the second shingled zone. In another embodiment, when the first location is part of the first shingled zone, and the second location is part of the second shingled zone, the controller 10 can decrement a first valid data counter corresponding to the first shingled zone, and a second valid data counter corresponding to the second shingled zone. The controller 10 can also increment a third valid data counter corresponding to the third shingled zone, which contains the third location.

Although the examples disclosed herein may utilize a valid data counter to keep track of the number of valid data in a shingled zone, in one embodiment, the controller 10 can utilize other means for keeping track of the number of valid data in a shingled zone. For example, in one embodiment the controller 10 can compare the metadata to the mapping table to determine whether the data in the physical location on the disk is valid or invalid.

In one embodiment, the controller 10 can perform garbage collection on the disk 60. During garbage collection, the controller 10 can move valid data from a first shingled zone to a second shingled zone in order to reduce an amount of valid data in the first shingled zone or ensure that the first shingled zone contains no valid data. Garbage collection can free up contiguous space for valid data to be written in one or more shingled zones. When there is no valid data in a shingled zone, garbage collection can be simplified or eliminated as all the data in the shingled zone is invalid and can be overwritten. Likewise, when there is a reduced amount of valid data in a shingled zone, garbage collection may be simplified as there will be less valid data to gather and relocate.

FIGS. 4-6 depict a force unit access write operation and a cache flush for a single force unit access write data according to one embodiment. In FIG. 4, when the controller 10 receives a force unit access write command, a force unit access write data (FUAWD) is written to the cache 128 as cache data. The controller 10 then writes the force unit access write data and a metadata (MD) to the disk 60. As seen in FIG. 5, the disk 60 includes a plurality of sectors designated by 110_n, 120_n, and 130_n. In FIG. 5, the force unit access write data is written to the sector 110₁, while the metadata is written to the sector 110₂. In this embodiment, the metadata is shown as a footer, however, as described above, a header and/or a write log could be written. The sectors 110₁ and 110₂ are located in the first location, which can be part of a first shingled zone. The first shingled zone can be a shingled zone allocated for force unit access write data. The controller 10 can then transmit a write complete status to the host.

Although the examples disclosed herein may depict a single force unit access write data being written to a single sector from a single force unit access write command, in one embodiment, one or more force unit access write data can be written to multiple sectors from a single force unit access write command.

In FIG. 6, the cache 128 can be full or store sufficient data (D) that a cache flush can or should be performed according to one embodiment. The data can include other force unit access write data or other various data. A cache flush can also be performed when the controller 10 indicates that a cache flush should be performed, regardless of how much data is in the cache 128. During a cache flush, for example, all or a portion of the cache data is written to the disk 60. For example, in FIG. 7, the cache data including the force unit access write data is written to the sector 130₁. Other data may be written, for example, to sectors 130₂-130₅. The other data need not be force unit access write data. A metadata corresponding to the cache data and the other data can be written, for example, in sector 130₆. Furthermore, a metadata is also written in the sector 130₁₈ for the half-track containing the sectors 130₁-130₁₈. Although in the examples disclosed herein, metadata can be written for every half-track, in one embodiment, metadata can also be written for any sized portion of the track 4. In one embodiment, a single metadata can also be written for multiple tracks. Also, the metadata in sector 130₆ need not be written if data fills up the half-track because the metadata in the sector 130₁₈ can be used, obviating the need for the metadata in the sector 130₆.

The sectors 130₁-130₁₈ can be located in a second location. As can be seen, the second location is at a different location than the first location. In one embodiment, the second location can be a second shingled zone, different than the first shingled zone. Optionally, the second shingled zone can be a shingled zone allocated for force unit access write data. In one embodiment, the second location can be selected to be located sequentially after a location in the plurality of tracks that the head 50 was performing a write operation on before the cache flush.

In one embodiment, after the cache data and the metadata corresponding to the cache data are written at the second location, a first valid data counter corresponding to the first shingled zone is decremented, while a second valid data counter corresponding to the second shingled zone is incremented.

For example, as seen in FIG. 8, a table 130a indicates a valid data counter corresponding to the various zones prior to the cache flush according to one embodiment. A first valid data counter corresponding to the first shingled zone (zone 1) indicates that there is a single valid data in the first shingled zone (zone 1). A second valid data counter corresponding to the second shingled zone (zone 2) indicates that there is no valid data in the second shingled zone. However, once the cache data and its corresponding metadata has been written to the disk 60, the table 130a can be updated to provide appropriate decrements and increments to the valid data counters.

For example, the table 130b is the updated table 130a and indicates valid data counters corresponding to the various zones after the cache flush. As seen in table 130b, the first valid data counter corresponding to the first shingled zone (zone 1) is decremented to indicate that there is now no valid data in the first shingled zone (zone 1). That is, the first location no longer contains any valid data, and any data in the shingled zone can be overwritten. Furthermore, the second valid data counter corresponding to the second shingled zone (zone 6) is incremented to indicate that there is now five valid data in the second shingled zone (zone 6).

FIGS. 9-16 illustrate multiple force unit access write operations and a cache flush for multiple force unit access write data in one embodiment. In FIG. 9, the controller 10 writes multiple force unit access write data to the cache 128 as part of the cache data in response to multiple force unit access write commands. In FIG. 10, the controller 10 writes the force unit access write data to the disk 60 in the first location. Furthermore the controller 10 can write a metadata for each of the force unit access write data. Thus, the force unit access write data and their corresponding metadata are written to the sectors 110₁-110₆. The controller 10 can then transmit a write complete status to the host after each force unit access write data and corresponding metadata is written to the disk. The sectors 110₁ and 110₂ can be located in a first location, the sectors 110₃ and 110₄ can be located in a second location, and the sectors 110₅ and 110₆ can be located in a third location. The first location, the second location, and the third location can be part of, for example, a first shingled zone.

In FIG. 11, the cache 128 is ready for a cache flush. In FIG. 12, the controller 10 performs a cache flush by writing some or all of the cache data to the disk 60. Thus, the force unit access data in the cache data are written in the sectors 130₁, 130₂, and 130₃. The sectors 130₁-130₁₈ can be a fourth location. The fourth location can be at a different location than the first location, the second location, and the third location. In one embodiment, the fourth location can be part of a second shingled zone, different than the first shingled zone. Optionally, the second shingled zone can also be a shingled zone allocated for force unit access write data. In one embodiment, the fourth location can be selected to be located sequentially after a location in the plurality of tracks that the head 50 was performing a write operation on before the cache flush.

Furthermore, the controller 10 writes a metadata corresponding to the cache data in the sector 130₄. In one embodiment, a metadata for the half a track containing the fourth location is also written in sector 130₁₈. As can be seen, instead of using three metadata in FIG. 10, only two metadata are now used in FIG. 12. Furthermore, in one embodiment, if the cache data encompasses a full half-track, only a single metadata is used and the metadata in sector 130₄ would not be used.

As seen in FIG. 13, the controller 10 can then update the valid data counters indicated in the tables 130a and 130b according to one embodiment. Thus, a first valid data counter indicates that the first shingled zone (zone 1) originally had three valid data, while the second valid data counter indicates that the second shingled zone (zone 6) had none as shown in table 130a and FIG. 12. However, the controller updates the table 130a as shown in table 130b by decrementing and incrementing the appropriate valid data counters. Thus, the first valid data counter is decremented to zero, while the second valid data counter is incremented to three.

However, instead of writing all of the force unit access write data in FIG. 9 to the same shingled zone as shown in FIG. 10, in one embodiment, the controller 10 can write the force unit access write data to different shingled zones as shown in FIG. 14.

For example, the controller can write a first force unit access write data and its corresponding metadata to the sectors 110₁, and 110₂. The sectors 110₁ and 110₂ are located in a first location. The first location can be a first shingled zone. Furthermore, in FIG. 14, additional data may be located in the first shingled zone which are not shown.

The controller can also write a third force unit access write data, a fourth force unit access write data, and their corresponding metadata to the sectors 120₁, 120₂, 120₃, and 120₄ respectively. The sectors 120₁, 120₂, 120₃, and 120₄, are located in a second location and a third location different from the first location. The second location and the third location can be a second shingled zone different from the first shingled zone. Furthermore, in FIG. 14, additional data may be located in the second shingled zone, which are not shown.

As seen in FIG. 15, during a cache flush, the cache data can be written in the sectors 130₁-130₁₈ according to one embodiment. The sectors 130₁-130₁₈ can be located in a fourth location. The fourth location is at a different location than the first location, the second location, and the third location. In one embodiment, the third location can be a third shingled zone, different than the first shingled zone or the second shingled zone. In one embodiment, the third shingled location can be selected to be located sequentially after a location in the plurality of tracks that the head 50 was performing a write operation on before the cache flush.

In one embodiment, the controller 10 can write the force unit access write data contained in the cache data together during a cache flush, and continue to write data from other write commands from the host after the cache flush is completed. The other write commands from the host need not be force unit access write commands. In such a case, the force unit access write data can be located in adjacent sectors such as sectors 130₁-130₃ instead of 130₁, 130₅, and 130₁₃. In addition, the data written adjacent the force unit access write data need not be cache data. Furthermore, in one embodiment, the force unit access write data need not be written to the beginning sectors of the half-track during a cache flush, and could be written, for example, in the sectors 130₆-130₈. In such a case, the head 50 could write data from other write commands from the host before and after the cache flush.

In FIG. 15, the third shingled zone is not a shingled zone allocated for force unit access write data as indicated by the other data (D) being written in the third shingled zone. However, in alternate embodiments, the third shingled zone could be dedicated to just force unit access write data without having other data. In such a case, the other data may not be written to the third shingled zone. In one embodiment, the first shingled zone and the second shingled zone need not be shingled zones allocated for force unit access write data. However, one or more of the first shingled zone, and the second shingled zone could be a shingled zone allocated for force unit access write data.

In FIG. 15, the cache data encompasses a half-track, and therefore a single metadata can be used. This can save space in the disk 60 because a single metadata instead of three metadata is used. However, if the cache data encompasses less than the half-track, an additional metadata can be used. This would still provide space savings because two metadata instead of three metadata would be used.

In FIG. 16, the appropriate valid data counters can be decremented and incremented as shown in tables 130a and 130b according to one embodiment. In table 130a, the first valid data counter indicates that the first shingled zone (zone 1) included 10 valid data, the second valid data counter indicates that the second shingled zone (zone 2) included 6 valid data, and the third shingled zone (zone 6) included 0 valid data in FIG. 14. Valid data includes other types of data aside from force unit access write data, and are not shown in FIG. 14.

In the updated table 130b, the first valid data counter indicates that the first shingled zone (zone 1) now includes only 9 valid data since the force unit access write data located in sector 110₁ is now invalid data, and the second valid data counter indicates that the second shingled zone (zone 2) now includes only 4 valid data since the force unit access write data located in the sectors 120₁ and 120₃ are now invalid data. Furthermore, the third valid data indicates that there are now 17 valid data since force unit access write data and other data are located in the sectors 130₁-130₁₈.

In one embodiment, the present invention is a process as shown in FIG. 17. In Step 1705, a first force unit access write data is written to a cache as part of a cache data. For example, the controller 10 can write a first force unit access write data to the cache 128 as part of a cache data. The controller 10 can write the first force unit access write data to the cache 128 in response to a first force unit access write command from a host.

In Step 1710, a first force unit access write data and a first metadata corresponding to the first force unit access write data are written to a first location on a disk. For example, the controller 10 can write the first force unit access write data and a first metadata corresponding to the first force unit access write data to a first location on a disk 60. The first location can be, for example, a first shingled zone. The first shingled zone can optionally be a shingled zone allocated for force unit access write data. In one embodiment, the first shingled zone can be, for example, a shingled zone located closest to a position of the head 50 when the controller 10 received a force unit access write command from the host. In the case of dynamic mapping, the first shingled zone need not be a shingled zone allocated for force unit access write data, but instead could be any other location in the disk 60.

In Step 1715, a first write complete status is transmitted to a host. For example, the controller 10 can transmit a first write complete status to the host. In Step 1720, the first force unit access write data is maintained in the cache as part of the cache data. For example, the controller 10 can maintain the first force unit access write data in the cache 128 as part of the cache data.

In Step 1725, a write data is written to the cache as part of the cache data. For example, the controller 10 can write a write data to the cache 128 as part of the cache data. The write data can be, for example, a second force unit access write data. The controller 10 can write the second force unit access write data to the cache 128 in response to a second force unit access write command from the host. Furthermore, the second force unit access write data can be written, for example, to a second location. The second location can be, for example, a second shingled zone. The second shingled zone can be, for example, a shingled zone located closest to a position of the head 50 when the controller 10 received a force unit access write command from the host. In the case of dynamic mapping, the second shingled zone need not be a shingled zone allocated for force unit access write data, but instead could be any other location in the disk 60.

In Step 1730, the write data is maintained in the cache as part of the cache data. For example, the controller 10 can maintain the write data in the cache 128 as part of the cache data. In Step 1735, the cache data is written to a third location on the disk. For example, the controller 10 can write the cache data to a third location on the disk. The third location can be part of, for example, a second shingled zone when the first location and the second location are part of the first shingled zone. In the case of dynamic mapping, the second shingled zone need not be a shingled zone allocated for force unit access write data, but instead could be any other location in the disk 60.

When the first location is part of the first shingled zone and the second location is part of the second shingled zone, the third location can be part of a third shingled zone different from the first shingled zone and the second shingled zone. The third shingled zone can optionally be a shingled zone allocated for force unit access write data. In the case of dynamic mapping, the third shingled zone need not be a shingled zone allocated for force unit access write data, but instead could be any other location in the disk 60.

Furthermore, the third location, regardless of whether it is part of the second shingled zone or the third shingled zone can optionally be selected to be located sequentially after a location in the plurality of tracks that the head was performing a write operation on before the cache flush.

In Step 1740, a second metadata corresponding to the cache data is written to the disk. For example, the controller 10 writes the second metadata corresponding to the cache data to the third location.

In Step 1745, a valid data counter is decremented. For example, the controller 10 can decrement a first valid data counter corresponding to the first shingled zone and a second valid data counter corresponding to the second shingled zone. Furthermore, the controller 10 can also increment a third valid data counter corresponding to the third shingled zone.

When the first location and the second location are part of the first shingled zone, and the third location is part of the second shingled zone, then the controller 10 decrements a first valid data counter corresponding to the first shingled zone. The controller 10 can also increment a second valid data counter corresponding to the second shingled zone.

Although the above description utilizes shingled zones, the disk 60 can utilize segments of varying sizes instead of or in addition to the shingled zones. Furthermore, the segments can be zones instead of shingled zones. Optionally, one or more of the segments can be dedicated to force unit access write data.

For example, in FIG. 5, the first location including the sectors 110₁ and 110₂ can be part of a first segment, while in FIG. 7, the second location including the sectors 130₁-130₁₈ can be part of a second segment. In FIG. 10, the first location, the second location, and the third location including the sectors 110₁-110₆ can be part of a first segment, while in FIG. 12, the fourth location including the sectors 130₁-130₁₈ can be part of a second segment. In FIG. 14, the first location including the sectors 110₁ and 110₂ can be part of a first segment, and the second location and the third location including the sectors 120₁-120₄ can be part of the second segment. In FIG. 15, the fourth location including the sectors 130₁-130₁₈ can be part of a third segment.

Those of ordinary skill would appreciate that the various illustrative logical blocks, modules, and algorithm steps described in connection with the examples disclosed herein may be implemented as electronic hardware, computer software, or combinations of both. Furthermore, the present invention can also be embodied on a machine readable medium causing a processor or computer to perform or execute certain functions.

To clearly illustrate this interchangeability of hardware and software, various illustrative components, blocks, modules, circuits, and steps have been described above generally in terms of their functionality. Whether such functionality is implemented as hardware or software depends upon the particular application and design constraints imposed on the overall system. Skilled artisans may implement the described functionality in varying ways for each particular application, but such implementation decisions should not be interpreted as causing a departure from the scope of the disclosed apparatus and methods.

The steps of a method or algorithm described in connection with the examples disclosed herein may be embodied directly in hardware, in a software module executed by a processor, or in a combination of the two. The steps of the method or algorithm may also be performed in an alternate order from those provided in the examples. A software module may reside in RAM memory, flash memory, ROM memory, EPROM memory, EEPROM memory, registers, hard disk, a removable disk, a CD-ROM, or any other form of storage medium known in the art. An exemplary storage medium is coupled to the processor such that the processor can read information from, and write information to, the storage medium. In the alternative, the storage medium may be integral to the processor. The processor and the storage medium may reside in an Application Specific Integrated Circuit (ASIC). The ASIC may reside in a wireless modem. In the alternative, the processor and the storage medium may reside as discrete components in the wireless modem.

The previous description of the disclosed examples is provided to enable any person of ordinary skill in the art to make or use the disclosed methods and apparatus. Various modifications to these examples will be readily apparent to those skilled in the art, and the principles defined herein may be applied to other examples without departing from the spirit or scope of the disclosed method and apparatus. The described embodiments are to be considered in all respects only as illustrative and not restrictive and the scope of the invention is, therefore, indicated by the appended claims rather than by the foregoing description. All changes which come within the meaning and range of equivalency of the claims are to be embraced within their scope.