JP2010044784A - Scheduling request in system - Google Patents

Abstract

To efficiently schedule resource requests of different processes and threads.
The system includes a resource, an execution entity configured to issue a request to the resource, and a table or table segment 202A-202E that includes a slot assignment for each execution entity. The schedule controller 314 is configured to access a table or table segment and process requests from execution entities according to slot assignments. The system also includes a scheduler 232 that updates slot assignments. In addition, the system may include an operating system 220 that negotiates with the executing entity and determines resource usage requests. The table or table segment may be updated by the operating system based on the resource usage request.
[Selection] Figure 2A

Description

BACKGROUND The present invention relates to deterministic scheduling of requests in a system.

  The software layer of a system (eg, a computer) typically includes an operating system and application programs. When an application program is executed, one or more processes or other basic units of work or execution entities may be constructed. In the case of a given operating system, such as the Windows 95 or Microsoft NT operating system from Microsoft, each process is included in the process address space to perform its assigned function. One or more units of work (called threads) that execute the generated code may be included. Threads belonging to the parent process may be assigned to perform different functions. For example, in the case of a spreadsheet process, the thread may be constructed to calculate, print, receive user input, perform help functions, and the like. For other operating systems, a task or process may constitute a basic unit of work or execution entity that is scheduled for execution by a central processing unit (CPU).

  The operating system may include a scheduler that manages multiple active threads or processes. Different types of operating systems may have different scheduling schemes. For example, for some Windows operating systems, time slots are assigned to active threads in a round robin fashion that the corresponding thread can execute. Further, for some Windows operating systems, priority classes may be assigned to threads. The highest priority class threads are executed first in the time slice assigned to them (followed by the lower priority class threads). Thus, in any particular priority class, scheduling may be performed in a round robin manner. The thread continues to execute until one or more events occur. The time slice ends or the thread is replaced by another thread of higher priority that is ready to execute.

  Different processes, threads, or other units of work may use system resources differently. For example, in the video playback and decoding process, data is transferred from a compact disc (CD) or digital video disc (DVD) drive to system memory, transferred between the CPU and system memory, and displayed by a graphics card on the monitor. May be transferred from system memory to video memory. In general, the data transferred from the CD or DVD drive to the system memory may be slower than the data transferred between the CPU and the system memory, and slower than the data transferred between the graphics card and the system memory. . Thus, system resources (eg, including system memory, buses, and other devices) may be used differently depending on the requirements of different units of work or execution entities.

  Conventional operating systems generally do not efficiently account for different resource requirements of different processes, threads or other units of work. Such conventional operating systems schedule (schedule) processes, threads, and other units of work at an appropriate level. That is, for example, processes, threads or other units of work associated with each application are assigned to a predetermined priority class. In general, requests from unit work are scheduled according to pre-assigned priorities and scheduling protocols, regardless of whether the required system resources are available.

In general, in one embodiment, a system includes a resource, an execution entity configured to make a request to the system, and a storage location that includes slot assignments associated with requests for the resource from each execution entity; Is included. The controller is coupled to the resource, configured to access the storage location and process a request for the resource from the executing entity according to the slot assignment.

  Other features will be apparent from the following description and the claims.

  According to the present invention, by using a decision scheme in which the availability and state of use of a requested resource is determined by the scheduler, the scheduler can request that the request from the executing entity be the bandwidth of the requested entity. It can better guarantee that it will be serviced according to request and ring time requirements.

1 is a block diagram of a system according to an embodiment of the present invention. FIG. 2 is a block diagram of layers in the system of FIG. 1. FIG. 2 is a block diagram of layers in the system of FIG. 1. It is a figure which shows the scheduling cycle by embodiment. 2 is a flowchart of a scheduling module in the embodiment of the system of FIG. 2 is a basic input / output system (BIOS) flowchart in the embodiment of the system of FIG. 2 is a flowchart of an operating system in the system embodiment of FIG.

