Data processing system and operating method thereof

A data processing system includes a host suitable for generating a candidate logical block address (LBA) list including a plurality of candidate LBAs, a memory device suitable for storing a plurality of map segments and user data corresponding to the respective map segments, and a controller suitable for receiving the candidate LBA list from the host, and loading target map segments from the memory device, the target map segments corresponding to the plurality of candidate LBAs.

CROSS-REFERENCE TO RELATED APPLICATION

This application claims priority under 35 U.S.C. § 119 to Korean Patent Application No. 10-2018-0160903 filed on Dec. 13, 2018, which is incorporated herein by reference in its entirety.

BACKGROUND

Various embodiments relate to a data processing system and operating method of the same, and more particularly, to a data processing system which performs a read operation efficiently and operating method of the same.

2. Discussion of the Related Art

The computer environment paradigm has been transitioning to ubiquitous computing, which enables computing systems to be used anytime and anywhere. As a result, use of portable electronic devices such as mobile phones, digital cameras, and laptop computers has rapidly increased. These portable electronic devices generally use a memory system having one or more memory devices for storing data. A memory system may be used as a main memory device or an auxiliary memory device of a portable electronic device.

Since they have no moving parts, memory systems provide advantages such as excellent stability and durability, high information access speed, and low power consumption. Examples of memory systems having such advantages include universal serial bus (USB) memory devices, memory cards having various interfaces, and solid state drives (SSDs).

SUMMARY

Various embodiments are directed to a data processing system which predicts a map segment corresponding to user data to be read in the future and loads the map segment to perform a read operation quickly.

In an embodiment, a data processing system may include: a host suitable for generating a candidate logical block address (LBA) list including a plurality of candidate LBAs; a memory device suitable for storing a plurality of map segments and user data corresponding to the respective map segments; and a controller suitable for receiving the candidate LBA list from the host, and loading target map segments from the memory device, the target map segments corresponding to the plurality of candidate LBAs.

In an embodiment, an operation method of a data processing system may include: checking, by a host, whether an empty slot is present among a plurality of slots in a command queue; generating, by the host, a candidate LBA list when the empty slot is not present; providing, by the host, a forecast command and the candidate LBA list from a host to a controller; retrieving, by the controller, target map segments corresponding to a plurality of candidate LBAs from a map buffer, based on the candidate LBA list; loading, by the controller, the target map segments corresponding to the respective candidate LBAs from a memory device, when the target map segments are not retrieved from the map buffer; and storing, by the controller, the loaded target map segments in the map buffer.

In an embodiment, a data processing system may include: a memory device suitable for storing a plurality of map segments and multiple pieces of data corresponding to the plurality of map segments; a host suitable for transmitting a read request for a piece of data among the multiple pieces of data, and generating and transmitting a candidate list for storing address information corresponding to at least one next piece of data to be read after reading the piece of data; and a controller suitable for reading the piece of data from the memory device to provide the piece of data to the host, in response to the read request, receiving the candidate list and loading the target map segment among the plurality of map segments from the memory device, based on the address information.

DETAILED DESCRIPTION

Various embodiments of the present invention are described below in more detail with reference to the accompanying drawings. However, various elements and features of the present invention may be configured or arranged differently than shown in the described embodiments, as will be apparent to those skilled in the art in light of this disclosure. Thus, the present invention is not limited to the embodiments set forth herein. Rather, the described embodiments are provided so that this disclosure is thorough and complete, and fully conveys the present invention to those skilled in the art to which this invention pertains. Moreover, reference to “an embodiment” does not necessarily mean only one embodiment, and different references to “an embodiment” are not necessarily to the same embodiment(s). Throughout the disclosure, like reference numerals refer to like parts throughout the various figures and embodiments of the present invention.

The drawings are not necessarily to scale and, in some instances, proportions may have been exaggerated in order to clearly illustrate various features of the disclosed embodiments.

FIG. 1is a block diagram illustrating a data processing system100including a memory system110in accordance with an embodiment of the present invention. The arrows between the components shown inFIG. 1represent the paths of data and commands, and do not represent actual physical connections. Data and commands can be transferred to the memory system110through a bus that can be shared among the components.

Referring toFIG. 1, the data processing system100may include a host102operatively coupled to the memory system110.

The host102may include any of various portable electronic devices such as a mobile phone, MP3 player and laptop computer, or any of various non-portable electronic devices such as a desktop computer, a game machine, a television (TV), and a projector.

The host102may include at least one operating system (OS) or a plurality of OSs, and execute an OS to perform an operation with the memory system110according to a user request. The host102may provide the memory system110with a plurality of commands corresponding to a user request. The memory system110may perform operations corresponding to the commands provided from the host102. The OS may manage and control overall functions and operations of the host102, and provide an interaction between the host102and the data processing system100or a user who uses the memory system110.

