Apparatus and method for adaptive context switching scheduling scheme for fast block input and output

Abstract

Provided is a method and apparatus for an adaptive context switching for a fast block input/output. The adaptive context switching method may include: requesting, by a process, an input/output device to perform an input/output of data; comparing a Central Processing Unit (CPU) effectiveness based on whether the context switching is performed; and performing the input/output through the context switching to a driver context of the input/output device, or directly performing, by the process, the input/output based on a comparison result of the CPU effectiveness.

Claims

1. A method for adaptive context switching by a computer, the method comprising: comparing a first efficiency (Eacs) for a direct I/O operation against a second efficiency (Ecs) for a context switching without a direct memory access(DMA); performing, upon a determination that Eacs>Ecs, the direct I/O operation; and performing, upon a determination that Eacs<Ecs, the direct I/O operation using the context switching without the DMA, wherein the Eacs is a function of at least the following factors: an amount of time used to transmit the data from a buffer cache to a memory via a bus (Tb), an amount of response standby time until an interrupt is received (Tw), and a temporally overlapping interval (Tv), and wherein Tv is the temporally overlapping interval between an amount of time used to read data and to transmit the read data to the buffer cache (Td) and Tb.

2. The method for adaptive context switching of claim 1, wherein:
Eacs=Tb(Tw+Tb−Tv).

3. The method of adaptive context switching of claim 1, wherein wherein the Ecs is a function of at least the following factors: an amount of response standby time until an interrupt is received (Tw), an amount of time used to transmit the data from a buffer cache to a memory via a bus (Tb), an amount of time used for the context switching (Tc), a temporally overlapping interval (Tv), and wherein Tv is the temporally overlapping interval between an amount of time used to read data and to transmit the read data to the buffer cache (Td) and Tb.

4. The method of adaptive context switching of claim 3, wherein:
Ecs=(Tw+Tb)/(Tw+Tb+(2Tc)−Tv).

Description

BRIEF DESCRIPTION OF DRAWINGS

(1) FIG. 1 is a flowchart illustrating a method for an adaptive context switching for a fast block input/output according to an embodiment of the present invention;

(2) FIG. 2 is a flowchart illustrating a process of performing an input/output process based on whether a context switching is performed according to an embodiment of the present invention;

(3) FIG. 3 is a diagram illustrating a flow of different times needed when a context switching is performed according to an embodiment of the present invention;

(4) FIG. 4 is a diagram illustrating a flow of different times needed when an input/output is directly performed without performing a context switching according to an embodiment of the present invention;

(5) FIG. 5 is a block diagram illustrating a configuration of an apparatus for an adaptive context switching for a fast block input/output according to an embodiment of the present invention; and

(6) FIG. 6 is a block diagram illustrating a configuration of a CPU effectiveness comparison unit of FIG. 5.

DETAILED DESCRIPTION OF THE INVENTION

(7) Reference will now be made in detail to embodiments of the present invention, examples of which are illustrated in the accompanying drawings, wherein like reference numerals refer to the like elements throughout. The embodiments are described below in order to explain the present invention by referring to the figures.

(8) FIG. 1 is a flowchart illustrating a method for an adaptive context switching for a fast block input/output according to an embodiment of the present invention.

(9) In operation S110, a process may request an input/output device to perform an input/output of data. Specifically, when the process having requested the input/output desires to input or output the data, the process may request the input/output of the data. Hereinafter, a data input/output operation will be described based on, for example, a data read operation.

(10) The method for the adaptive context switching for the fast block input/output may further include verifying whether the input/output devices uses a Direct Memory Access (DMA). The DMA denotes a hardware mechanism that allows a memory to directly transmit and receive input/output data without using a main Central Processing Unit (CPU) in a block input/output. At least one of an input/output response time and a CPU effectiveness may be considered to determine whether the context switching is performed. Here, the CPU effectiveness may be differently calculated with respect to a case where the DMA is used and a case where the DMA is not used. Accordingly, whether the DMA is used may be initially verified.

(11) In operation S120, the CPU effectiveness may be compared based on whether the context switching is performed. Specifically, based on whether the context switching is performed, it is possible to compare the CPU effectiveness according to a first input/output operation where the process having requested the input/output directly performs the input/output, and the CPU effectiveness according to a second input/output operation where the input/output is performed through the context switching to a driver context of the input/output device.