System according DETAILED DESCRIPTION Embodiments of the present invention is or accessed used by the software of firmware layers. By way of example, system resources may include system memory, one or more buses, and other devices. A scheduler according to an embodiment executing in a system, in some embodiments, is predetermined by a software layer and a hardware layer that include whether a given system resource is available and the request call time and bandwidth. Schedule requests from basic units (eg, processes, tasks or threads) of work or execution entities created according to criteria. In some embodiments, the scheduler is provided with feedback on system resource availability and usage status. By utilizing a decision scheme in which the availability and status of the requested resource is determined by the scheduler, the scheduler ensures that requests from the executing entity are in accordance with the requested entity's bandwidth and call time requirements. You can be better guaranteed to be serviced.

  Referring to FIG. 1, for example, a general purpose or special purpose computer, other microprocessor or microcontroller based system, portable computing device, set top box, appliance, game system, or application specific integrated circuit (ASIC) or programmable gate A block diagram of system 10 is shown, which may be another system including a controller such as an array (PGA).

  Although the description herein refers to specific configurations and architectures for the various layers of the system 10, numerous modifications and changes are possible with respect to the described and illustrated embodiments.

  In the embodiment of FIG. 1, the system 10 includes a central controller coupled to a host bridge controller 102 that includes a memory controller 103 coupled to a main memory (system memory) 104 and a graphics interface 105 coupled to a graphics card 106. A processing device (CPU) 100 is included. The graphics interface 105 may be, for example, an accelerated graphics port (AGP) described in the Accelerated Graphics Port Interface Specification, Rev. 2.0, issued in May 1998. The host bridge controller 102 also includes a cache controller 107 for controlling the second level (L2) cache memory 109. Host bridge controller 102 includes a bus interface 111 coupled to system bus 112. Note that this bus interface 111, in one embodiment, is a peripheral component interconnect (PCI) that operates as described in the PCI local bus specification, production version, revision 2.1 issued in June 1995. ) Bus, and in other embodiments, other types of interface protocols.

  For example, in other configurations, the host controller and bridge controller may be replaced with a memory hub and input / output hub coupled by a link. In such a configuration, the memory and graphics interface circuit may be in a memory hub and the bridge controller may be an I / O hub.

  The system bus 112 is coupled to a storage controller 114 that controls access to one or more storage devices, such as a hard disk drive 115 or a compact disk (CD) or digital video disk (DVD) drive 116. Other devices, such as network interfaces and slots (not shown) coupled to peripheral devices may be coupled to the system bus 112. Systems according to various other integration levels may have controllers that execute in different blocks. For example, a hard disk drive or a CD or DVD drive controller may be included in the system bridge controller 110.

  The system 10 has a secondary bus or expansion bus 120. System bridge controller 110 is coupled between system bus 112 and expansion bus 120. System bridge controller 110 includes a system bus interface 113 coupled to system bus 112 and an expansion bus interface 119 coupled to expansion bus 120. The system bridge controller 110 also includes a universal serial bus (USB) interface 117 coupled to the USB port 118 as described in the general bus specification published in January 1996, revision 1.0. The expansion bus 120 is coupled to various peripheral devices (input / output devices) 122 and a non-volatile memory 124. Components and devices coupled to the bus, the bus itself, and system memory form part of the system resources used or accessed by requests from units of work or execution entities within the system 10.

  With reference to FIGS. 2A-2B, the various software and hardware layers of the system 10 are shown in greater detail. By way of example, system 10 may include an operating system (OS) 220 and processes 222 and 224. In the following description, operating system 220 is assumed to be a thread-based system such as the Windows operating system where each process may include one or more threads. However, the request scheduling scheme according to the above embodiments may be executed in the operating system by differently configured execution entities or units of work.

  As shown in FIG. 2A, threads 228 and 229 belong to process 222 and threads 230 and 231 belong to process 224. The thread may communicate with the operating system (OS) 220 via a predetermined interface, such as an application programmable interface (API) defined under the operating system. Alternatively, a “third party” API may be used. The operating system (OS) 220 has a scheduler 232 that schedules requests from active threads via a predetermined interface. In one embodiment, scheduler 232 may access memory, I / O, other predetermined locations of system 10 and communicate with hardware components to perform scheduling operations in accordance with embodiments of the present invention. It may be associated with the driver 240. These elements 232 and 240 are collectively referred to as the scheduler. In other embodiments, the scheduler may be separated into more modules or layers.

  When receiving a request from a thread, the scheduler 232 schedules the request based on feedback communication from the hardware component, the number of requests not yet executed, the calling time of the request thread, and the bandwidth request. )

  According to one embodiment, scheduler 232 stores requests in request queue (queue) 204 having a predetermined number of entities. Each entry in the request queue 204 may be associated with a status flag in the status field 206 that indicates whether a particular request has been processed.

  A set of tables or table segments 202 stored in system memory 104 (or some other suitable storage location) that can be accessed by scheduler 232 via device driver 240 is a corresponding active each having a thread identifier (ID). Identifies the channel assignment for the thread. Each channel is defined as having a predetermined number of cycles of a basic clock, such as a clock generated by clock generator 250. The number of basic clocks for each channel is selected based on the desired granularity. Each table or table segment 202 corresponds to system 10 resources including, for example, system memory 104, graphics card 106, system bus 112, expansion bus 120, USB port 118, and the like.

  In an embodiment, the bridge controllers 102, 110 also store tables or table segments corresponding to various system resources that monitor channel assignments for specific threads by thread ID. The bridge controller table or table segment is loaded based on a corresponding table 202 maintained by the operating system (OS) 220. In the illustrated embodiment, the tables or table segments 302A, 302B, and 302C may be stored by the host bridge controller 102 to monitor channel assignments for each of the system memory 104, system bus 112, and graphics card 106. Good. The system bridge controller 110 may store tables or table segments 302D and 302E to monitor channel assignments to the USB port 118 and expansion bus 120. Other tables may also be reserved for other system resources.

  Although shown as being stored in the bridge controller 102, 110, the tables 302A-302E may be stored in the system memory 104 or other suitable location, such as an external storage device. Alternatively, the different system resources may be controlled by a controller disposed in the system rather than being integrated into the bridge controller 102, 110 as shown.

  Tables 302A-302E may be periodically updated by operating system (OS) 220 as channel assignment changes. In each of the tables 302A-302E, threads may be assigned the same or different number of channels. For example, the thread associated with the first thread ID may be assigned a first channel number, and the thread associated with the second thread ID may be assigned a different channel number.