For example, in case of a read request for user data, the host102may provide the memory system110with a read command and a logical block address (LBA) for performing a read operation. The memory system110may perform a read operation corresponding to the read command provided from the host102. However, when the memory system110has many operations in progress, the host102cannot provide a command to the memory system110. At this time, the host102may create a list of LBAs corresponding to data to be read afterwards. Hereafter, the LBAs will be referred to as candidate LBAs.

Specifically, the host102may include a list generator104which can be operated by the OS. The list generator104may generate and store a candidate LBA list200ofFIG. 2, when the memory system110cannot receive a command corresponding to a user request from the host102. Hereafter, referring toFIG. 2, the candidate LBA list200will be described.

FIG. 2illustrates a structure of the candidate LBA list200in accordance with an embodiment.

Referring toFIG. 2, the candidate LBA list200may include information on ‘Start LBA’ of candidate LBAs corresponding to a plurality of read commands which are to be executed afterwards according to a user request, ‘Length’ indicating the sizes of the candidate LBAs, and ‘Number’ indicating the order in which the candidate LBAs are stored in the candidate LBA list200. Each of candidate LBAs having a length greater than ‘1’ may include a plurality of consecutive LBAs. On the other hand, each candidate LBAs having a length of ‘1’ may include only itself.

For example, in the candidate LBA list200ofFIG. 2, a first candidate LBA210of the plurality of candidate LBAs was stored in the candidate LBA list200for the first time, and a first LBA LBA1is the start LBA of the first candidate LBA210and has a length of ‘1’. That is, the first candidate LBA210may include only the first LBA LBA1. For another example, a third candidate LBA230of the plurality of candidate LBAs was stored in the candidate LBA list200for the third time, and a fifth LBA LBA5is the start LBA of the third candidate LBA230and has a length of ‘6’. Therefore, the third candidate LBA230may include fifth to tenth LBAs. However, this is only an example, but the present embodiment is not limited thereto.

Referring back toFIG. 1, the list generator104may store candidate LBAs in the candidate LBA list200described with reference toFIG. 2. The candidate LBAs may correspond to a plurality of read commands which are to be executed afterwards according to a user request. Furthermore, when the size of data corresponding to the user request is greater than or equal to a predetermined threshold size, the list generator104may generate the candidate LBA list200. For example, when the memory system110cannot receive a command corresponding to a user request from the host102because the predetermined threshold size is ‘100 KB’ and the size of data corresponding to the user request is ‘160 KB’, the list generator104may generate the candidate LBA list200in which candidate LBAs corresponding to ‘160 KB’ are stored. On the other hand, even when the memory system110cannot receive a command corresponding to a user request from the host102, the list generator104may not generate the candidate LBA list200in the case that the size of data corresponding to the user request is less than the predetermined threshold size.

The list generator104may store candidate LBAs in the candidate LBA list only up to a predetermined ‘number’. The candidate LBAs may correspond to a plurality of read commands which are to be executed according to a user request. For example, when ‘number’ is set to ‘100’, the list generator104may store candidate LBAs in the candidate LBA list up to ‘100’. In this case, ‘n’ inFIG. 2is ‘100’. For another example, when the number of candidate LBAs corresponding to read commands which are to be executed according to a user request is ‘150’, the list generator104may generate a candidate LBA list for the ‘100’ candidate LBAs, and not separately generate a candidate LBA list for the other ‘50’ candidate LBAs.

Subsequently, when the memory system110is switched to a state in which the memory system110can receive a command corresponding to a user request from the host102, the host102may provide a forecast command to the memory system110. The forecast command may include information on the last number stored in the candidate LBA list.

The memory system110may operate to store data for the host102in response to a request of the host102. Non-limiting examples of the memory system110may include a solid state drive (SSD), a multi-media card (MMC), a secure digital (SD) card, a universal storage bus (USB) device, a universal flash storage (UFS) device, compact flash (CF) card, a smart media card (SMC), a personal computer memory card international association (PCMCIA) card and memory stick. The MMC may include an embedded MMC (eMMC), reduced size MMC (RS-MMC) and micro-MMC, and the. The SD card may include a mini-SD card and micro-SD card.

The memory system110may be embodied by various types of storage devices. Examples of such storage devices may include, but are not limited to, volatile memory devices such as a dynamic random access memory (DRAM) and a static RAM (SRAM) and nonvolatile memory devices such as a read only memory (ROM), a mask ROM (MROM), a programmable ROM (PROM), an erasable programmable ROM (EPROM), an electrically erasable programmable ROM (EEPROM), a ferroelectric RAM (FRAM), a phase-change RAM (PRAM), a magneto-resistive RAM (MRAM), resistive RAM (RRAM or ReRAM) and a flash memory. The flash memory may have a 3-dimensional (3D) stack structure.

The memory system110may include a controller130and a memory device150.

