Co-scheduling of Processes- Super Scheduling Approach



Memory Management in a Multi-Processor System – A Program Centered Approach.

Vishal Kathuria

University of Wisconsin, Madison

Abstract

This paper addresses the problem of memory management in multi-processor systems and proposes an approach that looks at a program as an entity for resource allocation. Instead of treating a program as merely a group of processes, it is viewed as an entity having a working set, virtual time, processor demand and memory demand. This view allows the memory management techniques developed for independent processes to be extended for use with multi-process parallel programs. The approach presented in this paper does not require any additional hardware and there is no substantial increase in the data maintained for the memory management.

1. Introduction

Resource allocation in multi-processor systems raises several interesting issues, especially when one tries to use the techniques that have been successfully used for uni-processor systems. The working set concept [1] of memory management relies on the virtual time of a process. In a multi-process program, processes share pages for communicating and there is no single owner process of a shared page. Section 2.1 discusses why the solution for this problem proposed in [1] is not sufficient. The notions of virtual time of a process and ownership of shared pages by the program are introduced in section 2.2. Section 2.3 contains the implementation details of WSClock-sharing, the modified WSClock.

Another issue in memory management is deciding which processes are chosen to be active and which are swapped out to disk. The Balancing Solution [1] treats each process independently according to its processor and memory demand. This approach is inadequate for a machine running multi-process programs because it is undesirable to have some of the processes of a program active and other inactive. Section 3.1 introduces the notion of the memory demand and the processor demand of a program. This allows the balancing policy to be applied to programs as a whole. This section also discusses how fairness at program level could be incorporated in the balancing policy.

2 Memory Management: Working Set Model

The model chosen for the memory management on the target machine is the Working Set model proposed by Denning[1]. The memory management facility described in this paper uses a modification of the WSClock[2] implementation of Working Set Model. WSClock can be used without any changes for managing private pages of a process. It maintains one last reference time for each frame, which is the virtual time of the owning process when it last accessed this page. This cannot be done for shared pages because they are not associated with a single process and the values of current virtual time and last reference time are not defined for shared pages.

2.1 Problems with Earlier Approaches

In [1], Denning suggests a scheme for managing shared pages. This scheme maintains last reference time LR(pi) for each of the processes pi that are accessing the shared page. The shared page is kept in memory if it belongs to the working set of any of the sharing processes. This approach has two disadvantages.

1. It requires LR(p) to be maintained for each referencing process. Since the number of processes can be large and dynamic, it will complicate the implementation of WSClock.

2. It might happen that a page might not be in the working set of any of the processes and still be frequently accessed.

An example will best illustrate the problem 2 and will also lend itself to a solution. Let there be two processes P1 and P2 each with working set parameter τ and each of them accesses the shared page SP at a regular interval of 1.5 τ. This way this page is not in the working set of either of the processes but still is being accessed at the rate of once every 0.75 τ. This approach is unfair to the shared pages and it can cause the shared pages (which might be referenced more frequently than some of the pages belonging to the working set) to be paged out. The problem is aggravated by the fact that a single missing shared page can cause many processes to block up and a page fault on a shared page is more expensive than a page fault on a private page. Assuming that the time for paging out and paging in is approximately 3τ in earlier example, both P1 and P2 will fault on it. There exists need for a scheme that is not unfair to shared pages and preferably favors shared pages.

2.2 Working Set of a Program

Since the shared pages do not belong to any single process, they can be considered as belonging to the program. The working set of a program is defined as the set of shared pages that have been accessed in the last τ sec of the virtual time of the program (by the processes of this program). This program virtual time should have all the nice properties of a process virtual time. One of the good things about the process virtual time is that it prevents the pages of blocked/runnable(but not running) processes from kicked out. A frame should not be paged out simply because the process owning that page did not get scheduled for quite some time. Similarly, a shared frame should not be paged out if most of the processes of the program have not been scheduled on a CPU for quite some time. This means that program virtual time should go faster if most of the processes of a program are running and slower if only a few of them are running. Now we can give formal definition to the program virtual time. If a program P has p processes in all and r are running currently, then the program virtual time advances at the rate r/p times the rate of progress of real time.

2.3 Implementation of WSClock-shared

