Method for efficient non-virtual main memory management

• US 5,159,678 A
• Filed: 08/23/1990
• Issued: 10/27/1992
• Est. Priority Date: 06/11/1990
• Status: Expired due to Term

• Current Assignee: Silicon Graphics International Corporation (Hewlett-Packard Enterprise Company)
• Original Assignee: Supercomputer Systems Limited Partnership
• Inventors: Wengelski, Diane M., Gaertner, Gregory G.
• Primary Examiner(s): Bowler, Alyssa H.
• Application Number:
  US07/572,045
• Time in Patent Office: 796 Days
• US Class Current: 711/153
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• CPC Class Codes: G06F 12/1036 for multiple virtual address spaces, e.g. segmentation G06F12/1045 takes precedence
• CPC Class Codes: G06F 12/109 for multiple virtual address spaces, e.g. segmentation G06F12/1036 takes precedence
• CPC Class Codes: G06F 12/12 Replacement control
• CPC Class Codes: G06F 8/41 Compilation
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis
• CPC Class Codes: G06F 8/445 Exploiting fine grain parallelism, i.e. parallelism at instruction level run-time instruction scheduling G06F9/3836
• CPC Class Codes: G06F 8/45 Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5016 the resource being the memory

Abstract

The present invention provides a parallel memory scheduler for execution on a high speed highly parallel multiprocessor architecture. The operating system software provides intelligence and efficiency in swapping out process images to facilitate swapping in another process. The splitting and coalescing of data segments are used to fit segments in to current free memory even though a single contiguous space of sufficient size does not exist. Mapping these splits through data control register sets retains the user'"'"'s contiguous view of the address space. The existence of dual images and partial swapping allows efficient, high speed swapping. Candidates for swap out are chosen in an intelligent fashion, selecting only those candidates which will most efficiently aLlow the swapin of another process.

Claims

1. An improved method for operating a non-virtual main memory manager using swapin and swapout operations to allocate and un-allocate space in a non-virtual main memory for one or more segments of one or more process images residing on a swap device and ready to be executed in a computer processing system that includes one or more processors sharing the main memory and the swap device wherein the segments require space of varying sizes and all of the segments for a process image must be resident in the main memory before the process image can be executed by the computer processing system:

and wherein the main memory manager performs a swapin operation for the segments of a selected process image ready to execute when space in the main memory is available and performs a swapout operation for the segments of one or more process images that are currently stored in the main memory, the steps of the improved method comprising;

constructing at least a segment location list identifying all physical segment spaces in the main memory, a segment active list identifying space in the main memory currently allocated to one or more segments, and a segment available list identifying space in the main memory currently un-allocated to any segments,

checking the segment available list for sufficient contiguous space in the main memory which has not been allocated to any segment and which is large enough to contain one or more segments of a process image which are ready to be swapped into the main memory,

performing a swapin allocation operation to allocate the contiguous space in the main memory to the one or more segments in the event that sufficient un-allocated contiguous space in the main memory is available to store one or more of the segments of the process image ready to be swapped into the main memory,

updating at least the segment available list and the segment active list after performing the swapin allocation operation,

checking the segment active list for a segment candidate to swap out from the main memory in the event that insufficient un-allocated contiguous space in the main memory is available to store any one or more segments of the process image ready to be swapped into the main memory,

performing a swapout operation on the segment candidate to un-allocate the space in the main memory which was allocated to the segment candidate, and

updating at least the segment available list and the segment active list after performing the swapout operation on the segment candidate.

2. The improved method of claim 1 wherein the segment location list is ordered by physical location of all segments in the main memory both allocated and un-allocated.

3. The improved method of claim 1 wherein the segment active list is ordered by the size of the contiguous space in the main memory required for each segment.

4. The improved method of claim 1 wherein the segment available list is ordered by the size of the contiguous space in main memory which is not allocated to any segment.

