Method to update a data structure disposed in an embedded device

A method to update a data structure is disclosed. The method receives a write thread, and sets a data structure indicator to indicate that the data structure is unusable. The method creates (N) thread indicators, and assigns each of said (N) indicators to a different one of said (N) threads. Upon return to the thread dispatcher, the (i)th thread sees the data structure indicator which shows that the data structure is unusable. The method then sets the (i)th thread indicator to indicate that upon subsequent dispatches the (i)th thread will see the data structure indicator that shows that the data structure is unusable. After each of the (N) threads has seen the data structure indicator marking the data structure as unusable, the method sets the data structure indicator to indicate that the data structure is invalid, updates the data structure, and sets the data structure indicator to indicate that the data structure is valid.

FIELD OF THE INVENTION

This invention relates to a method for efficient serialization. In certain embodiments, the invention relates to a method to update a data structure data read by multiple threads.

BACKGROUND OF THE INVENTION

Automated media storage libraries are known for providing cost effective access to large quantities of stored media. These media libraries are often interconnected with one or more host computers. Those one or more host computers write information to one or more information storage media disposed in the library, and/or read information from those one or more information storage media.

The various components of such media storage libraries often include what are sometimes referred to as “embedded” systems, applications, or devices. Such embedded systems comprise special purposes systems requiring high performance but having relatively few dedicated resources. For example, embedded devices typically comprise relatively little memory, a low performance processor, few if any standard utilities, and no hard disks.

In addition, embedded devices typically do not comprise a conventional operating system. A conventional operating system is written for flexibility. An embedded system, however, performs a single purpose. Therefore, such an embedded device operates using a device microcode written to optimize the device's single function.

A PCI card comprises such an embedded device. Such a PCI card typically includes a processor, a flash memory, and SDRAM. A FICON interface card comprises another such embedded device.

Using prior art methods, serialization is performed using “locks.” One thread obtains a lock to update or read a data structure. A second thread attempting to access the data structure must wait until the first thread completes its read/update. That second thread can then obtain the lock. These prior art methods are inefficient for structures that are updated infrequently but read frequently, such as data structures disposed in an embedded device's microcode, because the embedded device's processor must contend for the lock before being able to read the data structure.

What is needed is a method to update a data structure without first obtaining a lock. Applicant's invention includes a method to update a data structure without first obtaining a lock for that data structure.

SUMMARY OF THE INVENTION

Applicants' invention includes an apparatus and method to update a data structure disposed in an embedded device. The method provides a data structure comprising first information, (N) non-preemptable threads, a thread dispatcher, and a data structure indicator.

The method receives a write thread comprising second information, and sets the data structure indicator to indicate that the data structure is unusable. The method, creates (N) thread indicators, and assigns each of said (N) indicators to a different one of said (N) threads. Upon returning to the thread dispatcher, the (i)th thread sees the data structure indicator which indicates that the data structure is unusable. The method then sets the (i)th thread indicator.

The method determines if each of the (N) threads has seen the data structure indicator which indicates that the data structure is unusable. If each of the (N) threads has seen the data structure indicator which indicates that the data structure is unusable, then the method sets the data structure indicator to indicate that the data structure is invalid, updates the data structure to comprise the second information, and sets the data structure indicator to indicate that the data structure is valid.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

This invention is described in preferred embodiments in the following description with reference to the Figures, in which like numbers represent the same or similar elements. The invention will be described as embodied in an information storage and retrieval subsystem for use in a data processing environment. The following description of Applicant's method to update a data structure read by multiple threads is not meant, however, to limit Applicant's invention to either data storage and retrieval systems, or to data processing applications, as the invention herein can be applied to updating a data structure in general.

In the illustrated embodiment ofFIG. 1, Applicants' information storage and retrieval system100includes a first cluster101A and a second cluster101B. Each cluster includes a processor portion130/140and an input/output portion160/170, respectively. Internal PCI buses in each cluster are connected via a Remote I/O bridge155/165between the processor portions130/140and device I/O portions160/170, respectively.

In the illustrated embodiment ofFIG. 1, system100is capable of communicating with host computer125via communication link127. In certain embodiments, communication link127is selected from a serial interconnection, such as RS-232 or RS-422, an ethernet interconnection, a SCSI interconnection, a Fibre Channel interconnection, an ESCON interconnection, a FICON interconnection, a Local Area Network (LAN), a private Wide Area Network (WAN), a public wide area network, Storage Area Network (SAN), Transmission Control Protocol/Internet Protocol (TCP/IP), the Internet, and combinations thereof.

