Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1993-09-16
2001-07-03
Ellis, Kevin L. (Department: 2751)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C710S005000
Reexamination Certificate
active
06256704
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of managing the processing of quantities of data spanning logical disk partitions in computer systems. More particularly, the present invention relates to methods for optimizing data access across multiple logical partitions spread across one or more physical disk drives, and particularly for the transfer of large quantities of data. It is noted that the term “physical disk” is used in relation to the present invention to indicate any permanent storage device for data where the device includes an access mechanism; e.g., a disk drive head arm carrying one or more read/write heads that are capable of reading/writing one discrete area of the disk medium at any one time, and require time to move from one area of the medium to another.
DESCRIPTION OF THE PRIOR ART
A crucial characteristic of any file system associated with an operating system for a computer is how well the file system performs. Conventionally, all application file I/O is accomplished by, and through, the operating system file system. By way of example, in the IBM Operating System/2
1
* (OS/2*), which is a multi-tasking operating system where multiple programs execute concurrently, application programs access the file system through the application programming interface. When considering the speed of a computer, file operations are slow. For example, reading a sector from a disk is about 100 to 200 times slower than copying the same amount of data from the computer memory. Disk access time may be 40 milliseconds (ms) or more, depending upon sector location, the position of the read/write head, and the disk speed. Compare this with a memory-memory move of 512 bytes of data, which requires about 0.4 ms on an 8 MHz machine. Now consider the time to move large quantities of data to, or from, a hard file.
1
. * indicates a trademark of International Business Machines Corporation.
Large hard files, or hard disks, are usually supported as multiple “logical” devices. Disk partitioning is a very simple concept which is implemented fundamentally in the disk device driver. Each physical disk is divided into one or more areas called partitions or logical partitions. Each of the disk partitions is treated as a separate and distinct volume. In this connection, the file system, associated with the operating system (in our example, OS/2*), refers to each partition with a different drive identifier as if it were a different disk drive.
Much has been written and accomplished concerning methods of optimizing disk reading and writing at the file or sector level. These activities usually relate to readahead, data caching, data blocking, and the like. Typically, these activities do not assume any application type that is requesting the disk accesses. However, it is considered that these optimization are low-level and do not take into account operations which include reading to, and writing from, multiple logical partitions and physical disks. Additionally, these optimization are general purpose and are not tuned for any specific type of data access.
For example, with an operating system such as OS/2*, there is nothing which optimize applications where large quantities of data, spanning multiple disks and logical partitions, are to be transferred. These include such applications as disk backup and restore. These applications should take advantage of concurrency provided by the operating system and disk subsystems without using concurrency in a way which hinders overall performance. Generally, they do not. There has been limited prior activity in attempting to optimize on a fundamental level the transfer of large quantities of data when using partitioned drives. These attempts generally used one of two approaches: (1) Serialize the transfer tasks, or (2) perform all transfer tasks in parallel. The former operation is only optimum if all partitions are on a single drive. The latter task handling approach optimize for one partition on each of several drives, but bogs down when several partitions are located on each drive and concurrent transfer of data from multiple partitions on one drive is attempted. With requests for work which span multiple logical drives, for example, to backup a storage group (files in one or more partitions), it is highly desirable for performance efficiency to allow for parallel processing using a multi-threaded approach to handling the requests.
This utilizes parallelism to achieve the advantage of all of the available machine cycles. [NOTE: In a multitasking system, programs are associated with dispatchable units. Dispatchable units identify the programs that the operating system may run concurrently. A thread identifies a dispatchable unit of work or work element (a program runs within a thread).]
Multiple threads, one per physical hard file, will clearly outperform a single thread reading from multiple physical media serially. However, a multi-threaded approach can actually result in poorer performance than a single-threaded model if multiple threads end up spawned against a single physical hard file; e.g., disk (with multiple partitions). Each thread is I/O intensive and has the task of reading all the data from a logical partition. In a multi-tasking operating system, such as OS/2*, the multiple threads spawned contend for the read/write head of the hard file, causing thrashing (inefficient seeks) and degrading performance. In the OS/2* operating system, since time slicing is employed for multi-tasking, processor time is also wasted by this thrashing.
SUMMARY OF THE INVENTION
In view of the above, it is a principal object of the present invention to optimize concurrent data transfer tasks in a multi-tasking operating system environment (for example OS/2*) when large quantities of data are required to be transferred from multiple physical disk drives, at least one of which includes multiple logical partitions. This is accomplished, in accordance with the invention, by grouping large data access tasks against partitions on the physical disk that will be read from or written onto, and by executing threads serially, in accordance with a task list for the disk, while executing or dispatching parallel or concurrent thread execution on other disks. In this manner, concurrent tasks will not interfere with one another by contending for a disk read/write head, and optimum concurrency of tasks may be achieved.
Another object of the present invention is to maximize the transfer efficiency of large quantities of data to/from secondary memory storage in the environment heretofore described. This is accomplished by performing a partition analysis before dispatching program threads to work concurrent tasks. The partition analysis maps logical partitions to physical disks, and then creates a task list for each physical disk. A concurrent execution routine (referred to as a “thread of execution” or simply a “thread”) is then dispatched to process the task list for each physical disk.
The result of the partition analysis and consequent mapping into task lists for each physical disk and concurrent task dispatch causes only one task operation on each physical disk at any given moment. In this manner, optimum use of concurrency without causing disk head contention, which tends to slow down overall performance, is achieved. It should be noted that the present invention, while not including any low-level general purpose disk optimization at the read/write head or sector level, does operate in a manner to take advantage of schemes which may be available; e.g., read ahead, data caching, blocking, etc.
Other objects and a more complete understanding of the invention may be had by referring to the following description taken in conjunction with the accompanying drawings.
REFERENCES:
patent: 4371929 (1983-02-01), Brann et al.
patent: 4454595 (1984-06-01), Cage
patent: 4722051 (1988-01-01), Chattopadhya
patent: 4905141 (1990-02-01), Brenza
patent: 5220653 (1993-06-01), Miro
B.R. Howarth, “A Review of Disk Scheduling Policies”, The Australian Computer Journal, V
Hlava Alan
Mastie Scott David
Roberts Arthur Ray
Dick Wm. B.
Ellis Kevin L.
International Business Machines - Corporation
Sullivan Robert M.
LandOfFree
Task management for data accesses to multiple logical... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Task management for data accesses to multiple logical..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Task management for data accesses to multiple logical... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2558498