`US 20050246705Al
`
`(19) United States
`(12) Patent Application Publication
`Etelson et al.
`
`(10) Pub. No.: US 2005/0246705 Al
`Nov. 3, 2005
`(43) Pub. Date:
`
`(54) METHOD FOR DYNAMICALLY
`ALLOCATING AND MANAGING
`RESOURCES IN A COMPUTERIZED
`SYSTEM HAVING MULTIPLE CONSUMERS
`
`(75)
`
`Inventors: Garik Etelson, Kiryat Ono (IL);
`Gregory Bondar, Rishon Lezion (IL);
`Michael Stoler, Yahud (IL)
`
`(30)
`
`Foreign Application Priority Data
`
`Jul. 25, 2002
`
`(IL) ................................................. 150911
`
`Publication Classification
`
`Int. Cl.7 ....................................................... G06F 9/46
`(51)
`(52) U.S. Cl. .............................................................. 718/100
`
`Correspondence Address:
`FLEIT KAIN GIBBONS GUTMAN BONGINI
`& BIANCO
`21355 EAST DIXIE HIGHWAY
`SUITE 115
`MIAMI, FL 33180 (US)
`
`(73) Assignee: SPHERA CORPORATION, NEW(cid:173)
`TON, MA
`
`(21) Appl. No.:
`
`11/042,478
`
`(22) Filed:
`
`Jan.25,2005
`
`Related U.S. Application Data
`
`(63) Continuation of application No. PCT/IL03/00619,
`filed on Jul. 25, 2003.
`
`(57)
`
`ABSTRACT
`
`Method for dynamically allocating and managing resources
`in a computerized system managed by an operating system
`(OS) and having multiple accounts of consumers. Portions
`of the virtual memory address space are allocated, whenever
`desired, in a swap file, for each account associated with a
`consumer. The memory address space is limited for each
`account. The CPU usage is divided between the tasks
`requested from each account, and segments in the original
`code of the OS are changed by locating one or more specific
`procedures in the original code, and modifying the specific
`procedures to operate according to the allocation and/or the
`limitation of the memory address space and/or the limitation
`of the number of processes and/or the divided CPU usage.
`
`Co ied code
`Original commands
`
`Jump to continue of
`code
`
`22
`
`20
`
`Original code
`Jump to ...
`
`/
`
`Original code
`
`return
`
`New code
`Pre-check
`Call original code
`Post-check
`
`21
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1028, p. 1
`
`
`
`Patent Application Publication Nov. 3, 2005 Sheet 1 of 3
`
`US 2005/0246705 Al
`
`N
`~
`
`LO
`-~
`
`(0
`~
`
`~ .
`0)
`LL
`
`(cid:127) -
`
`0
`~
`
`l
`
`0
`(I)
`
`> (I) _.
`
`i
`
`Q)
`>
`Q)
`....J
`
`i
`N -Cl)
`> (I)
`...J
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1028, p. 2
`
`
`
`Patent Application Publication Nov. 3, 2005 Sheet 2 of 3
`
`US 2005/0246705 Al
`
`Original commands
`
`Jump to continue of
`code
`
`22
`
`20
`
`Original code /
`Jump to ...
`
`Original code
`
`return
`
`New code
`Pre-check
`Call original code
`Post-check
`
`21
`
`Fig. 2
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1028, p. 3
`
`
`
`Patent Application Publication Nov. 3, 2005 Sheet 3 of 3
`
`US 2005/0246705 Al
`
`••
`
`,_ 31
`
`32
`
`1
`
`0
`
`t
`
`Fig. 3
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1028, p. 4
`
`
`
`US 2005/0246705 Al
`
`Nov. 3, 2005
`
`1
`
`METHOD FOR DYNAMICALLY ALLOCATING
`AND MANAGING RESOURCES IN A
`COMPUTERIZED SYSTEM HAVING MULTIPLE
`CONSUMERS
`
`RELATED APPLICATION
`
`[0001] This application is a continuation of International
`Patent Application Serial number PCT/IL2003/000619 filed
`Jul. 25, 2003, the contents of which are here incorporated by
`reference in their entirety. The benefit of 35 USC Section
`120 is here claimed.
`
`BACKGROUND OF THE INVENTION
`[0002] 1. Field of the Invention
`
`[0003] The present invention relates to the field of man(cid:173)
`aging a computerized system. More particularly, the inven(cid:173)
`tion relates to a method for limiting the resources that are
`used by consumers, systems and web services of a given
`computerized system.
`
`[0004] 2. Prior Art
`
`[0005] Hosting a Website locally is relatively expensive,
`as it requires allocating sufficient bandwidth for Internet
`traffic to the site, as well as allocating resources for keeping
`the site available all the time (both in terms of software and
`hardware) and handling security aspects, such as a firewall.
`
`[0006] Web Hosting Providers (WHP), which are the
`consumers of a computerized system, use a variety of
`service models to address different types of customers,
`depending on the required class of service. The Web sites of
`small and medium-sized businesses normally do not pre(cid:173)
`empt the resources afforded by a dedicated server, and
`therefore might settle for a shared server model. However, as
`the requirements of the WHP change and their sites conduct
`more and more activity, they become more resource-con(cid:173)
`suming. When WHPs become more resource consuming,
`they usually, hire more resources, or keep the same resources
`with decreased performance. As the demand for the site's
`services is not constant over a time period, the customer
`might prefer to keep the same resources rather than hiring
`more resources, assuming that a relatively high demand for
`resources might occur for only a relatively short duration.
`
`[0007] Typically, each dedicated server runs an instance of
`the OS (Operation System). However, running an instance of
`the OS for each dedicated server comparatively requires a
`large amount of resources, which is required for each
`instance of the OS.
`
`[0008] Hereinafter, the term "computerized system" refers
`to a server that hosts a plurality of virtual dedicated servers
`that execute a plurality of services, wherein each virtual
`dedicated server utilizes a substantial portion of the com(cid:173)
`puter resources.
`
`[0009] A virtual dedicated server in such a computerized
`system is actually an emulation of a computer system's
`interface in which a remote client can access its system
`utilities and programs, and it will be called hereinafter a
`Virtual Dedicated Server (VDS). A plurality of VDS
`instances can be executed simultaneously on a single hosting
`computerized system.
`
`[0010] The term "account" refers to a certain part of the
`machine's resources that is allocated to a specific user. An
`
`account might share its allocated resource with other
`accounts, but together they can not utilize more than their
`allocated share. An "account" can be allocated to a user, a
`domain, a VDS, a service, a specific processes or process
`groups or to any other suitable user of the machine's
`resources.
`
`[0011] One of the existing solutions for limiting the
`resources consumption of an account is to use a static
`division of the computer resources. The hosting computer
`resources are divided in a static manner between the virtual
`computers. The result is that if, for example, the real
`computer is split into 10 identical virtual computers, then
`10% of the system resources are allocated to each virtual
`computer, even if only one virtual computer is being oper(cid:173)
`ated. A dynamic resource allocation would result in a better
`performance per virtual computer (if not all the VDSs are
`activated at the same time), with an appropriate allocation to
`each VDS (according to predefined parameters) in the case
`that a plurality of VDSS are activated at the same time.
`Therefore, the dynamic resource allocation results in a better
`performance from the user's point of view. The dynamic
`resource allocation can be used by any consumer of the
`computer resources, such as different services, different
`users, etc.
`
`[0012] Resources of a computerized system are limited
`due to several factors such as budget, spatial restrictions, etc.
`Resources of a computerized system comprise, among oth(cid:173)
`ers, the usage of a Central Processing Unit (CPU), the size
`of a memory address space, storage capabilities of data, etc.
`A computerized system used by multiple consumers,
`whether they are WHP or regular consumers, needs to
`provide to each of its consumers, at least, a predefined
`percentage of its resources according to predefined terms or
`agreements between each consumer and the corresponding
`resources owner in the computerized system. a WHP may
`offer more than the actual available resources, based on the
`low probability that all consumers will concurrently demand
`maximum resources Therefore, in order to enable different
`consumers to have their predefined share of resources, there
`is a need to limit the resources available to a specific
`consumer according to those predefined for him. Additional
`reasons for limiting the resources consumption for each
`consumer in a multiple consumer computerized system may
`be as follows:
`
`[0013]
`If the resources are not of a preempt kind (i.e.,
`non-preemptable), then a suitable process in the computer(cid:173)
`ized system should free those resources by itself, upon
`receipt of such a resource. For example, the memory or a
`suitable storage disk of a computerized system is usually
`non-preemptable. Granting a higher number of resources
`might prevent a process, before the previous resources were
`freed, from getting its share. Unfortunately, it is relatively
`complicated to remove the resources, once granted.
`
`[0014]
`If the resources are of a preempt kind (i.e., pre(cid:173)
`emptable ), then in every time-slice they are divided between
`the requesting processes. For example, a CPU is usually a
`preemptable resource. When dealing with preemptable
`resources, there are two possibilities to deal with the unused
`resources, as the allocation is performed on every time-slice
`from scratch. The first, granting the process more than his
`allocated share will make the user treat such performance as
`his base line. However, when additional consumers connect
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1028, p. 5
`
`
`
`US 2005/0246705 Al
`
`Nov. 3, 2005
`
`2
`
`to the computerized system and start to utilize their share of
`resources, then the previous consumers connected to such a
`system will suffer from a reduction in their total perfor(cid:173)
`mance. The second, limiting the resources from the begin(cid:173)
`ning, might prevent such a situation, but is less desirable
`from the end-user's point of view.
`
`[0015]
`If the resources are preemptable and an owner of a
`computerized system wishes to charge each of his consum(cid:173)
`ers differently, according to the guaranteed resources of
`each, the owner will accordingly wish to confine the con(cid:173)
`sumer to his allocated share of resources.
`
`[0016] There are several companies, such as "Ensim Cor(cid:173)
`poration", that create "static virtual computers" within the
`computer. Each "static virtual computer" is allocated a
`certain amount of CPU, memory etc. However, the comput(cid:173)
`er's owner is not able to allow the static virtual computer to
`use more than its allocated share, in case other users do not
`use their allocated share, and therefore there are available
`resources.
`
`[0017] Furthermore, in a static virtual computer, for
`example, if the WHPs want to allocate the computer
`resources to 2 different resellers (i.e., 50% for each reseller),
`and one of the resellers wants to supply his allocated part to
`2 additional users, guaranteeing 75% ( of his allocated part)
`for each, such hierarchical allocation can not be done. This
`is because 25% from the allocated resources for each user is
`less than the guaranteed resources, and 37.5% is too much
`to allow the consumers to use, as other users of the other
`reseller might be influenced.
`
`[0018]
`In the prior art, a common method of allocating
`resources of a computerized system is to provide a prede(cid:173)
`termined amount of resources to each consumer. However,
`such a method has several drawbacks, such as in a comput(cid:173)
`erized system with a relatively high number of consumers,
`adding a new consumer to such a system requires re(cid:173)
`allocating the resources for all the other consumers. For
`example, if the owner of a computerized system wants to
`share its system resources "evenly" between its consumers,
`then, for example in the case of 10 consumers-he grants
`10% of the system's resources to each (i.e., 100% of the
`system resources is allocated to all consumers). If, however,
`the owner wants to add an additional consumer to that
`system, he must update the allocated resources to each of the
`existing 10 consumers, in such a way that there will be
`available resources to the new added consumer. If there are
`numerous clients (e.g., 100, 1000 or more), this task will
`involve considerable time and/or might be prone to user
`errors while allocating all the resources for all the consumers
`each time there is a change of status in the system. The task
`of re-allocating resources increases in complexity where one
`or more consumers are granted more resources than the
`others. More complexity occurs if the owner of the com(cid:173)
`puterized system has "resellers" (i.e., consumers entitled to
`share resources with their own consumers). Typically, a
`comparison is made between what the account consumes
`and its allocated quota. However, the software re-calculates
`the system resources on each operation that might utilize
`resources. For example, if the resource that is checked for
`the comparison is memory, the comparison should be per(cid:173)
`formed only before memory allocations, however this is
`inefficient for suitable allocation due to the fact that it is only
`done before.
`
`[0019] All the methods described above have not yet
`provided satisfactory solutions to the problem of efficiently
`allocating and managing resources of a computerized system
`with multiple consumers.
`
`SUMMARY OF THE INVENTION
`
`[0020]
`It is an object of the present invention to provide a
`method for individually limiting the resources consumption
`of each consumer, whether it is a service or a user.
`
`[0021]
`It is an object of the present invention to provide a
`method for better allocating the resources between the
`consumers.
`
`[0022]
`It is still another object of the present invention to
`provide a method for allocating resources with a desired
`hierarchy.
`
`[0023]
`It is a further object of the present invention to
`provide a method and system for calculating the allocated
`resources, dynamically and on demand.
`
`[0024]
`It is yet an object of the present invention to
`provide a method and system for allowing a consumer to
`observe the current resource allocation.
`
`[0025] Other objects and advantages of the invention will
`become apparent as the description proceeds.
`
`[0026] The present invention is directed to a method for
`dynamically allocating and managing resources in a com(cid:173)
`puterized system managed by an operating system (OS) and
`having multiple accounts of consumers. Portions of the
`virtual memory address space are allocated, whenever
`desired, in a swap file, for each account associated with a
`consumer. The memory address space is limited for each
`account. The CPU usage is divided between the tasks
`requested from each account, and segments in the original
`code of the OS are changed by locating one or more specific
`procedures in the original code, and modifying the specific
`procedures to operate according to the allocation and/or the
`limitation of the memory address space and/or the limitation
`of the number of processes and/or the divided CPU usage.
`
`[0027] Preferably, the specific procedures are dynamically
`modifying to operate in response to varying allocation
`and/or limitation of the memory address space and/or the
`divided CPU usage. The location of the required procedure
`is allowed by obtaining the name of the required procedure
`that is stored in a symbol table, or by identifying a sequence
`of bytes of the required procedure.
`
`[0028]
`In order to modify a specific procedure, the allo(cid:173)
`cated memory address space is obtained and creating an
`executable code in the allocated memory address space.
`Code segments from the original code are copied, the
`commands line at the beginning of the copied code are saved
`and further commands are skipping until beginning of the
`next command in the original code. The commands line at
`the beginning of the original code is replaced by skipping to
`the beginning of the created application, and adding non(cid:173)
`operational bytes to the unused bytes of the created appli(cid:173)
`cation. The blank bytes may be No Operations (NOPs) data.
`
`[0029] The limitation of the memory address space is
`implemented by calling the original code whenever the call
`for consuming resources is not by an account of a specific
`consumer, and identifying the account by its related param-
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1028, p. 6
`
`
`
`US 2005/0246705 Al
`
`Nov. 3, 2005
`
`3
`
`eters. It is verified that the account will not exceed its quota,
`or the quota of the level above it according to the allocated
`memory address space, whenever resource consumption is
`required by an account. The result of an operation related to
`the account, whenever it succeeds is checked and the con(cid:173)
`sumption data of the account and/or of the levels above the
`account is updated. The identifying parameters may be a
`user ID, group ID or program name.
`[0030] When limiting the number of processes it is veri(cid:173)
`fied that the account will not exceed its quota, or the quota
`of the level above it, according to the allocated number of
`processes, whenever resource consumption is required by an
`account. The result of an operation related to the account,
`whenever it succeeds, is checked and the consumption data
`of the account and/or of the levels above the account is
`updated. The identifying parameters may be a user ID, group
`ID or program name.
`[0031] CPU resources that are not demanded by accounts
`according to their resource allocation policy are dynamically
`allocated to other demanding accounts and the available
`CPU resources are divided between all the tasks according
`to an optimal share allocation per each account. Division of
`the CPU usage between the tasks may be obtained by
`modifying the calculation of the "counter" of the tasks that
`are candidates for being executed, so that each task is limited
`by the quota of the account that is associated with the tasks.
`[0032] The modification of the counter calculation is per(cid:173)
`formed by intercepting the function that performs the cal(cid:173)
`culation of the "counters". Then, the desired "counter" value
`is calculated for each task, based on the guaranteed value to
`the user account and holding the correct value of the counter
`according to the quotas when its value is calculated when(cid:173)
`ever there are several tasks that belong to the same account.
`The "counter" value of the tasks is summed according to the
`account, while their internal allocation is currently per(cid:173)
`formed according to their usage. Information regarding the
`"behavior" of each process is kept and the amount of CPU
`resource that the account received during the last time is
`calculated on every "tick", and the calculated amount is
`added to the levels above the account. Whenever the account
`or a level above the account receives more than its allocated
`share, the "counter" of the task is decreased to zero, until the
`next CPU allocation is done. Whenever a decision is made
`about the next task to be executed, it is confirmed that the
`selection of the next task to be executed is valid.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`[0033] The above and other characteristics and advantages
`of the invention will be better understood through the
`following illustrative and non-limitative detailed description
`of preferred embodiments thereof, with reference to the
`appended drawings, wherein:
`[0034] FIG. 1 schematically illustrates hierarchical allo(cid:173)
`cation of resources in a computerized system with multiple
`consumers, according to a preferred embodiment of the
`invention;
`[0035] FIG. 2 schematically illustrates a modification of a
`required procedure as part of changing the OS behavior,
`according to a preferred embodiment of the invention; and
`[0036] FIG. 3 schematically illustrates the CPU usage by
`a specific account.
`
`DETAILED DESCRIPTION OF PREFERRED
`EMBODIMENTS
`
`[0037]
`In order to prevent consumers from exceeding the
`allocated resources in a computerized system, there is a need
`to limit the resources, such as the memory, number of
`processes and the CPU usage available to each consumer
`from such a system.
`[0038] The embodiments described hereinafter will be
`more apparent after clarifying the following terms:
`[0039] Program-An executable file that the kernel
`can read to memory and execute.
`[0040] Process-An executing instance of a pro(cid:173)
`gram. Every process in Unix is guaranteed to have a
`unique numeric identifier called Process ID (PID).
`[0041] A thread is a single sequential flow of control
`within a process. A process can thus have multiple concur(cid:173)
`rently executing threads. In Linux, each thread has its own
`PID.
`[0042]
`In Linux OS, the function that creates processes is
`do_fork. The functions that handle process termination are
`the exit family. A simple implementation could be to keep a
`counter per user that the system increases/decreases accord(cid:173)
`ing to initiation/termination of processes per account, except
`for processes owned by "root" (UID 0). When an account
`tries to initiate new process that causes it to exceed its quota,
`the system will fail performing the "fork" ( or "vfork",
`"thread_ create") function. Hierarchy semantics is the same
`as of the memory management.
`[0043] The following describes a mechanism for limiting
`the memory consumption of a specific account in the com(cid:173)
`puterized system. But first, for the sake of clarity, the method
`for allocating memory in an Operation System such as Unix,
`Linux, etc. will be described.
`[0044] Each executed application obtains a portion of
`memory area, from which it runs or operates. A memory
`area, referred to hereinafter as "memory address space",
`comprises relevant data of specific executed applications.
`The memory address space is only a portion of a virtual
`memory specific to each application. Each application has
`its own range of virtual memory, usually unrelated to the
`address space of other applications, or to the size of the
`physical computer on which the application is executed.
`[0045] Typically, the memory is divided into "pages",
`which is the basic unit handled by a memory management
`application. A memory manager can store the "pages" in the
`physical memory of the computer, or on the hard disk (in a
`so-called "Swap" section). The "swap" acts as a storage
`memory and temporarily stores data portions of the appli(cid:173)
`cation on the hard disk, typically, when there is not enough
`physical memory space for all the programs. The swap can
`be a set of files, special disk partitions, or both. Information
`can be stored on the hard disk ( either in the "swap" or in real
`files) for the following reasons:
`[0046] The memory manager transfers a relatively less
`relevant "page" to the "swap", to free storage space in the
`(faster) physical memory, for other pages that are currently
`required. The memory manager transfers only pages that
`might be changed by an application, the other pages being
`restored from their initial address ( as will be described
`hereinafter).
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1028, p. 7
`
`
`
`US 2005/0246705 Al
`
`Nov. 3, 2005
`
`4
`
`[0047] The page is part of the writeable area of the
`program, but the program does not change it. In this case, the
`page can be loaded from the disk when next needed.
`[0048] The page is part of the application "code" (i.e., the
`command line that the application executes, and not the data
`part of the application). The application code cannot be
`changed by the application itself, and therefore, if a page is
`removed from the memory, the memory manager can,
`retrieve it from the application file again.
`[0049] The page is part of the application "read only" data.
`The "read only" data cannot be changed by the application
`itself, and therefore, if a page is removed from the memory,
`the memory manager can again retrieve it from the appli(cid:173)
`cation file.
`[0050] The page is part of a file of an operation system
`such as the "mmap"ed file in Unix. The "mmap" function
`maps "length" bytes starting at the offset from the file ( or
`other object) specified by a variable that is passed to
`"mmap", such as the variable file descriptor (fd), into the
`memory, preferably at the address of the parameter that is
`passed to "mmap", such as the parameter "start").
`[0051] After the mapping, the program can access the file
`just like any part of its memory, without the need to actually
`read the information into buffers that it allocates. In that
`case, a file is mapped to part of the memory of an application
`and there is no need to keep the pages in the swap file, as
`they can be read from the hard disk.
`[0052] According to a preferred embodiment of the inven(cid:173)
`tion, in order to avoid exceeding the allocated memory of a
`consumer's account, the allocated memory address space on
`the swap file of that account is limited. In contrast, the
`physical memory used by an application is not limited, and
`thus this eliminates interference with the way in which the
`operating system works and decides what pages to swap. In
`the operating systems, such as Linux™ and Unix™, the
`amount of memory that a program utilizes can be influenced
`by one or more of the following methods:
`[0053]
`Initial allocation of memory, when the process is
`created;
`[0054] Enlargement of memory, due to one or more
`requests that utilized all the memory available ( e.g., the
`function "malloc" in Unix, which requests the OS to allocate
`more memory to the process. The OS might prefer to
`allocate more than the program requests, to handle the case
`where the program might request more pages later on. This
`is part of the memory management of the OS. The function
`"malloc" is standard in C and C++, and is available on
`Windows™ as well.)
`[0055] Mapping to a file (e.g., using the "mmap" func(cid:173)
`tion), that maps a file to a specific memory address space.
`[0056] Creating a shared memory region (e.g., using the
`function "shmget", wherein "shmget" enables a program to
`request a certain amount of memory from the OS, and in turn
`it associates an identifier with that program. Other programs
`might use this memory as well, by using the related iden(cid:173)
`tifier. The function "shmget" is a mechanism for sharing
`information between processes.).
`[0057] As will be explained hereinafter, all the above
`methods and other possible methods are mapped to a rela(cid:173)
`tively small set of functions in the kernel of the operation
`system.
`
`[0058] For example, in Linux with version of kernel 2.2 all
`the operations are mapped to a function in the kernel, named
`"do_mmap". The "do_mmap" function gets the following
`parameters:
`
`[0059] Access mode-Read/Write (RW) or Read Only
`(RO). If it is RO, then the memory can be accessed for read
`only, and in that case, no swap space is allocated, as the
`information can be retrieved from its place of origin. In this
`case, the method of the present invention does nothing.
`
`[0060] Mapping-private or shared in the case of RW. If
`it is shared, only the creator of the shared storage should be
`charged for this memory. The term private refers to a
`memory that only a specific program can access, such as
`memory that was allocated when the specific program
`started running, or that was "malloc"ed. The term Shared
`refers to one that is shared between processes, for example,
`while loading a shared object (e.g., a Dynamic Link Library
`(DLL, which is a collection of small programs, each of
`which can be called when needed by a larger program that
`is running in the computer, in Windows2000 environment.
`
`[0061] Of course, the "do_mmap" function is only one
`example of a Linux implementation, and such operation is
`suitable to other functions as well.
`
`[0062] Therefore, the only situation that involves allocat(cid:173)
`ing swap space is when the application asks for a private
`memory for RW.
`
`It is important to note that a function such as
`[0063]
`"do_mmap" returns the relevant memory addresses, but the
`pages are not allocated in the physical ( and thus not in the
`swap) memory, until they are actually used. The allocation
`is on a page basis, so a program can allocate one hundred
`pages, and access only two of them ( at the beginning and end
`of the memory, for example). In that case, only two pages are
`allocated in the memory, and thus can be moved into the
`'swap'.
`
`[0064] According to a preferred embodiment of the inven(cid:173)
`tion, it is assumed that all the pages are used and the
`calculation of memory usage is performed when the page is
`allocated. According to another preferred embodiment of the
`invention, the actual consumption is checked whenever a
`page is used for the first time. However, this might cause a
`program to stop working while accessing a valid address,
`which does not comply with the behavior of the OS. In order
`to allow the program to behave normally, without being
`aware that it is controlled by the embodiment of the inven(cid:173)
`tion, the present invention complies with the OS behavior.
`
`[0065]
`
`Interfering with the OS
`
`[0066]
`In the prior art, there are several known methods
`for changing the behavior of an operating system, such as:
`
`[0067] Changing the source code of the operating system.
`This solution is problematic, as the source code is not always
`available. If it is available, it must usually be maintained,
`and therefore, the solution of modifying the code would
`require updating every new version of the code that might be
`distributed.
`
`[0068] Use "hooks" in a code. Typically, an OS has
`"hooks" that may be used. These hooks are places that the
`OS activates specific modules that are defined by a user,
`wherein the OS performs specific operations. However,
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1028, p. 8
`
`
`
`US 2005/0246705 Al
`
`Nov. 3, 2005
`
`5
`
`"hooks" must be implemented as part of the OS, and
`therefore can be used only where the OS writers locate it.
`
`[0069] According to a preferred embodiment of the inven(cid:173)
`tion, no code change is made. Instead, it locates a required
`procedure in the code of the kernel, and then modifies it into
`a suitable code, as will be described hereinafter.
`
`[0070] Locating the Required Procedure
`
`[0071] The required procedure exists in the kernel's code,
`and therefore locating it in the kernel can be obtained, for
`example, by using the name of the required procedure that
`is stored in a suitable symbol table. Of course, the required
`procedure can be located in other ways, such as, if, for
`example, the function is 'not exported', there could be a
`mechanism used for locating a specific sequence of bytes of
`that function, etc.
`
`[0072] Modifying the Required Procedure
`
`[0073] FIG. 2 schematically illustrates a modification of a
`required procedure, according to a preferred embodiment of
`the invention. Modifying the required procedure (i.e., chang(cid:173)
`ing an original code) is done in the following way:
`
`[0074] Loading all the functions as will be mentioned later
`on, using, for example, the "insmod" program in Kernel 2.2
`of Linux.
`
`[0075] Allocating a required range of memory address
`space to be used by a New code 21.
`
`[0076]
`In this allocated range, creating a code, which are
`a series of commands (i.e., New code 21), that performs the
`logic mentioned later.
`
`[0077] Keeping the commands lines at the beginning of
`the copied code 22, and then performing a "jump" to the
`beginning of the next command in the Original code 20.
`
`[0078] Replacing the commands line at the beginning of
`the Original code 20 with a "jump" to the beginning of the
`New code 21, and adding bytes with that perform no
`operation, such as No Operations (NOPs), until the end of
`the relevant command. For example, if the function starts
`with three commands comprising four bytes each, and the
`"jump" comprises six bytes, then two NOPs are added, so
`that jumping to the place after the "jump" will not result in
`performing an unintended code.
`
`In the new code 21, one can call the original code
`[0079]
`20 by calling the code in the copied code 22. Original code
`20 performs the actual operation, which is the service of the
`relevant system module, such as memory allocation, CPU
`allocation or other suitable logic allocation by changing the
`program's information, parameters in the kernel, and any
`o