The channels assigned to the threads in tables 302A-302E define a thread request execution window or slot within the entire scheduling cycle 400 as shown in FIG. The scheduling cycle 400 includes a plurality of thread request execution windows or slots 420 ₀ , 402 ₁ ,. . . 402 _N-1 and 402 _N. Each request execution window 402 is assigned to execute a request from a thread.

In one embodiment, the first window 420 ₀ is assigned to a scheduler 232 that maintains coherency between the OS table 202 of the bridge controller 102, 110 and the corresponding table 302. The remaining windows 402 ₁ -402 _N may be assigned to requests from various other threads. In the illustrated embodiment, the tables 302A-302E are updated by the scheduler device driver 240 once every scheduling cycle 400 of Copyency Windows® 4200. During the time of the coherency window 420 ₀ , or in another window 402 _i , the scheduler device driver 240 also determines the status register 304 A of the bridge controller 102, 110 to determine which request has been completed. The contents of .about.304E may be read. Thus, scheduler 232 is configured to feed back information about which requests have been completed and which requests have not yet been executed so that it can monitor which system resources are available. Yes. Thus, when a request from a thread is received by scheduler 232, scheduler 232 can determine whether sufficient resources are available to process the request.

  Referring again to FIGS. 2A and 2B, according to an embodiment, each of the bridge controllers 102, 110 includes various call times that store requests for various resources of the system 10. As an example, the host bridge controller 102 has a memory queue 310 for the memory controller 103. Requests received by the memory controller 103 from various sources of the system 10 including the CPU 100 connected via the CPU bus interface 312 and various devices on the system bus 112 connected via the system bus interface 111, respectively. Are stored in the memory queue 310 for execution. In addition to the memory address and data information, the memory queue 310 is also configured to store an associated ID of the memory request.

  In some embodiments of the invention, the CPU 100 fetches an instruction (instruction fetch operation) along with the associated thread ID. The thread ID is sent to the bridge controllers 102 and 110 and stored in a queue of the bridge controllers 102 and 110.

