自学教程：C++ EnQ函数代码示例

void InitKernelData() {   	int i;	MyBzero((char *)&ready_q, sizeof(q_t));	MyBzero((char *)&free_q, sizeof(q_t));		//phase 3	MyBzero((char *)&sem_q, sizeof(q_t)); //clear the available semaphore queue    	for(i = 0; i < Q_LEN; i++)	// loop number i from 0 to 19	{      		EnQ(i, &free_q);	//call EnQ() to enqueue i to free_q		//phase 3		EnQ(i, &sem_q);	//fill it with available semaphore ID's (from 0 to Q_SIZE-1).      		MyBzero((char *) &pcb[i], sizeof(pcb_t));	}   	running_pid = 0;//set running_pid to 0;  none initially, need to chose by Scheduler()	//Phase 2	OS_clock = 0;		//reset OS_clock to 0		MyBzero((char *)&sleep_q, sizeof(q_t));	//reset sleep_q	//phase 4	MyBzero((char *)&msg_q, sizeof(msg_q_t)); 		}

int bfs(int source, int dest){    int u, v;    int d[300+10] , visited[300+10];    for(int i=0;i<305;i++) {d[i] = 10000; visited[i] = 0;}    d[source] = 0;    parent[source] = -1;    visited[source] = 1;    EnQ(source);    while(Q_Empty()==0){        u = DeQ();        for(v=1; v<=Total_Router; v++){            if(routing_table[u][v]==1&&visited[v]==0){                d[v] = d[u] + 1;                visited[v] = 1;                parent[v] = u;                EnQ(v);            }        }    }    return d[dest];}

void TimerISR(){	outportb(0x20, 0x60); // dismiss timer interrupt	// deal with sleep items	sys_tick++;	while(!EmptyQ(&sleep_q) && (pcbs[sleep_q.q[sleep_q.head]].wake_tick <= sys_tick)) {		int tmpPID = DeQ(&sleep_q);		pcbs[tmpPID].state=READY;		EnQ(tmpPID, &ready_q);	}	if(cur_pid == 0) return; // if Idle process, no need to do this on it	pcbs[cur_pid].tick_count++;	if(pcbs[cur_pid].tick_count == TIME_SLICE) // running up time, preempt it?	{		pcbs[cur_pid].tick_count = 0; // reset (roll over) usage time		pcbs[cur_pid].total_tick_count += TIME_SLICE; // sum to total		pcbs[cur_pid].state = READY;  // change its state		EnQ(cur_pid, &ready_q);       // move it to ready_q		cur_pid = -1;                 // no longer running	}}

void InitData(){	int i;	// queue initializations, both queues are empty first	InitQ(&avail_q);	InitQ(&ready_q);	InitQ(&avail_sem_q);	for(i=2; i < NUM_PROC ; i++) // init pcbs[], skip 0 since it's Idle Proc	{		pcbs[i].state = AVAIL;		EnQ(i, &avail_q);	}	for(i=NUM_SEM-1; i >= 0; i--) // init pcbs[], skip 0 since it's Idle Proc	{		EnQ(i, &avail_sem_q);	}	cur_pid = -1;  // no process is running initially	sys_tick = 0; // Set sys_tick to 0	InitQ(&sleep_q); // reset sleep_q to empty}

void TimerISR(){   int sleep_pid;// dismiss IRQ 0 at PIC control reg (0x20), if IRQ 7, send 0x67)   outportb(0x20, 0x60);   sys_tick++;      while( !EmptyPQ(&sleep_q) && ( peek(&sleep_q) <= sys_tick )){      sleep_pid = DePQ(&sleep_q);      EnQ(sleep_pid, &ready_q);      pcbs[sleep_pid].state = READY;   }   if(cur_pid == 0) return; // if Idle process, no need to do this on it   pcbs[cur_pid].tick_count++;   if(pcbs[cur_pid].tick_count == TIME_SLICE) // running up time, preempt it?   {      pcbs[cur_pid].tick_count = 0; // reset (roll over) usage time      pcbs[cur_pid].total_tick_count += TIME_SLICE; // sum to total      pcbs[cur_pid].state = READY;  // change its state      EnQ(cur_pid, &ready_q);       // move it to ready_q      cur_pid = -1;                 // no longer running   }}

void InitData(){   int i;   char * nextFramePtr =			(char *) ( (int) (_topHeapMemory + PAGE_SIZE)	//bump up                           & ( ~(PAGE_SIZE-1) ) )  ;	//mask down   cur_page = 0;   InitQ(&avail_q); // set queues initially empty   InitQ(&ready_q);   InitQ(&sleep_q);   InitQ(&avail_sem_q);   for(i=2; i<NUM_PROC; i++) // skip 0 (IdleProc) and 1 (Init)   {      pcbs[i].state = AVAIL;      EnQ(i, &avail_q);   }   for(i=NUM_SEM-1; i>=0; i--) EnQ(i, &avail_sem_q); // avail sem ID's 19-0      for(i = 0; i < NUM_PAGE; i++){      pages[i].available = 1;      pages[i].addr = nextFramePtr;      pages[i].pid = -1;      nextFramePtr += PAGE_SIZE;   }}

void MsgSndISR() {	   int mid, pid;   msg_t *src, *dest;   mid = pcbs[cur_pid].tf_p->eax;   src = (msg_t *)pcbs[cur_pid].tf_p->ebx;   src->sender = cur_pid;      // authenticate sender   src->time_stamp = sys_tick; // authenticate time_stamp   if(EmptyQ(&mboxes[mid].wait_q))   {      MsgEnQ( src, &( mboxes[mid].msg_q ) );   }   else   {	      pid = DeQ(&mboxes[mid].wait_q);      pcbs[pid].state = READY;      EnQ(pid, &ready_q);      dest = (msg_t *)pcbs[pid].tf_p->eax; // eax since MsgRcv changed      *dest = *src;   }}

////////////phase 4void MsgSndISR(int msg_addr){	int msg_q_id;	int freed_pid;	msg_t *incoming_msg_ptr, *dst_msg_ptr; 		incoming_msg_ptr = (msg_t *) msg_addr; 	msg_q_id = incoming_msg_ptr->recipient;	incoming_msg_ptr->OS_clock = OS_clock;	incoming_msg_ptr->sender = running_pid;	if(msg_q[msg_q_id].wait_q.len == 0)	{		MsgEnQ(incoming_msg_ptr, &msg_q[msg_q_id]);	}		else	{		freed_pid = DeQ(&(msg_q[msg_q_id].wait_q));		EnQ(freed_pid, &ready_q);		pcb[freed_pid].state = READY;		dst_msg_ptr = (msg_t *) pcb[freed_pid].TF_ptr->eax;		*dst_msg_ptr = *incoming_msg_ptr;	}			}

void TimerISR() {   	//just return if running PID is -1 (not any valid PID)		if(running_pid == -1){		cons_printf("PANIC MESSAGE: RUNNING PID = -1/n");		return;		}else{		//in PCB, upcount both runtime and total_runtime of running process		pcb[running_pid].runtime = pcb[running_pid].runtime+1;		pcb[running_pid].total_runtime = pcb[running_pid].total_runtime+1;			if(pcb[running_pid].runtime== TIME_LIMIT){ // If runtime has reached TIME_LIMIT			// Reset runtime			// Change the state to READY			// queue to ready_q			// Set pid to -1			pcb[running_pid].runtime = 0;			pcb[running_pid].state = READY;			EnQ(running_pid, &ready_q);			running_pid = -1;			Scheduler();		}		}}

void StartProcISR(int new_pid) {   	//clear the PCB of the new pid   	MyBzero((char *) &pcb[new_pid], sizeof(pcb_t));    	//set its state to READY	pcb[new_pid].state = READY;    	//if new pid is not 0 (IdleProc),      	//then, enqueue this new pid into the ready queue*/      	if(new_pid != 0){		EnQ(new_pid, &ready_q);	} 		//Clears the stack	MyBzero((char *) &proc_stack[new_pid], PROC_STACK_SIZE);	//Set TF_ptr of PCB close to end (top) of stack, then fill out	pcb[new_pid].TF_ptr = (TF_t *) &proc_stack[new_pid][PROC_STACK_SIZE - sizeof(TF_t)];	pcb[new_pid].TF_ptr->eflags = EF_DEFAULT_VALUE|EF_INTR; // set INTR flag	pcb[new_pid].TF_ptr->cs = get_cs();			// standard fair	pcb[new_pid].TF_ptr->ds = get_ds();			// standard fair	pcb[new_pid].TF_ptr->es = get_es();			// standard fair	pcb[new_pid].TF_ptr->fs = get_fs();			// standard fair	pcb[new_pid].TF_ptr->gs = get_gs();			// standard fair	if(new_pid == 0){		pcb[new_pid].TF_ptr->eip = (unsigned int) IdleProc; // if pid is 0, points to IdleProc 	}else{		pcb[new_pid].TF_ptr->eip = (unsigned int) UserProc; // or UserProc	}}

void StartProcISR(int new_pid, int func_addr) {			MyBzero((char *) &pcb[new_pid], sizeof(pcb_t));	//clear the PCB of the new pid	//phase 5	MyBzero((char *) &msg_q[new_pid], sizeof(msg_q_t));	pcb[new_pid].state = READY;		//set its state to READY	if(new_pid != 0)			//if new pid is not 0 (IdleProc),	{	      EnQ(new_pid, &ready_q);	//then, enqueue this new pid into the ready queue	}	//build initial trapframe in proc stack	MyBzero((char *)&proc_stack[new_pid], PROC_STACK_SIZE);	//call MyBzero() to clear the stack 1st	pcb[new_pid].TF_ptr = (TF_t *) &proc_stack[new_pid][PROC_STACK_SIZE - sizeof(TF_t)];	//set TF_ptr of PCB to close to end (top) of stack	pcb[new_pid].TF_ptr->eflags = EF_DEFAULT_VALUE|EF_INTR;	//set INTR flag   	pcb[new_pid].TF_ptr->cs = get_cs();				//standard fair	pcb[new_pid].TF_ptr->ds = get_ds();				//standard fair	pcb[new_pid].TF_ptr->es = get_es();				//standard fair	pcb[new_pid].TF_ptr->fs = get_fs();				//standard fair	pcb[new_pid].TF_ptr->gs = get_gs();				//standard fair	pcb[new_pid].TF_ptr->eip = func_addr;}

void MsgSndISR(){	int mid,pid,head;	msg_t *source, *destination;	mid = pcbs[cur_pid].tf_p ->eax;	source = (msg_t*)pcbs[cur_pid].tf_p -> ebx;	if(!EmptyQ(&mboxes[mid].wait_q))	{		pid = DeQ(&mboxes[mid].wait_q);		EnQ(pid,&ready_q);		pcbs[pid].state = READY;		destination = (msg_t *)pcbs[pid].tf_p -> ebx;		MyMemCpy((char*)destination,(char*)source,sizeof(msg_t));	}	else	{		EnQMsg(source, &mboxes[mid].msg_q);		head = mboxes[mid].msg_q.head;		destination = &mboxes[mid].msg_q.msgs[head];	}	destination->sender = cur_pid;	destination->send_tick = sys_tick;}

void SpawnISR(int pid, func_ptr_t addr){		MyBZero(user_stacks[pid], USER_STACK_SIZE);	MyBZero((char *) &mboxes[pid], sizeof(mbox_t));	// 1st. point to just above of user stack, then drop by 64 bytes (tf_t)	pcbs[pid].tf_p = (tf_t *)&user_stacks[pid][USER_STACK_SIZE];	pcbs[pid].tf_p--;    // pointer arithmetic, now points to trapframe	// fill in CPU's register context	pcbs[pid].tf_p->eflags = EF_DEFAULT_VALUE|EF_INTR;	//pcbs[pid].tf_p->eip = (unsigned int)SimpleProc; // new process code	pcbs[pid].tf_p->eip = (unsigned int)addr;	pcbs[pid].tf_p->cs = get_cs();	pcbs[pid].tf_p->ds = get_ds();	pcbs[pid].tf_p->es = get_es();	pcbs[pid].tf_p->fs = get_fs();	pcbs[pid].tf_p->gs = get_gs();	pcbs[pid].tick_count = pcbs[pid].total_tick_count = 0;	pcbs[pid].state = READY;	if(pid != 0) EnQ(pid, &ready_q);  // IdleProc (PID 0) is not queued}

void StartProcISR(int new_pid, int func_addr) {	MyBzero( (char*) &pcb[new_pid], sizeof (pcb_t));	//clear process msg queue	MyBzero( (char*) &msg_q[new_pid], sizeof (msg_q_t));	pcb[new_pid].state= READY;		if(new_pid > 0 ) {	  EnQ(new_pid, &ready_q);	}		MyBzero( (char*) &proc_stack[new_pid], PROC_STACK_SIZE);	pcb[new_pid].TF_ptr =(TF_t*) &proc_stack[new_pid][PROC_STACK_SIZE]; 	pcb[new_pid].TF_ptr--;			pcb[new_pid].TF_ptr->eflags = EF_DEFAULT_VALUE|EF_INTR; // set INTR flag   	pcb[new_pid].TF_ptr->cs = get_cs();                     // standard fair   	pcb[new_pid].TF_ptr->ds = get_ds();                     // standard fair   	pcb[new_pid].TF_ptr->es = get_es();                     // standard fair   	pcb[new_pid].TF_ptr->fs = get_fs();                     // standard fair   	pcb[new_pid].TF_ptr->gs = get_gs();                     // standard fair		pcb[new_pid].TF_ptr->eip = (unsigned int) func_addr;	}

int BFS(void){    int r,c,d,cl;    Cost[sr][sc][0][0]=0;    EnQ(sr,sc,0,0);    while(DeQ(&r,&c,&d,&cl))    {      if(r==dr && c==dc && cl==0) return 1;      if(Valid(r,c,d,cl,r+Gr[d],c+Gc[d],d,(cl+1)%5,1))	EnQ(r+Gr[d],c+Gc[d],d,(cl+1)%5);      if(Valid(r,c,d,cl,r,c,(d+1)%4,cl,1))	EnQ(r,c,(d+1)%4,cl);      if(Valid(r,c,d,cl,r,c,(d+3)%4,cl,1))	EnQ(r,c,(d+3)%4,cl);    }    return 0;}

void SleepISR(){	int secs = pcb[running_pid].TF_ptr->eax;	pcb[running_pid].wake_time = OS_clock + (secs * 100);	//calculate wake time for the calling process, mark the wake time in its PCB	EnQ(running_pid, &sleep_q);		//queue its PID to the sleep queue	pcb[running_pid].state = SLEEP;       	//change its state to SLEEP	running_pid = -1;			//reset current running PID}

void KillISR(){	if(cur_pid < 1) return; // skip Idle Proc or when cur_pid has been set to -1	pcbs[cur_pid].state = AVAIL;	EnQ(cur_pid, &avail_q);	cur_pid = -1;          // no proc running any more}

void Sleep_ISR(int sleep_secs) {    int wake_time;    wake_time = (sleep_secs*100) + OS_clock;    pcb[running_pid].wake_time = wake_time;    EnQ(running_pid, &sleep_q);    pcb[running_pid].state = SLEEP;    running_pid = -1;}

void InitData(){   int i;   InitQ(&avail_q); // set queues initially empty   InitQ(&ready_q);   InitQ(&sleep_q);   InitQ(&avail_sem_q);      sys_tick = 0;   for(i=2; i<NUM_PROC; i++) // skip 0 (IdleProc) and 1 (Init)   {      pcbs[i].state = AVAIL;      EnQ(i, &avail_q);   }   for(i=NUM_SEM-1; i>=0; i--) EnQ(i, &avail_sem_q); // avail sem ID's 19-0   cur_pid = -1;}

void SemPostISR(int sid){	if (!EmptyQ(&(sems[sid].wait_q))) {		int free_pid = DeQ(&(sems[sid].wait_q));		pcbs[free_pid].state = READY;		EnQ(free_pid, &ready_q);	}	else {		sems[sid].sem_count += 1;	}}

void SemWaitISR(int sid){	if (sems[sid].sem_count > 0) {		sems[sid].sem_count -= 1;	}	else {		pcbs[cur_pid].state = WAIT;		EnQ(cur_pid, &(sems[sid].wait_q));		cur_pid = -1;	}}

void SleepISR(int sleep_secs){	q_t tmp_q;	InitQ(&tmp_q);	pcbs[cur_pid].wake_tick = (sys_tick + sleep_secs * 100);	while( !(EmptyQ(&sleep_q)) &&			(pcbs[sleep_q.q[sleep_q.head]].wake_tick <= pcbs[cur_pid].wake_tick)         ){		int tmpPID= DeQ(&sleep_q);		EnQ(tmpPID, &tmp_q);	}	EnQ(cur_pid, &tmp_q);	while (!EmptyQ(&sleep_q)){		EnQ(DeQ(&sleep_q), &tmp_q);	}	while(!EmptyQ(&tmp_q)){		EnQ(DeQ(&tmp_q), &sleep_q);	}	pcbs[cur_pid].state = SLEEP;	cur_pid = -1;}

void ExitISR(){	int ppid = pcbs[cur_pid].ppid;	if(ppid == -1)	{		pcbs[cur_pid].exit_code = pcbs[cur_pid].tf_p->eax;		pcbs[cur_pid].state = ZOMBIE;		pages[cur_pid].owner = -1;		cur_pid = -1;		return;	}	pcbs[ppid].state = READY;	EnQ(ppid,&ready_q);	pcbs[ppid].tf_p->eax = pcbs[cur_pid].tf_p->eax;	pages[cur_pid].owner = -1;	EnQ(cur_pid,&avail_q);	cur_pid = -1;}

void SemWaitISR(int sem_id){		if(sem[sem_id].limit > 0){		sem[sem_id].limit--;		return;	}	pcb[running_pid].state = WAIT;	EnQ(running_pid, &sem[sem_id].wait_q);	running_pid = -1;	}

//void SemWaitISR(int sid) {void SemWaitISR() {   int sid = pcbs[cur_pid].tf_p->eax;   if(sems[sid].sem_count > 0) {      sems[sid].sem_count--;   }   else {      EnQ(cur_pid, &sems[sid].wait_q);      pcbs[cur_pid].state = WAIT;      cur_pid = -1;   }}

void InitKernelData() {   int i;   MyBzero((char*)&sleep_q,sizeof (q_t));   MyBzero((char*)&ready_q,sizeof(q_t)); //clear queues   MyBzero((char*)&free_q,sizeof(q_t));   MyBzero((char*)&sem_q,sizeof(q_t));      for(i=0; i<MAX_PROC_NUM;i++){	MyBzero((char*)&msg_q[i],sizeof(msg_q_t));   }   //loop number i from 0 to 19:   for(i=0; i<Q_LEN; i++){      EnQ(i,&free_q);      EnQ(i,&sem_q);      MyBzero((char*)&pcb[i],sizeof(pcb_t));    }	OS_clock = 0;   running_pid = 0; }

void MsgRcvISR(msg_t *p){		if(!MsgEmptyQ(&(mboxes[cur_pid].msg_q)))		MsgDeQ(p, &(mboxes[cur_pid].msg_q));	else	{		EnQ(cur_pid, &(mboxes[cur_pid].wait_q));		pcbs[cur_pid].state = WAIT;		cur_pid = -1;	}}

//void SemPostISR(int sid) {void SemPostISR() {   int pid, sid = pcbs[cur_pid].tf_p->eax;      if(!EmptyQ(&sems[sid].wait_q)) {      pid = DeQ(&sems[sid].wait_q);      EnQ(pid, &ready_q);      pcbs[pid].state = READY;   }   else {      sems[sid].sem_count++;   }}

int IsGraphBipartite(void){    /* Start with node 0 of the graph as root node of BFS Tree */    if (num >0) {        /* Colour the first node or 0th node and EnQ it */        color[0] = RED;        EnQ(0);    }    while (!IsQEmpty()) {        int k;        /* DeQ one element and make it currently working Node */        int cwn = DeQ();        printf("Dequeued value is [%d] color[%d]/n", cwn, color[cwn]);        if (IsQEmpty()) {            printf(" Q is empty.../n");        }        /* Check each neighbouring node of currently working node and try color it opposite to currently working node*/        for(k=0; k <num; k++) {            if (mat[cwn][k]) {                if (color[k] == color[cwn]) {                    printf("Got an vertex [%d] from [%d] which is already coloured [%s]/n", k, cwn, whichcolor(color[k]));                     printf("Currently working node colour is also [%s]/n", whichcolor(color[cwn]));                    return 0;                } else  if (color[k] == NOTCOLORED) {                    /* Color the adjacent node and Enqueue it */                    color[k] = opposite(color[cwn]);                    /* EnQ all the neightbouring nodes to Q */                    EnQ(k);                }            }        }    }    return 1;}