Dynamic resource allocation for user management in multi-processor time shared computer systems

[0002] This invention relates to an assembly and method suitable for optimizing allocation of resources in a multi-processor time-shared computer system.

[0003] In a time shared computer system, each user gets pro-rated computer resources over some interval of time. These resources are various classes of memory and disk storage and, in multi-processor systems, the available CPUs. These resources are limited to no-more than k users for k processors and not all users can be active or even contained in memory at any given time.

[0004] Currently, each user has a priority and is given a fixed slice of computer time in which he does his processing, and then has an inactive period of time during which other users are active. The frequency of user activation is determined by the given user's priority. There is no discipline for the optimal resource allocation in support of a set of k users, based on optimizing computer resource utilization. The problem addressed in this invention is how to optimally allocate computer resources in support of a given number of active users.

[0005] We have now discovered novel methodology and an assembly in realization of this methodology, which are responsive and in satisfaction of this problem.

[0006] In a first aspect, we disclose an assembly suitable for optimizing allocation of resources in support of k users, in a multi-processor time-shared computer system, the assembly comprising:

[0007] (i) a resource monitor comprising:

[0008] (a) means for inputting data comprising current job requirements;

[0009] (b) means for operating upon the current job requirements for determining required resources;

[0010] (c) means for storing said required resources for subsequent processing by a resource allocation;

[0011] and

[0012] (ii) a resource allocator connected to the resource monitor comprising:

[0013] (a) means for inputting, from the resource monitor, said required resources; and

[0014] (b) means for executing the required resources for generating a resource allocation for said k users.

[0015] In a second aspect, we disclose a method suitable for optimizing allocation of resources in support of k users, in a multi-processor time-shared computer system, the method comprising the steps of:

[0016] 1) inputting data comprising current job requirements;

[0017] 2) operating upon the current job requirements for determining required resources;

[0018] 3) storing said required resources for subsequent processing by a resource allocator;

[0019] and

[0020] 4) executing the required resources for generating a resource allocation for said k users.

[0021] The invention is illustrated in the accompanying drawings, in which:

[0022] FIG. 1 shows an environment in which an assembly of the present invention may be utilized;

[0023] FIGS. 2a-2cshow alternative environments that can advantageously incorporate an assembly of the present invention;

[0024] FIGS. 3 and 4 respectively show an assembly of the present invention defining an included resource monitor and a resource allocator;

[0025] and

[0026] FIGS. 5 and 6 are used to reference an Example of the present invention.

[0027] The invention as genus is summarized above. We now turn our attention to preferred species and embodiments subsumed by the genus. In overview, and with reference to FIG. 1, numeral 10, we note that an assembly of the invention is preferably located with reference to a construct that includes a master CPU/main-memory 12 that can interface with a plurality of secondary CPUs 14-26 and external storage 28. In particular, as shown in FIG. 2a, numeral 30, an assembly 32 of the present invention may be located internal to the master CPU 12. Alternatively, as shown in FIG. 2b, numeral 34, an assembly 32 of the present invention may be located internally to a secondary CPU. It is also possible to provide first and second assemblies 32 respectively located in the master CPU 12 and a secondary CPU, as shown in FIG. 2c, numeral 36. For this last situation, for example, the master CPU may request the secondary CPU either assist, take over, or work in tandem with its resident assembly. This may be accomplished by either sending a signal to a designated CPU to take over the job, only assigning subordinate jobs to a designated secondary CPU.

[0028] We now turn our attention to details of the assembly 32 referenced in FIGS. 2a-2c. To this end, we reference FIG. 3, numeral 38, and FIG. 4, numeral 40, sequentially.

[0029] FIG. 3 comprises a resource monitor (RM). The overall function of the resource monitor is to, on the one hand, accept as input a current job (Jm) for each of k users accessing the computer system of the type shown above in FIG. 1, and, on the other hand, generate an output comprising the required resources to support the k users. This output is to b e subsequently input to a resource allocator (RA), as discussed in detail below and as shown in FIG. 4.

[0030] Both the RM and RA reside in memory. The master CPU coordinates the information flow and supplies data to the appropriate section of memory and secures relevant information to supply the RA.

[0031] FIG. 3 shows the resource monitor: it specifies four resource types, namely, main memory, secondary memory, CPU loading, and external connections. These resource types are needed to satisfy the requirements of programs and data modules of any user. As indicated above, based upon this information, the resource monitor generates an output to the resource allocator, the output generates an output to the resource allocator, the output comprising the required resources to support the k users.

[0032] FIG. 4, numeral 40, as indicated above, comprises the resource allocator RA which can accept as input the output of the resource monitor, 38, namely, a file comprising jobs Jm (k=1, . . . , k). In overview, the resource allocator computes the loads of all jobs Jm for the k users in order to allocate them to the available resources. In particular, and to this end, the resource monitor first computes the required resource (load) for each of the jobs (tasks) in support of the k users. Second, the resource monitor accesses information regarding the capacity of each of the available CPU resources. Thirdly and fourthly, the resource monitor utilizes the above information, together with system constraint (e.g., permissible assignments) to make actual task-to-resource assignments which meet all requirements within system constraints.

[0033] We now provide an example of the present invention. To this end, we make reference to FIGS. 5 and 6. In particular, FIG. 5 depicts an assignment illustration for k=5 users and 4 available CPU resources. For the purpose of this example, it is assumed that the loads required to satisfy each user are: 50, 100, 50, 100, 100 units in arbitrary scale. The capacities of the 4 CPUs are each 100 units in the same scale. Matrix Cij contains permissible assignments where 1 denotes a permissible assignment and 0 denotes impermissible assignment between tasks Tj and processors Pi. Matrix Yij contains actual assignments meeting all requirements and constraints, and derived from the pertinent preferred algorithm specified in FIG. 6.