5. The improved method of claim 1 wherein the segment location list, the segment available list, and the segment active list are circular doubly linked lists.

6. The improved method of claim 1 further comprising the steps of:

repeating in sequence any of the steps of checking the segment available list, performing a swapin allocation operation, updating at least the segment available list and the segment active list after performing the swapin operation, checking the segment active list, performing a swapout operation on the segment candidate and updating at least the segment available list and the segment active list until each segment of the process image ready to be swapped into the main memory has been allocated space in the main memory,

transfering all of the segments from the swap device to the main memory, and

updating the segment location list, the segment available list and the segment active list to reflect the current location of segments in the main memory and the current locations of segments in the main memory which have been allocated and which have not been allocated.

7. An improved dual image allocation method for operating non-virtual main memory manager using swapin and swapout operations to allocate and un-allocate space in a non-virtual main memory for one or more segments of one or more process images residing on a swap device and ready to be executed in a computer processing system that includes one or more processors sharing the main memory and the swap device wherein the segments require space of varying sizes and all of the segments for a process image must be resident in the main memory before the process image can be executed by the computer processing system, the steps of the improved method comprising:

performing a swapin allocation operation to allocate contiguous space in the main memory to at least one segment of one process image residing on the swap device,

the swapin allocation operation including the step of checking to determine if the one segment already has been allocated space in the main memory,

if so, performing another swapin allocation operation to allocate contiguous space in the main memory to another segment of the one process image,

if not, checking for an un-allocated contiguous space in the main memory large enough to store the entire one segment, and allocating that space to the one segment and copying the segment to the main memory,

in the event that space is allocated to the one segment, retaining an image of the segment on the swap device so as to create a dual image allocation whereby it is only necessary to un-allocate the space allocated to the one segment, without copying the segment to the swap device in the event the segment is to be removed from main memory by a swapout operation.

8. The improved method of claim 7 further comprising the step of:

retaining allocated space in the main memory for some segments of a process image until all segments of that process image have been allocated space in the main memory.

9. The improved method of claim 8 further comprising the step of:

freeing a process image from the swap device in the event that all segments of that process image have been allocated space in the main memory.

10. An improved partial image swapout method for operating a non-virtual main memory manager using swapin and swapout operations to allocate and un-allocate space in non-virtual main memory for one or more segments of one or more process images residing on a swap device and ready to be executed in a computer processing system that includes one or more processors sharing the main memory and the swap device wherein the segments require space of varying sizes and all of the segments for a process image must be resident in the main memory before the process image can be executed by the computer processing system, the steps of the improved method comprising:

as one step in the swapout operation, performing a partial swapout operation by swapping out of the main memory less than all of the segments of one process image contained in the main memory in order to free allocated space in the main memory to enable the swapin operation to allocate the now un-allocated space in the main memory to one or more segments of another process image.

11. The improved method of claim 10 wherein the step of performing the partial swapout operation enables one or more of the segments that were swapped out to obtain additional space in the main memory in the event that the segment is swapped in again with out swapping out all of the segments of the process image at the time that the one or more segments are swapped out.

12. An improved split image swapin method for operating a non-virtual main memory manager using swapin and swapout operations to allocate and un-allocate space in non-virtual main memory for one or more segments of one or more process images residing on a swap device and ready to be executed in a computer processing system that includes one or more processors sharing the main memory and the swap device wherein the segments require space of varying sizes and all of the segments for a process image must be resident in the main memory before the process image can be executed by the computer processing system, the steps of the improved method comprising:

determining whether there is un-allocated space in the main memory of sufficient size to contain a segment to be swapped into the main memory,

if there is un-allocated space in the main memory of sufficient size to contain the segment to be swapped into the main memory, then allocating that space to the segment,

if there is not sufficient un-allocated space in the main memory to contain the segment to be swapped into the main memory, then determining whether the segment may be divided into split segments according to a pre-determined criteria and