The controller130and the memory device150may be integrated into a single semiconductor device. For example, the controller130and the memory device150may be integrated as one semiconductor device to constitute a solid state drive (SSD). When the memory system110is used as an SSD, the operating speed of the host102connected to the memory system110can be improved. In addition, the controller130and the memory device150may be integrated as one semiconductor device to constitute a memory card. For example, the controller130and the memory device150may constitute a memory card such as a personal computer memory card international association (PCMCIA) card, compact flash (CF) card, smart media (SM) card, memory stick, multimedia card (MMC) including reduced size MMC (RS-MMC) and micro-MMC, secure digital (SD) card including mini-SD card, micro-SD card and SDHC card, or universal flash storage (UFS) device. Non-limiting application examples of the memory system110may include a computer, a smart phone, and a portable game machine.

The memory device150may be a nonvolatile memory device and may retain data stored therein even though power is not supplied. The memory device150may store data provided from the host102through a write operation, and provide data stored therein to the host102through a read operation.

Each of a plurality of memory blocks152may include a plurality of pages, and each of the pages may include a plurality of memory cells coupled to a word line. The memory device150may include a plurality of planes each of which may include the plurality of memory blocks152, and include a plurality of memory dies each of which may include the plurality of planes. In an embodiment, the memory device150may be a flash memory. The flash memory may have a 3-dimensional (3D) stack structure.

The controller130may control the memory device150in response to a request from the host102. For example, the controller130may provide data read from the memory device150to the host102, and store data provided from the host102into the memory device150. For this operation, the controller130may control read, program and erase operations of the memory device150.

The controller130may include a host interface (I/F)132, a processor134, a memory I/F142, and a memory144all operatively coupled via an internal bus.

The host interface132may be configured to process a command and data of the host102, and may communicate with the host102through one or more of various interface protocols such as universal serial bus (USB), multi-media card (MMC), peripheral component interconnect-express (PCI-e or PCIe), small computer system interface (SCSI), serial-attached SCSI (SAS), serial advanced technology attachment (SATA), parallel advanced technology attachment (DATA), enhanced small disk interface (ESDI) and integrated drive electronics (IDE). The host interface132may be driven through firmware referred to as a host interface layer (HIL) in order to exchange data with the host.

Specifically, the host interface132may include a command queue136capable of queuing commands provided from the host102, a queue manager138capable of managing the command queue136, and a data input and output (I/O) circuit140capable of inputting/outputting data provided from the host102.

The command queue136may include a plurality of slots. The command queue136may queue the commands provided from the host102in the respective slots. Hereafter, referring toFIG. 3, the structure of the command queue136will be described.

FIG. 3illustrates a structure of the command queue136in accordance with an embodiment.

Referring toFIG. 3, the command queue136may include a plurality of slots (e.g., m slots), and include numbers corresponding to the respective slots and commands queued in the respective slots. For example, a command queued in a first slot is ‘Read’ command. Furthermore, a command queued in a second slot is ‘Write’ command. The command queue136may have a first-in first-out (FIFO) structure. When the command queue136has a FIFO structure, the ‘Read’ command queued in the first slot may be first processed, and the ‘Write’ command queued in the second slot may be then processed. However, this is only an example, and the present embodiment is not limited thereto.

The command queue136may have a limited number of slots (hereafter, referred to as a queue depth). Therefore, the command queue136may queue a plurality of commands received from the host102only up to the queue depth. For example, when the queue depth is ‘32’ (i.e., m inFIG. 3is ‘32’), the command queue136may queue only ‘32’ commands provided from the host102in the slots. If commands are queued in all of the ‘32’ slots, the host102cannot provide a command to the memory system110anymore. When one or more of the commands queued in the ‘32’ slots are processed to create an empty slot, the host102can provide a command to the memory system110, and the provided command may be queued in the empty slot within the command queue136. Furthermore, when the command queue136has no empty slots, the host102may generate the candidate LBA list200.

Referring back toFIG. 1, the queue manager138may manage the command queue136. Specifically, the queue manager138may check whether the command queue136has empty slots. If the command queue136has no empty slots, the queue manager138may provide the host102with information indicating that the command queue136has no empty slots (hereafter, referred to as empty slot information). The host102may determine whether to provide a command to the memory system110, based on the empty slot information. Furthermore, the queue manager138may decide a processing order of commands queued in the command queue136. If the command queue136does not have a FIFO structure, the commands queued in the command queue136may be processed according to the processing order decided by the queue manager138. The queue manager138may inform the processor134of the commands based on the decided processing order.

The data I/O circuit140may receive data corresponding to a command from the host102and store the received data, under control of the processor134. The data I/O circuit14may have a FIFO structure like the command queue136.

For example, when the host102provides a read command to the memory system110, the data I/O circuit140may receive data such as LBA information corresponding to the read command from the host102. The data I/O circuit140may store the data under control of the processor134.

For another example, when the host102provides a write command to the memory system110, the data I/O circuit140may receive write data corresponding to the target of the write command from the host102. The data I/O circuit140may store the write data under control of the processor134.

For another example, when the host102provides a forecast command to the memory system110, the data I/O circuit140may receive the candidate LBA list200. The data I/O circuit140may store the data associated with the candidate LBA list200under control of the processor134.