(12) An operation of calculating the input/output response time and the CPU effectiveness will be further described with reference to FIGS. 3 and 4.

(13) FIG. 3 is a diagram illustrating a flow of different times needed when a context switching is performed according to an embodiment of the present invention.

(14) FIG. 3 shows an amount of time used for each of a process 310 having requested an input/output, a third process 320, and an input/output device 330 when the input/output is performed through the context switching. In FIG. 3, Tc denotes an amount of time used for the context switching and Tw denotes an amount of response standby time until an interrupt is received from the input/output device 330. Tw includes To and Td. To may include at least one of an input/output command process time, a seek time, and a rotation delay time. Td denotes an amount of time used to read data from a physical disk, and to transmit the read data to a buffer cache. Tb denotes an amount of time used to transmit the data from a buffer cache of a disk to a memory via a bus. A temporally overlapping interval may occur between Td and Tb. The temporally overlapping interval may be defined as Tv. Specifically, Tv may correspond to an overlapping interval that may occur during a process of generating the interrupt and transmitting the data to the memory via the bus in a state where a data transmission is not completed, when transmitting the data from the disk to the buffer cache. The process 310 having requested the input/output may be in a sleep state until the data transmission is entirely completed. When the data transmission is completed, a scheduler may wake the process 310 in the sleep state whereby an operation may proceed. An amount of time used for the process 310 having requested the input/output to enter the sleep state and be awaken is referred to as the amount of input/output response time. An example of the input/output response time when the context switching is performed may be expressed by the following Equation 1:
R.sub.cs=T.sub.w+T.sub.b+2.Math.T.sub.c−T.sub.v  [Equation 1]

(15) FIG. 4 is a diagram illustrating a flow of different times needed when a process 410 having requested an input/output directly performs the input/output without performing a context switching according to an embodiment of the present invention. For a period of time corresponding to Tw−Tv without performing the context switching, the process 410 may be waiting until a data transmission preparation interrupt is received from a disk, and may transmit data during a period of time corresponding to Td using a CPU. Accordingly, an input/output response time when the process 410 having requested the input/output directly performs the input/output may be expressed by the following Equation 2:
R.sub.acs=T.sub.w+T.sub.b−T.sub.v  [Equation 2]

(16) Based on a comparison between the above Equation 1 and Equation 2, it can be known that, when the process 410 directly performs the input/output, an amount of time of 2×Tc may be saved. However, when the process 410 directly performs the input/output, the CPU may not allocate an amount of time corresponding to Tw−Tv to another process. Therefore, it is possible to additionally review a CPU effectiveness. Accordingly, the CPU effectiveness may be expressed by the following Equation 3:

(17) $\begin{array}{cc}E=\frac{T_r}{T_{\mathrm{io}}}& \left[\mathrm{Equation}3\right]\end{array}$

(18) Tio denotes an input/output response time used until the input/output is completed, and Tr denotes an actual amount of time a CPU is allocated to the process 410 and processing of the calculation. When the context switching is performed, the CPU may be allocated to another device for a period of time corresponding to Tw to process the calculation, and a driver context of an input/output device may process an input/output request for a period of time corresponding to Tb. Accordingly, when the input/output device performs the context switching without using the DMA, the CPU effectiveness may be expressed by the following Equation 4:

(19) $\begin{array}{cc}{E}_{\mathrm{cs}}=\frac{T_w+T_b}{T_w+T_b+2.Math.T_c-T_v}.& \left[\mathrm{Equation}4\right]\end{array}$

(20) When the input/output is directly performed, the CPU may need to wait for a period of time corresponding to Tw until an interrupt is received from the input/output device. Therefore, the standby time may not be included in Tr. Only Tb where the input/output is executed may be included in Tr. Accordingly, when the input/output is directly performed, the CPU effectiveness may be expressed by the following Equation 5:

(21) $\begin{array}{cc}{E}_{\mathrm{acs}}=\frac{T_b}{T_w+T_b-T_v}& \left[\mathrm{Equation}5\right]\end{array}$