if the segment may be divided into split segments, then splitting the segment into at least two split segments, at least one of the split segments being allocated a memory size corresponding to an un-allocated contiguous space in the main memory.

13. The improved method of claim 12 further comprising the step of:

recording for the segment which has been split into split segments a lower bound, an upper bound and a displacement to enable mapping of a logical storage address to its physical location in the main memory.

14. The improved method of claim 13 wherein the lower bound, the upper bound and the displacement are recorded in a set of registers in the multiprocessor system.

15. The improved method of claim 14 wherein the multiprocessor system has a predetermined number of sets of registers to enable a predetermined number of segments to be split into split segments and thereby provide mapping of a logical storage address to its physical location in the main memory for each split segment.

16. The improved method of claim 15 wherein in the event that a split segment is swapped out of the main memory, the set of registers containing the lower bound, the upper bound, and the displacement is cleared and thereby becomes available for recording the lower bound, the upper bound and the displacement of another segment which is split into split segments.

17. The improved method of claim 16 further comprising the step of:

coalescing the split segments of the one segment into contiguous space on the swap device.

18. An improved swapout selection method for operating a non-virtual main memory manager using swapin and swapout operations to allocate and un-allocate space in a non-virtual main memory for one or more segments of one or more process images residing on a swap device and ready to be executed in a computer processing system that includes one or more processors sharing the main memory and the swap device wherein the segments require space of varying sizes and all of the segments for a process image must be resident in the main memory before the process image can be executed by the computer processing system, the steps of the improved method comprising:

creating un-allocated space in the main memory by performing a swapout operation on a segment chosen by analyzing the segments stored in the main memory which are adjacent to any contiguous space in the main memory that can be allocated to a segment to be swapped into the main memory,

such that a segment will not be swapped out of the main memory unless doing so creates sufficient contiguous space in the main memory to allocate for the memory size of the segment to be swapped into the main memory, thereby increasing the efficiency of the main memory manager.

19. The improved method of claim 18 wherein the segment selected as the focus of the swapout operation to increase the efficiency of the main memory manager is a segment having both allocated space in the main memory and an image of the process associated with the segment on the swap device.

20. The improved method of claim 18 wherein the segment selected as the focus of the swapout operation to increase the efficiency of the main memory manager is a segment associated with a process image which currently cannot be executed and which has allocated space in the main memory that is adjacent to un-allocated space in the main memory of sufficient size that when the adjacent un-allocated space in the main memory is combined with the memory size of the space allocated to the segment to be swapped out the resulting memory size is large enough to contain another segment to be swapped into the combined space in the main memory.

21. The improved method of claim 18 wherein the segment selected as the focus of the swapout operation to increase the efficiency of the main memory manager is a segment associated with a process image which currently cannot be executed and is adjacent to a second segment associated with another process image which currently cannot be executed such that when the space in the main memory for the one segment is combined with the space in main memory for the second segment, the resulting memory size is large enough to contain a current segment to be swapped into the combined space in main memory.

22. The improved method of claim 18 wherein the segment selected as the focus of the swapout operation to increase the efficiency of the main memory manager is a segment associated with either a process image which is currently executable or a process image which is not currently executable and is adjacent to un-allocated space in the main memory of sufficient size that when the memory size of the space allocated to the segment which is the focus of the swapout operation and the adjacent un-allocated space in the main memory are combined, the resulting memory size is large enough to contain another segment to be swapped into the combined space in the main memory.

23. The improved method of claim 18 wherein the segment selected as the focus of the swapout operation to increase the efficiency of the main memory manager is a segment associated with a process image which currently cannot be executed and is adjacent to a second segment associated with a process image which currently can be executed such that when the space in the main memory for the one segment is combined with the space in main memory for the second segment, the resulting memory size is large enough to contain a current segment to be swapped into the combined space in main memory.