The data I/O circuit140may provide the data received from the host102to the memory144under control of the processor134.

When the host102provides a read command to the memory system110, the data I/O circuit140may output user data corresponding to the read command to the host102under control of the processor134. The user data may be loaded to the memory144from the memory device150.

The memory interface142may interface the controller130and the memory device150, such that the controller130controls the memory device150in response to a request of the host102.

The memory144may serve as a working memory of the memory system110and the controller130, and store data for driving the memory system110and the controller130.

The memory144may be implemented as a volatile memory. For example, the memory144may be implemented as a static random access memory (SRAM) or a dynamic random access memory (DRAM). In an embodiment, the memory144may be present inside the controller130. Alternatively, the memory144may be present outside the controller130. At this time, the memory144may be implemented as an external volatile memory to and from which data from the controller130is inputted and outputted through the memory interface142.

The memory144may store data required for performing a data write/read operation between the host102and the memory device150and data during the data write/read operation. For example, when the host102provides a read command to the memory system110, the memory144may load read data to be provided to the host102from the memory device150, and temporarily store the read data. For another example, when the host102provides a forecast command to the memory system110, the memory144may store the candidate LBA list200provided from the host102. The memory144may include a program memory, a data memory, a write buffer/cache, a read buffer/cache, a data buffer/cache, a map buffer/cache and the like, in order to store the data.

The processor134may control overall operations of the memory system110. In response to a write command, a read command and a forecast command of the host102, the processor134may perform operations corresponding to the respective commands on the memory device150. The operation of the processor134will be described in more detail with reference toFIG. 4.

Hereafter, referring toFIG. 4, command operations which are performed in the memory system110in accordance with the present embodiment will be described in detail.

FIG. 4is a conceptual diagram illustrating an operation of the memory system110in accordance with an embodiment.FIG. 4illustrates only the memory144and the memory device150, but data may be moved from the memory144to the memory device150or from the memory device150to the memory144, under control of the processor134.

In accordance with an embodiment, when the host102provides a read command to the memory system110, the processor134may perform a read operation. Specifically, the processor134may retrieve a map segment from the memory144. The map segment may correspond to an LBA provided from the host102with the read command. If the map segment is not retrieved from the memory144, the processor134may load the map segment from the memory device150. Then, the processor134may load data corresponding to the read command from the memory device150based on the loaded map segment, store the loaded data in the memory144, and output the stored data through the host interface132.

The controller130may perform command operations corresponding to the plurality of commands received from the host102. For example, when the host102provides write commands to the memory system110, the controller130may perform program operations. At this time, the controller130may store user data corresponding to the write commands by programming the user data to memory blocks452to484of the memory device150. Further, the controller130may generate and update meta data for the user data according to the operation of programming the user data to the memory blocks452to484, and then store the meta data in the memory blocks452to484of the memory device150.

The controller130may generate and update information indicating that the user data are stored in pages in the plurality of blocks452to484of the memory device150, for example, first map data and second map data. In other words, the controller130may generate and update logical segments of the first map data, i.e. L2P segments, and physical segments of the second map data, i.e. P2L segments, and then store the L2P segments and the P2L segments in the pages in the memory blocks452to484of the memory device150.

For example, the controller130may store the user data in the data buffer410in the memory144of the controller130. The user data may correspond to the write commands provided from the host102. Furthermore, after storing data segments412of the user data in the data buffer410, the controller130may store the data segments412in the data buffer410into the pages in the memory blocks452to484of the memory device150. As the data segments412of the user data corresponding to the write commands provided from the host10are programmed and stored into the pages in the memory blocks452to484of the memory device150, the controller130may generate and update the first map data and the second map data, and store the first map data and the second map data in the map buffer420in the memory144of the controller130. That is, the controller130may store the L2P segments422of the first map data and the P2L segments424of the second map data for the user data in the map buffer420. As described above, the L2P segments422of the first map data and the P2L segments424of the second map data or a map list for the L2P segments422of the first map data and a map list for the P2L segments424of the second map data may be stored in the map buffer420in the memory144of the controller130. Furthermore, the controller130may store the L2P segments422of the first map data and the P2L segments424of the second map data, stored in the map buffer420, into the pages in the memory blocks452to484of the memory device150.

For another example, the controller130may perform read operations corresponding to read commands provided from the host102. At this time, the controller130may read user data stored in the memory blocks452to484of the memory device150, based on map segments of user data corresponding to the read commands, for example, the L2P segments422of the first map data and the P2L segments424of the second map data. However, when a map segment corresponding to an LBA provided with a read command from the host102is not present in the map buffer420, the controller130may load the map segment into the map buffer420and check the loaded map segment. Then, the controller130may read user data stored in pages of the corresponding memory blocks among the memory blocks452to484of the memory device150. Furthermore, the controller130may store the data segments412of the read user data in the data buffer410, and then output the data segments412to the host102.