The scheduler controller 314 of the host bridge controller 102 receives the output value from the counter 306 and the tables or table segments 302A to 302C. Counter 306 clocked by the base clock from clock generator 250 may be configured to count through the channel in scheduling cycle 400. Based on the value of the counter 306, the scheduler controller 314 can determine the current thread request execution window 400 _i (i = 0 to N) within the scheduling cycle 400. Based on which window 400 _i is active and the channel assignments in table 302 A, a request associated with the corresponding thread ID in memory queue 310 may be selected for processing by memory controller 103.

  The selected request is executed in the current window 400i. Upon completion of the request, the host bridge controller 102 may return to the request completion state by programming the appropriate bits in the status register 304A. In the next coherency window 4020, under the control of the scheduler device driver 240, the CPU 100 reads the status register 304A (as well as the other status registers 304B-304E) to determine which request has been completed. Next, the scheduler device driver 240 updates the completion request flag 206 in the request queue 204.

In addition to the memory queue 310, the host bridge controller 102 in one embodiment may also include a system bus queue 316 for the system bus interface 111 and a graphics card request queue 318 for the graphics interface 105. Requests for the system bus 112 are placed in the system bus queue 316, while requests for the graphics card 106 are placed in the graphics card queue 318. Since the request is related to the thread ID, the scheduler controller 314 performs appropriate processing by the bus interface 111 or the graphic interface 105 based on the channel assignment stored in the current thread request execution window 402 _i and the tables 302B and 302C. You can choose. Completion of requests in queues 316 and 318 is indicated by status registers 304B and 304C, respectively.

Similarly, the system bridge controller 110 includes an expansion bus queue 320 that stores requests supplied to the expansion bus 120 and a USB bus queue 322 that stores requests supplied to the USB port 118. Counter 308 clocked by the base clock from clock generator 250 counts the channels in scheduling cycle 400. Based on the current thread request execution window 402 _i as indicated by the counter 308 and the channel assignments stored in the tables 302D and 302E, the scheduler controller 324 of the system bridge controller 110 determines the request for each of the queues 320 and 322, respectively. Determine which ones should be processed. Completion of the request is indicated by status registers 304D and 304E.

  As shown in FIG. 4, the scheduler device driver 240 cooperating with the scheduler 232 waits (at step 502) to receive a predetermined event. If a request from a thread, which may be in the form of an Application Programmable Interface (API) call, is received, the scheduler device driver 240 (in step 504) enters the request queue 204 and the channel assignment table 202. Having access, scheduler 232 can determine (at step 506) whether resources are available to process the thread request.

  If the scheduler 232 determines that the resource is not available to process the request properly, the requested thread is notified (at step 508). In response to this notification, the thread can wait for some time before reissuing the request, or the thread can otherwise handle this condition particularly well. If the requested resource is available, the request from the thread is added to the request queue 204 (at step 510).

  When a specific request in schedule queue 204 is processed and completed, all flags in flag field 206 of queue 204 may be set as described above.

The scheduler device driver 240 itself is a thread that can issue requests to access memory locations corresponding to the request queue and thread channel allocation table. (In step 520) a request from the schedule device driver threads placed in the request queue 204 may be processed by the first window 402 ₀ schedule cycle 400. Alternatively, other windows 402 _i may be assigned to the scheduler device driver 240.