24. An improved method for operating a non-virtual main memory manager using swapin and swapout operations to allocate and un-allocate space in non-virtual main memory for one or more segments of one or more process images residing on a swap device in a computer processing system that includes one or more processors sharing the main memory and the swap device wherein the segments require space of varying sizes and all of the segments for a process image must be resident in the main memory before the process image can be executed by the computer processing system, and wherein the main memory manager performs a swapin operation for the segments of a selected swapin process image ready to execute and performs a swapout operation for the segments of one or more process images currently stored in the main memory, the steps of the improved method comprising:

determining for each segment of the selected swapin process image if space in main memory has or has not been allocated for that segment,

in the event that space in the main memory has not been allocated for a segment, then determining if sufficient contiguous space in the main memory can or cannot be allocated for that segment,

in the event that sufficient contiguous space in the main memory cannot be allocated for that segment, then attempting to allocate space in the main memory for that segment by allowing segments shared by more than one process image to be forced out of the main memory.

25. The improved method of claim 24 wherein the step of attempting to allocate space in the main memory comprises:

performing a search of space in main memory to determine if sufficient contiguous un-allocated space in the main memory exists which is of sufficient size to contain that segment.

26. The improved method of claim 24 wherein the step of allocating space in the main memory comprises:

splitting that segment into split segments, each split segment of a memory size which fits within the currently un-allocated spaces in the main memory.

27. The improved method of claim 24 wherein the step of allocating space in the main memory comprises:

performing a swapout operation on segments in the main memory which are associated with other process images which do not have all segments associated with the process image contained in the main memory.

28. The improved method of claim 24 wherein the step of allocating space in the main memory comprises:

performing a swapout operation on segments in the main memory associated with a process image which is not currently executable and which are adjacent to un-allocated space in the main memory such that the memory size of the segments combined with the memory size of the adjacent un-allocated space in the main memory is sufficient contiguous space in the main memory to contain that segment which is to be swapped into main memory.

29. The improved method of claim 24, wherein the step of allocating space in the main memory comprises:

performing a swapout operation on segments in the main memory associated with a process image which is not currently executable or associated with a process image which is currently executable and which are adjacent to un-allocated space in the main memory such that the memory size of the segments combined with the memory size of the adjacent un-allocated space in the main memory is sufficient contiguous space in the main memory to contain that segment which is to be swapped into main memory.

30. The improved method of claim 24 wherein the step of allocating space in the main memory comprises:

performing a swapout operation on adjacent segments in the main memory associated with other process image which is not currently executable and associated with process image which is currently executable and, such adjacent segments are adjacent to un-allocated space in the main memory such that the memory size of each segment combined with the memory size of the adjacent un-allocated space in the main memory is sufficient contiguous space in the main memory to contain that segment which is to be swapped into main memory.

31. The improved method of claim 24 wherein the step of allocating space in the main memory comprises:

first searching space in the main memory to determine if any un-allocated space in the main memory exists which is large enough to contain that segment, and in the event that sufficient space in the main memory to contain that segment is not un-allocated, then,

secondly attempting to split that segment into split segments which fit within currently un-allocated spaces in the main memory and if the split segments of that segment do not fit within currently un-allocated spaces in the main memory, then

thirdly performing a swapout operation on segments of other process images which have some segments already swapped out and if that segment did not fit within then un-allocated spaces in the main memory, then

fourthly performing a swapout operation on segments of a process image which is not currently executable which combined with adjacent un-allocated space in the main memory creates contiguous memory of a size to contain that segment and if that segment did not fit within then un-allocated spaces in the main memory, then

fifthly performing a swapout operation on segments of a process image which are not currently executable or a process image which is currently executable, these segments combined with un-allocated space in the main memory adjacent to those segments creates contiguous memory of a size to contain that segment which is to be swapped into main memory.

