Locally made, globally coordinated resource allocation decisions based on information provided by the second-price auction model

[0002] This invention relates to a method and apparatus for scheduling access to resources by activities.

[0003] There have been many scheduling mechanisms proposed that are based on an economic paradigm [3, 4]. Some of these incorporate the idea of using an auction to determine the next activity to be granted access to a resource. However, these proposals have dealt only with the high-level problem of allocating access to resources, and not with the low-level details of how those allocation decisions are carried out. In particular, these scheduling mechanisms have not been coupled with an efficient mechanism, i.e., one that does not incur significant overheads due to frequent communication and transfer of control between the activities contending for the resource and the arbitrator of the resource, for maintaining the relationships between activities' bids and for determining which activity is the highest bidder.

[0004] Many of the previous mechanisms that have tried to incorporate an economic model have been concerned with distributed systems in which the high cost of communication dwarf any over head involved in scheduling unlike in parallel, tightly coupled systems, where scheduling overhead can be relatively more important [5,6,7].

[0005] Processor scheduling is a central and well-studied problem in computer system design. Today, multithreaded applications are common. A thread is an independently schedulable sequence of operations. A process is a collection of one or more threads of control executing within a single address space. Threads provide an abstraction that allows a programmer to express parallelism that can be exploited to enhance application performance. Most current operating systems support multithreaded applications in such a fashion that the operating system treats each thread as a separately scheduled entity. When threads are supported in this fashion, it is simple to enforce global scheduling policies to ensure that when a single thread blocks on some request to the operating system (e.g. a system call or page fault), the rest of the application is unaffected. Treating each thread as a separately scheduled activity will also allow different threads of the same process to have different priorities. Unfortunately, such threads are inefficient because they require frequent transfer of control between the application and operating system, and because they require that the operating system maintain a state for each thread.

[0006] User-level thread schedulers manage the threads of a particular process in a fashion that is local to the process; that is, the operating system is not involved in most scheduling decisions and maintains no per-thread state. This has the advantage of greatly reducing the overhead of supporting multiple threads. However, most user-level thread packages provide no interaction between the threads and thread scheduler and the operating system. As a result, any communication with the operating system (e.g., a system call or page-fault) blocks the entire process, even though there may be threads in the process that could make use of the processor while one thread blocks on a system call. Also, since the operating system is unaware of the user-level threads, from the operating system perspective all threads within a process have the same priority, and it is not possible to manage priorities across different applications.

[0007] Two user-level thread scheduling mechanisms that do provide operating system interaction, and in which a thread that blocks in the kernel does not block the entire process containing the thread, are that of the Psyche operating system [1] and the Scheduler Activations mechanism [2]. Psyche employs shared memory for communication between the kernel and user-level processes, but this memory is not used in Psyche to coordinate the scheduling of threads belonging to different user level processes. Psyche allows a user-level process to yield a processor when it has no more ready threads. Psyche arbitrates priorities among user-level processes, but Psyche cannot arbitrate priorities among the threads of different processes.

[0008] As does Psyche, Scheduler Activations arbitrate priorities within a user-level process. The mechanism allows threads to migrate between processors in a multiprocessor system to ensure the execution of the highest priority threads of a user-level process spanning multiple processors. The authors comment parenthetically that their system is capable of arbitrating between threads with associated globally meaningful priorities, but do not discuss a mechanism for achieving this.

[0009] What is needed in a user-level thread scheduling system is a model and mechanism that enable a user-level scheduler to make an efficient local scheduling decision that is globally the correct decision, that is, the same decision would be made if there was access to all priority information.

[0010] An exclusive resource such as a computer's central processing unit is a resource that can be used by only one activity at a time. In a system with multiple concurrent activities, access to an exclusive resource must be arbitrated between activities that require access to the resource. This invention applies to systems in which activities place potentially time-varying numeric values (these values, whether time varying or constant, shall be referred to as bids) on the importance of accessing the resource, and in which at any given time, some policy is used to arbitrate between the competing bids to assign access to the resource. In addition, this invention applies to systems in which activities are to be charged for access to the resource, where the amount an activity is charged depends on both the importance it places on accessing the resource, and on the demand on that resource by other activities. These charges do not necessarily correspond to any real monetary value (although they may); in general, they are a means of enforcing a policy for allocation of rights to access the resource.

[0011] This invention is a mechanism by which activities (possibly including a designated scheduler activity) are able to cooperate to make scheduling decisions while exchanging a minimal amount of information in an efficient manner. Most decisions made by an activity are based only on local information, that is, information available to the activity without having to initiate communication with any other activity. The key piece of information, the “next-bid”, identifies the highest bid for a resource by any activity other than the activity currently using the resource. The latter activity, the one using the resource, will also be referred to as the “currently active activity.” When the need for the resource changes, the next-bid is used by a currently active activity to determine whether it should release the resource to another activity. Also, in a system that charges activities for their resource usage, the activity that accesses the resource is charged according to the next bid (as in a second-price auction) for each unit of time that it accesses the resource; that is, the value of the time used is assessed according to the bid of the activity waiting for the resource. The next bid is posted in memory available to the activity using the resource, the facility charging for the resource, and the entity scheduling the resource, allowing this information to be accessed without incurring any communication costs.