Information storage and retrieval system100further includes a plurality of host adapters102-105,107-110,112-115, and117-120, disposed in four host bays101,106,111, and116. Each host adapter may comprise one or more Fibre Channel ports, one or more FICON ports, one or more ESCON ports, or one or more SCSI ports. Each host adapter is connected to both clusters through one or more Common Platform Interconnect bus121such that each cluster can handle I/O from any host adapter.

I/O portion160further comprises a plurality of device adapters, such as device adapters165,166,167, and168, and information storage media organized into two arrays, namely array “A” and array “B”. The illustrated embodiment ofFIG. 1shows two information storage arrays. In other embodiments, Applicants' information storage and retrieval system includes more than two information storage arrays. Each such information storage array appears to a host computer as one or more logical devices.

In certain embodiments, Applicants' information storage media comprise magnetic media, such as for example hard disks disposed in individual hard disk drive units. In certain embodiments, Applicants' information storage media comprise optical media, such as for example CDs, DVDs, and the like. In certain embodiments, Applicants' information storage media comprise electronic storage media, such as PROMs, EPROMs, EEPROMs, Flash PROMs, compactflash, smartmedia, and the like.

In certain embodiments, arrays “A” and “B” utilize a RAID protocol. In certain embodiments, arrays “A” and “B” comprise what is sometimes called a JBOD array, i.e. “Just a Bunch Of Disks” where the array is not configured according to RAID. As those skilled in the art will appreciate, a RAID (Redundant Array of Independent Disks) rank comprises independent information storage media configured in an array to obtain performance, capacity and reliability that exceeds that of a single large storage medium.

In the certain embodiments, array “A” includes hard disk drives181,182,183,191,192,193, and194, and array “B” includes hard disk drives185,186,187,188,196,197, and198.

FIG. 2summarizes the steps of Applicant's method. Referring now toFIG. 2, in step210Applicant's method provides a data structure comprising first information. In certain embodiments, the data structure of step210comprises a control flag to begin or end special processing.

In step215, Applicant's method provides a write thread comprising second information. As those skilled in the art will appreciate, a thread is a path of execution of a process, and the thread context is the task. In certain embodiments, the write thread of step215is provided by a host computer interconnected to Applicant's information storage and retrieval system. In certain embodiments, the write thread of step215is provided by a processor disposed in Applicant's information storage and retrieval system. In certain embodiments, the write thread of step215is provided by a processor disposed in an embedded device, such as for example a host adapter or a device adapter, disposed in Applicant's information storage and retrieval system. In certain embodiments, the write thread of step215comprises part of device microcode disposed in an embedded device disposed in Applicant's information storage and retrieval system, such as for example device microcode102A (FIG. 1) disposed in host adapter102(FIG. 1) or device microcode165A (FIG. 1) disposed in device adapter165(FIG. 1).

In step220, Applicant's method provides (N) non-preemptable threads. By “non-preemptable threads,” Applicant means a thread which will return to the dispatcher in a finite amount of time. As those skilled in the art will appreciate, most operating systems allow a thread to never return to the dispatcher, but those operating systems may periodically preempt such non-reporting threads and switch to other threads. One or more of these (N) non-preemptable threads comprise read threads. In certain embodiments, one or more of the (N) threads of step220comprise part of device microcode disposed in an embedded device disposed in Applicant's information storage and retrieval system, such as for example device microcode102A (FIG. 1) disposed in host adapter102(FIG. 1) or device microcode165A (FIG. 1) disposed in device adapter165(FIG. 1).

In step225, Applicant's method provides a thread dispatcher. In certain embodiments, this thread dispatcher comprises part of device microcode disposed in an embedded device disposed in Applicant's information storage and retrieval system.

In step230, Applicant's method posts the write thread of step215. In certain embodiments, step230is performed by device microcode disposed in an embedded device disposed in Applicant's information storage and retrieval system.

In step235, Applicant's method marks the data structure of step210as unusable. In certain embodiments, step235includes providing a data structure indicator. In certain embodiments, that data structure indicator comprises a pointer. In certain embodiments, Applicant's device microcode includes such a pointer pointing to the data structure of step210. In these embodiments, step235includes setting that pointer to indicate that the data structure is unusable. In certain embodiments, step235is performed by device microcode disposed in an embedded device disposed in Applicant's information storage and retrieval system. In certain embodiments, step235is performed by a processor disposed in an embedded device disposed in Applicant's information storage and retrieval system. In certain embodiments, step235is performed by the write thread of step215.

In step240, Applicant's method, in response to the posting of the write thread in step230, creates (N) indicators, where each of those (N) indicators is assigned to a different one of the (N) threads, and where each of those indicators can be set to one of two values, and where each of those indicators is initially set to the first value. If the (i)th indicator is set to the first value, then the (i)th thread has not examined the data structure indicator set in step235. Alternatively, if the (i)th indicator is set to the second value, then subsequent dispatches of the (i)th read thread will see the data structure indicator which indicates that the data structure is unusable.