32. An improved swapout coalescing method for operating a non-virtual main memory manager using swapin and swapout operations to allocate and un-allocate space in non-virtual main memory for one or more segments of one or more process images residing on a swap device and ready to be executed in a computer processing system that includes one or more processors sharing the main memory and the swap device and wherein the segments require space of varying sizes and all of the segments for a process image must be resident in the main memory before the process image can be executed by the computer processing system, and wherein the main memory manager performs a swapin operation for the segments of a selected process image ready to execute and performs a swapout operation for the segments of one or more process images currently stored in the main memory, the steps of the improved method comprising:

allocating a space on the swap device of a size which is large enough to contain a segment of a selected swapout segment of a process image,

determining if the selected swapout segment has been divided into two or more split segments,

in the event that the selected swapout segment has split segments, coalescing the split segments into the space allocated on the swap device, and

in the event that the segment has no split segments, moving the segment into the allocated space on the swap device.

33. An improved dual allocation swapout method for operating a non-virtual main memory manager using swapin and swapout operations to allocate and un-allocate space in non-virtual main memory for one or more segments of one or more process images residing on a swap device and ready to be executed in a computer processing system that includes one or more processors sharing the main memory and the swap device and wherein the segments require space of varying sizes and all of the segments for a process image must be resident in the main memory before the process image can be executed by the computer processing system, and wherein the main memory manager performs a swapin operation for the segments of a selected process image ready to execute and performs a swapout operation for the segments of one or more process images currently stored in the main memory, the steps of the improved method comprising:

determining if a segment to be swapped out of the main memory has a dual allocation in the main memory and on the swap device,

in the event that the segment has a dual allocation in the main memory and on the swap device, un-allocating space in the main memory allocated for that dual allocation of the segment without copying the segment to the swap device as part of a swapout operation.

34. The improved method of claim 33 further comprising the steps of:

determining that the segment to be swapped out does not have a dual allocation in the main memory and on the swap device,

allocating a space on the swap device of a sufficient size to contain the segment,

determining that the segment has been divided into split segments,

in the event that the segment has been divided into partial segments, coalescing the split segments into the space allocated on the swap device, and

in the event that the segment has no split segments, moving the segment into the space on the swap device.

35. In a computer processing system, an efficient method for managing memory allocation of a non-virtual main memory to a plurality of processes to be executed by one or more processors in the computer processing system, each process having a process image including one or more segments that are stored in the main memory or in a swap device, each segment having a defined memory size and containing a type of information associated with that process, wherein the memory size of different segments is variable and all of the segments of a process must be resident in the non-virtual main memory in order for that process to be executed by the computer processing system, the method comprising the processor-implemented steps of:

(a) selecting a swapin process to be swapped into the main memory from the swap device;

(b) for each segment of the process image of the swapin process, performing the steps of;

(b1) determining whether the segment has been allocated space in the main memory;

(b2) if the segment has not been allocated space in the main memory, determining whether there are any un-allocated contiguous spaces in the main memory;

(b3) if there are no un-allocated contiguous spaces in the main memory, executing a swapout procedure to create one or more un-allocated contiguous spaces in the main memory; and

(b4) if there is at least one un-allocated contiguous space in the main memory, attempting to allocate contiguous space in the main memory for the segment, including the steps of;

(b41) allocating space to the segment if there is sufficient un-allocated contiguous space in the main memory for the memory size of the segment,

(b42) splitting the segment into two or more split segments if there is not sufficient contiguous space in the main memory to allocate for the memory size of the segment and if the segment contains one of a predetermined set of types of information which can be split, such that at least one of the split segments is of a memory size that sufficient un-allocated contiguous space in the main memory can be allocated to that split segment, and

(b43) executing the swapout procedure if there is not sufficient un-allocated contiguous space in the main memory for the memory size of the segment or one of the split segments and repeating steps (b41)-(b42); and

(c) if all of the segments of the swapin process were allocated space in the main memory, copying all of the segments of the process image from the swap device to the main memory and adding the process to a run queue of processes to be executed by one or more of the processors.

36. The method of claim 35 further comprising in the event that all of the segments for the swapin process were not allocated space in the main memory as a result of step (b), performing the steps of:

