From 0055d2cc17b8b884c97d8288705c6a52379931b7 Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=B4me=20Benoit?= Date: Wed, 20 Aug 2025 16:44:44 +0200 Subject: [PATCH] fix: avoid starvation with task priority MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Signed-off-by: Jérôme Benoit --- src/queues/abstract-fixed-queue.ts | 5 +- src/queues/fixed-priority-queue.ts | 21 +++++- src/queues/fixed-queue.ts | 6 +- src/queues/queue-types.ts | 1 + tests/queues/fixed-priority-queue.test.mjs | 74 +++++++++++--------- tests/queues/fixed-queue.test.mjs | 80 +++++++++++++--------- 6 files changed, 115 insertions(+), 72 deletions(-) diff --git a/src/queues/abstract-fixed-queue.ts b/src/queues/abstract-fixed-queue.ts index 5d64719b3..7563e2e97 100644 --- a/src/queues/abstract-fixed-queue.ts +++ b/src/queues/abstract-fixed-queue.ts @@ -48,6 +48,7 @@ export abstract class AbstractFixedQueue implements IFixedQueue { /** @inheritdoc */ public delete (data: T): boolean { + if (this.empty()) return false let currentPhysicalIndex = this.start let logicalIndex = -1 for (let i = 0; i < this.size; i++) { @@ -162,8 +163,8 @@ export abstract class AbstractFixedQueue implements IFixedQueue { `Invalid fixed queue size: '${size.toString()}' is not an integer` ) } - if (size < 0) { - throw new RangeError(`Invalid fixed queue size: ${size.toString()} < 0`) + if (size <= 0) { + throw new RangeError(`Invalid fixed queue size: ${size.toString()} <= 0`) } } } diff --git a/src/queues/fixed-priority-queue.ts b/src/queues/fixed-priority-queue.ts index c5fc17aee..509b1ad43 100644 --- a/src/queues/fixed-priority-queue.ts +++ b/src/queues/fixed-priority-queue.ts @@ -10,17 +10,34 @@ import { AbstractFixedQueue } from './abstract-fixed-queue.js' export class FixedPriorityQueue extends AbstractFixedQueue implements IFixedQueue { + private readonly agingFactor: number + + /** + * Constructs a FixedPriorityQueue. + * @param size - Fixed queue size. @defaultValue defaultQueueSize + * @param agingFactor - Aging factor to apply to items in priority points per millisecond. A higher value makes items age faster. + * @returns IFixedQueue. + */ + public constructor (size?: number, agingFactor = 0.001) { + super(size) + this.agingFactor = agingFactor + } + /** @inheritdoc */ public enqueue (data: T, priority?: number): number { if (this.full()) { throw new Error('Fixed priority queue is full') } priority = priority ?? 0 + const now = performance.now() let insertionPhysicalIndex = -1 let currentPhysicalIndex = this.start for (let i = 0; i < this.size; i++) { // eslint-disable-next-line @typescript-eslint/no-non-null-assertion - if (this.nodeArray[currentPhysicalIndex]!.priority > priority) { + const node = this.nodeArray[currentPhysicalIndex]! + const nodeEffectivePriority = + node.priority - (now - node.timestamp) * this.agingFactor + if (nodeEffectivePriority > priority) { insertionPhysicalIndex = currentPhysicalIndex break } @@ -45,7 +62,7 @@ export class FixedPriorityQueue shiftPhysicalIndex = previousPhysicalIndex } } - this.nodeArray[insertionPhysicalIndex] = { data, priority } + this.nodeArray[insertionPhysicalIndex] = { data, priority, timestamp: now } return ++this.size } } diff --git a/src/queues/fixed-queue.ts b/src/queues/fixed-queue.ts index 736c40fb1..e18c9d33f 100644 --- a/src/queues/fixed-queue.ts +++ b/src/queues/fixed-queue.ts @@ -19,7 +19,11 @@ export class FixedQueue if (index >= this.capacity) { index -= this.capacity } - this.nodeArray[index] = { data, priority: priority ?? 0 } + this.nodeArray[index] = { + data, + priority: priority ?? 0, + timestamp: performance.now(), + } return ++this.size } } diff --git a/src/queues/queue-types.ts b/src/queues/queue-types.ts index c5710d422..0d3296a2a 100644 --- a/src/queues/queue-types.ts +++ b/src/queues/queue-types.ts @@ -12,6 +12,7 @@ export const defaultQueueSize = 2048 export interface FixedQueueNode { data: T priority: number + timestamp: number } /** diff --git a/tests/queues/fixed-priority-queue.test.mjs b/tests/queues/fixed-priority-queue.test.mjs index 42d2ec30e..2bb3306b4 100644 --- a/tests/queues/fixed-priority-queue.test.mjs +++ b/tests/queues/fixed-priority-queue.test.mjs @@ -9,7 +9,7 @@ describe('Fixed priority queue test suite', () => { new TypeError("Invalid fixed queue size: '' is not an integer") ) expect(() => new FixedPriorityQueue(-1)).toThrow( - new RangeError('Invalid fixed queue size: -1 < 0') + new RangeError('Invalid fixed queue size: -1 <= 0') ) const fixedPriorityQueue = new FixedPriorityQueue() expect(fixedPriorityQueue.start).toBe(0) @@ -34,8 +34,8 @@ describe('Fixed priority queue test suite', () => { expect(fixedPriorityQueue.size).toBe(2) expect(rtSize).toBe(fixedPriorityQueue.size) expect(fixedPriorityQueue.nodeArray).toMatchObject([ - { data: 1, priority: 0 }, - { data: 2, priority: 0 }, + { data: 1, priority: 0, timestamp: expect.any(Number) }, + { data: 2, priority: 0, timestamp: expect.any(Number) }, ]) expect(fixedPriorityQueue.capacity).toBe(queueSize) rtSize = fixedPriorityQueue.enqueue(3) @@ -43,9 +43,9 @@ describe('Fixed priority queue test suite', () => { expect(fixedPriorityQueue.size).toBe(3) expect(rtSize).toBe(fixedPriorityQueue.size) expect(fixedPriorityQueue.nodeArray).toMatchObject([ - { data: 1, priority: 0 }, - { data: 2, priority: 0 }, - { data: 3, priority: 0 }, + { data: 1, priority: 0, timestamp: expect.any(Number) }, + { data: 2, priority: 0, timestamp: expect.any(Number) }, + { data: 3, priority: 0, timestamp: expect.any(Number) }, ]) expect(fixedPriorityQueue.capacity).toBe(queueSize) rtSize = fixedPriorityQueue.enqueue(3, -1) @@ -53,10 +53,10 @@ describe('Fixed priority queue test suite', () => { expect(fixedPriorityQueue.size).toBe(4) expect(rtSize).toBe(fixedPriorityQueue.size) expect(fixedPriorityQueue.nodeArray).toMatchObject([ - { data: 3, priority: -1 }, - { data: 1, priority: 0 }, - { data: 2, priority: 0 }, - { data: 3, priority: 0 }, + { data: 3, priority: -1, timestamp: expect.any(Number) }, + { data: 1, priority: 0, timestamp: expect.any(Number) }, + { data: 2, priority: 0, timestamp: expect.any(Number) }, + { data: 3, priority: 0, timestamp: expect.any(Number) }, ]) expect(fixedPriorityQueue.capacity).toBe(queueSize) rtSize = fixedPriorityQueue.enqueue(1, 1) @@ -64,11 +64,11 @@ describe('Fixed priority queue test suite', () => { expect(fixedPriorityQueue.size).toBe(5) expect(rtSize).toBe(fixedPriorityQueue.size) expect(fixedPriorityQueue.nodeArray).toMatchObject([ - { data: 3, priority: -1 }, - { data: 1, priority: 0 }, - { data: 2, priority: 0 }, - { data: 3, priority: 0 }, - { data: 1, priority: 1 }, + { data: 3, priority: -1, timestamp: expect.any(Number) }, + { data: 1, priority: 0, timestamp: expect.any(Number) }, + { data: 2, priority: 0, timestamp: expect.any(Number) }, + { data: 3, priority: 0, timestamp: expect.any(Number) }, + { data: 1, priority: 1, timestamp: expect.any(Number) }, ]) expect(fixedPriorityQueue.capacity).toBe(queueSize) expect(() => fixedPriorityQueue.enqueue(4)).toThrow( @@ -102,8 +102,8 @@ describe('Fixed priority queue test suite', () => { expect(rtItem).toBe(2) expect(fixedPriorityQueue.nodeArray).toMatchObject([ undefined, - { data: 1, priority: 0 }, - { data: 3, priority: 0 }, + { data: 1, priority: 0, timestamp: expect.any(Number) }, + { data: 3, priority: 0, timestamp: expect.any(Number) }, ]) expect(fixedPriorityQueue.capacity).toBe(queueSize) rtItem = fixedPriorityQueue.dequeue() @@ -113,7 +113,7 @@ describe('Fixed priority queue test suite', () => { expect(fixedPriorityQueue.nodeArray).toMatchObject([ undefined, undefined, - { data: 3, priority: 0 }, + { data: 3, priority: 0, timestamp: expect.any(Number) }, ]) expect(fixedPriorityQueue.capacity).toBe(queueSize) rtItem = fixedPriorityQueue.dequeue() @@ -146,22 +146,22 @@ describe('Fixed priority queue test suite', () => { expect(fixedPriorityQueue.start).toBe(0) expect(fixedPriorityQueue.size).toBe(3) expect(fixedPriorityQueue.nodeArray).toMatchObject([ - { data: 2, priority: -1 }, - { data: 1, priority: 0 }, - { data: 3, priority: 0 }, + { data: 2, priority: -1, timestamp: expect.any(Number) }, + { data: 1, priority: 0, timestamp: expect.any(Number) }, + { data: 3, priority: 0, timestamp: expect.any(Number) }, ]) expect(fixedPriorityQueue.delete(2)).toBe(true) expect(fixedPriorityQueue.start).toBe(0) expect(fixedPriorityQueue.size).toBe(2) expect(fixedPriorityQueue.nodeArray).toMatchObject([ - { data: 1, priority: 0 }, - { data: 3, priority: 0 }, + { data: 1, priority: 0, timestamp: expect.any(Number) }, + { data: 3, priority: 0, timestamp: expect.any(Number) }, ]) expect(fixedPriorityQueue.delete(3)).toBe(true) expect(fixedPriorityQueue.start).toBe(0) expect(fixedPriorityQueue.size).toBe(1) expect(fixedPriorityQueue.nodeArray).toMatchObject([ - { data: 1, priority: 0 }, + { data: 1, priority: 0, timestamp: expect.any(Number) }, ]) expect(fixedPriorityQueue.delete(1)).toBe(true) expect(fixedPriorityQueue.start).toBe(0) @@ -212,16 +212,24 @@ describe('Fixed priority queue test suite', () => { }) it('Verify clear() behavior', () => { - const fixedPriorityQueue = new FixedPriorityQueue(2) - fixedPriorityQueue.start = 1 - fixedPriorityQueue.size = 2 - fixedPriorityQueue.nodeArray = [ - { data: 2, priority: 0 }, - { data: 3, priority: 0 }, - ] + const queueSize = 3 + const fixedPriorityQueue = new FixedPriorityQueue(queueSize) + fixedPriorityQueue.enqueue(1) + fixedPriorityQueue.enqueue(2, -1) + fixedPriorityQueue.enqueue(3) + expect(fixedPriorityQueue.size).toBe(queueSize) + expect(fixedPriorityQueue.nodeArray).toMatchObject([ + { data: 2, priority: -1, timestamp: expect.any(Number) }, + { data: 1, priority: 0, timestamp: expect.any(Number) }, + { data: 3, priority: 0, timestamp: expect.any(Number) }, + ]) fixedPriorityQueue.clear() - expect(fixedPriorityQueue.start).toBe(0) expect(fixedPriorityQueue.size).toBe(0) - expect(fixedPriorityQueue.nodeArray).toStrictEqual([undefined, undefined]) + expect(fixedPriorityQueue.start).toBe(0) + expect(fixedPriorityQueue.nodeArray).toStrictEqual([ + undefined, + undefined, + undefined, + ]) }) }) diff --git a/tests/queues/fixed-queue.test.mjs b/tests/queues/fixed-queue.test.mjs index faf10a16d..579c3ffae 100644 --- a/tests/queues/fixed-queue.test.mjs +++ b/tests/queues/fixed-queue.test.mjs @@ -9,7 +9,7 @@ describe('Fixed queue test suite', () => { new TypeError("Invalid fixed queue size: '' is not an integer") ) expect(() => new FixedQueue(-1)).toThrow( - new RangeError('Invalid fixed queue size: -1 < 0') + new RangeError('Invalid fixed queue size: -1 <= 0') ) const fixedQueue = new FixedQueue() expect(fixedQueue.start).toBe(0) @@ -25,15 +25,17 @@ describe('Fixed queue test suite', () => { expect(fixedQueue.start).toBe(0) expect(fixedQueue.size).toBe(1) expect(rtSize).toBe(fixedQueue.size) - expect(fixedQueue.nodeArray).toMatchObject([{ data: 1, priority: 0 }]) + expect(fixedQueue.nodeArray).toMatchObject([ + { data: 1, priority: 0, timestamp: expect.any(Number) }, + ]) expect(fixedQueue.capacity).toBe(queueSize) rtSize = fixedQueue.enqueue(2) expect(fixedQueue.start).toBe(0) expect(fixedQueue.size).toBe(2) expect(rtSize).toBe(fixedQueue.size) expect(fixedQueue.nodeArray).toMatchObject([ - { data: 1, priority: 0 }, - { data: 2, priority: 0 }, + { data: 1, priority: 0, timestamp: expect.any(Number) }, + { data: 2, priority: 0, timestamp: expect.any(Number) }, ]) expect(fixedQueue.capacity).toBe(queueSize) rtSize = fixedQueue.enqueue(3) @@ -41,9 +43,9 @@ describe('Fixed queue test suite', () => { expect(fixedQueue.size).toBe(3) expect(rtSize).toBe(fixedQueue.size) expect(fixedQueue.nodeArray).toMatchObject([ - { data: 1, priority: 0 }, - { data: 2, priority: 0 }, - { data: 3, priority: 0 }, + { data: 1, priority: 0, timestamp: expect.any(Number) }, + { data: 2, priority: 0, timestamp: expect.any(Number) }, + { data: 3, priority: 0, timestamp: expect.any(Number) }, ]) expect(fixedQueue.capacity).toBe(queueSize) rtSize = fixedQueue.enqueue(3, -1) @@ -51,10 +53,10 @@ describe('Fixed queue test suite', () => { expect(fixedQueue.size).toBe(4) expect(rtSize).toBe(fixedQueue.size) expect(fixedQueue.nodeArray).toMatchObject([ - { data: 1, priority: 0 }, - { data: 2, priority: 0 }, - { data: 3, priority: 0 }, - { data: 3, priority: -1 }, + { data: 1, priority: 0, timestamp: expect.any(Number) }, + { data: 2, priority: 0, timestamp: expect.any(Number) }, + { data: 3, priority: 0, timestamp: expect.any(Number) }, + { data: 3, priority: -1, timestamp: expect.any(Number) }, ]) expect(fixedQueue.capacity).toBe(queueSize) rtSize = fixedQueue.enqueue(1, 1) @@ -62,11 +64,11 @@ describe('Fixed queue test suite', () => { expect(fixedQueue.size).toBe(5) expect(rtSize).toBe(fixedQueue.size) expect(fixedQueue.nodeArray).toMatchObject([ - { data: 1, priority: 0 }, - { data: 2, priority: 0 }, - { data: 3, priority: 0 }, - { data: 3, priority: -1 }, - { data: 1, priority: 1 }, + { data: 1, priority: 0, timestamp: expect.any(Number) }, + { data: 2, priority: 0, timestamp: expect.any(Number) }, + { data: 3, priority: 0, timestamp: expect.any(Number) }, + { data: 3, priority: -1, timestamp: expect.any(Number) }, + { data: 1, priority: 1, timestamp: expect.any(Number) }, ]) expect(fixedQueue.capacity).toBe(queueSize) expect(() => fixedQueue.enqueue(4)).toThrow( @@ -100,8 +102,8 @@ describe('Fixed queue test suite', () => { expect(rtItem).toBe(1) expect(fixedQueue.nodeArray).toMatchObject([ undefined, - { data: 2, priority: -1 }, - { data: 3, priority: 0 }, + { data: 2, priority: -1, timestamp: expect.any(Number) }, + { data: 3, priority: 0, timestamp: expect.any(Number) }, ]) expect(fixedQueue.capacity).toBe(queueSize) rtItem = fixedQueue.dequeue() @@ -111,7 +113,7 @@ describe('Fixed queue test suite', () => { expect(fixedQueue.nodeArray).toMatchObject([ undefined, undefined, - { data: 3, priority: 0 }, + { data: 3, priority: 0, timestamp: expect.any(Number) }, ]) expect(fixedQueue.capacity).toBe(queueSize) rtItem = fixedQueue.dequeue() @@ -144,21 +146,23 @@ describe('Fixed queue test suite', () => { expect(fixedQueue.start).toBe(0) expect(fixedQueue.size).toBe(3) expect(fixedQueue.nodeArray).toMatchObject([ - { data: 1, priority: 0 }, - { data: 2, priority: -1 }, - { data: 3, priority: 0 }, + { data: 1, priority: 0, timestamp: expect.any(Number) }, + { data: 2, priority: -1, timestamp: expect.any(Number) }, + { data: 3, priority: 0, timestamp: expect.any(Number) }, ]) expect(fixedQueue.delete(2)).toBe(true) expect(fixedQueue.start).toBe(0) expect(fixedQueue.size).toBe(2) expect(fixedQueue.nodeArray).toMatchObject([ - { data: 1, priority: 0 }, - { data: 3, priority: 0 }, + { data: 1, priority: 0, timestamp: expect.any(Number) }, + { data: 3, priority: 0, timestamp: expect.any(Number) }, ]) expect(fixedQueue.delete(3)).toBe(true) expect(fixedQueue.start).toBe(0) expect(fixedQueue.size).toBe(1) - expect(fixedQueue.nodeArray).toMatchObject([{ data: 1, priority: 0 }]) + expect(fixedQueue.nodeArray).toMatchObject([ + { data: 1, priority: 0, timestamp: expect.any(Number) }, + ]) expect(fixedQueue.delete(1)).toBe(true) expect(fixedQueue.start).toBe(0) expect(fixedQueue.size).toBe(0) @@ -208,16 +212,24 @@ describe('Fixed queue test suite', () => { }) it('Verify clear() behavior', () => { - const fixedQueue = new FixedQueue(2) - fixedQueue.start = 1 - fixedQueue.size = 2 - fixedQueue.nodeArray = [ - { data: 2, priority: 0 }, - { data: 3, priority: 0 }, - ] + const queueSize = 3 + const fixedQueue = new FixedQueue(queueSize) + fixedQueue.enqueue(1) + fixedQueue.enqueue(2, -1) + fixedQueue.enqueue(3) + expect(fixedQueue.size).toBe(queueSize) + expect(fixedQueue.nodeArray).toMatchObject([ + { data: 1, priority: 0, timestamp: expect.any(Number) }, + { data: 2, priority: -1, timestamp: expect.any(Number) }, + { data: 3, priority: 0, timestamp: expect.any(Number) }, + ]) fixedQueue.clear() - expect(fixedQueue.start).toBe(0) expect(fixedQueue.size).toBe(0) - expect(fixedQueue.nodeArray).toStrictEqual([undefined, undefined]) + expect(fixedQueue.start).toBe(0) + expect(fixedQueue.nodeArray).toStrictEqual([ + undefined, + undefined, + undefined, + ]) }) }) -- 2.43.0