为什么Ready队列中使用链表？
如何使用？
栈和队列在其中是如何发挥作用的？
它如何影响调度程序和 PCB 执行？
从《Abraham Siberschatz 的操作系统概念》一书中引用了这段代码
// Define Process Control Block (PCB)
typedef struct PCB {
int pid; // Process ID
char state[10]; // Process state (e.g., "Ready", "Running", etc.)
struct PCB* next; // Pointer to the next PCB in the ready queue
} PCB;
// Define Ready Queue structure with pointers to first and last PCB
typedef struct ReadyQueue {
PCB* first; // Pointer to the first PCB in the ready queue
PCB* last; // Pointer to the last PCB in the ready queue
} ReadyQueue;
// Function to create a new PCB
PCB* createPCB(int pid, const char* state) {
PCB* newPCB = (PCB*)malloc(sizeof(PCB)); // Allocate memory for the new PCB
newPCB->pid = pid; // Assign process ID
snprintf(newPCB->state, sizeof(newPCB->state), "%s", state); // Assign process state
newPCB->next = NULL; // Set the next pointer to NULL initially
return newPCB; // Return the pointer to the new PCB
}
// Function to initialize a ReadyQueue
ReadyQueue* initializeReadyQueue() {
ReadyQueue* rq = (ReadyQueue*)malloc(sizeof(ReadyQueue)); // Allocate memory for the ready queue
rq->first = NULL; // Set the first PCB pointer to NULL
rq->last = NULL; // Set the last PCB pointer to NULL
return rq;
}
// Function to add a PCB to the ready queue (end of the list)
void enqueue(ReadyQueue* rq, PCB* pcb) {
if (rq->last == NULL) { // If the queue is empty
rq->first = pcb; // Set both first and last to the new PCB
rq->last = pcb;
} else { // If queue is not empty
rq->last->next = pcb; // Link the new PCB to the end of the queue
rq->last = pcb; // Update the last pointer to the new PCB
}
}
// Function to remove a PCB from the ready queue (from the front of the list)
PCB* dequeue(ReadyQueue* rq) {
if (rq->first == NULL) { // If the queue is empty
printf("Ready queue is empty.\n");
return NULL;
}
PCB* temp = rq->first; // Get the first PCB
rq->first = rq->first->next; // Move the first pointer to the next PCB
if (rq->first == NULL) { // If the queue is now empty after dequeue
rq->last = NULL; // Update the last pointer to NULL
}
return temp; // Return the dequeued PCB
}
双线程程序的旧示例，使用链接列表作为具有 Windows 互斥体和信号量的线程之间的消息队列来复制文件。这类似于我在小型计算机和嵌入式设备（磁带驱动器、硬盘驱动器）的全盛时期所工作的多线程操作系统上实现队列的方式。上次我使用类似此示例代码的程序是为了捕获流式原始数据，该数据对于单个硬盘驱动器来说太快了，但可以通过在两个硬盘驱动器之间交替来处理，因此它使用了三个线程和队列，一组用于读取，并在两组之间交替进行写作。这个 Windows 示例和我所使用的操作系统的共同点是对链表队列使用互斥体和信号量。操作系统还包含一个时间参数，以便单个调用可以等待（互斥体和信号量）或时间。
/*----------------------------------------------------------------------*/
/* mtcopy.c multi-thread file copy demo */
/* */
/* Uses linked list fifo's to hold buffered data: LLIST. */
/* Uses mutexes for ownership of link lists. */
/* Uses semaphores for list counts. */
/* */
/* Uses the existing thread for file reads. */
/* Creates a second thread for file writes. */
/* */
/* Jeff Reid 2015MAY22 15:00 */
/*----------------------------------------------------------------------*/
#include <windows.h>
#include <stdio.h>
#include <stddef.h>
#include <malloc.h>
#include <memory.h>
#include <string.h>
#include <conio.h>
#define NBFR 64 /* number of buffers */
#define BFRSZ 0x10000 /* buffer size */
typedef struct _NODE /* node structure */
{
struct _NODE *pNext; /* ptr to next node */
BYTE *pBfr; /* ptr to buffer */
DWORD dwCnt; /* # bytes in buffer */
}NODE;
typedef struct _LIST /* linked List structure */
{
NODE *pFirst; /* ptr to 1st node */
NODE *pLast; /* ptr to last node */
HANDLE hMtxSem[2]; /* mutex and semaphore handles */
}LIST;
#define hMtx hMtxSem[0] /* mutex == ownership */
#define hSem hMtxSem[1] /* semaphore == list count */
/*----------------------------------------------------------------------*/
/* data */
/*----------------------------------------------------------------------*/
static HANDLE htT1; /* thread handles */
static LIST llT0; /* thread 0 list */
static LIST llT1; /* thread 1 list */
static NODE aNode[NBFR]; /* array of nodes */
static DWORD fExitThread; /* flag to indicate thread exit */
static DWORD dwThreadT1; /* thread id's (not used) */
static DWORD dwExitCode; /* exit code */
static HANDLE hSrc; /* file I/O */
static HANDLE hDst;
static PBYTE pMem; /* ptr to allocated memory */
/*----------------------------------------------------------------------*/
/* code */
/*----------------------------------------------------------------------*/
static DWORD WINAPI Thread0(LPVOID);
static DWORD WINAPI Thread1(LPVOID);
static void InitThread0List(void);
static NODE * GetNode(LIST *);
static DWORD PutNode(LIST *, NODE *);
/*----------------------------------------------------------------------*/
/* main */
/*----------------------------------------------------------------------*/
DWORD main(DWORD argc, BYTE **argv)
{
hSrc = INVALID_HANDLE_VALUE; /* init file handles to not open */
hDst = INVALID_HANDLE_VALUE;
if(argc != 3){
printf("usage is mtcopy <src> <dst>\n");
goto exit0;}
pMem = malloc(BFRSZ*NBFR); /* allocate memory */
if(!pMem){
_cputs("can't allocate enough memory\r\n");
goto exit0;}
hSrc = CreateFile(argv[1], /* open src file */
GENERIC_READ, FILE_SHARE_READ, NULL, OPEN_EXISTING, 0, 0);
if(hSrc == INVALID_HANDLE_VALUE){
printf("Can't open %s\n", argv[1]);
goto exit0;}
hDst = CreateFile(argv[2], /* open dst file */
GENERIC_ALL , 0, NULL, CREATE_ALWAYS, FILE_FLAG_BACKUP_SEMANTICS, 0);
if(hDst == INVALID_HANDLE_VALUE){
printf("Can't create %s\n", argv[2]);
goto exit0;}
/* create mutex and semaphore for each list */
if((llT0.hSem = CreateSemaphore(NULL,0,NBFR+1,NULL))==NULL){
_cputs("can't create semaphore\r\n");
goto exit0;}
if((llT0.hMtx = CreateMutex(NULL,FALSE,NULL))==NULL){
_cputs("can't create mutex\r\n");
goto exit0;}
if((llT1.hSem = CreateSemaphore(NULL,0,NBFR+1,NULL))==NULL){
_cputs("can't create semaphore\r\n");
goto exit0;}
if((llT1.hMtx = CreateMutex(NULL,FALSE,NULL))==NULL){
_cputs("can't create mutex\r\n");
goto exit0;}
/* create threads */
htT1 = CreateThread(NULL, 0, Thread1, 0, 0, &dwThreadT1);
if(!htT1){
_cputs("can't create thread\r\n");
goto exit0;}
InitThread0List(); /* init Thread 0 list */
Thread0((LPVOID)NULL); /* start Thread 0 */
exit0:
if(htT1){ /* close thread */
WaitForSingleObject(htT1, INFINITE);
CloseHandle(htT1);}
if(llT1.hSem){ /* close mutex, semaphore */
CloseHandle(llT1.hSem);}
if(llT1.hMtx){
CloseHandle(llT1.hMtx);}
if(llT0.hSem){
CloseHandle(llT0.hSem);}
if(llT0.hMtx){
CloseHandle(llT0.hMtx);}
if(hDst != INVALID_HANDLE_VALUE){ /* close files */
CloseHandle(hDst);}
if(hSrc != INVALID_HANDLE_VALUE){
CloseHandle(hSrc);}
if(pMem){ /* free memory */
free(pMem);}
return(0);
}
/*----------------------------------------------------------------------*/
/* Thread0 read bfr from file 0 */
/*----------------------------------------------------------------------*/
static DWORD WINAPI Thread0(LPVOID lpvoid)
{
NODE *pNode;
while(1){
pNode = GetNode(&llT0); /* get node */
ReadFile(hSrc, pNode->pBfr, BFRSZ, &(pNode->dwCnt), NULL);
PutNode(&llT1, pNode); /* send node to thread 1 */
if(pNode->dwCnt == 0){ /* exit if end of file */
return(0);}}
}
/*----------------------------------------------------------------------*/
/* Thread1 write bfr to file 1 */
/*----------------------------------------------------------------------*/
static DWORD WINAPI Thread1(LPVOID lpvoid)
{
NODE *pNode;
DWORD dwWrite;
DWORD dwCnt = 1;
while(dwCnt){
pNode = GetNode(&llT1); /* get node */
dwCnt = pNode->dwCnt; /* localize count */
if(dwCnt) /* write data if count != 0 */
WriteFile(hDst, pNode->pBfr, dwCnt, &dwWrite, NULL);
PutNode(&llT0, pNode);} /* return node to thread 0 */
return(0);
}
/*----------------------------------------------------------------------*/
/* InitThread0List init thread 0 list */
/*----------------------------------------------------------------------*/
static void InitThread0List(void)
{
BYTE * pBfr;
DWORD i;
pBfr = pMem;
for(i = 0; i < NBFR; i++){
aNode[i].pBfr = pBfr;
PutNode(&llT0, &aNode[i]);
pBfr += BFRSZ;}
}
/*----------------------------------------------------------------------*/
/* GetNode get first node from list */
/* */
/* WaitForMultipleObjects eliminates any thread priority issues */
/*----------------------------------------------------------------------*/
static NODE * GetNode(LIST * pList)
{
NODE * pNode; /* used for return value */
/* wait for ownership, node, and decrement semaphore count */
WaitForMultipleObjects(2, pList->hMtxSem, TRUE ,INFINITE);
pNode = pList->pFirst; /* set return value */
pList->pFirst = pNode->pNext; /* advance first ptr */
if(pList->pFirst == NULL) /* if emptied list */
pList->pLast = NULL; /* reset last ptr as well */
ReleaseMutex(pList->hMtx); /* release ownership of list */
return(pNode);
}
/*----------------------------------------------------------------------*/
/* PutNode append node to end of list */
/* returns 0 if list was previously empty */
/* */
/* ReleaseSemaphore increments list count and enables pending thread */
/*----------------------------------------------------------------------*/
static DWORD PutNode(LIST * pList, NODE * pNode)
{
DWORD dwPrevCount;
/* wait for ownership of list */
WaitForSingleObject(pList->hMtx, INFINITE);
if(pList->pFirst == NULL) /* if empty list */
pList->pFirst = pNode; /* set first ptr */
else /* else set tail node ptr */
pList->pLast->pNext = pNode;
pList->pLast = pNode; /* set last ptr */
pNode->pNext = NULL; /* reset next ptr */
/* increment semaphore list count */
ReleaseSemaphore(pList->hSem,1,&dwPrevCount);
ReleaseMutex(pList->hMtx); /* release ownership of list */
return(dwPrevCount);
}