For another example, when the host102provides forecast commands to the memory system110, the controller130may perform operations corresponding to the forecast commands. At this time, the controller130may check the candidate LBA list200stored in the memory144, load a map segment corresponding to a candidate LBA stored in the candidate LBA list200from the memory device150, and store the loaded map segment in the map buffer420. However, when the map segment corresponding to the candidate LBA is already present in the map buffer420, the controller130may utilize the map segment which is already present in the map buffer420. By loading a map segment corresponding to a read command to be provided afterwards by an operation corresponding to the forecast command (hereafter, referred to as a forecast operation) to the map buffer420in advance, the controller130may rapidly perform a read operation.

Hereafter, referring toFIGS. 5A to 8B, an operation of the data processing system100in accordance with the present embodiment will be described. Specifically, an operation of the data processing system100for processing a forecast command will be described. For convenience of description, suppose that ‘n’ of the candidate LBA list200is ‘100’, and ‘m’ of the command queue136is ‘32’. Furthermore, suppose that the size of data by a user request is large enough to generate the candidate LBA list. In addition, suppose that the command queue136and the data I/O circuit140have a FIFO structure. However, this is only an example, and the present embodiment is not limited thereto. Furthermore, only components required for description are illustrated in each of the drawings.

FIG. 5Ais a conceptual diagram illustrating operations of the host102and the controller130in accordance with an embodiment. In particular,FIG. 5Ais a conceptual diagram illustrating the operation of generating the candidate LBA list200in accordance with the present embodiment.

First, the host102may provide the memory system110with a plurality of commands generated by a user request. The commands provided from the host102may be queued in the command queue136within the host interface132.

For example, ‘32’ commands may be queued in the plurality of slots within the command queues136, respectively. When the plurality of commands are all queued in the respective ‘32’ slots, the queue manager138may check that the command queue136has no empty slot. The queue manager138may provide empty slot information to the host102in order to inform the host102that there is no empty slot.

The host102receiving the empty slot information cannot provide a command to the memory system110until an empty slot occurs in the command queue136. At this time, the list generator104in the host102may generate the candidate LBA list200having candidate LBAs stored therein, the candidate LBAs corresponding to a plurality of read commands, respectively, which are to be generated afterwards by a user request. The list generator104may store the candidate LBA list.

FIG. 5Bis a flowchart illustrating the process of generating the candidate LBA list200in accordance with the present embodiment.

Referring toFIG. 5B, in step S501, the host102may generate a read command or write command according to a user request.

In step S503, the host102may determine whether the command queue136has an empty slot, based on empty slot information provided by the queue manager138.

When it is determined that there is an empty slot (‘Yes’ in step S503), the host102may provide the generated read or write command to the memory system110in step S505. The provided command may be queued in the empty slot within the command queue136.

On the other hand, when it is determined that there is no empty slot (‘No’ in step S503), the list generator104may reset the value of ‘i’ (i.e., i=1) to generate the candidate LBA list200in step S507. Here, ‘i’ represents the number of the candidate LBA list200.

In step S509, the list generator104may store an ithcandidate LBA in an ithplace within the candidate LBA list200. The ithcandidate LBA may correspond to a read command to be generated afterwards.

In step S511, the list generator104may determine whether the value of ‘i’ is greater than or equal to ‘100’. Since it is assumed that ‘n’ is ‘100’, the value of ‘i’ may be compared to ‘100’.

When it is determined that the value of ‘i’ is less than ‘100’. (‘No’ in step S511), the list generator104may increase the value of ‘i’ by ‘1’ (i.e., i=1++) to continuously store a candidate LBA in the candidate LBA list200through steps S509and S511.

On the other hand, when it is determined that the value of ‘i’ is greater than or equal to ‘100’ (‘Yes’ in step S511), the list generator104may complete the generating of the candidate LBA list200. As a result, the list generator104may generate the candidate LBA list200in which the first to 100th candidate LBAs are stored as illustrated inFIG. 5A.

Although not illustrated inFIG. 5B, the list generator104may generate another candidate LBA list different from the generated candidate LBA list, if there are more candidate LBAs than the 100 candidate LBAs corresponding to the user request. For example, when there are 150 candidate LBAs corresponding to a user request, the list generator104may generate a first LBA list including first to 100th candidate LBAs, and generate a second candidate LBA list including 101st to 150th candidate LBAs.

FIG. 6Ais a conceptual diagram illustrating operations of the host102and the controller130in accordance with an embodiment. In particular,FIG. 6Ais a conceptual diagram illustrating the operation of the host102to provide the forecast command and the candidate LBA list200to the controller130, and the operation of the controller130to process the forecast command and the candidate LBA list200in accordance with the present embodiment.

When an empty slot occurs in the plurality of slots within the command queue136, the queue manager138may provide empty slot information to inform the host102of the occurrence of the empty slot. Then, the host102may provide the forecast command and the candidate LBA list200to the memory system110based on the empty slot information. The forecast command may include information on the ‘number’ of the candidate LBA list200, which is stored in the candidate LBA list200.