(22) Here, a criterion to determine whether to directly perform the input/output when the DMA is not used may include an excellent performance in an aspect of the input/output response time. In an aspect of the CPU effectiveness, for example, the input/output may be directly performed when the following Equation 6 is satisfied, Equation 6 being given by:
E.sub.acs>E.sub.cs  [Equation 6]

(23) The CPU effectiveness when the DMA is used may be calculated to be different from the CPU effectiveness when the DMA is not used. When the DMA is used, it may be classified into a case where the CPU directly performs the input/output in a process context, or into a case where the DMA is used after the context switching to the driver context of the input/output device is performed. In an aspect of the input/output response time, to perform the input/output without performing the context switching may not use a time used for the context switching and thus be more advantageous. However, in an aspect of the CPU effectiveness, when the context switching is performed, it is possible to process both Tw and Tb using the DMA. During the above period of time, the scheduler may allocate the CPU to another process. Accordingly, it is possible to utilize an amount of time corresponding to twice an amount of time of Tw+Tb. Accordingly, when the context switching is performed by using the DMA, the CPU effectiveness may be expressed by the following Equation 7:

(24) $\begin{array}{cc}{E}_{\mathrm{cs\_dma}}=\frac{\left(T_w+T_b\right).Math.2}{T_w+T_b+2.Math.T_c-T_v}.& \left[\mathrm{Equation}7\right]\end{array}$

(25) When the process having requested the input/output performs the input/output without attempting the context switching, the CPU effectiveness may be expressed the same as in the above Equation 5. Therefore, when the process directly performs the input/output using the DMA, the CPU effectiveness may be expressed by the following Equation 8:

(26) $\begin{array}{cc}{E}_{a\mathrm{cs\_dma}}=\frac{T_b}{T_w+T_b-T_v}.& \left[\mathrm{Equation}8\right]\end{array}$

(27) Accordingly, when the process directly performs the input/output using the DMA, the CPU effectiveness may be expressed by the following Equation 9:
E.sub.acs.sub._.sub.dma>E.sub.cs.sub._.sub.dma  [Equation 9]

(28) The aforementioned schemes of calculating the input/output response time and the CPU effectiveness are only examples and thus it is possible to calculate the input/output response time and the CPU effectiveness using various types of schemes and equations.

(29) Accordingly, the adaptive context switching may classify whether the DMA is used, whereby the process having requested the input/output may directly perform the input/output when the above Equation 6 or Equation 9 is satisfied.

(30) Here, the process having requested the input/output may directly perform the input/output only when a request in a response standby state does not exist in a queue of the input/output device. Specifically, when the request exists, the process may perform the context switching.

(31) Referring again to FIG. 1, in operation S130, the process may perform the input/output based on the comparison result. Specifically, when the CPU effectiveness according to the first input/output operation is greater than the CPU effectiveness according to the second input/output operation, the process may perform the first input/output operation. When the CPU effectiveness according to the second input/output operation is greater than the CPU effectiveness according to the first input/output operation, the process may perform the second input/output operation.

(32) Also, operation S130 may include determining whether a request in a response standby state exists in a queue of the input/output device exists, and performing the input/output through the context switching to the driver context of the input/output device when the request exists. Specifically, only when the response in the response standby state does not exist in the queue of the input/output device, may the adaptive context switching scheme be performed. When the request exists in the queue of the input/output device, the input/output may be performed only through the context switching.

(33) Also, the adaptive context switching method may further include determining whether the input/output device corresponds to a fast block device. When the input/output device corresponds to the fast block device, operations S110 through S130 may be performed.

(34) According to an embodiment of the present invention, when a process executes an input/output, whether a context switching is performed may be determined based on a CPU effectiveness. Through this, it is possible to enhance a use effectiveness of a CPU, and to obtain a quick response time.

(35) FIG. 2 is a flowchart illustrating a process of performing an input/output process based on whether a context switching is performed according to an embodiment of the present invention.

(36) Referring to FIG. 2, in operation S210, a process may request an input/output of data.

(37) In operation S220, the process may register the input/output in a block input/output structure in a kernel mode.