(b5) swapping out all of the sements of the swapin process that were allocated space in the main memory to allow any split segments to be coalesced and repeating steps (b2)-(b4);

(b6) in the event that all of the segments for the swapin process were not allocated space in the main memory as a result of step (b5), delaying for a predetermined period of time and repeating step (b5); and

(b7) in the event that all of the segments for the swapin process were not allocated space in the main memory as a result of step (b6), selecting a new swapin process and repeating step (b).

37. The method of claim 35 wherein the swapout operation selects the segments to be swapped out of the main memory by analyzing the segments stored in the main memory which are adjacent to any contiguous spaces in the main memory that can be allocated to the segment of the swapin process, such that a segment will not be swapped out of the main memory unless doing so creates sufficient contiguous un-allocated space in the main memory to allocate for the memory size at least one of the segments or split segments of the swapin process.

38. The method of claim 37 wherein the swapout operation comprises the steps of:

(a) unallocating space for any segments of any process images for which not all of the segments of the process image have been allocated space in the main memory;

(b) determining if swapping out a process that is sleeping and is adjacent to any unallocated space will create sufficient space to allocate to one or more of the segments or split segments of the swapin process and, if so, swapping out that process and exiting the swapout operation;

(c) determining is swapping out adjacent processes that are sleeping and are adjacent to any unallocated space will create sufficient space to allocate to one or more of the segments or split segments of the swapin process and, if so, swapping out those processes and exiting the swapout operation; and

(d) determining if there is a combination of processes that are sleeping and executing and are adjacent to any unallocated space that will create sufficient space to allocate to one or more of the segments or split segments of the swapin process and, if so, swapping out that process and exiting the swapout operation.

39. In a computer processing system, a split segment method for managing memory allocation of a non-virtual main memory to a plurality of processes to be executed by one or more processors in the computer processing system, each process including one or more segments that are stored in the main memory or in a swap device, each segment having a defined memory size and containing a type of information associated with that process, wherein the memory size of different segments is variable and all of the segments of a process must be resident in the non-virtual main memory in order for that process to be executed by the computer processing system, the method comprising the processor-implemented steps of:

during a swapin allocation operation wherein contiguous space in the main memory is allocated to one or more of the segments of a process that are to be swapped into the main memory from the swap device,

attempting to split one or more of the segments of the process into two or more split segments if there is not sufficient contiguous space in the main memory to allocate for the memory size of the segment and if the segment contains one of a predetermined set of types of information which can be split, such that at least one of the split segments will be of a memory size that sufficient contiguous space in the main memory can be allocated to that split segment; and

during a swapout operation wherein one or more of the segments of a process are to be swapped out of the main memory to the swap device,

coalescing any split segments of a segment of the process into the memory size of that segment as the segments are transferred to the swap device,

whereby utilization of the main memory is enhanced by splitting the split segments into memory sizes that correspond to contiguous memory spaces in the main memory that are available each time a swapin allocation operation is performed for a process.

40. In a computer processing system, an adjacent swapout method for managing memory allocation of a non-virtual main memory to a plurality of processes to be executed by one or more processors in the computer processing system, each process including one or more segments that are stored in the main memory, in a swap device, or in both the main memory and the swap device, each segment having a defined memory size and containing a type of information associated with that process, wherein the memory size of different segments is variable and all of the segments of a process must be resident in the non-virtual main memory in order for that process to be executed by the computer processing system, the method comprising the processor-implemented steps of:

during a swapout operation wherein one or more of the segments of one or more of the processes are to be swapped out of the main memory to the swap device, selecting the segments to be swapped out of the main memory by analyzing the segments stored in the main memory which are adjacent to any contiguous space in the main memory that can be allocated to the segment to be swapped into the main memory, such that a segment will not be swapped out of the main memory unless doing so creates sufficient contiguous space in the main memory to allocate for the memory size of the segment to be swapped into the main memory.