During the coherency window 402 _0, CPU 100 under the control of the scheduler device driver 240, the bridge controller table 302A～302E (in step 522) and updated as needed, change the channel assignment. CPU 100 may access status registers 304A-304E to determine which requests have been completed (at step 524). Instead, the table update operation and the status register read operation may be performed separately. Next, CPU 100 under control of device driver 240 may update request queue 204 (at step 526).

  The scheduler 232 can determine what system resources are required by the request by examining the request parameters, such as the request itself and the parameters of the API call. For example, the parameter may specify access to a location in the memory address space of the system memory 104. Other parameters may specify the location of the I / O address space on one of the buses 112, 120 of the graphics card 106 on the USB bus coupled to the USB port 118 or other location of the system 10. Good. Based on the requested resources, the requests already in the queue 204, and the channel assignment specified in the table or table segment 202 as retrieved by the scheduler device driver 240, the scheduler device driver 232 may determine that the request is reasonably reasonable. It can be determined whether the method can be processed. This may be defined according to criteria pre-programmed into the system 10 and loaded by a startup routine (eg, basic input / output system or BIOS routine). The scheduler 232 is aware of the call time and bandwidth requirements of the various threads of the system. Call time requirements and bandwidth requirements may be used by scheduler 232 to determine whether sufficient resources are available to satisfy a thread request.

  As an example, the thread may issue a request to transfer a frame of video data from the video memory of graphics card 106 to system memory 104. Given a frame size (eg, 720 × 480 pixels) and a number of bits defined for each pixel, the bandwidth requirement for video transfer is determined based on the specific time that the transfer must occur. May be. Further, the call time for the transfer request may be known. Based on the bandwidth and ring time information, and based on outstanding requests for resources that have not yet been executed, the scheduler 232 can determine whether the video transfer request can be processed by the available resources. If not, the thread is informed by the scheduler 232 and the thread responds in one of a number of ways, including waiting before issuing another request or splitting the request into parts. It's okay.

  As shown in FIG. 5, system initialization is performed by a system BIOS routine according to an embodiment. After the system hardware is initialized by a system reset, the CPU 100 is responsible for initializing the components of the system 10 to a known state and configuring system configuration information for the operating system (OS) 220 to be used. Start executing instructions of the BIOS power on self test (POST) procedure. Several initialization tasks are performed in the system 10 (in step 602) and the BIOS routine then sets up the system memory 104 or other suitable storage location (in step 604) to create a channel assignment table or table segment. 202 is stored. The BIOS routine may specify the number of basic clocks for each channel (eg, one or several clocks per channel) and the full width of the schedule cycle 400. A particular memory address may be reserved for storing a table or table segment 202. Furthermore, criteria may be specified for use by scheduler 232 in determining whether to accept or reject a thread request.

  The default channel assignment may then be loaded into the table (in step 606). For example, certain threads (eg, schedulers and other system management layers) associated with the operating system (OS) are assigned to windows at cycle 400. In addition, the BIOS may set a default window with a predetermined number of channels to handle thread requests that are not assigned to a particular window. The BIOS can poll the system configuration space and other information that determines the type of processor available when the processor is a multi-processing system. From this information, the BIOS can determine the communication processing capability of the system. Based on such determined communication throughput, the BIOS can allocate the default window channel number accordingly. Next, the system components are initialized and configured by the BIOS routine (at step 608). Next, the operating system (OS) 220 is booted (in step 610).

