Why a linked list is used in a Ready queue?
How it is used?
How the stack and queues play a role in it?
How does it affects the scheduler and PCB execution?
Got this chunk of code referenced from the book Operating System Concepts by 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 }
Why a linked list is used in a Ready queue?
It is a simple way to implement messaging between threads and processes and common to many operating systems. A linked list node can be dequeued from one queue and enqueued to another queue, allowing for the node to "travel" through a sequence of queues and corresponding threads or processes.
How It is used?
Typically a thread uses a function to dequeue a node from a queue, but if the queue is empty, that thread is put into a wait state until the queue becomes non-empty.
The example code below uses two threads to copy a file, such as doing a backup from one hard drive to another, one thread to read, the other thread to write. A pool of buffers is allocated, and a free pool of messages where each message includes a pointer to a buffer is created. There is also a write pool that is created and is initially empty. The read thread waits | gets a message from the free pool, reads the data into the message buffer, then queues the message to the write pool. The write thread waits | gets a message from the write pool, writes the data from the message buffer, then queues the message back to the free pool. When the end of file is reached, the byte count will be zero which will complete the copy.
How the stack and queues play a role in it?
Queues are normally used because they are handled in order, first in first out. Stacks are normally not used because they are last in first out.
How does It affects the scheduler and PCB execution?
The scheduler needs code to put threads or processes in a wait state while waiting for a message on a empty queue, and then to be able to wake up the thread once one or more messages are added to a queue. Generally this requires a mutex for queue ownership and semaphore for queue count, and a single call that can wait for both.
Old example of a two thread program to copy a file using linked lists as queues for messages between threads with Windows mutexes and semaphores. This is similar to how queues were implemented on multi-threaded operating systems I worked on in the heydays of mini-computers and embedded devices (tape drives, hard drives). The last time I used a program like this example code was to capture streaming raw data that was too fast for a single hard drive, but could be handled by alternating between two hard drives, so it used three threads and queues, one set for reading, and alternating between two sets for writing. What is common to this Windows example and the operating systems I worked on was being able to wait for multiple things with a single call to the operating system, such as wait for message (mutex + semaphore) or event (such as system shutdown) or some amount of elapsed time in a single call to the operating system. In the example code, this is done with WaitForMultipleObjects(). There is a bit of code to set this up, but the threads themselves are fairly simple.
/*----------------------------------------------------------------------*/
/* 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);
}