(38) In operation S230, the process may merge the input/output with an input/output waiting in a current device or change a sequence the input/output in order to decrease a motion of a head of a disk drive. To handle the input/output as above may be performed using an elevator algorithm, and may be performed based on a Logical Block Address (LBA) on a system side.

(39) In operation S240, the process having requested the input/output may determine whether to perform the input/output directly or through the context switching. At least one of an input/output response time and a CPU effectiveness may be considered to determine whether to perform the input/output directly or through the context switching.

(40) In operation S250, when the process having requested the input/output determines to directly perform the input/output, the process may directly process the input/output.

(41) Conversely, when the process having requested the input/output determines to perform the input/output through the context switching instead of directly processing the input/output, the process may be switched to an unplug and sleep state in operation S260, and may call an input/output scheduler in operation S270. In this instance, the context switching from a process context to a device driver context may occur.

(42) In operation S280, a device driver may process the input/output one by one until all the input/output is completed. When the input/output is completed, the context switching may occur again and the input/output scheduler may wake the process in the sleep state.

(43) Specifically, a system performance may be enhanced by selectively determining whether the context switching is performed based on the input/output response time and the CPU effectiveness.

(44) FIG. 5 is a block diagram illustrating a configuration of an apparatus for an adaptive context switching for a fast block input/output according to an embodiment of the present invention. FIG. 6 is a block diagram illustrating a configuration of a CPU effectiveness comparison unit of FIG. 5.

(45) Referring to FIG. 5, the adaptive context switching apparatus may include an input/output request unit 510, a CPU effectiveness comparison unit 520, and an input/output performing unit 530. The adaptive context switching apparatus may further include a DMA utilization verifying unit (not shown).

(46) A process may request an input/output device (not shown) to perform an input/output, using the input/output request unit 510.

(47) The DMA utilization verifying unit may verify whether the input/output device uses a DMA.

(48) The CPU effectiveness comparison unit 520 may compare a CPU effectiveness based on whether the context switching is performed. Hereinafter, a configuration of the CPU effectiveness comparison unit 520 will be further described.

(49) Referring to FIG. 6, the CPU effectiveness comparison unit 520 may include a CPU effectiveness calculation unit 610 and an effectiveness comparison unit 620.

(50) A first CPU effectiveness calculation unit 611 may calculate the CPU effectiveness according to a first input/output operation where the process having requested the input/output directly performs the input/output, and the CPU effectiveness according to a second input/output operation where the input/output is performed through the context switching to the driver context of the input/output device, when the input/output device does not uses a DMA. A second CPU effectiveness calculation unit 612 may calculate the CPU effectiveness according to the first input/output operation and the CPU effectiveness according to the second input/output operation, when the input/output device uses the DMA. The first CPU effectiveness calculation unit 611 and the second CPU effectiveness calculation unit 612 may be included in the CPU effectiveness calculation unit 610.

(51) The effectiveness comparison unit 620 may compare the CPU effectiveness according to the first input/output operation and the CPU effectiveness according to the second input/output operation. Specifically, based on whether the input/output device uses the DMA, the effectiveness comparison unit 620 may compare the CPU effectiveness calculated when the process directly performs the input/output, with the CPU effectiveness calculated when the process performs the input/output through the context switching.

(52) Referring again to FIG. 5, the input/output performing unit 530 may perform the input/output based on the comparison result. Specifically, the process having requested the input/output may perform the input/output directly or through the context switching based on the comparison result of the CPU effectiveness.

(53) Since the context switching is selectively performed in the input/output of data in order to further effectively use a main CPU according to a change of hardware, it is possible to more adaptively cope with the change of hardware, and to enhance a system performance.

(54) In computing-based embedded systems, for example, a television (TV), a portable multimedia player (PMP), an ultra mobile PC (UMPC), a notebook, and the like, when a context switching is performed every time an input/output request is received, overload may occur in loading a small amount of data. Also, a booting time may increase. Accordingly, a booting time may decrease in a computing-based system by selectively performing the context switching.

(55) Although a few embodiments of the present invention have been shown and described, the present invention is not limited to the described embodiments. Instead, it would be appreciated by those skilled in the art that changes may be made to these embodiments without departing from the principles and spirit of the invention, the scope of which is defined by the claims and their equivalents.