[0012] When an activity's valuation of the resource changes, the activity compares its new bid to the next bid. This can be done locally, without incurring the overhead of communicating with any other activity or scheduler. As long as the bid of the activity that has current access to the resource is at least as great as the next bid, no rescheduling action is needed. The currently scheduled activity continues to use the resource, and in a system that charges activities for their resource usage, is charged as described. For example, in a computer system, where high priority processes are assigned higher numbers, then each of the processes is charged based on the priority of the second highest bid multiplied by the time the process has had access to the resource. Only when the activity's bid falls below the next bid does the activity need to relinquish the resource. Unless it does so, it will be charged according to the next bid in a system that employs a charging scheme, which may limit its ability to access the resource at a later time, when its need to access the resource truly is greater than of any other activity. Similarly, when an activity that is not currently accessing the resource changes its bid (or its bid is changed on its behalf by some other entity), the new bid can be compared to the bid that is posted by the currently scheduled activity (currently active). Only when the new bid exceeds that of the activity accessing the resource does that activity need to be preempted.

[0013] FIG. 1 shows a multiprocess system using the shared next bid in accordance with this invention.

[0014] FIG. 2 shows a process of FIG. 1 in more detail.

[0015] FIG. 3 is a flow chart used to show how to change the next bid for the ready and waiting processes.

[0016] FIG. 4 is a flow chart used to show how to change the bid of a running process.

[0017] FIG. 5 is a flow chart used to charge the current process and preempt it if its access privilege is exhausted at a given priority level.

[0018] FIG. 6 is a flow chart used to show how to control frequency of access to a resource by a process.

[0019] It is an object of this invention to provide the ability for resource managers to make decisions that are globally correct based on local information, thus not requiring consultation with a global server, and hence avoiding communication overhead.

[0020] It is a more specific object of this invention to provide an efficient mechanism for mutually trusting and untrusting activities to determine the globally most important activity to execute.

[0021] It is another object of this invention to provide an improved accounting mechanism so that resource usage by activities can be monitored and limited if necessary.

[0022] It is another object of this invention to provide an efficient mechanism (activities access local only information) to arbitrate priorities across multiple user-level processes containing threads of mixed priorities.

[0023] It is another object of this invention to provide an efficient dispatch mechanism for economic-based schedulers in which activities' rights are represented by an artificial currency.

[0024] Thus this invention uses the auction model not just for an interesting theoretical property it provides, but in addition and primarily to be able to make local decisions while correctly enforcing a global policy.

[0025] Though our invention is not limited to the following described implementation, this implementation demonstrates the potential advantages of using our mechanism over other mechanisms. The preferred embodiment of this invention is illustrated in FIGS. 1-6. The context of this preferred embodiment is that of processor scheduling for user-level thread schedulers. However, this invention could also be applied to the scheduling of resources other than processors such as I/O, memory, network bandwidth, etc. Throughout the embodiment the highest, second-highest, and maximum bids are referred to. The patent and ensuing techniques work just as well for the lowest, second-lowest, and minimum, or other equivalent. The goal of the bids is to determine the activity that should have access to the resource as well as the next-in-line activity.

[0026] FIG. 1 shows an operating system kernel 10, several user-level processes 102A-C, and their associated memory locations 103A-C, respectively. The memory location represented by 107 is shared by all of the processes, though our invention is not limited to this particular implementation. It is only necessary that there is a location shared by the kernel and the currently running process, and it is not necessary that this location be accessible to other processes. Directions of data flow are indicated by arrows 110A-C, 116, 117A-C, 118A-C. The arrows in

[0027] FIGS. 1 and 2 indicate the directions in which information flows. More specifically, processes 102A, 102B, and 102C read and write to the shared memory location (103A, 103B and 103C respectively for each process) via arrows 117A, 117B, and 117C respectively. Likewise the kernel also reads and writes the bid via arrows 110A, 110B, and 110C. The kernel can read and write the next bid (box 107) via arrow 116, and the processes, 102A, 102B, and 102C can only read the next bid via arrows 118A, 118B, and 118C respectively. Threads, 210A, 210B and 210C can inform the user-level scheduler (209) of their priorities via arrows 211A, 211B, and 211C respectively. In this example there are three user-level processes, though our invention is not limited to any particular number of processes. Each user-level process contains one or more independent threads of control. Each thread has an associated time-varying priority value, though our invention is not limited to priority-based scheduling policies. The user-level processes and the kernel cooperate to determine which thread should be given access to a resource, e.g., the computer's central processing unit (CPU), though our invention is not limited to systems in which a central kernel provides a scheduler to enforce the scheduling policy. The scheduling policy specifies that at any time, the thread with the greatest priority value should execute, regardless of which process the thread belongs to.

