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.
How It is used?
For example a tape drive when reading: A free pool of messages is created and the tape is commanded to start reading. There is a thread to read raw data, a thread to perform error correction, a thread to receive corrected data, a thread to wait for a read command from the host, a thread that waits for both a pending read from the host and corrected data ready which sends the data to the host, and a thread that waits for data sent back to have completed which returns the message back to the free pool
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 rarely 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);
}