Classifications

• • G—PHYSICS
  • G06—COMPUTING OR CALCULATING; COUNTING
  • G06F—ELECTRIC DIGITAL DATA PROCESSING
  • G06F9/00—Arrangements for program control, e.g. control units
  • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
  • G06F9/46—Multiprogramming arrangements
  • G06F9/48—Program initiating; Program switching, e.g. by interrupt
  • G06F9/4806—Task transfer initiation or dispatching
  • G06F9/4843—Task transfer initiation or dispatching by program, e.g. task dispatcher, supervisor, operating system
  • G06F9/485—Task life-cycle, e.g. stopping, restarting, resuming execution
  • G06F9/4856—Task life-cycle, e.g. stopping, restarting, resuming execution resumption being on a different machine, e.g. task migration, virtual machine migration

Definitions

• the present invention relates to computing systems. More particularly, this invention relates to process checkpointing and migration in computing systems, such as communications systems.
• a process is a piece of a program in execution. It represents a job assigned to a computer (also called a computing device or machine) during the execution of a program.
• a program may comprise one or more processes running on single or multiple computers.
• the software and hardware on a computer create a distinct computing platform.
• an executable file is provided via a compiler for that particular computer.
• the executable file contains a sequence of machine instructions in form of platform-specific binary code.
• One or more processes are created on a computer before an executable file can be executed on a computer, so that the operating system of the computer can load those instructions into the computer's main memory and assign the instructions to the central processing unit (CPU).
• CPU central processing unit
• a programmer can write a program (or source code) in the form of a high-level computer language such as C, C++, or FORTRAN, and pass it to a compiler for that language.
• a program comprises a global data definition area and a description of functions. Each function description comprises of parameter variable declarations, local variable declarations, and programming language statements.
• the compiler translates the program source code into the platform-specific binary code, and stores them in an executable file. During compilation, the compiler can also optimize the machine instructions according to specific features of the computing platform.
• the operating system loads the executable file into the computer's memory. The loaded executable file is then ready to be executed by the CPU and is recognized as one or more processes or tasks.
• Process migration where the execution of a process is suspended on one computer and then resumed on another computer (or, for example, on different CPUs associated with the same computer), is a mechanism to adapt process and resource assignment.
• the process being migrated can be transferred, for example, via direct network- to-network communication (network migration), or file migration.
• Applications of process migration include load distribution, which involves migrating processes from overloaded computers to underloaded computers to make use of otherwise unused computing cycles; fault resilience, which involves migrating processes from computers that may be experiencing partial or total failure; resource sharing, which involves migrating processes to computers with special hardware or other unique resources such as databases or peripherals required for computations; and data access locality, which involves migrating processes towards the source of the data.
• load distribution which involves migrating processes from overloaded computers to underloaded computers to make use of otherwise unused computing cycles
• fault resilience which involves migrating processes from computers that may be experiencing partial or total failure
• resource sharing which involves migrating processes to computers with special hardware or other unique resources such as databases or peripherals
• the mobile agent approach to process migration is an alternative to "true" process migration.
• Mobile agents are implemented on top of safe or interpreted languages, such as Java, which are more secure and promising for certain applications.
• the interpreter acts as a virtual machine to create an artificial homogeneous environment.
• these languages are less powerful, slow, and require rewrites of existing software.
• Checkpointing for process migration has been developed primarily for fault tolerance, and involves transferring and restarting one or more checkpointed processes on properly functioning machines.
• Checkpointing requires access to file systems and roll backs to a consistent global state in parallel processes.
• checkpointing a process requires the additional step of saving the data contents of a process to a file periodically. Later, when recovery is needed, data from the checkpointed file is read and restored in a new process to resume execution of the application.
• implementations of the invention may provide one or more of the following advantages. For example, duties of a process can be efficiently transferred from one computing device (e.g., an accelerator card) to another computing device (e.g., another accelerator card). Additionally, for example, a supervisor task can monitor the status of migration of a process.
• one computing device e.g., an accelerator card
• another computing device e.g., another accelerator card
• a supervisor task can monitor the status of migration of a process.
• the invention provides a method for use in process checkpointing and migration in a computing system, where the method includes invoking a first standard operating system call to checkpoint a first process running on a first computing device to produce checkpointing results, transmitting at least a portion of the checkpointing results to a second computing device, and invoking a second standard operating system call to use the transmitted checkpointing results to de-checkpoint a second process running on the second computing device.
• the invention provides a system for checkpointing and migrating processes between a first computing device and a second computing device in a computing system, where the system includes means for invoking a first standard operating system call to checkpoint a first process running on the first computing device to produce checkpointing results, means for transmitting at least a portion of the checkpointing results to the second computing device, and means for invoking a second standard operating system call to use the transmitted checkpointing results to de- checkpoint a second process running on the second computing device
• the invention provides a system for checkpointing and migrating processes between a first computing device and a second computing device in a computing system, where the system includes a first computing device on which a first process is running, and a second computing device on which a second process is running, wherein at least a portion of the checkpointing results produced by invoking a first standard operating system call to checkpoint the first process are transmitted to the second computing device, and wherein a second standard operating system call uses the checkpointing results received by the second computing device to de-checkpoint the second process.
• FIG. 1 is a simplified illustration of a chassis in a computing system that includes multiple PACs among which migration of processes according to the principles of the present invention may be accomplished;
• FIG. 2 is a simplified illustration of an active packet accelerator card (PAC) that includes four CPUs from which migration of processes according to the principles of the present invention may be accomplished;
• PAC active packet accelerator card
• FIG. 3 is a simplified illustration of a standby PAC that includes four CPUs to which migration of processes according to the principles of the present invention may be accomplished;
• FIG. 4 is a simplified illustration showing two PACs that may be involved in the checkpointing and migration of one or more processes in accordance with the principles of the present invention.
• FIG. 5 is a flow chart illustrating the steps performed according to one embodiment of the present invention in the checkpointing and migration of processes from a first computing device to a second computing device in a computing system.
• a process or task is migrated from a first computing device to a second computing device by creating a matching process that runs on the second computing device, invoking a standard operating system call on the first computing device to save data reflecting the state of the process, transmitting at least some of the saved data to the second computing device, and invoking another standard operating system call on the second computing device to use the transmitted data to cause the matching process to assume the state of the process and execute accordingly.
• memory and register contents of a process on one communications computing device may be restored as the memory and register contents of a matching process on another communications computing device.
• computing systems generally use multiple computing devices, such as electronic circuitry cards, for handling various processes.
• electronic circuitry cards such as packet accelerator cards (PACs) are used.
• PACs packet accelerator cards
• FIG. 1 shows a chassis 100 in a computing system that includes multiple
• PACs 101-114 among which migration of processes according to the invention may be accomplished.
• PAC 102 serves as a redundant or backup PAC for operational PAC 101
• PAC 104 serves as a backup PAC for operational PAC 103
• PAC 114 which serves as a backup PAC for operational PAC 113.
• Chassis 100 shown in FIG. 1 shows a 1 : 1 redundancy of backup PACs to operational PACs, the invention is not limited in this manner. Rather, it will be understood that a 1 :N redundancy is used according to various embodiments of the invention, as explained below. Chassis 100 shown in FIG.
• chassis 100 also includes a management card, such as a Switch Processor Card (SPEC) 115 as developed by Starent Networks Corporation of Tewksbury, MA, for controlling some or all of the chassis operations (e.g., starting chassis 100, managing PACs 101-114, handling recovery tasks, etc.).
• SPEC Switch Processor Card
• chassis 100 also includes a redundant SPEC (or RPC) 116.
• PACs such as those shown in FIG. 1 can be classified as either active PACs or standby PACs.
• a standby PAC serves as a redundant or backup PAC that can take over and assume many or all processes or tasks that are running when an active PAC fails.
• the act of transferring processes from an active to a standby PAC is known as PAC migration, and can occur for any of a number of reasons as described below.
• an active PAC 200 includes four CPUs 202, 204, 206, and 208.
• a standby PAC 300 includes four CPUs 302, 304, 306, and 308. The invention is not, however, limited by the number of CPUs present in active PAC 200 or standby PAC 300.
• Each CPU 202, 204, 206 and 208 of PAC 200 and each CPU 302, 304, 306, and 308 of PAC 300 executes a set of one or more processes or tasks specific to the host PAC.
• each of these CPUs executes a special task, referred to as sitCPU or a monitoring task, which keeps track of (e.g., monitors) all the other processes running on the respective CPU.
• the sitCPU of CPUs 202, 204, 206 and 208 (of active PAC 200) may maintain a current list of all the other processes running on the respective CPUs, their process ID numbers and process types (e.g., critical, restartable, or migratable), etc.
• graceful and ungraceful two types of PAC migrations can occur: graceful and ungraceful.
• processes are transferred between a first PAC and a second PAC while the first PAC is still fully functional.
• a graceful migration may take place, for example, for maintenance purposes.
• graceful migrations have required that the second PAC (to which processes are transferred) mirror the first PAC's state from initialization and up to the point of the migration.
• this requirement is often burdensome and subject to errors, due, e.g., to timing inaccuracies.
• the first and second PACs are not said to be running in "active" and "standby" mode.
• FIG. 4 is a simplified illustration showing PACs 410 and 420 that may be involved in the checkpointing and migration of one or more processes in accordance with the principles of the present invention, e.g., from a CPU 412 of PAC 410 to a CPU 422 of PAC 420, as will now be explained in greater detail with reference to the flow chart shown in FIG. 5.
• FIG. 5 is a flow chart outlining several steps involved in the checkpointing and migration of processes according to various embodiments of the invention.
• migration of a process 430 of PAC 410 is initiated (e.g., because PAC 410 is to become disabled), and a Recovery Control Task (RCT) 440 (such as developed by Starent Networks Corporation of Tewksbury, MA) or a similar task is used to determine which card to migrate from (in this example, PAC 410) and which card to migrate to (in this example, PAC 420).
• RCT 440 helps to coordinate process checkpointing and migration of an individual process or task, and may be running on a SPEC (or RPC) associated with the chassis (e.g., chassis 100) that includes PACs 410 and 420.
• SPEC or RPC
• the migration of process 430 may be initiated from any one (or more than one) of several system inputs.
• the administrator of the computing system in which PACs 410 and 420 operate may want to service PAC 410 while ensuring that any processes currently running on it are not lost.
• CLI system Command Line Interface
• the administrator can indicate that one or more processes are to be migrated from PAC 410 to PAC 420.
• the administrator can also initiate a migration, for example, by manually removing PAC 410 from the chassis in which it resides (e.g., chassis 100 shown in FIG. 1).
• a trigger lock In order to remove PAC 410, the administrator generally manipulates a physical device called a trigger lock, which sends a signal indicating that a migration is necessary for PAC 410.
• the migration of process 430 may also be initiated, for example, if a diagnostic system senses that PAC 410 is experiencing one or more failures and needs to be shut down. It will be understood by persons versed in the art that migration of a process may be initiated by other means as well, and that the invention is not limited to the particular examples provided above.
• RCT 440 passes information regarding the process 430 to be migrated, and the PAC 420 to which migration is to take place, to sitCPU 450 of CPU 412 (the CPU on which process 430 is running).
• sitCPU 450 notifies and sends migration information to sitCPU 455 of CPU 422 (the CPU to which process 430 is being migrated) regarding the migration to take place, and sitCPU 455 creates a new process 460 corresponding to original process 430.
• new process 460 may run another PAC (in this case, PAC 420).
• new process 460 has been started and is ready to receive, e.g., a TCP connection, at step 508, sitCPU 450 of CPU 412 sends a message to process 430 instructing (or requesting) process 430 to being a migration.
• original process 430 executes pre-migration including, e.g., invoking a checkpointing operating system (OS) kernel call 470 (e.g., using a standard software LINUX tool).
• OS checkpointing operating system
• the checkpointing OS kernel call records (saves) state information 480.
• the state information being recorded at step 512 may include, for example, the state of CPU registers being used by process 430.
• the state information may include some (or all) of the memory or stack controlled by original process 430, shared memory, and/or dynamic load libraries. It will be understood by persons versed in the art that the foregoing list is not necessary exhaustive, but rather is illustrative of the items that may be included in the state information being recorded at step 512.
• original process 430 transmits the saved state information 480 to new process 460 (e.g., using RCT 440 or another task).
• the state information 480 may be transmitted, e.g., over a Transmission Control Protocol (TCP) connection or over a StarChannel link.
• TCP Transmission Control Protocol
• StarChannel link The invention is not limited in this manner.
• new process 460 Upon receiving the state information transmitted by process 430, at step 516, new process 460 invokes a de-checkpointing OS kernel call 490 using the received state information 480. For example, during this de-checkpointing operation, the OS restores the full state of original process 430 to new process 460 (including, e.g., the respective memory and the internal CPU registers).
• new process 450 sends a message to sitCPU 450 indicating that migration is completed and executes post-migration including, e.g., process-specific post- migration.
• the process-specific post-migration being executed by new process 460 may include closing, e.g., the TCP connection over which the state information 470 was transmitted, and fixing file descriptors and signal information, e.g., to refer to new process 460 rather than original process 430.
• the interface to the socket may be modified so that new process 460 is in communication with the socket.
• the TCP socket being used may be released in pre-migration and a new TCP socket may be started in post-migration for use with the new (migrated) Telnet process.
• new process 450 Once new process 450 has executed post-migration, it begins to execute normally on PAC 420.
• original process 430 informs RCT 440 that migration is complete, and optionally terminates.
• original process 430 may be kept running, e.g., for load balancing or load sharing purposes.
• original process 430 has registered with a migration library to publish the process' mechanism for receiving a migration notification.
• steps described above in connection with the flow chart of FIG. 5 may be executed in other sequences.
• processes associated with a single CPU of PAC 410 are migrated to multiple CPUs associated with PAC 420 (with, or without redundancy).
• processes from multiple CPUs of PAC 410 are migrated to a single CPU of PAC 420.
• one or more processes can be migrated from one or more CPUs of PAC 410 to one or more other CPUs of PAC 410 (i.e., processes may be migrated between or among different CPUs in the same PAC in accordance with various embodiments of the invention).
• migration of a process in accordance with the principles of the present invention does not necessarily involve migration of the entire process.
• migration may occur from a active PAC to a standby PAC, the invention is not limited in this manner. For example, migration may be performed from one active PAC to another active PAC.

Landscapes

• Engineering & Computer Science (AREA)
• Software Systems (AREA)
• Theoretical Computer Science (AREA)
• Physics & Mathematics (AREA)
• General Engineering & Computer Science (AREA)
• General Physics & Mathematics (AREA)
• Retry When Errors Occur (AREA)
• Hardware Redundancy (AREA)

Applications Claiming Priority (3)

Publications (2)

Family

ID=36036671

Family Applications (2)

Family Applications After (1)

Country Status (2)

Families Citing this family (5)

Family Cites Families (9)

• 2005
  • 2005-04-18 EP EP05737750A patent/EP1815332A4/de not_active Withdrawn
  • 2005-04-18 EP EP05738099A patent/EP1815333A4/de not_active Ceased
  • 2005-04-18 WO PCT/US2005/013126 patent/WO2006028521A1/en not_active Ceased
  • 2005-04-18 WO PCT/US2005/013122 patent/WO2006028520A1/en not_active Ceased

Also Published As

Similar Documents

Legal Events