[0028] FIG. 2 shows these elements in more detail for an operating system kernel 10 and just one user-level process 102, and the memory locations 103 and 107 shared by them. The directions of data flow are described above. Within the user-level process 102 is a user-level thread scheduler 209. The user-level scheduler is responsible for choosing one of its threads to run and is charged at the rate of the second-highest bid. In this example there are three threads 210, 211, and 212, though our invention is not limited to any particular number of threads overall or per process. The user-level thread scheduler 209 (or the kernel 10 acting on its behalf) records the priority of the selected thread in the bid memory location 103. (Note: in this embodiment we use the term priority for determining the ordering of activities. In reality this could be any scheme that allows an ordering of activities. For instance, currency or tokens may be distributed to activities and then used in differing quantities based on the degree to which an activity needs a resource. This is just one example; any other scheme that allows an ordering on activities to be achieved may be used.) The bid memory location 103 is writable both by the user process 102 and by the kernel. This is because the kernel may update the bid of the user process on its behalf For instance, on completion of an input/output (I/O) operation, an interrupt handler in the kernel may respond to the event, and raise the priority of a process since the availability of the data changes the thread's status from “blocked on I/O” to “ready.” The next bid location 107, which is readable by the user process and readable and writable by the kernel, contains the second-highest priority among those posted by all user processes. If there are two or more bids that are identical and higher than all other bids, then one of these bids is treated as the second highest bid for the purpose of this algorithm.

[0029] FIG. 3 shows the flowchart used upon a change in the bid of a process that is not currently executing. In the figure, “new bid” refers to the new value of the bid of the process which is changing its bid, and “old bid” refers to that process' former bid. “Next bid” refers to the second-highest bid maintained by the kernel. “Current” refers to the process that is currently executing. The new bid is compared to the old bid (step 301). If the new bid is greater than the old bid, it is possible that the process changing its bid becomes the highest bidder or the second-highest bidder. The new bid is thus compared to the next bid to determine whether this is the case (step 302). If the new bid is greater than the next bid, then the new bid is compared to the bid of the current process (step 303). If the new bid is greater than that of the current process, the process changing its bid will be granted access to the resource, and the next bid location is updated to contain the bid of the preempted process (step 304). Otherwise, the new bid is now the second-highest bid, and the next bid location is updated to reflect this (steps 305 and 308). If the new bid is not greater than the old bid, then it is possible that the old bid was previously the second-highest bid, and that the next bid location must be updated to reflect the current situation. Step 306 checks for this condition. If the answer to step 306 is yes, the second-highest bid among all processes must be determined (step 307) and stored in the next bid location (step 308). Now the second-highest bidder must be determined from the set of bidders. An appropriate method should be chosen from the literature based on the number of processes that will be represented. While the patent is not limited the below methods for this determination they illustrate how one might implement this determination. For example, for a small number of processes, this could be accomplished by scanning though a linked list; and for a large number of processes, the priorities could be stored in a data structure known in the literature as a priority queue. A priority queue is a data structure that allows the greatest value to be determined and removed, and new values to be stored, in time logarithmic in the number of values stored. (This use of the term “priority” in “priority queue” is distinct from that of process or thread priorities; the use of a priority queue to store thread priorities is incidental.)

[0030] Those skilled in the art will appreciate that in the case that the new bid does not cause a change in the current allocation of the resource, little computation is required on the part of the process changing its bid, and more importantly, that no communication or transfer of control between processes is necessary. In the case that the new bid does cause a change in the current allocation of the resource, communication between processes is unavoidable, since the currently running process must relinquish the resource to the new highest bidder.

[0031] FIG. 4 shows the flowchart used upon a change in the bid of the process that is currently executing. Again, “new bid” refers to the new value of the bid of the process which is changing its bid, and “old bid” refers to that process' former bid. The new bid is compared to the old bid (step 401). If the new bid is greater than the old bid, the process will still be the highest bidder, and the second-highest bid will not change, so no action is necessary. Otherwise, it is possible that the process is no longer the highest bidder. The new bid is compared to the second-highest bid (step 402). If the new bid is lower than the second-highest bid, the current process should relinquish the resource (step 403). The former second-highest bidder is granted access, and the second-highest bid among all processes (which may be that of the process that reduced its bid and relinquished the resource) must be determined and stored in the next bid location. As before, the second-highest bid is found by scanning a list or by accessing a priority queue.