The WSClock-shared is a page replacement algorithm that is a modification of WSClock [2] and incorporates handling of shared pages as well. The system keeps track of not only the virtual time of each process but also of each program. This means that every time a process goes in or out of a CPU, there is an additional overhead of calculating the program virtual time. Since a process switch is an expensive operation, the percentage increase in cost of process switch because of this overhead is low. Also, with every frame, a bit saying whether it is shared or not, is maintained. This will add one bit per page. If a page is shared, program virtual time is stored in LR(p) instead of process virtual time of the referencing process. Similarly, while deciding whether a page is in the working set of its process (or program) or not, the LR(p) is compared with current program virtual time in case of shared pages. Figure 1 shows the flowchart of this algorithm. The system also needs to determine the working set parameter for each program. A parameter value same as the that of individual processes would not be unreasonable. A good system should modify this value dynamically depending on some feedback like percentage of page faults on shared pages. Another difference between WSClock algorithm and WSClock-shared is that because of program level balancing policy (explained later), there is no notion of an individual process being active or inactive. Either the whole program is active or is inactive. So while determining which page to replace, only the activeness of the program need to be checked. WSClock-shared does not need any additional assistance from hardware so any machine that can run WSClock can also run WSClock-shared.

3.1 Resource Allocation

The policy for resource allocation chosen for this system is the Balancing Policy suggested by Denning [1]. The main difference in the approach used here and suggested in [1] is that the resources are allocated to programs rather than individual processes. This implies that it is the whole program that is active or inactive (swapped out) at any point in time. The Balancing Policy needs the processor and memory demands to decide which processes gets to be active and which not. Once the processor and memory demand of a program is defined, the Balancing approach can be applied to programs without any changes.

The memory demand of a program Pi is defined as

mi = ΣWS(pi) U WS(P)

where pi is a process belonging to program P. WS(pi) is the private working set of the process. WS(P) is the set of shared pages.

The processor demand of a program is defined as the expected number of processes that will be runnable simultaneously in the near future. The approach used here to calculate processor demand assumes that the past is a good indicator of the future and the average number of simultaneously runnable[1] processes during a recent interval is taken as the future processor demand of a program. It needs to be verified whether this assumption holds good for the applications that would be running on the target computer. The function pri(t) is the number of simultaneously runnable1 processes of program Pi at a given instant t.

The processor demand

pdi=[pic]

Where N = number of processors, b and e is the beginning and end respectively of the last interval during which the program was scheduled to be running1. Since the exact calculation of processor demand as given by the above formula is hard to implement, a summation at discrete intervals should provide a reasonable accurate value.

The problem with this balancing policy is that it does not address the issue of fairness. Any real system has to have some sense of fairness otherwise some programs might starve. Since the Balancing Problem is a minimization problem, the unfairness done to programs can be put as one of the parameters that the algorithm tries to minimize while trying to allocate resources. Let Ei be the amount of compute time that has been expended by program Pi and Si be the compute time that this program should have received according to the fairness policy used by the system. The quantity favor done to a program is defined as

FD(Pi) = Ei - Si.

F = [pic] quantifies the fact that how much extra compute time, the running processes have consumed, than they should have. The Balancing Policy will now try to minimize

{|S-(α,β)| + γF}

where γ is the parameter that can be used to specify how important fairness is depending on the kind of workload this machine would be running. (Please refer to [1] for the definition of S, α and β.)

4. Conclusions and Future Work

In a multi-processor environment, where programs can have multiple processes cooperating in a computation, using uni-processor memory management techniques pose certain problems. This paper discussed the problems of shared pages and co-scheduling and observed that treating a program as an entity for resource allocation provides simple solutions to these problems. The pitfall of this approach is that it does not try to collect and use information about individual processes. Therefore, this approach might be missing out on some optimization opportunities. Nevertheless, the ease of implementation, simplicity and no additional hardware requirements makes this approach attractive. Future work consists of investigating two things. One, whether the assumptions about the workloads made in the paper hold for the real workloads. Second, whether the price being paid for not looking at the individual processes too high.

References

1. Peter J. Denning, "The Working Set Model of Program Behavior", Communications of the ACM, 11 5, May 1968, pp.323-333.

2. Richard Carr, John Hennessy, "WSCLOCK - A Simple and Effective Algorithm for Virtual Memory Management", 8th Symposium on Operating Systems Principals (SOSP), Pacific Grove, California, December 1981, pp. 87-95.

-----------------------

[1] A program is said to be runnable (or running) when it is not swapped out to disk. A process is said to be runnable when it is not blocked for any event and is ready to run

-----------------------

No

Yes

Clear

Set

Figure 1 WSClock-shared Algorithm

Schedule Page for Cleaning

Clear

Clear

Clear

Set

Set

Set

No

No

Yes

Yes

VT(proc)

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download