Device for shared management of a resource among several users
The device comprises a memory ( 3 ) for storing several user share parameters and several amounts capable of advancing. A decision means ( 6 ) allocates a chosen service slice of the resource to a user selected as possessing the least advanced amount. It subsequently advances his amount according to a chosen increment. A memory link means ( 5 ) defines user queues of “FIFO” type, such that the user having the least advanced amount in a queue appears at the head of this queue. According to the invention, the memory ( 3 ) stores a limited number of values of increments. The memory link means ( 5 ) associates one of these values of increments with each user and allocates an increment value to each queue.
1. A device for shared management of a resource between several users, comprising:
a memory for storing virtual deadlines (E i ) and share parameters (D i ) associated with respective user-identifiers each (u i ), of the user-identifiers (u i ) representing one of the users, the memory further storing values of increments (P(c));
a plurality of classes, each class being associated with a respective one of the values of increments (P(c)) stored in the memory;
a plurality of first-in-first-out (FIFO) queues for storing the user-identifiers (u i ) of the users, each FIFO being assigned to one of the plurality of classes and being associated with one of the values of increments (P(c)) of one of the plurality of classes; and
a processing unit coupled to the memory and the FIFO queues, wherein the processing unit is configured to:
select a user-identifier (u s ) of one of the FIFO queues, the selected user-identifier (u s ) being at a head of the one of the FIFO queues and having the least advanced virtual deadline (E s ) among the stored virtual deadlines;
allocate to the user represented by the selected user-identifier (u s ) a service slice (Q s ) of the resource, the service slice (Q s ) being derived from the values of the share parameters (D s ) associated with the selected user-identifier (u s ) and of the increment (P(c)) of the FIFO in which the selected-identifier (u s ) is stored; and
increase the virtual deadline (E s ) associated with the selected user-identifier (u s ) according to a value of increment (dE s ), wherein the service slice (Q s ) allocated to the user represented by the selected user-identifier (u s ) results from a formula Q s =P(c)×D s .
2. The device according to claim 1 , wherein the processing unit is further configured to:
maintain a virtual point in time (V) managed by the device;
increase the virtual point in time (V) by an increment value (pV) for advancing the virtual point in time (V); and
allow allocation of the service slice (Q s ) to the user represented by the selected user-identifier (u s ) as long as the virtual deadline (E s ) associated to the selected user-identifier (u s ) is less advanced than the virtual point in time (V).
3. The device according to claim 2 , wherein the virtual point in time (V) is increased by the increment value (pV) for each allocation to the user represented by the selected user-identifier (u s ) of the service slice (Q s ) of the resource, the increment value (pV) being a quotient of the increment (P(c)) of the FIFO queue in which the selected-identifier (u s ) is stored and a sum of the share parameters (D i ).
4. The device according to claim 1 , wherein the memory comprises:
a FIFO queues area storing, for each of the FIFO queues, one of the values of the increments (P(c)) and the user-identifier (u s ) of the user at the head of the FIFO queue; and
a users area storing, for each user, the user-identifiers (u i ), the share parameters (D i ), and an end of queue item (nd(u)).
5. The device according to claim 4 , wherein FIFO queues are cyclic queues defining circular lists, and wherein each of the FIFO queues associates a single virtual deadline (F(c)) to the user-identifiers (u i ) stored in the FIFO queue, said single virtual deadline (F(c)) being stored in the FIFO queues area.
6. The device according to claim 5 , wherein the processing unit is further configured to:
allocate to the user represented by the selected user-identifier (u s ) the service slice (Q s ) of the resource, the selected user-identifier (u s ) being in the list having the least advanced virtual deadline (F(c)); and
increase the virtual deadline (F(c)) of said list after allocating a service slice (Q i ) to a user at the end of said list.
7. The device according to claim 1 , wherein users requesting a service slice of the resource are distinguished from users not requesting a service slice of the resource.
8. The device according to claim 7 , wherein user-identifiers of newly requesting users and user-identifiers of formerly requesting users are stored in distinct FIFO queues.
9. The device according to claim 8 , wherein a virtual deadline (F(u)) is assigned to the user-identifiers (u i ) of a newly requesting user, the virtual deadline (F(u)) being dependent on a virtual point in time (V) managed by the device.
10. The device according to one of the claims 7 to 9 , further configured to eliminate non-requesting users appearing at the head of one of the FIFO queues.
11. The device according to claim 10 , wherein a non-requesting user is eliminated when said non-requesting user is allowed to use a resource and possesses the least advanced virtual deadline (F(u)) among the stored virtual deadlines.