Time-division multiplexing method and circuit for arbitrating concurrent access to a computer resource based on a processing slack associated with a critical program

Patent metadata

Field	Value
Publication number	US-12045671-B2
Application number	US-201917289270-A
Country	US
Kind code	B2
Filing date	Oct 22, 2019
Priority date	Oct 31, 2018
Publication date	Jul 23, 2024
Grant date	Jul 23, 2024

Abstract

The invention relates to a method implemented by computer for arbitration between computer programs seeking to access a shared resource concurrently and each transmitting an access request. The method performs time-division multiple access according to which the time is divided into time slots, each of which is allocated to a critical program for access to the shared resource, each time slot comprising a plurality of time units. The method exploits a processing slack associated with each critical program in order to delay a processing deadline for an access request transmitted by the critical program. The method comprises, for each unit time, a step of selecting a waiting access request and a step of determining authorization for immediate processing of the selected access request. This determining operation comprises, for a unit time which does not correspond to the beginning of a time slot, when the critical program to which the next time slot is allocated has not issued the selected request, authorization for the immediate processing of the selected request if the processing slack of the critical program to which the next time slot is allocated is greater than a threshold.

First claim

The invention claimed is:

1. A computer-implemented method for arbitrating between computer programs attempting to concurrently access a shared resource (MM) by each issuing an access request, the method performing time-division multiple access whereby time is divided into time slots each allocated to a critical program for access to the shared resource, each time slot comprising a plurality of time units,
in which method a processing slack (MA 1 , MA 2 ) is associated with each critical program for delaying a processing deadline (I 1 ) of an access request issued by the critical program,
which method is characterised in that it comprises, at each time unit, a step of selecting an access request (B 0 , c 0 , c 1 ) from one or more waiting access requests and a step of determining an authorisation for immediate processing of the access request selected, said determination step comprising, for a time unit not corresponding to the beginning of a time slot, when the critical program (A) to which the next time slot is allocated has not issued the selected request, authorising immediate processing of the selected request (B 0 , c 0 , c 1 ) if the processing slack of the critical program to which the next time slot is allocated is greater than a threshold.

2. The method according to claim 1 , wherein the determination step comprises, for a time unit not corresponding to the beginning of a time slot, when the critical program to which the next time slot is allocated (B) has not issued the selected request (A 0 ) and when the processing slack of the critical program to which the next time slot is allocated is less than the threshold, putting the request selected in a wait state.

3. The method according to claim 1 , wherein the threshold corresponds to the time difference between the time unit at which the determination step is performed and the time unit corresponding to the beginning of the next time slot.

4. The method according to claim 1 , wherein said determination step comprises for a time unit not corresponding to the beginning of a time slot, when the critical program (A) to which the next time slot is allocated has issued the selected request, authorising immediate processing of the request (A 1 ) selected.

5. The method according to claim 1 , wherein said determination step comprises, for a time unit corresponding to the beginning of a time slot, authorising immediate processing of the request (A 0 ) selected.

6. The method according to claim 1 , wherein the selection step comprises, in the presence of a waiting access request (B 1 ) of a critical program and a waiting access request (c 0 ) of a non-critical program, selecting the access request of the non-critical program (c 0 ) if the processing deadline of the access request (B 1 ) of the critical program is subsequent to the end of the next time slot.

7. The method according to claim 1 , wherein the processing slack of a critical program is updated at each termination of processing of an access request of the critical program to correspond to the number of time units separating the termination of processing of the access request and the processing deadline of the access request.

8. The method according to claim 1 , further comprising pre-empting, for the benefit of a critical program, a first program that issued an access request to the shared resource awaiting processing, said pre-emption comprising calculating a processing deadline of said request corresponding to the end of a time slot allocated to the critical program.

9. A time-division multiplexing circuit (CMT) for concurrent access to a shared resource required by computer programs, characterised in that it is configured to implement the method according to claim 1 .

10. The method according to claim 7 , wherein the processing deadline of an access request of a critical program corresponds to the end of a time slot allocated to the critical program that is the first to begin after a date corresponding to an issue date of the access request delayed by adding the processing slack of the critical program.

Assignees

• Commissariat Energie Atomique
• Inst Mines Telecom

Inventors

• Hebbache Farouk
• Jan Mathieu
• Brandner Florian
• Pautet Laurent

Classifications

• G06F9/5005

  to service a request · CPC title

• G06F9/526 Primary

  Mutual exclusion algorithms · CPC title

• G06F9/52 Primary

  Program synchronisation; Mutual exclusion, e.g. by means of semaphores · CPC title