As shown in FIG. 6, after the operating system (OS) 220 is booted, the operating system (OS) 220 identifies (at step 650) a number of active threads in the system 10. The operating system (OS) 220 queries (at step 652) each thread for its bandwidth request and call time request for resources of the system 10. Some threads know what call time and bandwidth requirements are for each system resource. For example, a thread associated with a multimedia process may have “real time” requests that require high data transfer throughput that can tolerate relatively small call times for data transfer. Other threads may be able to tolerate higher call times and lower data transfer bandwidth. Based on a comparison of different call time requests and bandwidth requests from active threads, several channels that allocate different request windows 402 _i corresponding to different threads facilitate threads with lower call times and higher bandwidth May be set by the operating system (OS) (in step 654). As a result, these types of threads may be assigned multiple channels and possibly multiple windows 402 _i . A number of assigned windows 402 _i may be continuous in a scheduling cycle 400 or may be distributed. If a thread does not provide call time and bandwidth information for system resources, this thread may be assigned to the default window 402 _i in the scheduling cycle 400 of the table or table segment 202.

  Based on the calculated number of channels, the table or table segment 202 may be loaded with channel assignments (at step 656) according to thread ID.

  Thus, according to some embodiments, a scheduling scheme may request a request from a system thread by determining whether a data flow request may be satisfied based on resource availability and channel allocation. Schedule (schedule). Resource availability is indicated to the system scheduler by hardware requirements. Further, based on the request type and request parameters, the scheduler can determine what resources are required by a particular request.

  Other embodiments are within the scope of the above claims. For example, in the case of different operating systems, the basic unit of work or execution entity in the system may not be a thread but may be a process or other defined unit. Furthermore, the hardware components of the system may be configured differently. Operations performed by software or illustrated firmware modules or layers may be altered.

  Although the present invention has been disclosed with respect to a limited number of embodiments, those skilled in the art will appreciate numerous modifications and variations therefrom. It is intended that the appended claims cover all modifications and changes as fall within the true spirit and scope of the invention.

Claims (20)

Resources and
An execution entity configured to issue a request to the resource;
A storage location including slot assignments associated with requests for the resource from each executing entity;
A controller coupled to the resource and configured to access the storage location and to process a request for the resource from the execution entity according to the slot assignment.   The system of claim 1, further comprising a scheduler configured to update a slot assignment of the storage location.   The system of claim 2, further comprising a second storage location accessible by the scheduler and comprising a slot assignment for the execution entity.   The scheduler is configured to determine whether the resource is available for a request issued by an executing entity based on a slot allocation of the second storage location and an outstanding request. 4. A system according to claim 3, characterized in that   The scheduler is aware of the bandwidth for each execution entity's resources and determines whether the scheduler is available for requests made by the execution entity based on the bandwidth information 5. The system of claim 4, wherein the system is configured to:   The system of claim 4, wherein the request includes an application programmable interface call associated with one or more parameters.   The system of claim 2, wherein the scheduler is configured to access the controller to determine whether a request has been processed.   The system of claim 1, further comprising a counter accessible by the controller to determine which slot is active.   9. The system of claim 8, wherein each slot includes one or more channels and the counter is configured to count the channels.   The system of claim 1, wherein a plurality of slots are defined in a scheduling cycle, and the controller is configured to process requests from the executing entity in corresponding slots. An operating system that cooperates with the execution unit to determine resource usage requests;
A storage location that allocates a channel to the execution unit based on the resource usage request of the execution unit that is updatable by the operating system and has access to system resources during the allocated channel. The system according to claim 1.   The system of claim 11, wherein the execution entity is configured to communicate bandwidth information for the resource to the operating system.   The system of claim 12, wherein the execution entity is configured to further communicate call time information for the resource to the operating system. A method for scheduling requests from execution devices in a system, comprising:
Determining data flow information of the execution unit for system resources;
Based on the data flow information, assigning a time slot to the execution unit for access to the system resources;
Programming a controller based on the assigned time slot, and the controller requests for the system resources based on information about which time slot is currently active and the time slot assignment. A method characterized by processing.   The method of claim 14, wherein determining the data flow information comprises determining bandwidth information used by the execution device for access to the system resources.   The method of claim 14, wherein determining the data flow information comprises determining call time information used by the execution unit for access to the system resources.   The method of claim 1, further comprising determining whether a request from a first execution unit can be processed based on the time slot allocation for the system resource and the availability of the system resource. 14. The method according to 14.   The method of claim 17, further comprising determining availability of the system resource based on the data flow information and an outstanding request for the system resource. An apparatus having a storage medium containing instructions for scheduling requests from execution entities,
Based on the instructions, a processor
Receiving a first request from an execution entity including access to system resources;
Accessing a controller coupled to the system resource to determine whether a predetermined other outstanding request for the system resource has been processed, and the system resource is in response to the first request Determine if it is available,
A device characterized by that.   The apparatus of claim 19, further comprising instructions for operating the processor to further notify the execution entity if the request cannot be processed because the resource is not available.