[0032] Again, those skilled in the art will appreciate that in the case that the new bid does not cause a change in the current allocation of the resource, little computation is required on the part of the process changing its bid, and more importantly, that no communication or transfer of control between processes is necessary. In the case that the new bid does cause a change in the current allocation of the resource, communication between processes is unavoidable, since the currently running process must relinquish the resource to the new highest bidder.

[0033] FIG. 5 shows the actions taken by the kernel to monitor resource usage in a system that charges activities for their resource usage. The kernel uses this flowchart when the activity currently accessing the resource yields it, as well as at periodic intervals in order to ensure that activities are not using the resource more than allowed by their privileges. The kernel decrements the current activity's balance of currency according to its resource consumption (step 501). The resource consumption of that activity is the integral of the next bid over the time from the last periodic interval to the present. Next, the kernel takes one of two paths depending on whether the current activity has yielded the resource or the kernel is performing one of its periodic checks (step 502). If the latter, the kernel checks whether the activity has exhausted its allocation of currency (step 503). If it has not, the activity is allowed to continue to access the resource. Otherwise, the resource is preempted from the activity (step 504), the new high bidder and second highest bidder are determined, and the new high bidder is allowed to access the resource (step 505). If the current activity has yielded the resource, step 505 is carried out immediately after step 502.

[0034] FIG. 6 shows the actions taken by the kernel in a system that limits resource consumption based on an activity's past resource usage on a per-priority basis. The kernel determines whether the current activity has exceeded its limit of consumption at its currently claimed priority level in the current time period (step 601). If this is true, the kernel next determines the maximum priority value that the activity is eligible to claim (step 602), and assigns this value as the current activity's new bid. The kernel then determines the activity that should be allowed to access the activity next upon a change in the current activity's bid as in the procedure illustrated in FIG. 4.

[0035] This invention does not preclude the use of additional policies to enforce limits on resource usage. This example illustrates one method by which our invention might be used to charge user-level processes for their resource usage and to cooperate with additional policies to enforce limits on resource usage. Consider a system with two priority levels, “high” and “low,” though our invention is not limited to any particular number of priority levels. Suppose that the resource allocation policy specifies that each process is allowed up to two units of high priority service out of every ten units of time; these values are meant as an example only. Suppose a process A reaches this limit by scheduling one of its threads for two consecutive units of time while there is at least one other process with a ready thread with a bid of value “high.” After it receives its two units of high-priority service, process A should not be allowed to schedule its threads claiming a bid of “high” until eight time units elapse. The kernel scheduler will preempt the CPU from process A after it receives its allotted two units of service, and will grant access to one of the waiting processes which have posted bids of “high.” The kernel scheduler will record the fact that A has used its two units of high priority service and must wait eight time units before accessing the resource again with a bid of “high.” Even if A posts a bid of “high,” the kernel scheduler will grant the CPU to user-level processes as though A's bid were “low” for eight time units, until A is eligible to receive high-priority service again. The kernel can use a standard timer interrupt mechanism to wake itself up periodically and detect situations such as this example.

[0036] All of the above preferred embodiment describes the arbitration of one resource on a single processor. However, in actual computers, many resources may need to be arbitrated on multiple processors. The techniques above can be applied to each resource whether that resource is CPU time, memory, I/O, network bandwidth, etc., and the techniques can be applied per processor on each of the processors in the system. As used in this application, a computer system is any system that uses computers to schedule use of its resources.

[0037] 1. B. D. Marsh, M. L. Scott, T. J. LeBlanc and E. P. Markatos, “Proceedings of the 13th ACM Symposium on Operating System Principles, October 1991.

[0038] 2. T. E. Anderson, B. N. Bershard, E. D. Lazowska and H. M. Levy, “AMC Transactions on Computer Systems,” Vol. 10, No. 1, February 1992.

[0039] 3. S. H. Clearwater, Editor, “Market-based Control: A Paradigm for Distributed Resource Allocation,” World Scientific 1995.

[0040] 4. B. A. Huberman, Editor, “The Ecology of Computation,” North Holland, Amsterdam 1988.

[0041] 5. K. Eric Drexler and Mark S. Miller, “Incentive Engineering for Computational Resource Management”, The Ecology of Computation, pp. 231-266.

[0042] 6. Thomas W. Malone, Richard E. Fikes, Kenneth R. Grant, and Michael T. Howard “Enterprise: A Market-like Task Scheduler for Distributed Computing Environments”, The Ecology of Computation, pp. 177-205

[0043] 7. Carl. A Waldspurger, Tad Hogg, Bernardo A. Huberman, Jeffrey O. Kephart, and Scott Stornetta, “Spawn: A Distributed Computational Economy”, IEEE Transactions on Software Engineering 18:103-117, 1992.