In certain embodiments, the (N) indicators of step240comprise a bitmask which includes (N) bits. Each of those bits can be set to either a first value or a second value. In certain embodiments, the first value comprises a “0”, and the second value comprises a “1.”

In certain embodiments, step240is performed by a processor disposed in Applicant's information storage and retrieval system. In certain embodiments, step240is performed by a processor disposed in an embedded device disposed in Applicant's information storage and retrieval system. In certain embodiments, step240is performed by a processor using device microcode disposed in an embedded device disposed in Applicant's information storage and retrieval system. In certain embodiments, step240is performed by the write thread of step215. In certain embodiments, step240is performed by the thread dispatcher of step225.

Each time the thread dispatcher dispatches one of the (N) threads, that dispatched thread returns to the thread dispatcher after completing its task. In addition, each of the (N) threads returns to the thread dispatcher after a specified time interval. Upon returning to the thread dispatcher, the (i)th thread sees the data structure indicator set in step235. In step245, after the (i)th thread returns to the thread dispatcher and sees the data structure indicator which indicates that the data structure is unusable, Applicant's method sets the (i) thread indicator to the second value, i.e. to indicate that upon subsequent dispatches the (i)th thread will see the data structure marked as unusable. In certain embodiments, step245is performed by the thread dispatcher.

In step250, the method determines if each of the (N) threads has seen the data structure indicator showing that the data structure is unusable, i.e. if the thread indicator for each of the (N) threads is set to the second value. In certain embodiments, step250is performed by a processor disposed in Applicant's information storage and retrieval system. In certain embodiments, step250is performed by a processor disposed in an embedded device disposed in Applicant's information storage and retrieval system. In certain embodiments, steps250is performed by the write thread of step215. In certain embodiments, step250is performed by the thread dispatcher of step225.

If Applicant's method determines in step250that each of the (N) threads has not seen the indication that the data structure is unusable, then the method transitions from step255to step245and continues. Alternatively, if Applicant's method determines in step250that each of the (N) threads indicators is set to the second value, i.e. upon a subsequent dispatch each of the (N) threads has seen the indication that the data structure is unusable, then the method transitions from step250to step260wherein the method sets the data structure indicator of step235to indicate that the data structure is invalid. In certain embodiments, step260includes setting a pointer pointing to that data structure to indicate that the data structure is invalid.

In certain embodiments, step260is performed by a processor disposed in Applicant's information storage and retrieval system. In certain embodiments, step260is performed by a processor disposed in an embedded device disposed in Applicant's information storage and retrieval system. In certain embodiments, step260is performed by the write thread of step215. In certain embodiments, step260is performed by the thread dispatcher of step230.

Applicant's method transitions from step260to step270wherein the method dispatches the write thread posted in step230. In certain embodiments, step270is performed by a processor disposed in Applicant's information storage and retrieval system. In certain embodiments, step270is performed by a processor disposed in an embedded device disposed in Applicant's information storage and retrieval system. In certain embodiments, steps270is performed by the write thread of step215. In certain embodiments, step270is performed by the thread dispatcher of step225.

Applicant's method transitions from step270to step280wherein the write thread updates the data structure to comprise second information. Applicant's method transitions from step280to step290wherein the method sets the data structure indicator to indicate that the data structure is valid. In certain embodiments, step290includes setting a pointer pointing to that data structure to indicate that the data structure is valid. In certain embodiments, step290is performed by a processor disposed in Applicant's information storage and retrieval system. In certain embodiments, step290is performed by a processor disposed in an embedded device disposed in Applicant's information storage and retrieval system. In certain embodiments, step290is performed by the write thread of step215. In certain embodiments, step290is performed by the thread dispatcher of step225.

In certain embodiments, Applicants' invention includes instructions residing in memory133(FIG. 1), where those instructions are executed by processor132(FIG. 1) to performs steps230,235,240,245,250,260,270,280, and290, recited inFIG. 2. In other embodiments, Applicants' invention includes instructions residing in any other computer program product, where those instructions are executed by a computer external to, or internal to, system100, to perform steps230,235,240,245,250,260,270,280, and290, recited inFIG. 2. In either case, the instructions may be encoded in an information storage medium comprising, for example, a magnetic information storage medium, an optical information storage medium, an electronic information storage medium, and the like. By “electronic storage media,” Applicants mean, for example, a device such as a PROM, EPROM, EEPROM, Flash PROM, compactflash, smartmedia, and the like.