First, the command queue136may queue the forecast command provided from the host102in the empty slot. Since it was assumed that the command queue136has a FIFO structure, the forecast command may be first queued in the 32nd slot.

The data I/O circuit140may receive the candidate LBA list200from the host120with the forecast command. The data I/O circuit140may store the candidate LBA list200under control of the processor134. The provided candidate LBA list200may be stored in the memory144under control of the processor134.

After a plurality of commands queued before the forecast command are completely processed, the processing of the forecast command may be started. When the processing of the plurality of commands queued before the forecast command is completed, the forecast command may be queued in the first slot. At this time, the queue manager138may request the processor134to start processing the forecast command queued in the first slot. Then, the processor134may perform a forecast operation based on information on the last ‘number’ stored in the candidate LBA list200in the forecast command.

FIG. 6Bis a flowchart illustrating the process of providing the forecast command and the candidate LBA list200to the memory system110in accordance with the present embodiment.

Referring toFIG. 6B, in step S601, the host102may generate the candidate LBA list200, and store the generated candidate LBA list200therein until the candidate LBA list200is provided to the memory system110.

In step S603, the host102may compare the number within the candidate LBA list200to a preset threshold value. That is, referring toFIG. 6A, the host102may check whether 100 candidate LBAs are stored in the candidate LBA list200.

When it is checked that the number of candidate LBAs stored in the candidate LBA list200is less than the preset threshold value (‘No’ in step S603), the procedure may return to step S601, and the host102may continuously generate the candidate LBA list200.

On the other hand, when it is checked that the number of candidate LBAs stored in the candidate LBA list200is greater than or equal to the preset threshold value (‘Yes’ in step S603), the host102may determine whether an empty slot is present in the command queue136, based on the empty slot information provided from the queue manager138, in step S605.

When it is determined that there is no empty slot (‘No’ in step S605), the host102may wait until an empty slot occurs in the command queue136.

On the other hand, when it is determined that there is an empty slot (‘Yes’ in step S605), the host102may provide a forecast command (CMD) and the candidate LBA list200to the memory system110in step S607.

In step S609, the command queue136may queue the forecast command in the empty slot.

In step S611, the data I/O circuit140may receive the candidate LBA list200. The data I/O circuit140may store the candidate LBA list200under control of the processor134.

Although steps S609and S611are separately described, the operations corresponding to steps S609and S611, respectively, may be performed in parallel to each other.

In step S613, the candidate LBA list200may be stored in the memory144under control of the processor134.

FIG. 6Cis a flowchart illustrating a point of time that the forecast command is processed in accordance with the present embodiment.

Referring toFIG. 6C, in step S611, a command queued in the first slot may be preferentially processed according to the characteristic of the command queue136having a FIFO structure. At this time, the queue manager138may determine whether to start processing the forecast command queued in step S609ofFIG. 6B.

When it is determined that the forecast command is not a processing target (‘No’) in step S621), the queue manager138may process a command having a priority to the forecast command queued in the command queue136in step S623. Specifically, the queue manager138may request the processor134to process the command queued in the first slot. When the processing of the command queued in the first slot is completed, a command queued in the second slot may be queued in the first slot, and the queue manager138may request the processor134to process the command queued in the first slot. Then, the procedure may return to step S621, and the queue manager138may determine whether to start processing the forecast command.

On the other hand, when it is determined that the forecast command is the processing target (‘Yes’ in step S621), the queue manager138may process the forecast command. Specifically, the queue manager138may request the processor134to process the forecast command. Then, the processor134may perform a forecast operation based on information on the last ‘number’ stored in the candidate LBA list200included in the forecast command.

FIG. 7Ais a conceptual diagram illustrating an operation of processing a forecast command in accordance with an embodiment.

Referring toFIG. 7A, the processor134may receive a processing request for a forecast command from the queue manager138. The processor134may check the candidate LBA list200stored in the memory144. The processor134may load a map segment corresponding to a candidate LBA from the memory device150to the map buffer420, based on the candidate LBA list200. However, when the map segment corresponding to the candidate LBA is already present in the map buffer420, the processor134may retrieve a map segment corresponding to the next candidate LBA. For example, the processor134may first retrieve a map segment from the map buffer420within the memory144. The map segment may correspond to a first LBA LBA1which is a first candidate LBA stored in the candidate LBA list200. If the map segment corresponding to the first LBA LBA1is not present in the map buffer420, the processor134may read the map segment from the memory device150, and store the read map segment in the map buffer420. On the other hand, when the map segment corresponding to the first LBA LBA1is present in the map buffer420, the processor134may directly retrieve a map segment corresponding to the second candidate LBA.

