[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

WO2017026740A1 - 전자 장치 및 이의 데이터 압축 방법 - Google Patents

전자 장치 및 이의 데이터 압축 방법 Download PDF

Info

Publication number
WO2017026740A1
WO2017026740A1 PCT/KR2016/008596 KR2016008596W WO2017026740A1 WO 2017026740 A1 WO2017026740 A1 WO 2017026740A1 KR 2016008596 W KR2016008596 W KR 2016008596W WO 2017026740 A1 WO2017026740 A1 WO 2017026740A1
Authority
WO
WIPO (PCT)
Prior art keywords
page
data
electronic device
memory
compressed
Prior art date
Application number
PCT/KR2016/008596
Other languages
English (en)
French (fr)
Inventor
한상복
구진규
김현식
문선호
한충석
Original Assignee
삼성전자 주식회사
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 삼성전자 주식회사 filed Critical 삼성전자 주식회사
Priority to US15/750,733 priority Critical patent/US11226738B2/en
Priority to CN201680047598.7A priority patent/CN107924350B/zh
Publication of WO2017026740A1 publication Critical patent/WO2017026740A1/ko

Links

Images

Classifications

    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02Addressing or allocation; Relocation
    • G06F12/08Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601Interfaces specially adapted for storage systems
    • G06F3/0602Interfaces specially adapted for storage systems specifically adapted to achieve a particular effect
    • G06F3/0608Saving storage space on storage systems
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F11/00Error detection; Error correction; Monitoring
    • G06F11/07Responding to the occurrence of a fault, e.g. fault tolerance
    • G06F11/14Error detection or correction of the data by redundancy in operation
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02Addressing or allocation; Relocation
    • G06F12/0223User address space allocation, e.g. contiguous or non contiguous base addressing
    • G06F12/023Free address space management
    • G06F12/0238Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory
    • G06F12/0246Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory in block erasable memory, e.g. flash memory
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601Interfaces specially adapted for storage systems
    • G06F3/0628Interfaces specially adapted for storage systems making use of a particular technique
    • G06F3/0629Configuration or reconfiguration of storage systems
    • G06F3/0631Configuration or reconfiguration of storage systems by allocating resources to storage systems
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601Interfaces specially adapted for storage systems
    • G06F3/0628Interfaces specially adapted for storage systems making use of a particular technique
    • G06F3/0655Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices
    • G06F3/0658Controller construction arrangements
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601Interfaces specially adapted for storage systems
    • G06F3/0668Interfaces specially adapted for storage systems adopting a particular infrastructure
    • G06F3/0671In-line storage system
    • G06F3/0673Single storage device
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/06Arrangements for sorting, selecting, merging, or comparing data on individual record carriers
    • G06F7/14Merging, i.e. combining at least two sets of record carriers each arranged in the same ordered sequence to produce a single set having the same ordered sequence
    • HELECTRICITY
    • H03ELECTRONIC CIRCUITRY
    • H03MCODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
    • H03M7/30Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/10Providing a specific technical effect
    • G06F2212/1016Performance improvement
    • G06F2212/1024Latency reduction
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/10Providing a specific technical effect
    • G06F2212/1032Reliability improvement, data loss prevention, degraded operation etc
    • G06F2212/1036Life time enhancement
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/21Employing a record carrier using a specific recording technology
    • G06F2212/214Solid state disk
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/40Specific encoding of data in memory or cache
    • G06F2212/401Compressed data
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/72Details relating to flash memory management
    • G06F2212/7201Logical to physical mapping or translation of blocks or pages

Definitions

  • the present invention relates to an electronic device and a data compression method thereof. More specifically, the present invention proposes an electronic device and a data compression method thereof for efficiently managing a memory.
  • a memory deduplication technique is used to increase the available memory.
  • swap is a technique in which an OS frees available memory by periodically checking a memory and moving a process that is not expected to be performed for a while among processes running on the memory to a predetermined swap area.
  • an embodiment of the present invention provides an electronic device capable of removing redundant storage for a page including the same data when compressing and storing swapped-out pages. It provides a data compression method thereof.
  • a data compression method of an electronic device may include compressing a page, determining whether data included in the compressed page is stored in a memory, and including the result in the compressed page. If the stored data is the same as the data previously stored in the memory, the method may include merging the compressed page with the previously stored data.
  • the merging may include mapping the compressed page to a page of the memory including the pre-stored data.
  • the method may further include allocating a memory and storing the compressed page in the allocated memory.
  • the compressing may include changing a predetermined number of arbitrary bits included in the page to a specific value, and compressing the page including the arbitrary bit changed to the specific value.
  • merging the compressed page to the pre-stored data it may be characterized by.
  • the predetermined number of bits included in the page may be a bit included in a predetermined position in the page or a bit included in a variable position according to data included in the page. .
  • the electronic device compresses a memory and a page storing data, determines whether data included in the compressed page is stored in a memory, and determines that the compressed page If the data contained in the same as the data previously stored in the memory, it may include a control unit for controlling to merge the compressed page to the previously stored data.
  • the controller may map the compressed page to a page of the memory including the pre-stored data.
  • the controller receives an area of the memory and stores the compressed page in the area of the allocated memory. It may be characterized by.
  • the controller may be further configured to change a predetermined number of arbitrary bits included in the page to a specific value and compress the page including the arbitrary bit changed to the specific value.
  • control unit before the change to the specific value maps the value of the original data included in the arbitrary bits or the address where the value of the original data is stored, and merges the compressed page into the pre-stored data You can do
  • the predetermined number of bits included in the page may be a bit included in a predetermined position in the page or a bit included in a variable position according to data included in the page.
  • a page including the same or similar data is not stored in the swap area a plurality of times.
  • the memory acquisition efficiency can be improved.
  • FIG. 1 is a diagram illustrating a method of storing a compressed page in a swap area in general.
  • FIG. 2 is a diagram for a method of storing a compressed page in a swap area according to an embodiment of the present invention
  • 3A illustrates compressed data generated by compressing similar pages, respectively
  • 3B is a diagram illustrating a method of storing a compressed page in a swap area according to another embodiment of the present invention.
  • 3C and 3D illustrate pages changed to the same page according to another embodiment of the present invention.
  • FIG. 4 is a diagram illustrating a page frame number, a page storage address, and an index number mapping table that can be stored in an electronic device according to an embodiment of the present disclosure
  • FIG. 5 is a flowchart illustrating a data compression method according to an embodiment of the present invention.
  • FIG. 6 is a flowchart illustrating a data compression method according to an embodiment of the present invention.
  • FIG. 7 is a block diagram illustrating a configuration of an electronic device according to an embodiment of the present disclosure.
  • FIG. 8 is a flowchart illustrating a method of determining a magic bit by an electronic device according to an embodiment of the present disclosure
  • 9A and 9B are diagrams for describing a method of compressing a divided page according to an embodiment of the present invention.
  • first and second may be used to describe various components, but the components should not be limited by the terms. The terms are only used to distinguish one component from another.
  • the module or unit performs at least one function or operation, and may be implemented by hardware or software, or a combination of hardware and software.
  • the plurality of modules or the plurality of units may be integrated into at least one module except for the modules or units that need to be implemented with specific hardware, and are implemented as at least one processor (not shown). Can be.
  • FIG. 1 is a diagram illustrating a general method of storing a compressed page in a swap area.
  • the kernel of the electronic device attempts to secure more than a certain level of available memory in order to smoothly perform the memory allocation requested by the system. Therefore, when the kernel periodically checks the available memory of the system and the available memory falls below a certain level, the kernel may operate a thread called a swap daemon to secure available memory.
  • the swap daemon wakes up at the request of the kernel and stores the old pages of the currently used pages in secondary storage, such as a hard disk, and deletes the pages from memory. Can be secured.
  • a page is a continuous section having a fixed length in the virtual address space, and means a basic unit constituting the virtual address space.
  • a page may have a length of 4 kb.
  • Swap through compression does not store the old pages in secondary storage when the swap daemon performs a swap out.
  • the swap daemon may compress an old page and use it to allocate and store a memory pool in system memory.
  • a memory pool may mean a portion of system memory.
  • the compressed page is stored in the system memory, but according to an exemplary embodiment, the compressed page may be stored in secondary storage such as a disk or primary storage such as RAM.
  • the swap daemon When the swap daemon stores compressed pages in a memory pool, the swap daemon restores them to the state before they were compressed when a read / write request of the pages was performed to perform a swap in. Meta data may be stored together.
  • the I / O overhead is reduced, and the available memory is also increased by compressing and storing pages.
  • the electronic device may generate a compressed page 110 by compressing the page 100 that has been used for a swap-out since it has been used for a long time.
  • the electronic device may increase the available memory by storing the compressed page 110 in the swap area 120 (eg, system memory).
  • FIG. 2 is a diagram illustrating a method of storing a compressed page in a swap area according to an embodiment of the present invention.
  • the electronic device may determine the page 200 which is a target of swap-out as a page 200 which is the target of swap-out.
  • the page 200 that is the target of swap-out may be determined according to a setting or a user command.
  • the electronic device may compress the page 200.
  • the electronic device may determine whether data included in the compressed page 210 is stored in the swap area 220 of the memory.
  • the electronic device may store the compressed page 210 in the previously stored data 230. You can merge.
  • Merging of the compressed page 210 may mean that the electronic device maps the compressed page 210 to previously stored data 230 of the swap area 220. For example, the electronic device may map an address of the compressed page 210 to an address of the pre-stored data 230.
  • the electronic device By merging the data page described above, when the data included in the compressed page 210 is the same as the data 230 previously stored in the swap area 220, the electronic device does not store the same data a plurality of times.
  • the electronic device when data included in the compressed page 210 is not stored in the swap area 220, the electronic device creates a memory pool and stores the compressed page 210. It can be stored in the memory pool.
  • the electronic device can increase the memory securing efficiency by preventing data having the same contents from being stored in the swap area 120 a plurality of times.
  • the electronic device may perform initial booting and merge and store pages including the same data.
  • 3A is a diagram showing compressed data generated by compressing similar pages, respectively.
  • the first page 300 and the second page 310 differ in that data included in all bits is the same and only data included in one bit is used.
  • the n th bit 301 of the first page 300 includes '1', whereas the n th bit 311 of the second page 310 includes '0'.
  • the first page 300 and the second page 310 have very similar contents, but since the data contained in the n-th bit is different from each other, the first page 300 and the second page 310 are different from each other. Each compressed data is also different.
  • the compressed data 305 compressing the first page 300 and the compressed data 315 compressing the second page 310 may be different compressed data.
  • the compressed data 305 that compresses the first page 300 and the compressed data that compresses the second page 310 are each stored in swap area 340, although the included data is very similar.
  • FIG. 3B a method for improving memory efficiency by storing similar pages in the swap area only once in which the contents of the included data are not the same will be described.
  • the electronic device may change a predetermined number of bits included in the page 300 to a specific value.
  • the electronic device may set the bits 306, 307, 308, and 309 of specific positions of the page as magic bits.
  • the electronic device may change the data included in the predetermined magic bits 306, 307, 308, and 309 to a specific value such as '0'.
  • the specific value '0' is only an example, and may be determined as another value according to the initial setting of the electronic device, the type of application, or the user setting.
  • the electronic device may change data of the magic bit 309 including '1' to a specific value '0'.
  • the electronic device may generate the compressed data 330 by compressing the page 320 in which data of the predetermined magic bits 306, 307, 308, and 309 is changed to a specific value '0'. In this case, the electronic device may generate the original value before the change of the magic bits 306, 307, 308, and 309 as metadata 335.
  • the electronic device may determine whether the same data as the compressed data 330 is previously stored in the swap area 340. If it is determined that the same data 350 as the compressed data 330 is stored in the swap area 340, the electronic device may merge the compressed data 330 into the same data 350.
  • the electronic device may map the metadata 335 together while merging the compressed data 330 into the same pre-stored data 350.
  • the electronic device restores the same data 350 and the magic bits 306, 307, 308, and 309 of the restored data. ) May be replaced with a value included in the meta data 335 to obtain the original page 300.
  • 3C and 3D illustrate pages 360 and 370 changeable to the changed page 320 as shown in FIG. 3B according to another embodiment of the present invention.
  • data of '1', '0', '0', and '0' are sequentially sequenced to each of the magic bits 306, 307, 308, and 309 existing at a predetermined position. It is included.
  • the electronic device may change the magic bits 306, 307, 308, and 309 of the page 360 to a specific value '0' by the above-described method. Accordingly, the page 360 may be identical to the modified page 320 of FIG. 3B.
  • the electronic device may generate the compressed data 330 by compressing the page 320 in which data of the predetermined magic bits 306, 307, 308, and 309 is changed to a specific value '0'.
  • the electronic device may generate an original value before the change of the magic bits 306, 307, 308, and 309 as metadata, '1000'.
  • the electronic device may map the metadata '1000' together while merging the compressed data 330 into the pre-stored data 350 of the swap area 340.
  • the page 370 of FIG. 3D sequentially includes data of '1', '1', '1', and '1' in each of the magic bits 306, 307, 308, and 309 existing at predetermined positions. It is.
  • the electronic device may change the magic bits 306, 307, 308, and 309 of the page 370 to a specific value '0' by the above-described method. Accordingly, the page 370 may be identical to the modified page 320 of FIG. 3B.
  • the electronic device may generate the compressed data 330 by compressing the page 320 in which data of the predetermined magic bits 306, 307, 308, and 309 is changed to a specific value '0'.
  • the electronic device may generate the original value before the change of the magic bits 306, 307, 308, and 309 as metadata, '1111'.
  • the electronic device may map the metadata “1111” together while merging the compressed data 330 into the pre-stored data 350 of the swap area 340.
  • the electronic device may map similar pages in which the remaining data is the same except for a part of the data included in the magic bits 306, 307, 308, and 309 to the same area of the swap area. Therefore, the electronic device can increase the available memory efficiency.
  • the magic bit described with reference to FIGS. 3A to 3D may mean a bit in which a value of data is frequently changed among bits included in the page while storing the data while changing the data a plurality of times.
  • the electronic device may perform an operation for determining a magic bit for all pages. However, in operation S800, the electronic device may determine whether an arbitrary page is a page selected for determining the magic bit in order to reduce the load generated by performing an operation for determining the magic bit.
  • the electronic device may perform a specific operation such as memset or memcpy on the plurality of pages.
  • pages including the same data may be selected as pages for determining a magic bit.
  • the electronic device may store data for a page selected to determine a magic bit.
  • a plurality of pages for determining the magic bit may be selected.
  • the electronic device may store the stored data value in an old-page and store new data in the selected page.
  • the electronic device may compare the page where the old-page and the new data are stored. For example, the electronic device may determine whether the value stored in the bit included in the old-page and the bit at the same position of the page where the new data is stored is changed.
  • the electronic device may increment the counter by one for the bit whose data value is changed.
  • the electronic device may repeatedly perform the above-described operation. If it is determined in step S850 that the threshold time is taken, in step S860, the electronic device may calculate (the number of times the bit is changed) / (the number of data storages) for each bit included in the page.
  • the electronic device may determine the N bits as magic bits in the order in which the calculated values are large.
  • the electronic device may merge pages compressed by using magic bits.
  • the camera application requests about 700MB or more of memory.
  • the 700MB of memory may be used after being initialized to '0' through memset. Accordingly, the electronic device may select pages initialized by performing a memset as a page for obtaining a magic bit.
  • the electronic device may include a separate module for determining whether the page is a predetermined page for selecting a magic bit. Therefore, the method of determining the magic bit disclosed in FIG. 8 may be performed through the electronic device or the separate module included in the electronic device.
  • the unit compressed by the electronic device may be a page unit, but is not limited thereto.
  • the electronic device may divide one page 900 into two and compress the divided data 910 and 920, respectively.
  • the electronic device may divide one page 900 into two.
  • the electronic device may compress the divided data 910 and 920, respectively, to generate two compressed data 915 and 925.
  • the electronic device may store each of the two pieces of compressed data 915 and 925 by matching the original size values of the divided data 910 and 920.
  • the electronic device may divide the page, change the magic bit data of the divided page to a specific value, and then compress the page.
  • FIG. 9B a case in which most data of one page 930 is filled with '0' and data '1' is included at one end thereof is illustrated.
  • the electronic device may determine that some pages including only data '0' may be generated.
  • the electronic device may divide the page 930 to generate the first partial page 940 and the second partial page 950 including only data '0'.
  • the electronic device may generate the first partial compressed data 945 by compressing the first partial page 940 including only data '0'.
  • the electronic device may change the bit including the data '1' of the second partial page 950 to the data '0'.
  • the electronic device may generate the second partial compressed data 970 by compressing the changed second partial page 960 which is the same as the first partial page 940.
  • the electronic device may form data '1' of the second partial page 950 as metadata and map the data '1' to the second partial compressed data 970 and store the data.
  • the electronic device may store the first partial compressed data 945 and the second partial compressed data 970 in the same swap area. Can be stored.
  • the electronic device may map and store the second partial compressed data 970 by mapping the metadata.
  • the electronic device divides one page into two partial pages of the same size, and the electronic device may divide one page into a plurality of partial pages, and each of the some pages may be different from each other. It may be different.
  • the electronic device may display a page frame number (PFN) 410 of a compressed page, an address 420 of the compressed page, and the compression.
  • PPN page frame number
  • the table 400 including the index number 430, which is information about metadata of the page, may be stored.
  • each page may have a unique frame number. Therefore, when swapping out a compressed page, the electronic device may map an address of the compressed page to an address where a compressed page including the same data as the compressed page of a swap area exists. In this case, the electronic device may generate a table that maps the frame number 410 of the swapped out page and the address 420 of the compressed page including the same data.
  • the electronic device may add the original value of the magic bit to the table as an index value 430.
  • the index value 430 is not limited to the original value of the magic bit, but may be an address of an area in which the original value is stored.
  • the predetermined number of bits described above may be bits included in a predetermined position in the page or bits included in a variable position according to data included in the page.
  • the arbitrary bits may be predetermined in which number of each page is included and how many are included in one page. However, this is only an example, and the electronic device may set a magic bit whose position is variable according to an initial setting, a user setting, an execution program, or an application type.
  • the electronic device may compare pages that are subject to swap. As a result of the comparison, when the plurality of pages are determined to have the same data included in the remaining bits except for some bits (for example, four bits), the electronic device may set the excluded bits as magic bits. The electronic device may change the data included in the magic bit to a specific value and compress and swap out pages including the changed specific value by the above-described method.
  • step S500 the electronic device compresses a page.
  • the electronic device may select a page to be compressed and stored in order to perform a swap.
  • the electronic device may determine a page, etc., which takes a predetermined time or more from the last use as a page to be swapped out.
  • a page which is a target of swap-out may be determined according to a setting or a user command.
  • the electronic device determines whether data included in the compressed page is stored in the memory.
  • step S520 when a compressed page including the same data as the data included in the compressed page is pre-stored in the memory, in step S520, the electronic device merges the compressed page into the pre-stored page. For example, the electronic device may point the address of the compressed page to the storage address of the compressed page previously stored in the memory.
  • step S530 the electronic device is allocated a memory and the compressed memory is allocated to the allocated memory. Saved pages can be saved.
  • the electronic device may change a predetermined number of bits included in the page to a specific value. For example, the electronic device may set a bit of a specific position of a page as a magic bit. The electronic device may change the data included in the predetermined magic bit to a specific value such as '0'.
  • the specific value '0' is only an example, and may be determined as another value according to the initial setting of the electronic device, the type of application, or the user setting.
  • the electronic device may compress a page including any bits changed to a particular square. For example, the electronic device may generate compressed data by compressing a page in which data of a predetermined magic bit is changed to a specific value '0'. In this case, the electronic device may generate the original value before the change of the magic bit as metadata.
  • the electronic device may determine whether data included in the compressed page is stored in the memory. For example, the electronic device may determine whether the same data as the compressed data is previously stored in the swap area.
  • step S630 the electronic device stores the value of the original data included in the random bit or the value of the original data before changing to the specific value.
  • the compressed data may be merged with previously stored data.
  • the electronic device may generate the original data value of the magic bit as metadata while changing the data of the magic bit to a specific value and map the pre-stored data together with the compressed data.
  • the electronic device stores the original data of the magic bit separately generated while changing the data of the magic bit into a specific value in a predetermined area, and maps the compressed data to the prestored data.
  • the address of the predetermined area in which the value of the original data is stored may be mapped together.
  • the electronic device may map the metadata 335 together while merging the compressed data into the same pre-stored data 350.
  • the electronic device restores the same data, replaces the magic bit of the restored data with a value included in the metadata, and replaces the original page. You can get it.
  • the memory is allocated in step S6340 and included in the arbitrary bits before changing to the specific value in the allocated memory.
  • the compressed page may be stored by mapping an original data value or an address in which the original data value is stored.
  • the electronic device 700 may include a memory 710 and a controller 720.
  • the electronic device 700 may be a various device such as a mobile phone, a tablet PC, a digital camera, a camcorder, a notebook PC, a desktop, a PDA, an MP3, a smart glass, a smart watch, or a smart ring. Can be implemented.
  • the memory 710 is a component for storing data.
  • the memory 710 stores various programs and data for driving the electronic device 700.
  • the memory 710 may store an operating system (OS) for driving the electronic device 700, an application for performing various functions, and data used in an application execution process.
  • OS operating system
  • the memory 710 may store various software such as a base module, a sensing module, a communication module, a presentation module, a web browser module, a service module, and the like.
  • the memory 710 may include RAM, ROM, and primary storage including L1 and L2 cache memories, and secondary storage including a hard disk.
  • secondary storage of memory 710 may store pages that have been swapped out.
  • the controller 720 is a component for controlling the electronic device 700 as a whole.
  • the controller 720 may further include components such as a duplicate page determiner 721, a page merger 722, and a manager 733.
  • Components included in the controller 720 may be implemented as separate hardware modules. However, this is only an example, and the duplicate page determiner 721, the page merger 722, and the manager 733 are implemented in software, and the controller 720 stores the program in a nonvolatile memory. After copying the stored programs to RAM, the copied programs can be executed to perform a function.
  • the duplicate page determiner 721 may compress a page determined as a target of swap. In addition, it may be determined whether data included in the compressed page is pre-stored in the swap area.
  • the duplicate page determiner 721 may change data included in a predetermined arbitrary bit of the page to a specific value (eg, '0').
  • a page filled with a specific value in the arbitrary bits may be compressed.
  • the duplicate page determiner 721 may generate the original data value before the specific value change of the arbitrary bit as metadata.
  • the page merger 722 may merge pages according to the determination result of the duplicate page determiner 721. For example, when the duplicate page determiner 721 determines that the same data as the data included in the compressed page is pre-stored in the swap area of the memory 710, the page merger 722 may store the compressed data. A page may be merged with the previously stored page. For example, the page merger 722 may map a storage address of the compressed page to an address of the previously stored page.
  • the page merger 722 may merge the compressed page into the previously stored page and map the metadata together.
  • the page merger 722 stores the memory ( Some areas of the device 710 may be allocated, and the compressed page may be stored in the allocated area.
  • the manager 733 may manage the merged pages.
  • the management unit 733 may map and manage the frame page number of the compressed page and the storage address of the compressed page.
  • the management unit 733 stores the metadata containing the original value of the arbitrary bit, the frame page number of the compressed page and the compressed page. It can be managed by mapping with the address.
  • the compressed page may be restored using the storage address and the metadata.
  • control unit 720 includes separate function blocks 721 to 723, and the control unit 720 and each of the detailed function blocks 721 to 723 perform different functions. Although described, this is only one embodiment that can be implemented.
  • the controller 720 may perform a function performed by the duplicate page determiner 721.
  • the electronic device 700 As described above, even when the amount of pages swapped out increases, the page containing the same or similar data is not stored in the memory a plurality of times, thereby ensuring memory efficiency. To increase.
  • the controller of the electronic device may further include a flash memory or other nonvolatile memory.
  • the nonvolatile memory may store a program for performing each role of the controller.
  • controller of the electronic device may be implemented in a form including a CPU and a random access memory (RAM).
  • the CPU of the controller may copy the above-described programs stored in the nonvolatile memory to the RAM and then execute the copied programs to perform the functions of the above-described electronic device.
  • the controller is a component in charge of controlling the electronic device.
  • the controller may be used interchangeably with the same meaning as a central processing unit, a microprocessor, a controller, a processor, an operating system, and the like.
  • the controller of the electronic device may be implemented as a single chip system (System-on-a-chip or System on chip, SOC, SoC) together with other functional units such as a communication module included in the electronic device.
  • the data compression method of the electronic device may be coded in software and stored in a non-transitory readable medium.
  • Such non-transitory readable media can be mounted and used in a variety of devices.
  • the non-transitory readable medium refers to a medium that stores data semi-permanently and is readable by a device, not a medium storing data for a short time such as a register, a cache, a memory, and the like. Specifically, it may be a CD, a DVD, a hard disk, a Blu-ray disk, a USB, a memory card, a ROM, or the like.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Human Computer Interaction (AREA)
  • Quality & Reliability (AREA)
  • Memory System Of A Hierarchy Structure (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Memory System (AREA)

Abstract

전자 장치 및 이의 데이터 압축 방법이 개시된다. 본 발명의 전자 장치의 데이터 압축 방법에 따르면, 페이지를 압축하는 단계, 압축된 페이지에 포함된 데이터가 메모리에 저장되어 있는지 여부를 판단하는 단계 및 판단 결과 압축된 페이지에 포함된 데이터가 메모리에 기저장된 데이터와 동일한 경우, 압축된 페이지를 기저장된 데이터에 병합(merge)하는 단계를 포함한다. 따라서, 전자 장치는 동일하거나 유사한 데이터를 포함하는 페이지가 스왑(swap) 영역에 복수번 저장되지 않도록 함으로써, 메모리 확보 효율을 높일 수 있게 된다.

Description

전자 장치 및 이의 데이터 압축 방법
본 발명은 전자 장치 및 이의 데이터 압축 방법에 관한 것이다. 보다 구체적으로, 본 발명에서는, 메모리를 효율적으로 관리하기 위한 전자 장치 및 이의 데이터 압축 방법을 제안한다.
운영 체제(Operating System, OS)의 메모리를 효율적으로 관리하기 위해서, 가용 메모리를 늘리기 위한 메모리 중복 제거 기술이 사용된다.
예를 들면, 스왑(swap)은 OS가 주기적으로 메모리를 체크하고, 상기 메모리 상에서 수행중인 프로세스 중에서 당분간 수행되지 않을 것으로 예상되는 프로세스를 기설정된 swap 영역으로 옮김으로써, 가용 메모리를 확보하는 기술이다.
그러나, 메모리에서 스왑(swap) 영역으로 프로세스를 이동시키는 스왑-인(swap in) 및 스왑(swap) 영역에서 메모리로 프로세스를 이동시키는 스왑-아웃(swap out)에 의해 오버헤드가 발생하게 된다는 문제점이 있다. 또한, 플래시 기반 저장부를 사용하는 장치에서는 스왑(swap)을 이용함으로써, 플래시 메모리의 수명을 감소시키는 문제점이 존재할 수 있다.
한편, 상술한 문제점을 해결하기 위해, 스왑-아웃(swap out)되는 페이지를 압축하여 시스템 메모리에 저장하고, 다시 스왑-인(swap in)하는 경우 압축을 복원하여 사용하는 방법이 사용된다.
그러나 이와 같은 방법에 의해서도 압축된 데이터를 시스템 메모리에 저장함으로, 시스템 메모리의 사용량이 증가한다는 문제점이 존재한다.
이에 따라, I/O 오버헤드는 감소시키면서 시스템 메모리의 사용량도 일정 수준으로 유지할 수 있도록 하기 위한 방법에 대해 고찰할 필요성이 대두된다.
본 발명이 이루고자 하는 기술적 과제는 메모리를 효율적으로 관리하기 위해서, 스왑-아웃(swap out)된 페이지를 압축하여 저장하는 경우, 동일한 데이터를 포함하는 페이지에 대해 중복 저장을 제거할 수 있는 전자 장치 및 이의 데이터 압축 방법을 제공하는 것이다.
본 발명의 일 실시예에 따른 전자 장치의 데이터 압축 방법은, 페이지를 압축하는 단계, 상기 압축된 페이지에 포함된 데이터가 메모리에 저장되어 있는지 여부를 판단하는 단계 및 판단 결과 상기 압축된 페이지에 포함된 데이터가 상기 메모리에 기저장된 데이터와 동일한 경우, 상기 압축된 페이지를 상기 기저장된 데이터에 병합(merge)하는 단계를 포함할 수 있다.
그리고 상기 병합하는 단계는, 상기 압축된 페이지를 상기 기저장된 데이터가 포함된 상기 메모리의 페이지에 매핑하는 것을 특징으로 할 수 있다.
한편, 상기 판단 결과, 상기 압축된 페이지에 포함된 데이터가 상기 메모리에 저장되어 있지 않는 경우, 메모리를 할당받고, 상기 압축된 페이지를 상기 할당된 메모리에 저장하는 단계를 더 포함할 수 있다.
그리고 상기 압축하는 단계는, 상기 페이지에 포함된 기설정된 개수의 임의의 비트를 특정값으로 변경하고, 상기 특정값으로 변경된 상기 임의의 비트를 포함하는 상기 페이지를 압축하는 것을 특징으로 할 수 있다.
한편, 상기 병합하는 단계는, 상기 특정값으로 변경 전에 상기 임의의 비트에 포함된 오리지널 데이터의 값 또는 상기 오리지널 데이터의 값이 저장된 주소를 매핑하여, 상기 압축된 페이지를 상기 기저장된 데이터에 병합하는 것을 특징으로 할 수 있다.
그리고 상기 페이지에 포함된 기설정된 개수의 임의의 비트는, 상기 페이지에서 미리 결정된 위치에 포함된 비트이거나, 상기 페이지에 포함된 데이터에 따라 가변적인 위치에 포함된 비트인 것을 특징으로 하는 할 수 있다.
한편, 본 발명의 일 실시 예에 따른 전자 장치는, 데이터를 저장하는 메모리 및 페이지를 압축하고, 상기 압축된 페이지에 포함된 데이터가 메모리에 저장되어 있는지 여부를 판단하여, 판단 결과 상기 압축된 페이지에 포함된 데이터가 상기 메모리에 기저장된 데이터와 동일한 경우, 상기 압축된 페이지를 상기 기저장된 데이터에 병합(merge)하도록 제어하는 제어부를 포함할 수 있다.
그리고 상기 제어부는, 상기 압축된 페이지를 상기 기저장된 데이터가 포함된 상기 메모리의 페이지에 매핑하는 것을 특징으로 할 수 있다.
한편, 상기 제어부는, 상기 판단 결과, 상기 압축된 페이지에 포함된 데이터가 상기 메모리에 저장되어 있지 않는 경우, 상기 메모리의 영역을 할당받고, 상기 압축된 페이지를 상기 할당된 메모리의 영역에 저장하는 것을 특징으로 할 수 있다.
그리고 상기 제어부는, 상기 페이지에 포함된 기설정된 개수의 임의의 비트를 특정값으로 변경하고, 상기 특정값으로 변경된 상기 임의의 비트를 포함하는 상기 페이지를 압축하는 것을 특징으로 할 수 있다.
한편, 상기 제어부는, 상기 특정값으로 변경 전에 상기 임의의 비트에 포함된 오리지널 데이터의 값 또는 상기 오리지널 데이터의 값이 저장된 주소를 매핑하여, 상기 압축된 페이지를 상기 기저장된 데이터에 병합하는 것을 특징으로 할 수 있다.
그리고 상기 페이지에 포함된 기설정된 개수의 임의의 비트는, 상기 페이지에서 미리 결정된 위치에 포함된 비트이거나, 상기 페이지에 포함된 데이터에 따라 가변적인 위치에 포함된 비트인 것을 특징으로 할 수 있다.
본 발명의 실시 예에 따르면, 전자 장치는 스왑-아웃(swap out) 되는 페이지의 양이 증가하는 경우에도, 동일하거나 유사한 데이터를 포함하는 페이지가 스왑(swap) 영역에 복수번 저장되지 않도록 함으로써, 메모리 확보 효율을 높일 수 있게 된다.
도 1은 일반적으로 압축된 페이지를 스왑(swap) 영역에 저장하는 방법을 나타낸 도면,
도 2는 본 발명의 일 실시 예에 따라, 압축된 페이지를 스왑(swap) 영역에 저장하는 방법을 나타낸 도면,
도 3a는 유사한 페이지를 각각 압축하여 생성된 압축 데이터를 도시한 도면,
도 3b는 본 발명의 다른 실시 예에 따라, 압축된 페이지를 스왑(swap) 영역에 저장하는 방법을 나타낸 도면,
도 3c 및 도 3d는 본 발명의 다른 실시 예에 따라 동일한 페이지로 변경되는 페이지들을 나타낸 도면,
도 4는 본 발명의 일 실시 예에 따라, 전자 장치에서 저장 가능한 페이지 프레임 넘버, 페이지 저장 어드레스 및 인덱스 넘버 매핑 테이블을 도시한 도면,
도 5는 본 발명의 일 실시 예에 따른 데이터 압축 방법을 나타내는 흐름도,
도 6은 본 발명의 일 실시 예에 따른 데이터 압축 방법을 구체적으로 나타내는 흐름도,
도 7은 본 발명의 일 실시 예에 따른 전자 장치의 구성을 도시한 블럭도,
도 8을 본 발명의 일 실시 예에 따른 전자 장치가 매직 비트를 결정하는 방법을 나타내는 흐름도, 그리고
도 9a 및 도 9b는 본 발명의 일 실시 예에 따라 분할된 페이지를 압축하는 방법을 설명하기 위한 도면이다.
본 실시 예들은 다양한 변환을 가할 수 있고 여러 가지 실시 예를 가질 수 있는바, 특정 실시 예들을 도면에 예시하고 상세한 설명에 상세하게 설명하고자 한다. 그러나 이는 특정한 실시 형태에 대해 범위를 한정하려는 것이 아니며, 개시된 사상 및 기술 범위에 포함되는 모든 변환, 균등물 내지 대체물을 포함하는 것으로 이해되어야 한다. 실시 예들을 설명함에 있어서 관련된 공지 기술에 대한 구체적인 설명이 요지를 흐릴 수 있다고 판단되는 경우 그 상세한 설명을 생략한다.
제1, 제2 등의 용어는 다양한 구성요소들을 설명하는데 사용될 수 있지만, 구성요소들은 용어들에 의해 한정되어서는 안 된다. 용어들은 하나의 구성요소를 다른 구성요소로부터 구별하는 목적으로만 사용된다.
본 출원에서 사용한 용어는 단지 특정한 실시 예를 설명하기 위해 사용된 것으로, 권리범위를 한정하려는 의도가 아니다. 단수의 표현은 문맥상 명백하게 다르게 뜻하지 않는 한, 복수의 표현을 포함한다. 본 출원에서, "포함하다." 또는 "구성되다." 등의 용어는 명세서상에 기재된 특징, 숫자, 단계, 동작, 구성요소, 부품 또는 이들을 조합한 것이 존재함을 지정하려는 것이지, 하나 또는 그 이상의 다른 특징들이나 숫자, 단계, 동작, 구성요소, 부품 또는 이들을 조합한 것들의 존재 또는 부가 가능성을 미리 배제하지 않는 것으로 이해되어야 한다.
실시예에 있어서 ‘모듈’ 혹은 ‘부’는 적어도 하나의 기능이나 동작을 수행하며, 하드웨어 또는 소프트웨어로 구현되거나 하드웨어와 소프트웨어의 결합으로 구현될 수 있다. 또한, 복수의‘모듈’ 혹은 복수의‘부’는 특정한 하드웨어로 구현될 필요가 있는 ‘모듈’ 혹은 ‘부’를 제외하고는 적어도 하나의 모듈로 일체화되어 적어도 하나의 프로세서(미도시)로 구현될 수 있다.
도 1은 압축된 페이지를 스왑(swap) 영역에 저장하는 일반적인 방법을 설명하기 위한 도면이다.
일반적으로, 전자 장치의 커널은 시스템이 요청하는 메모리 할당(memory allocation)을 원활히 수행하기 위해, 가용 메모리를 일정 수준 이상으로 확보하고자 한다. 따라서, 커널은 주기적으로 시스템의 가용 메모리를 확인하고 가용 메모리가 일정 수준 이하로 떨어지게 되면, 스왑 데몬(swap daemon)이라는 스레드(thread)를 동작시켜서 가용 메모리를 확보할 수 있다.
상기 스왑 데몬(swap daemon)은 커널의 요청에 의해 깨어나게 되며, 현재 사용하는 페이지 중에서 사용한지 오래된 페이지를 하드디스크와 같은 2차 스토리지(storage)에 저장하고, 상기 페이지를 메모리에서 삭제함으로써 가용 메모리를 확보할 수 있다.
페이지는 가상의 주소 공간에서 고정된 길이를 가지는 연속적인 구간으로, 가상의 주소 공간을 구성하는 기본 단위를 의미한다. 일반적으로, 페이지는 4kb의 길이를 가질 수 있다.
스왑 데몬(swap daemon)이 사용한지 오래된 페이지를 2차 스토리지에 저장하는 동작을 수행하는 동안, 상당한 I/O 오버헤드가 발생할 수 있다. 상기 I/O 오버헤드를 해결하기 위한 방안으로는 압축을 통한 스왑(swap) 이 있다.
상기 압축을 통한 스왑(swap)은 스왑 데몬(swap daemon)이 스왑-아웃(swap out)을 수행할 때, 상기 사용한지 오래된 페이지를 2차 스토리지에 저장하지 않게 된다. 스왑 데몬(swap daemon)은 상기 사용한지 오래된 페이지를 압축하여 시스템 메모리(system memory)에 메모리 풀(memory pool)을 할당 받아 저장할 수 있다. 예를 들면, 메모리 풀은 시스템 메모리의 일부 영역을 의미할 수 있다.
다만, 압축된 페이지가 시스템 메모리에 저장되는 것은 일 실시 예에 불과할 뿐, 실시 예에 따라 압축된 페이지는 디스크와 같은 2차 스토리지 또는 RAM과 같은 1차 스토리지 등에 저장될 수 있다.
이하에서는, 압축된 페이지가 시스템 메모리에 저장되는 실시 예를 바탕으로 발명이 구현되는 방법을 설명한다.
그리고 스왑 데몬(swap daemon)은 압축된 페이지를 메모리 풀(memory pool)에 저장할 때, 추후 상기 페이지의 read/write 요청이 발생하여 스왑-인(swap in)을 수행하는 경우에 압축 전의 상태로 복원하기 위한 메타 데이터(meta data)를 함께 저장할 수 있다.
상술한 방법에 의해, I/O 오버헤드가 감소되고, 페이지를 압축하여 저장함으로써, 가용 메모리도 증가하게 된다.
다만, 스왑-아웃(swap out) 되는 페이지의 양이 증가하는 경우에는, 시스템 메모리의 사용량도 증가하게 되므로, 스왑-아웃(swap out)을 통한 메모리 확보 효율이 떨어질 수 있다.
구체적으로, 도 1에 도시된 바와 같이, 전자 장치는 사용한지 오래되어 스왑-아웃(swap out)의 대상이 된 페이지(100)를 압축하여, 압축된 페이지(110)를 생성할 수 있다. 그리고 전자 장치는 압축된 페이지(110)를 스왑 영역(120)(예를 들면, 시스템 메모리)에 저장함으로써, 가용 메모리를 증가시킬 수 있다.
스왑 영역(120)에 압축된 페이지(110)와 동일한 내용의 데이터(110-1, 110-2)가 기저장된 경우에도, 전자 장치는 압축된 페이지(110)를 다시 스왑 영역(120)에 저장하게 된다.
따라서, 상술한 바와 같이 스왑-아웃(swap out) 되는 페이지의 양이 증가하는 경우, 스왑 영역(120)에 동일한 내용의 데이터가 복수번 저장됨으로써, 스왑-아웃(swap out)을 통한 메모리 확보 효율이 떨어지게 된다.
이하에서는, 도 2를 참조하여, 상기 문제점들을 해결하면서 효율적으로 가용 메모리를 확보할 수 있는 방법을 설명한다.
도 2는 본 발명의 일 실시 예에 따라, 압축된 페이지를 스왑(swap) 영역에 저장하는 방법을 나타낸 도면이다.
구체적으로, 전자 장치는 마지막 사용으로부터 기설정된 시간 이상 소요된 페이지를 스왑-아웃(swap out)의 대상이 되는 페이지(200)로 결정할 수 있다. 그러나 이는 일 실시 예에 불과할 뿐, 설정 또는 사용자 명령에 따라 스왑-아웃(swap out)의 대상이 되는 페이지(200)가 결정될 수도 있다.
전자 장치는 상기 페이지(200)를 압축할 수 있다. 그리고 전자 장치는 압축된 페이지(210)에 포함된 데이터가 메모리의 스왑 영역(220)에 저장되어 있는지 여부를 판단할 수 있다.
판단 결과, 압축된 페이지(210)에 포함된 데이터가 상기 스왑 영역(220)에 기저장된 데이터(230)와 동일한 경우, 전자 장치는 상기 압축된 페이지(210)를 상기 기저장된 데이터(230)에 병합(merge)할 수 있다.
압축된 페이지(210)의 병합은, 전자 장치가 상기 압축된 페이지(210)를 스왑 영역(220)의 기저장된 데이터(230)에 매핑하는 것을 의미할 수 있다. 예를 들면, 전자 장치는 압축된 페이지(210)의 어드레스(address)를 기저장된 데이터(230)의 어드레스에 매핑할 수 있다.
상술한 데이터 페이지 병합에 의해, 전자 장치는 압축된 페이지(210)에 포함된 데이터가 상기 스왑 영역(220)에 기저장된 데이터(230)와 동일한 경우, 동일한 데이터를 복수번 저장하지 않게 된다.
한편, 판단 결과, 압축된 페이지(210)에 포함된 데이터가 상기 스왑 영역(220)에 저장되어 있지 않은 경우, 전자 장치는 메모리 풀(memory pool)을 생성하고, 상기 압축된 페이지(210)를 상기 메모리 풀에 저장할 수 있다.
결과적으로, 전자 장치는 스왑-아웃(swap out) 되는 페이지의 양이 증가하는 경우에도, 스왑 영역(120)에 동일한 내용의 데이터가 복수번 저장되지 않도록 함으로써, 메모리 확보 효율을 높일 수 있게 된다.
전자 장치는 최초 부팅을 수행하고, 메모리가 초기화 된 상태에서 상기 도 2에서 설명한 바와 같이, 동일한 데이터를 포함하는 페이지를 병합하여 저장할 수 있다.
한편, 도 3a는 유사한 페이지를 각각 압축하여 생성된 압축 데이터를 도시한 도면이다.
도 3a에 도시된 바와 같이, 모든 비트에 포함된 데이터는 동일하고, 하나의 비트에 포함된 데이터만 상이한 제1 페이지(300) 및 제2 페이지(310)를 예로 든다.
제1 페이지(300)의 n 번째 비트(301)는 '1'을 포함하지만, 제2 페이지(310)의 n 번째 비트(311)는 '0'을 포함한다.
제1 페이지(300) 및 제2 페이지(310)는 포함하는 데이터의 내용이 매우 유사하지만, n 번째 비트에 포함된 데이터가 서로 다르므로, 제1 페이지(300) 및 제2 페이지(310)를 각각 압축한 압축 데이터도 서로 달라진다. 구체적으로, 제1 페이지(300)를 압축한 압축 데이터(305) 및 제2 페이지(310)를 압축한 압축 데이터(315)는 서로 다른 압축 데이터가 될 수 있다.
따라서, 도 2에서 설명한 방법에 의해 압축된 데이터를 스왑-아웃(swap out)하는 경우, 제1 페이지(300)를 압축한 압축 데이터(305) 및 제2 페이지(310)를 압축한 압축 데이터(315)는, 포함된 데이터가 매우 유사함에도 불구하고, 스왑 영역(340)에 각각 저장되게 된다.
도 3b에서는, 포함된 데이터의 내용이 동일하지 않고, 유사한 페이지도 스왑 영역에 한번만 저장함으로써, 메모리 효율을 향상 시키기 위한 방법을 설명한다.
먼저, 전자 장치는 페이지(300)에 포함된 기설정된 개수의 임의의 비트를 특정값으로 변경할 수 있다. 예를 들면, 전자 장치는 페이지의 특정 위치의 비트(306, 307, 308, 309)를 매직 비트(magic bit)로 설정할 수 있다. 그리고 전자 장치는 기설정된 매직 비트(306, 307, 308, 309)에 포함된 데이터를 '0'과 같은 특정값으로 변경할 수 있다. 특정값이 '0'인 것은 일 실시 예에 불과할 뿐, 전자 장치의 초기 설정, 어플리케이션의 종류 또는 사용자 설정 등에 따라 다른 값으로 결정될 수도 있다.
도 3b에 도시된 실시 예에서, 매직 비트(306, 307, 308, 309) 중 일부 매직 비트(306, 307, 308)는 이미 '0'을 포함한다. 따라서, 전자 장치는 '1'을 포함하는 매직 비트(309)의 데이터를 특정값 '0'으로 변경할 수 있다.
전자 장치는 기설정된 매직 비트(306, 307, 308, 309)의 데이터가 특정값 '0'으로 변경된 페이지(320)를 압축하여, 압축된 데이터(330)를 생성할 수 있다. 이때, 전자 장치는 매직 비트(306, 307, 308, 309)의 변경 전 오리지널 값을 메타 데이터(335)로 생성할 수 있다.
전자 장치는 압축된 데이터(330)와 동일한 데이터가 스왑 영역(340)에 기저장되어 있는지 여부를 판단할 수 있다. 판단 결과, 스왑 영역(340)에 압축된 데이터(330)와 동일한 데이터(350)가 저장된 것으로 판단되면, 전자 장치는 압축된 데이터(330)를 동일한 데이터(350)에 병합할 수 있다.
그리고 전자 장치는 압축된 데이터(330)를 기저장된 동일한 데이터(350)에 병합하면서, 상기 메타 데이터(335)를 함께 매핑할 수 있다.
따라서, 추후 압축된 데이터(330)에 대해 스왑-인(swap in)을 수행하는 경우, 전자 장치는 동일한 데이터(350)를 복원하고, 상기 복원된 데이터의 매직 비트(306, 307, 308, 309)를 메타 데이터(335)에 포함된 값으로 치환하여, 오리지널 페이지(300)를 획득할 수 있게 된다.
도 3c 및 도 3d는 본 발명의 또 다른 실시예에 의해, 도 3b에 도시된 바와 같이 변경된 페이지(320)로 변경 가능한 페이지들(360, 370)을 도시한 도면이다.
예를 들면, 도 3c의 페이지(360)는 기설정된 위치에 존재하는 매직 비트(306, 307, 308, 309) 각각에 '1', '0', '0' 및 '0'의 데이터가 순차적으로 포함되어 있다. 전자 장치는 전술한 방법에 의해, 페이지(360)의 매직 비트(306, 307, 308, 309)를 특정값 '0'으로 변경할 수 있다. 이에 따라, 페이지(360)는 도 3b의 변경된 페이지(320)와 동일해질 수 있다.
전자 장치는 기설정된 매직 비트(306, 307, 308, 309)의 데이터가 특정값 '0'으로 변경된 페이지(320)를 압축하여, 압축된 데이터(330)를 생성할 수 있다. 이때, 전자 장치는 매직 비트(306, 307, 308, 309)의 변경 전 오리지널 값을 메타 데이터, '1000'으로 생성할 수 있다.
전자 장치는 스왑 영역(340)의 기 저장된 데이터(350)에 압축된 데이터(330)를 병합하면서, 메타 데이터 '1000'을 함께 매핑할 수 있다.
한편, 도 3d의 페이지(370)는 기설정된 위치에 존재하는 매직 비트(306, 307, 308, 309) 각각에 '1', '1', '1' 및 '1'의 데이터가 순차적으로 포함되어 있다. 전자 장치는 전술한 방법에 의해, 페이지(370)의 매직 비트(306, 307, 308, 309)를 특정값 '0'으로 변경할 수 있다. 이에 따라, 페이지(370)는 도 3b의 변경된 페이지(320)와 동일해질 수 있다.
전자 장치는 기설정된 매직 비트(306, 307, 308, 309)의 데이터가 특정값 '0'으로 변경된 페이지(320)를 압축하여, 압축된 데이터(330)를 생성할 수 있다. 이때, 전자 장치는 매직 비트(306, 307, 308, 309)의 변경 전 오리지널 값을 메타 데이터, '1111'으로 생성할 수 있다.
전자 장치는 스왑 영역(340)의 기 저장된 데이터(350)에 압축된 데이터(330)를 병합하면서, 메타 데이터 '1111'을 함께 매핑할 수 있다.
상술한 방법에 의해, 전자 장치는 매직 비트(306, 307, 308, 309)에 포함된 데이터의 일부를 제외하고 나머지 데이터가 동일한, 유사 페이지들을 스왑 영역의 동일한 영역에 매핑할 수 있다. 따라서, 전자 장치는 가용 메모리 효율을 높일 수 있게 된다.
상기 도 3a 내지 도 3d를 통해 설명한 매직 비트는, 임의의 페이지에 대해 데이터를 복수번 변경하면서 저장하는 동안, 상기 페이지에 포함된 비트 중에서 데이터의 값이 자주 변경되는 비트를 의미할 수 있다.
이하에서는, 도 8을 참조하여 전자 장치가 매직 비트를 결정하는 방법에 대해 구체적으로 설명한다.
전자 장치는 모든 페이지에 대해, 매직 비트를 결정하기 위한 동작을 수행할 수 있다. 다만, 단계 S800에서, 전자 장치는 매직 비트를 결정하기 위한 동작을 수행함으로써 발생하는 부하를 줄이기 위해, 임의의 페이지가 매직 비트를 결정하기 위해 선정된 페이지인지 여부를 판단할 수 있다.
예를 들면, 전자 장치는 복수의 페이지들에 대해, memset 또는 memcpy와 같은 특정 동작을 수행할 수 있다. 수행 결과, 동일한 데이터를 포함하는 페이지들을 매직 비트를 결정하기 위한 페이지로 선정할 수 있다.
단계 S810에서, 전자 장치는 매직 비트를 결정하기 위해 선정된 페이지에 대해 데이터를 저장할 수 있다. 매직 비트를 결정하기 위한 페이지는 복수개 선정될 수 있다.
단계 S820에서, 전자 장치는 저장된 데이터 값을 올드-페이지(old-page)에 저장하고, 상기 선정된 페이지에 새로운 데이터를 저장할 수 있다.
그리고 단계 S830에서, 전자 장치는 올드-페이지 및 새로운 데이터가 저장된 페이지를 비교할 수 있다. 예를 들면, 전자 장치는 올드-페이지에 포함된 비트와 새로운 데이터가 저장된 페이지의 같은 위치의 비트에 저장된 값이 변경되었는지 여부를 판단할 수 있다.
단계 S840에서, 전자 장치는 데이터 값이 변경된 비트에 대해, 카운터(counter)를 1 증가시킬 수 있다.
임계 시간이 소요되는 동안, 전자 장치는 상술한 동작을 반복하여 수행할 수 있다. 그리고 단계 S850에서 임계 시간이 소요된 것으로 판단되면, 단계 S860에서 전자 장치는 페이지에 포함된 각 비트에 대해, (비트가 변경된 횟수)/(데이터 저장 횟수)를 계산할 수 있다.
단계 S870에서, 전자 장치는 계산된 값이 큰 순서대로 N개의 비트를 매직 비트로 결정할 수 있다.
예를 들면, 전자 장치는 임의의 어플리케이션을 구동시키는 경우, 매직 비트를 활용하여 압축된 페이지를 병합할 수 있다. 구체적으로, 전자 장치가 카메라 어플리케이션을 구동하는 경우, 카메라 어플리케이션은 약 700MB이상의 메모리를 요청하게 된다. 이때, 700MB의 메모리는 memset을 통해 ‘0’으로 초기화된 후에 사용될 수 있다. 따라서, 전자 장치는 memset을 수행함으로써 초기화되는 페이지들을 매직 비트를 구하기 위한 페이지로 선정할 수 있다.
한편, 전자 장치는 임의의 페이지에 대해 데이터를 쓰는(write) 경우, 상기 페이지가 매직 비트를 선정하기 위해 미리 결정된 페이지 인지 판단하기 위한 별도의 모듈을 포함할 수 있다. 따라서, 도 8에 개시된 매직 비트를 결정하는 방법은 전자 장치 또는 전자 장치에 포함된 상기 별도의 모듈을 통해 수행될 수도 있다.
본 발명의 일 실시 예에 따르면, 전자 장치가 압축하는 단위는 페이지 단위일 수 있으나, 이에 한정되지 않는다. 예를 들면, 도 9a에 도시된 바와 같이, 전자 장치는 하나의 페이지(900)를 두 개로 분할하고, 상기 분할된 데이터(910, 920)를 각각 압축할 수 있다. 예를 들면, 하나의 페이지(900)를 두 개로 분할하는 경우에, 동일한 내용의 데이터가 포함될 확률이 높다고 판단된 경우, 전자 장치는 하나의 페이지(900)를 두 개로 분할할 수 있다. 그리고 전자 장치는 상기 분할된 데이터(910, 920)를 각각 압축하여, 압축된 두 개의 데이터(915, 925)를 생성할 수 있다. 이때, 전자 장치는 압축된 두 개의 데이터(915, 925) 각각을 상기 분할된 데이터(910, 920)의 오리지널 크기 값과 매칭하여 저장할 수 있다.
또 다른 실시 예에 따라, 전자 장치는 페이지를 분할하고, 분할된 페이지의 매직 비트의 데이터를 특정값으로 변경한 뒤에, 압축할 수도 있다.
도 9b에 도시된 바와 같이, 하나의 페이지(930)의 대부분의 데이터가 ‘0’으로 채워지고, 일 말단에 데이터 ‘1’ 이 포함된 경우를 예로 든다. 전자 장치는 페이지(930)를 분할하는 경우, 데이터 ‘0’ 만을 포함하는 일부 페이지를 생성할 수 있다고 판단할 수 있다.
따라서, 전자 장치는 페이지(930)를 분할하여, 데이터 ‘0’ 만을 포함하는 제1 일부 페이지(940) 및 제2 일부 페이지(950)를 생성할 수 있다. 전자 장치는 데이터 ‘0’ 만을 포함하는 제1 일부 페이지(940)를 압축하여 제1 일부 압축 데이터(945)를 생성할 수 있다.
그리고 전자 장치는 제2 일부 페이지(950)의 데이터 ‘1’ 이 포함된 비트를 데이터 ‘0’으로 변경할 수 있다. 전자 장치는 제1 일부 페이지(940)와 동일해진 변경된 제2 일부 페이지(960)를 압축하여, 제2 일부 압축 데이터(970)를 생성할 수 있다. 그리고 전자 장치는 제2 일부 페이지(950)의 데이터 ‘1’을 메타 데이터로 형성하여, 제2 일부 압축 데이터(970)와 매핑하여 저장할 수 있다.
제1 일부 페이지(940) 및 변경된 제2 일부 페이지(960)는 데이터 ‘0’ 만을 포함하므로, 전자 장치는 제1 일부 압축 데이터(945) 및 제2 일부 압축 데이터(970)를 동일한 스왑 영역에 저장할 수 있다. 그리고 전자 장치는 제2 일부 압축 데이터(970)는 상기 메타 데이터를 매핑하여 저장할 수 있다.
한편, 전자 장치가 하나의 페이지를 동일한 크기의 두 개의 일부 페이지로 분할하는 것은 일 실시 예에 불과할 뿐, 전자 장치는 하나의 페이지를 복수개의 일부 페이지로 분할할 수 있으며, 각 일부 페이지는 서로 크기가 상이할 수도 있다.
본 발명의 일 실시 예에 따르면, 전자 장치는 도 4에 도시된 바와 같이, 압축된 페이지의 페이지 프레임 넘버(page frame number, PFN)(410), 상기 압축된 페이지의 어드레스(420) 및 상기 압축된 페이지의 메타 데이터에 대한 정보인, 인덱스 넘버(430)를 포함하는 테이블(400)을 저장할 수 있다.
구체적으로, 각 페이지는 고유의 프레임 넘버를 가질 수 있다. 따라서, 전자 장치는 압축된 페이지를 스왑-아웃하는 경우, 상기 압축된 페이지의 어드레스를 스왑 영역의 상기 압축된 페이지와 동일한 데이터를 포함하는 압축 페이지가 존재하는 어드레스에 매핑할 수 있다. 이때, 전자 장치는 스왑-아웃하는 페이지의 프레임 넘버(410)와 상기 동일한 데이터를 포함하는 압축 페이지의 어드레스(420)를 매핑한 테이블을 생성할 수 있다.
그리고 상술한 방법에 의해, 스왑-아웃하는 페이지의 매직 비트가 특정값으로 변경된 경우, 전자 장치는 상기 매직 비트의 오리지널 값을 인덱스 값(430)으로 테이블에 추가할 수 있다. 한편, 인덱스 값(430)은 매직 비트의 오리지널 값에 한정되는 것이 아니라, 상기 오리지널 값이 저장된 영역의 어드레스일 수도 있다.
한편, 상술한 기설정된 개수의 임의의 비트는, 상기 페이지에서 미리 결정된 위치에 포함된 비트이거나 상기 페이지에 포함된 데이터에 따라 가변적인 위치에 포함된 비트일 수 있다.
임의의 비트는 각 페이지의 몇번째에 포함되는 비트인지, 하나의 페이지에 몇개가 포함되는지 미리 결정되어 있을 수 있다. 그러나 이는 일 실시 예에 불과할 뿐, 전자 장치는 초기 설정, 사용자 설정, 실행 프로그램 또는 어플리케이션의 종류 등에 따라, 위치가 가변적인 매직 비트를 설정할 수도 있다.
예를 들면, 스왑(swap)을 수행하는 경우, 전자 장치는 스왑의 대상이 되는 페이지들을 비교 할 수 있다. 비교 결과, 복수의 페이지들이 일부 비트(예를 들면, 4개의 비트)를 제외하고, 나머지 비트에 포함된 데이터가 동일한 것으로 판단되면, 전자 장치는 상기 제외되는 일부 비트를 매직 비트로 설정할 수 있다. 그리고 전자 장치는 상술한 방법에 의해, 매직 비트에 포함된 데이터를 특정값으로 변경하고, 상기 변경된 특정값을 포함하는 페이지들을 압축하여 스왑-아웃할 수 있다.
한편, 도 5는 본 발명의 일 실시 예에 따른 데이터 압축 방법을 나타내는 흐름도이다. 먼저, 단계 S500에서, 전자 장치는 페이지를 압축한다. 전자 장치는 스왑(swap)을 수행하기 위해, 압축하여 저장할 페이지를 선택할 수 있다. 예를 들면, 전자 장치는 마지막 사용으로부터 기설정된 시간 이상 소요된 페이지 등을 스왑-아웃(swap out)의 대상이 되는 페이지로 결정할 수 있다. 그러나 이는 일 실시 예에 불과할 뿐, 설정 또는 사용자 명령에 따라 스왑-아웃(swap out)의 대상이 되는 페이지가 결정될 수도 있다.
단계 S510에서, 전자 장치는 압축된 페이지에 포함된 데이터가 메모리에 저장되어 있는지 여부를 판단한다.
판단 결과, 상기 압축된 페이지에 포함된 데이터와 동일한 데이터를 포함하는 압축 페이지가 상기 메모리에 기저장된 경우, 단계 S520에서, 전자 장치는 상기 압축된 페이지를 상기 기저장된 페이지에 병합(merge)한다. 예를 들면, 전자 장치는 상기 압축된 페이지의 어드레스를 상기 메모리에 기저장된 압축 페이지의 저장 어드레스로 포인팅 할 수 있다.
한편, 판단 결과, 상기 압축된 페이지에 포함된 데이터와 동일한 데이터를 포함하는 압축 페이지가 상기 메모리에 기저장되지 않은 경우, 단계 S530에서, 전자 장치는 메모리를 할당받고, 상기 할당된 메모리에 상기 압축된 페이지를 저장할 수 있다.
이하에서는, 도 6을 참조하여, 유사한 데이터를 포함하는 페이지도 스왑 영역의 동일한 영역에 저장함으로써, 메모리 효율을 향상 시키기 위한 방법을 설명한다.
단계 S600에서, 전자 장치는 페이지에 포함된 기설정된 개수의 임의의 비트를 특정값으로 변경할 수 있다. 예를 들면, 전자 장치는 페이지의 특정 위치의 비트를 매직 비트(magic bit)로 설정할 수 있다. 그리고 전자 장치는 기설정된 매직 비트에 포함된 데이터를 '0'과 같은 특정값으로 변경할 수 있다. 특정값이 '0'인 것은 일 실시 예에 불과할 뿐, 전자 장치의 초기 설정, 어플리케이션의 종류 또는 사용자 설정 등에 따라 다른 값으로 결정될 수도 있다.
단계 S610에서, 전자 장치는 특정갑승로 변경된 임의의 비트를 포함하는 페이지를 압축할 수 있다. 예를 들어, 전자 장치는 기설정된 매직 비트의 데이터가 특정값 '0'으로 변경된 페이지를 압축하여, 압축된 데이터를 생성할 수 있다. 이때, 전자 장치는 매직 비트의 변경 전 오리지널 값을 메타 데이터로 생성할 수 있다.
그리고 단계 S620에서, 전자 장치는 압축된 페이지에 포함된 데이터가 메모리에 저장되어 있는지 여부를 판단할 수 있다. 예를 들면, 전자 장치는 압축된 데이터와 동일한 데이터가 스왑 영역에 기저장되어 있는지 여부를 판단할 수 있다.
판단 결과, 스왑 영역에 압축된 데이터와 동일한 데이터가 저장된 것으로 판단되면, 단계 S630에서, 전자 장치는 상기 특정 값으로 변경 전에 상기 임의의 비트에 포함된 오리지널 데이터의 값 또는 상기 오리지널 데이터의 값이 저장된 주소를 매핑하여, 상기 압축된 데이터를 기저장된 데이터에 병합할 수 있다.
예를 들면, 전자 장치는 매직 비트의 데이터를 특정값으로 변경하면서 상기 매직 비트의 오리지널 데이터 값을 메타 데이터로 생성하여, 상기 기저장된 데이터에 상기 압축된 데이터와 함께 매핑시킬 수 있다.
또는, 전자 장치는 매직 비트의 데이터를 특정값으로 변경하면서 별도로 생성한 상기 매직 비트의 오리지널 데이터의 값을 기설정된 영역에 저장하고, 상기 기저장된 데이터에 상기 압축된 데이터를 매핑시키면서, 상기 매직 비트의 오리지널 데이터의 값이 저장된 상기 기설정된 영역의 어드레스를 함께 매핑시킬 수도 있다. 그리고 전자 장치는 압축된 데이터를 기저장된 동일한 데이터(350)에 병합하면서, 상기 메타 데이터(335)를 함께 매핑할 수 있다.
따라서, 추후 압축된 데이터에 대해 스왑-인(swap in)을 수행하는 경우, 전자 장치는 동일한 데이터를 복원하고, 상기 복원된 데이터의 매직 비트를 메타 데이터에 포함된 값으로 치환하여, 오리지널 페이지를 획득할 수 있게 된다.
한편, 판단 결과, 스왑 영역에 압축된 데이터와 동일한 데이터가 기저장되어 있지 않은 것으로 판단되면, 단계 S6340에서, 메모리를 할당하고, 상기 할당된 메모리에 상기 특정 값으로 변경 전에 상기 임의의 비트에 포함된 오리지널 데이터의 값 또는 상기 오리지널 데이터의 값이 저장된 주소를 매핑하여, 상기 압축된 페이지를 저장할 수 있다.
도 7은 본 발명의 일 실시 예의 따른 전자 장치의 구성을 도시한 블럭도이다. 도 7에 도시된 바와 같이, 전자 장치(700)는 메모리(710) 및 제어부(720)를 포함할 수 있다. 전자 장치(700)는 휴대폰, 태블릿 PC, 디지털 카메라, 캠코더, 노트북 PC, 데스크탑, PDA, MP3, 스마트 안경(Smart Glass), 스마트 시계(Smart Watch) 또는 스마트 링(Smart Ring) 등과 같은 다양한 장치로 구현될 수 있다.
메모리(710)를 데이터를 저장하기 위한 구성요소이다. 메모리(710)는 전자 장치(700)를 구동하기 위한 다양한 프로그램 및 데이터를 저장한다. 예를 들어, 메모리(710)에는 전자 장치(700)를 구동시키기 위한 OS(Operating System), 각종 기능 수행을 위한 어플리케이션, 어플리케이션 실행 과정에서 사용되는 데이터 등이 저장될 수 있다. 그 밖에도, 메모리(710)에는 베이스 모듈, 센싱 모듈, 통신 모듈, 프리젠테이션 모듈, 웹 브라우저 모듈, 서비스 모듈 등과 같은 다양한 소프트웨어가 저장될 수 있다.
메모리(710)는 RAM, ROM 및 L1, L2 캐시 메모리를 포함하는 1차 스토리지 및 하드디스크를 포함하는 2차 스토리지를 포함할 수 있다. 예를 들면, 메모리(710)의 2차 스토리지는 스왑-아웃(swap out)된 페이지를 저장할 수 있다.
한편, 제어부(720)는 전자 장치(700)를 전반적으로 제어하기 위한 구성요소이다. 제어부(720)는 중복페이지 판단부(721), 페이지 병합부(722) 및 관리부(733)와 같은 구성요소를 더 포함할 수 있다. 제어부(720)에 포함된 구성요소들은 별도의 하드웨어 모듈로 구현될 수 있다. 그러나 이는 일 실시 예에 불과할 뿐, 중복 페이지 판단부(721), 페이지 병합부(722) 및 관리부(733)는 소프트웨어로 구현되고, 제어부(720)는 비휘발성 메모리에 상기 프로그램을 저장하고, 상기 저장된 프로그램들을 RAM으로 복사한 뒤에, 복사한 프로그램들을 실행시켜 기능을 수행할 수도 있다.
중복 페이지 판단부(721)는 스왑의 대상으로 결정된 페이지를 압축할 수 있다. 그리고 압축된 페이지에 포함된 데이터가 스왑 영역에 기저장되어 있는지 여부를 판단할 수 있다.
또한, 중복 페이지 판단부(721)는 페이지의 기설정된 임의의 비트에 포함된 데이터를 특정값(예를 들면, '0')으로 변경할 수 있다. 그리고 상기 임의의 비트에 특정값이 채워진 페이지를 압축할 수도 있다. 중복 페이지 판단부(721)는 상기 임의의 비트의 특정값 변경전의 오리지널 데이터 값을 메타 데이터로 생성할 수 있다.
한편, 페이지 병합부(722)는 중복 페이지 판단부(721)의 판단 결과에 따라, 페이지를 병합할 수 있다. 예를 들면, 중복 페이지 판단부(721)에 의해, 압축된 페이지에 포함된 데이터와 동일한 데이터가 메모리(710)의 스왑 영역에 기저장된 것으로 판단된 경우, 페이지 병합부(722)는 상기 압축된 페이지를 상기 기저장된 페이지에 병합할 수 있다. 예를 들면, 페이지 병합부(722)는 상기 압축된 페이지의 저장 어드레스를 상기 상기 기저장된 페이지의 어드레스로 매핑할 수 있다.
또한, 페이지 병합부(722)는 상기 압축된 페이지를 상기 기저장된 페이지에 병합하면서, 상기 메타 데이터를 함께 매핑할 수 있다.
한편, 중복 페이지 판단부(721)에 의해, 압축된 페이지에 포함된 데이터와 동일한 데이터가 메모리(710)의 스왑 영역에 기저장되어 있지 않은 것으로 판단된 경우, 페이지 병합부(722)는 메모리(710)의 일부 영역을 할당하고, 상기 할당된 영역에 상기 압축된 페이지를 저장할 수 있다.
관리부(733)는 병합된 페이지들을 관리할 수 있다. 관리부(733)는 압축된 페이지의 프레임 페이지 넘버 및 상기 압축된 페이지의 저장 어드레스를 매핑하여 관리할 수 있다. 또한, 상기 압축된 페이지의 임의의 비트가 특정값으로 변경된 경우, 관리부(733)는 상기 임의의 비트의 오리지널 값을 포함하는 메타 데이터를 상기 압축된 페이지의 프레임 페이지 넘버 및 상기 압축된 페이지의 저장 어드레스와 함께 매핑하여 관리할 수 있다.
따라서, 추후 스왑-인(swap in)이 수행되는 경우, 상기 저장 어드레스 및 상기 메타 데이터를 이용하여 상기 압축된 페이지를 복원할 수 있게 된다.
상기 기술에 있어서, 제어부(720)가 각각 별도의 기능 블록들(721 내지 723)을 포함하고, 제어부(720) 및 각각의 세부 기능 블록들(721 내지 723)이 상이한 기능을 수행하는 것으로 도시 및 기재하였으나 이는 구현 가능한 일 실시예에 불과하다. 예를 들어, 중복 페이지 판단부(721)가 수행하는 기능을 제어부(720) 자체가 수행할 수도 있는 것이다.
상술한 바와 같은 전자 장치(700)에 의해, 스왑-아웃(swap out) 되는 페이지의 양이 증가하는 경우에도, 메모리에 동일하거나 유사한 데이터를 포함하는 페이지가 복수번 저장되지 않도록 함으로써, 메모리 확보 효율을 높일 수 있게 된다.
한편, 상술한 전자 장치의 구성요소들은 소프트웨어로 구현될 수 있다. 가령, 전자 장치의 제어부는 플래시 메모리나 기타 비휘발성 메모리를 더 포함할 수 있다. 이러한 비휘발성 메모리에는 제어부의 각각의 역할을 수행하기 위한 프로그램이 저장될 수 있다.
또한, 전자 장치의 제어부는 CPU 및 RAM(Random Access Memory)을 포함하는 형태로 구현될 수 있다. 제어부의 CPU는 비휘발성 메모리에 저장된 상술한 프로그램들을 RAM으로 복사한 후, 복사한 프로그램들을 실행시켜 상술한 바와 같은 전자 장치의 기능을 수행할 수 있다.
제어부는 전자 장치의 제어를 담당하는 구성이다. 제어부는 중앙처리장치, 마이크로 프로세서, 제어부, 프로세서, 운용체제(operating system) 등과 동일한 의미로 혼용되어 사용될 수 있다. 또한, 전자 장치의 제어부는 전자 장치에 포함된 통신 모듈 등의 다른 기능부와 함께 단일칩 시스템 (System-on-a-chip 또는 System on chip, SOC, SoC)로 구현될 수 있다.
한편, 상술한 다양한 실시 예들에 따른 전자 장치의 데이터 압축 방법은 소프트웨어로 코딩되어 비일시적 판독 가능 매체(non-transitory readable medium)에 저장될 수 있다. 이러한 비일시적 판독 가능 매체는 다양한 장치에 탑재되어 사용될 수 있다.
비일시적 판독 가능 매체란 레지스터, 캐쉬, 메모리 등과 같이 짧은 순간 동안 데이터를 저장하는 매체가 아니라 반영구적으로 데이터를 저장하며, 기기에 의해 판독(reading)이 가능한 매체를 의미한다. 구체적으로는, CD, DVD, 하드 디스크, 블루레이 디스크, USB, 메모리카드, ROM 등이 될 수 있다.
또한, 이상에서는 본 발명의 바람직한 실시예에 대하여 도시하고 설명하였지만, 본 발명은 상술한 특정의 실시예에 한정되지 아니하며, 청구범위에서 청구하는 본 발명의 요지를 벗어남이 없이 당해 발명이 속하는 기술분야에서 통상의 지식을 가진자에 의해 다양한 변형실시가 가능한 것은 물론이고, 이러한 변형실시들은 본 발명의 기술적 사상이나 전망으로부터 개별적으로 이해되어져서는 안 될 것이다.

Claims (12)

  1. 전자 장치의 데이터 압축 방법에 있어서,
    페이지를 압축하는 단계;
    상기 압축된 페이지에 포함된 데이터가 메모리에 저장되어 있는지 여부를 판단하는 단계; 및
    판단 결과 상기 압축된 페이지에 포함된 데이터가 상기 메모리에 기저장된 데이터와 동일한 경우, 상기 압축된 페이지를 상기 기저장된 데이터에 병합(merge)하는 단계; 를 포함하는 데이터 압축 방법.
  2. 제1항에 있어서,
    상기 병합하는 단계는,
    상기 압축된 페이지를 상기 기저장된 데이터가 포함된 상기 메모리의 페이지에 매핑하는 것을 특징으로 하는 데이터 압축 방법.
  3. 제1항에 있어서,
    상기 판단 결과, 상기 압축된 페이지에 포함된 데이터가 상기 메모리에 저장되어 있지 않은 경우, 메모리를 할당받고, 상기 압축된 페이지를 상기 할당된 메모리에 저장하는 단계; 를 더 포함하는 데이터 압축 방법.
  4. 제1항에 있어서,
    상기 압축하는 단계는,
    상기 페이지에 포함된 기설정된 개수의 임의의 비트를 특정값으로 변경하고, 상기 특정값으로 변경된 상기 임의의 비트를 포함하는 상기 페이지를 압축하는 것을 특징으로 하는 데이터 압축 방법.
  5. 제4항에 있어서,
    상기 병합하는 단계는,
    상기 특정값으로 변경 전에 상기 임의의 비트에 포함된 오리지널 데이터의 값 또는 상기 오리지널 데이터의 값이 저장된 주소를 매핑하여, 상기 압축된 페이지를 상기 기저장된 데이터에 병합하는 것을 특징으로 하는 데이터 압축 방법.
  6. 제4항에 있어서,
    상기 페이지에 포함된 기설정된 개수의 임의의 비트는,
    상기 페이지에서 미리 결정된 위치에 포함된 비트이거나, 상기 페이지에 포함된 데이터에 따라 가변적인 위치에 포함된 비트인 것을 특징으로 하는 데이터 압축 방법.
  7. 전자 장치에 있어서,
    데이터를 저장하는 메모리; 및
    페이지를 압축하고, 상기 압축된 페이지에 포함된 데이터가 메모리에 저장되어 있는지 여부를 판단하여, 판단 결과 상기 압축된 페이지에 포함된 데이터가 상기 메모리에 기저장된 데이터와 동일한 경우, 상기 압축된 페이지를 상기 기저장된 데이터에 병합(merge)하도록 제어하는 제어부; 를 포함하는 전자 장치.
  8. 제7항에 있어서,
    상기 제어부는,
    상기 압축된 페이지를 상기 기저장된 데이터가 포함된 상기 메모리의 페이지에 매핑하는 것을 특징으로 하는 전자 장치.
  9. 제7항에 있어서,
    상기 제어부는,
    상기 판단 결과, 상기 압축된 페이지에 포함된 데이터가 상기 메모리에 저장되어 있지 않는 경우, 상기 메모리의 영역을 할당받고, 상기 압축된 페이지를 상기 할당된 메모리의 영역에 저장하는 것을 특징으로 하는 전자 장치.
  10. 제7항에 있어서,
    상기 제어부는,
    상기 페이지에 포함된 기설정된 개수의 임의의 비트를 특정값으로 변경하고, 상기 특정값으로 변경된 상기 임의의 비트를 포함하는 상기 페이지를 압축하는 것을 특징으로 하는 전자 장치.
  11. 제10항에 있어서,
    상기 제어부는,
    상기 특정값으로 변경 전에 상기 임의의 비트에 포함된 오리지널 데이터의 값 또는 상기 오리지널 데이터의 값이 저장된 주소를 매핑하여, 상기 압축된 페이지를 상기 기저장된 데이터에 병합하는 것을 특징으로 하는 전자 장치.
  12. 제10항에 있어서,
    상기 페이지에 포함된 기설정된 개수의 임의의 비트는,
    상기 페이지에서 미리 결정된 위치에 포함된 비트이거나, 상기 페이지에 포함된 데이터에 따라 가변적인 위치에 포함된 비트인 것을 특징으로 하는 전자 장치.
PCT/KR2016/008596 2015-08-12 2016-08-04 전자 장치 및 이의 데이터 압축 방법 WO2017026740A1 (ko)

Priority Applications (2)

Application Number Priority Date Filing Date Title
US15/750,733 US11226738B2 (en) 2015-08-12 2016-08-04 Electronic device and data compression method thereof
CN201680047598.7A CN107924350B (zh) 2015-08-12 2016-08-04 电子设备及其数据压缩方法

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
KR10-2015-0113935 2015-08-12
KR1020150113935A KR102294669B1 (ko) 2015-08-12 2015-08-12 전자 장치 및 이의 데이터 압축 방법

Publications (1)

Publication Number Publication Date
WO2017026740A1 true WO2017026740A1 (ko) 2017-02-16

Family

ID=57984016

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/KR2016/008596 WO2017026740A1 (ko) 2015-08-12 2016-08-04 전자 장치 및 이의 데이터 압축 방법

Country Status (4)

Country Link
US (1) US11226738B2 (ko)
KR (1) KR102294669B1 (ko)
CN (1) CN107924350B (ko)
WO (1) WO2017026740A1 (ko)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2021080385A1 (en) * 2019-10-25 2021-04-29 Samsung Electronics Co., Ltd. Computing device and operating method thereof

Families Citing this family (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP3933566A4 (en) * 2019-02-28 2022-10-12 LG Electronics Inc. DIGITAL DEVICE AND CONTROL METHOD THEREOF
KR20210039617A (ko) * 2019-10-02 2021-04-12 삼성전자주식회사 전자장치 및 그 제어방법

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20120284587A1 (en) * 2008-06-18 2012-11-08 Super Talent Electronics, Inc. Super-Endurance Solid-State Drive with Endurance Translation Layer (ETL) and Diversion of Temp Files for Reduced Flash Wear
KR101331098B1 (ko) * 2011-10-28 2013-11-19 국방과학연구소 메모리압축 스왑도구를 이용하는 가상화 임베디드 시스템 및 방법
WO2014104509A1 (ko) * 2012-12-31 2014-07-03 고려대학교 산학협력단 가상화 시스템에서의 메모리 관리 방법

Family Cites Families (15)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5406278A (en) * 1992-02-28 1995-04-11 Intersecting Concepts, Inc. Method and apparatus for data compression having an improved matching algorithm which utilizes a parallel hashing technique
US6226411B1 (en) * 1997-01-31 2001-05-01 Fujitsu Limited Method for data compression and restoration
US6879266B1 (en) * 1997-08-08 2005-04-12 Quickshift, Inc. Memory module including scalable embedded parallel data compression and decompression engines
KR100354531B1 (ko) * 1998-05-06 2005-12-21 삼성전자 주식회사 실시간 복호화를 위한 무손실 부호화 및 복호화 시스템
CN100517979C (zh) 2005-10-10 2009-07-22 中兴通讯股份有限公司 一种数据压缩及解压缩方法
US8694703B2 (en) * 2010-06-09 2014-04-08 Brocade Communications Systems, Inc. Hardware-accelerated lossless data compression
US8548944B2 (en) 2010-07-15 2013-10-01 Delphix Corp. De-duplication based backup of file systems
KR20130027253A (ko) * 2011-09-07 2013-03-15 삼성전자주식회사 데이터의 압축 방법
US9875723B2 (en) 2013-08-13 2018-01-23 Mediatek Inc. Data processing apparatus for transmitting/receiving randomly accessible compressed pixel data groups over display interface and related data processing method
US20150067238A1 (en) 2013-08-29 2015-03-05 Sandisk Technologies Inc. Computing Device and Method for Predicting Low Memory Conditions
CN103744617B (zh) 2013-12-20 2016-09-28 北京奇虎科技有限公司 一种键-值存储系统中数据文件的合并压缩方法及装置
CN104035822A (zh) * 2014-05-28 2014-09-10 中国科学院计算技术研究所 一种低开销的高效内存去冗余方法及系统
CN104199892B (zh) * 2014-08-26 2018-01-30 上海爱数信息技术股份有限公司 一种基于压缩合并异步更新的索引读写方法
US9977598B2 (en) * 2014-10-27 2018-05-22 Mediatek Inc. Electronic device and a method for managing memory space thereof
US10296457B2 (en) * 2017-03-30 2019-05-21 Intel Corporation Reducing conflicts in direct mapped caches

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20120284587A1 (en) * 2008-06-18 2012-11-08 Super Talent Electronics, Inc. Super-Endurance Solid-State Drive with Endurance Translation Layer (ETL) and Diversion of Temp Files for Reduced Flash Wear
KR101331098B1 (ko) * 2011-10-28 2013-11-19 국방과학연구소 메모리압축 스왑도구를 이용하는 가상화 임베디드 시스템 및 방법
WO2014104509A1 (ko) * 2012-12-31 2014-07-03 고려대학교 산학협력단 가상화 시스템에서의 메모리 관리 방법

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
LI, YAQIONG ET AL.: "TMemCanal: A VM-oblivious Dynamic Memory Optimization Scheme for Virtual Machines in Cloud Computing", 2010 10TH IEEE INTERNATIONAL CONFERENCE ON COMPUTER AND INFORMATION TECHNOLOGY (CIT 2010, 2010, pages 179 - 186, XP031758045 *
PARK, SANGDUCK ET AL.: "Compressed Swapping for NAND Flash Memory Based Embedded Systems", EMBEDDED COMPUTER SYSTEMS: ARCHITECTURES, MODELING, AND SIMULATION, LNCS VOL. 3553 , PROCEEDINGS OF 5TH INTERNATIONAL WORKSHOP SAMOS 2005, 2005, pages 314 - 323, XP019012224 *

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2021080385A1 (en) * 2019-10-25 2021-04-29 Samsung Electronics Co., Ltd. Computing device and operating method thereof
US11467734B2 (en) 2019-10-25 2022-10-11 Samsung Electronics Co., Ltd. Managing swap area in memory using multiple compression algorithms

Also Published As

Publication number Publication date
US11226738B2 (en) 2022-01-18
CN107924350B (zh) 2022-01-25
KR20170019729A (ko) 2017-02-22
KR102294669B1 (ko) 2021-08-27
US20190004708A1 (en) 2019-01-03
CN107924350A (zh) 2018-04-17

Similar Documents

Publication Publication Date Title
US10983955B2 (en) Data unit cloning in memory-based file systems
WO2013042880A2 (ko) 다양한 블록 크기를 지원하는 주소 사상을 사용하여 플래시 메모리 내에 데이터를 저장하는 방법 및 장치
US8909853B2 (en) Methods and apparatus to share a thread to reclaim memory space in a non-volatile memory file system
WO2016045096A1 (zh) 一种文件迁移方法、装置和存储设备
US20170177497A1 (en) Compressed caching of a logical-to-physical address table for nand-type flash memory
US9081692B2 (en) Information processing apparatus and method thereof
US10754567B2 (en) Partially deactivated application with termination protection
US10754785B2 (en) Checkpointing for DRAM-less SSD
CN105718530A (zh) 文件存储系统及其文件存储控制方法
WO2016204529A1 (ko) 전원 손실 이후 데이터 손실을 방지하기 위한 메모리 저장 장치 및 방법
WO2013176376A1 (ko) 칩 레벨 평행 플래시 메모리를 위한 정보 분별 방법 및 장치
WO2017026740A1 (ko) 전자 장치 및 이의 데이터 압축 방법
WO2024099448A1 (zh) 内存释放、内存恢复方法、装置、计算机设备及存储介质
KR20130076973A (ko) 응용 프로세서 및 이를 포함하는 시스템
JP6505266B2 (ja) メモリ管理装置を用いた自動メモリ管理
WO2019194394A1 (ko) 전자 장치 및 그의 제어방법
WO2017116186A1 (ko) 파일의 메타데이터에 대한 보호 방법 및 보호 장치
US20230142948A1 (en) Techniques for managing context information for a storage device
WO2016182255A1 (ko) 전자 장치 및 이의 페이지 병합 방법
US10204002B1 (en) Method for maintaining a cache index on a deduplicated storage system
US11615019B2 (en) Non-volatile storage device, host device, and data storage system to increase data write speed
WO2017057934A1 (en) Electronic apparatus and booting method thereof
WO2019164172A1 (ko) 메모리를 제어하는 전자 장치 및 제어 방법
US20210191851A1 (en) System and method for facilitating reduction of latency and mitigation of write amplification in a multi-tenancy storage drive
US20200142623A1 (en) Storage device and electronic device managing data transmitted to storage device

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 16835380

Country of ref document: EP

Kind code of ref document: A1

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 16835380

Country of ref document: EP

Kind code of ref document: A1