우선 순위에 따라 스레드를 예약하는 방법과 두 스레드가 동일한 우선 순위를 갖는 FCFS (First-Come-First Serve)를 찾고 있습니다. 큐의 힙이나 그런 것을 사용하려고 생각했습니다. 문제는, 비록 자신의 우선 순위 대기열을 구현하더라도, 우선 순위를 변경하는 능력은이 대기열에 대한 삽입 순서를 망칠 수 있다는 것입니다.우선 순위 대기열 (구성 요소를 계속 유지하는 기능)
이 문제를 해결하기 위해 각 스레드의 삽입 시간을 절약하고 삽입 시간 (우선 순위 매개 변수의 보조 매개 변수로 사용)에 따라 우선 순위 큐를 정렬 할 수 있지만 데이터 조합 삽입 시간의 사용없이 문제를 해결할 수있는 구조.
복잡성은 보통 O(N)의 복잡성을 가진 순진한 해결책이 있습니다 (예 : 일반 대기열이 있고 스레드를 팝해야 할 때마다 대기열을 반복합니다).
문제가 올바르게 발생하지 않았지만 우선 순위별로 별도의 목록을 만들 수 있습니다.
각 스레드는 우선 순위에 따라 해당 목록에 추가됩니다. 그리고 항상 목록의 끝에 추가하고 머리에서 제거하면 FCFS 동작을 갖게됩니다.
우선 순위 큐를 생성하여 우선 순위가 가장 낮은 다음 스레드 (O (1))를 삽입하여 다음 스레드를 가져오고 O (logN)을 삽입 할 수도 있습니다. 비교를 위해 우선 순위와 삽입 시간의 조합을 사용할 수 있습니다 각 노드.
작은 우선 순위 집합이있는 경우에만 작동합니다. 그럴 가능성이 가장 높지만 그럴 필요는 없습니다. – svick
이것이 바로 우선 순위 큐 (우선 순위별로 인덱싱 된 FIFO 큐 배열)의 처리 방법입니다. 나는 우선 순위의 작은 세트 이상의 것을 요구하지 않았다. 실제 스레드의 우선 순위 대기열을 보지 못했습니다. 다중 스레드 OS 커널 내부에서 작업을 처리했습니다. –
감사합니다. 사실 우선 순위가 낮습니다. 당신의 솔루션을 이해했다면, 스레드의 우선 순위를 변경하면 새로운 우선 순위의 목록에 추가됩니다. 이것은 스레드의 삽입 순서를 저장하려는 좋은 beacause가 아니며 우선 순위의 변경은 삽입 시간을 재설정하지 않습니다. – Lior
만약 OS 커널이라면, 나는 각 스레드의 삽입 시간을 절약하려고 노력하는 것 근처에 가지 않을 것입니다 - 충분한 이득을 얻기에는 너무 번거 롭습니다. 누군가가 스레드 우선 순위를 변경하는 드문 경우에는 하나의 대기열에서 스레드를 제거하고 다른 스레드로 이동 시키십시오. 우선 순위가 증가한 경우 머리에 놓고 줄이면 꼬리에 놓은 다음 디스패치를 실행하여 최고 수의 스레드에서 [프로세서 수] 우선 순위 큐 및 아래쪽으로 작업하고 일반적인 방식으로 스레드를 프로세서에 할당하는 방법을 결정하십시오. –
정말 혼란 스러워요. (대기열에 추가 된 스레드는 0 시간을 보장받습니다. 이제 막 삽입되었으므로 대기열의 뒤쪽으로 가야합니다. 이전 대기열에서 삽입 시간을 사용할 수는 있지만 스레드가 이전의 이전 대기열에서 최근에 이동되었을 수 있습니다 ...이 요구 사항을 얻지 못하고 해결할 내용을 상상할 수 없습니다. 그것에 대해 좀 더 생각해야만합니다 ... –
삽입 시간을 절약함으로써 실제로 시간을 절약 할 수는 없지만 카운터를 가지고 실행 및 삽입 준비가되었을 때 각 스레드에 "타임 스탬프"제공 대기열에 넣으므로 스레드는 시간 소인별로 정렬 할 수 있습니다. 너무 많은 비용이 드나요? – Lior