When the map segment corresponding to the first candidate LBA is completely loaded, the processor134may first retrieve a map segment from the map buffer420within the memory144. The map segment may correspond to a 43rd LBA LBA43which is a second candidate LBA. If the map segment corresponding to the 43rd LBA LBA43is not present in the map buffer420, the processor134may read the map segment from the memory device150, and store the read map segment in the map buffer420. On the other hand, when the map segment corresponding to the 43rd LBA LBA43is present in the map buffer420, the processor134may directly retrieve a map segment corresponding to a third candidate LBA.

According to the same principle, the processor134may store a map segment in the map buffer420. The map segment may correspond to a 250th LBA LBA250which is a 100th candidate LBA.

Furthermore, the processor134may check the end point of the forecast operation based on information on the last ‘number’ stored in the candidate LBA list200included in the forecast command. For example, since the last number stored in the candidate LBA list200is ‘100’, the processor134may complete the forecast operation by storing the map segment, corresponding to the 250th LBA LBA250which is the 100th candidate LBA, in the map buffer420.

After the forecast operation is completed, the processor134may inform the queue manager138of the completing of the forecast operation. In response, the queue manager138may erase the forecast command queued in the command queue136.

The processor134receiving the processing request for the forecast command from the queue manager138may check the candidate LBA list200stored in the memory144.

FIG. 7Bis a flowchart illustrating the operation of processing the forecast command in accordance with the present embodiment.

Referring toFIG. 7B, in step S701, the processor134may start processing the forecast command according to a request of the queue manager138.

In step S703, the processor134may set an initial value (i.e., i=1) in order to load a map segment corresponding to a candidate LBA stored in the candidate LBA list200.

In step S705, the processor134may check an ithcandidate LBA stored in the candidate LBA list200.

In step S707, the processor134may determine whether a target map segment corresponding to the ithcandidate LBA is retrieved from the map buffer420within the memory144.

If it is determined that the target map segment corresponding to the ithcandidate LBA is not retrieved from the map buffer420(‘No’ in step S707), the processor134may control the memory device to detect the target map segment, and obtain the read target map segment from the memory device150, in step S709.

In step S711, the processor134may receive and store the target map segment provided from the memory device150in the map buffer420within the memory144.

In step S713, the processor134may check whether the current value of ‘i’ is the last number, based on information on the last number stored in the candidate LBA list200included in the forecast command.

On the other hand, when it is determined that the target map segment corresponding to the ithcandidate LBA is retrieved from the map buffer420(‘Yes’ in step S707), the operations corresponding to steps S709and S711may not be performed, but the processor134may directly check whether the current value of ‘i’ is the last number, based on the information on the last number stored in the candidate LBA list200included in the forecast command, in step S713.

If it is determined that ‘i’ is not the last number (‘No’ in step S713), the processor134may increase the value ‘i’ of by ‘1’ (i.e., i=1++) to perform the operations corresponding to steps S705to S713, respectively, or to control the memory device150, in step S715.

On the other hand, when it is determined that the value of ‘i’ is the last number (‘Yes’ in step S713), the processing operation for the forecast command may be completed. Although not illustrated in the drawing, the processor134may inform the queue manager138of the completing of the forecast operation, after the forecast operation is completed, and the queue manager138may erase the forecast command queued in the command queue136. The processor134receiving the processing request for the forecast command from the queue manager138may check the candidate LBA list200stored in the memory144.

FIG. 8Ais a conceptual diagram illustrating the process of processing a read command in accordance with an embodiment. In particular,FIG. 8Aillustrates processing a read command corresponding to the first LBA LBA1which is the first candidate LBA recorded in the candidate LBA list200.

Referring toFIG. 8A, the host102may set the read command including information on the first LBA LBA1, and provide the read command to the memory system110.

The command queue136may queue the read command provided from the host102in an empty slot. For convenience of description, suppose that the read command is queued in the first slot. The queue manager138may request the processor134to process the read command queued in the first slot. Then, the processor134may start a read operation corresponding to the read command.

First, the processor134may retrieve a map segment corresponding to the first LBA LBA1. However, as described with reference toFIGS. 5A to 7B, the map segment corresponding to the first LBA LBA1may be stored in the map buffer420. Therefore, the processor134may read user data corresponding to the read command from the memory device150based on the map segment stored in the map buffer420.

The processor134may store the user data in the data buffer410of the memory144. The user data may correspond to the first LBA LBA1in the read command provided from the host102.

The processor134may provide the user data to the data I/O circuit140. In response, the data I/O circuit140may finally output the user data to the host102under control of the processor134.

FIG. 8Bis a flowchart illustrating the process of processing the read command in accordance with the present embodiment. In particular,FIG. 8Bshows the process of processing the read command corresponding to the first LBA LBA1which is the first candidate LBA recorded in the candidate LBA list200, as described with reference toFIG. 8A.

Referring toFIG. 8B, in step S801, the host102may provide a read command to the memory system110.

In step S803, the command queue136may queue the provided read command in an empty slot.

In step S805, the queue manager138may determine whether the read command corresponds to the processing order.

When it is determined that the read command does not correspond to the processing order (‘No’ in step S805), the queue manager138may request the processor134to process a command having a priority to the read command. Then, in step S805, the queue manager138may determine whether the read command corresponds to the processing order.

On the other hand, when it is determined that the read command corresponds to the processing order (‘Yes’ in step S805), the queue manager138may request the processor134to process the read command in step S809.

In step S811, the processor134may retrieve a map segment including an LBA corresponding to the read command from the map buffer420, read user data from the memory device150based on the retrieved map segment, and store the read user data in the data buffer410. Under control of the processor134, the user data stored in the data buffer410may be moved to the data I/O circuit140.

In step S813, the data I/O circuit140may output the user data to the host102under control of the processor134.

As described above, when the host102cannot provide a command to the memory system110, the host102may generate a list of candidate LBAs for data to be read afterwards, and provide only the list to the memory system110. Thus, the memory system110may predict that a read command will be provided in the future, based on the list, even though the read command is not directly provided. Then, the memory system110may load a map segment to the controller130from the memory device150. As a result, the time required for retrieving the map segment may be reduced, and data requested by a user may be quickly outputted by as much as the time required for retrieving the map segment is reduced.

FIG. 9is a diagram schematically illustrating another example of a data processing system6200including the memory system in accordance with an embodiment.

Referring toFIG. 9, the data processing system6200may include a memory device6230having one or more nonvolatile memories (NVMs) and a memory controller6220for controlling the memory device6230. The data processing system6200may serve as a storage medium such as a memory card (e.g., CF card, SD card or the like) or USB device, as described with reference toFIG. 1. The memory device6230may correspond to the memory device150in the memory system110illustrated inFIG. 1, and the memory controller6220may correspond to the controller130in the memory system110illustrated inFIG. 1.

The memory controller6220may control a read, write or erase operation on the memory device6230in response to a request of the host6210. The memory controller6220may include one or more central processing units (CPUs)6221, a buffer memory such as a random access memory (RAM)6222, an error correction code (ECC) circuit6223, a host interface6224and a memory interface such as an NVM interface6225.

FIG. 10is a diagram schematically illustrating another example of the data processing system including the memory system in accordance with an embodiment. For example,FIG. 10schematically illustrates a solid state drive (SSD)6300to which the memory system may be applied.

Referring toFIG. 10, the SSD6300may include a controller6320and a memory device6340including a plurality of nonvolatile memories (NVMs). The controller6320may correspond to the controller130in the memory system110ofFIG. 1, and the memory device6340may correspond to the memory device150in the memory system ofFIG. 1.

More specifically, the controller6320may be connected to the memory device6340through a plurality of channels CH1to CHi. The controller6320may include one or more processors6321, an error correction code (ECC) circuit6322, a host interface6324, a buffer memory6325and a memory interface, for example, a nonvolatile memory interface6326.

The host interface6324may provide an interface function with an external device, for example, the host6310, and the nonvolatile memory interface6326may provide an interface function with the memory device6340connected through the plurality of channels.

Furthermore, a plurality of SSDs6300to which the memory system110ofFIG. 1is applied may be provided to embody a data processing system, for example, a redundant array of independent disks (RAID) system. The RAID system may include the plurality of SSDs6300and a RAID controller for controlling the plurality of SSDs6300.

FIG. 11is a diagram schematically illustrating another example of the data processing system including the memory system in accordance with an embodiment, for example, a user system6900.

Referring toFIG. 11, the user system6900may include a user interface6910, a memory module6920, an application processor6930, a network module6940, and a storage module6950.

The application processor6930may be provided as System-on-Chip (SoC).

The memory module6920may be used as a main memory, work memory, buffer memory or cache memory of the user system6900. For example, the application processor6930and the memory module6920may be packaged and mounted, based on Package on Package (PoP).

The network module6940may communicate with external devices. For example, the network module6940may not only support wired communication, but also support various wireless communication protocols such as code division multiple access (CDMA), global system for mobile communication (GSM), wideband CDMA (WCDMA), CDMA-2000, time division multiple access (TDMA), long term evolution (LTE), worldwide interoperability for microwave access (WiMAX), wireless local area network (WLAN), ultra-wideband (UWB), Bluetooth, wireless display (WI-DI), thereby communicating with wired/wireless electronic devices, particularly mobile electronic devices. Therefore, the memory system and the data processing system, in accordance with an embodiment of the present invention, can be applied to wired/wireless electronic devices. The network module6940may be included in the application processor6930.

The storage module6950may store data, for example, data received from the application processor6930, and then may transmit the stored data to the application processor6930. The storage module6950may be embodied by a nonvolatile semiconductor memory device such as a phase-change RAM (PRAM), a magnetic RAM (MRAM), a resistive RAM (ReRAM), a NAND flash, NOR flash and 3D NAND flash, and provided as a removable storage medium such as a memory card or external drive of the user system6900. The storage module6950may correspond to the memory system110described with reference toFIG. 1. Furthermore, the storage module6950may be embodied as an SSD as described above with reference toFIG. 10.