C : round robin

I_Choose_Noise · 12 Ιανουαρίου 2007

kalispera paidia ,

prospa8o na ftia3o to round robin se c ,

alla lamvano to e3is exception :

-----------------------------------------------------------------------

Unhandled exception at 0xcccccccc in miniOS.exe: 0xC0000005: Access violation reading location 0xcccccccc.

pd {process_id=1 num_ticks=0 function=0xcccccccc ...} data

-----------------------------------------------------------------------

visual c++ express edition

k de mporo na vro ti ftaiei , kalodexoumeni opoiadipote voi8eia k sumvouli

oriste k o kodikas

/******************************************/

/* Doubly_Linked_List */

/******************************************/

typedef struct node {

struct node *next ;

struct node *prev ;

void *data ;

} NODE ;

typedef struct {

long num ;

NODE *head ;

NODE *tail ;

} ROOT ;

#define NEW( x ) (x *)malloc( sizeof( x ))

#define VALID( x ) ( (*x) != NULL )

#define NUM( x ) ( (*x)->num )

typedef int DATA ;

/* making a root node */

ROOT *make_root( void )

{

ROOT *root ;

if( (root = NEW( ROOT )) != NULL )

{

root->head = root->tail = NULL ;

root->num = 0 ;

}

return root ;

}

/* making a node for a doubly linked list */

NODE *dbl_make_node( void *data )

{

NODE *node ;

if( (node = NEW( NODE )) != NULL )

{

node->data = data ;

node->next = NULL ;

node->prev = NULL ;

}

return node ;

}

/* inserting data into a doubly linked list */

int dbl_insert_data( ROOT **root, void *data, int position )

{

NODE *temp ;

if( !VALID( root ) )

if( (*root = make_root()) == NULL )

return (-1) ;

if( (temp = dbl_make_node( data )) == NULL )

{

if( NUM( root ) ==0 )

{

free( *root ) ;

*root = NULL ;

}

return (-1) ;

}

if( NUM(root) == 0 )

(*root)->head = (*root)->tail = temp ;

else {

if( position == 0 )

{

temp->next = (*root)->head ;

(*root)->head->prev = temp ;

(*root)->head = temp ;

}

else

{

(*root)->tail->next = temp ;

temp->prev = (*root)->tail ;

(*root)->tail = temp ;

}

NUM( root )++ ;

return 0 ;

}

int dbl_insert_at_position( ROOT **root, NODE *node, void *data, int position )

{

int flag = 0 ;

NODE *temp, *prev ;

if( !VALID( root ) )

return (-1) ;

if( ((*root)->head == node) && (position == 0) )

flag = dbl_insert_data( root, data, 0 ) ;

else if( ((*root)->tail == node) && (position == 1) )

flag = dbl_insert_data( root, data, 1 ) ;

else

{

prev = node->prev ;

if( (temp = dbl_make_node( data )) == NULL )

return (-1) ;

if( position == 1 )

{

temp->next = node->next ;

temp->next->prev = temp ;

node->next = temp ;

temp->prev = node ;

}

else

{

temp->next = node ;

node->prev = temp ;

prev->next = temp ;

temp->prev = prev ;

}

NUM( root )++ ;

}

return flag ;

}

/* deleting a node from a doubly linked list */

void *dbl_delete_node( ROOT **root, NODE *that )

{

void *data_ptr ;

if( !VALID( root ) )

return (NULL) ;

if( NUM(root) > 1 ) {

if( (*root)->head == that )

{

(*root)->head = that->next ;

that->next->prev = NULL ;

}

else if( (*root)->tail == that )

{

(*root)->tail = that->prev ;

that->prev->next = NULL ;

}

else

{

that->next->prev = that->prev ;

that->prev->next = that->next ;

}

data_ptr = that->data ;

free( that ) ;

if( --NUM( root ) == 0 )

{

*root = NULL ;

free( *root ) ;

}

return (data_ptr) ;

}

/* traversal of a doubly linked list */

void display_list_tail( ROOT **root, void (*disp)( void *data ) )

{

NODE *node ;

if( VALID( root ) )

{

printf( "Backwards : " ) ;

node = (*root)->tail ;

do {

disp( node->data ) ;

node = node->prev ;

} while( node != NULL ) ;

}

/* save and recover a doubly linked list */

int save_list( const char *filename, ROOT **root, size_t datasize )

{

FILE *fp ;

NODE *node = (*root)->head ;

if( VALID( root ) ) {

if( (fp = fopen( filename, "wb" )) == NULL )

return (-1) ;

do {

if( fwrite( node->data, datasize, 1, fp ) != 1 )

return (-1) ;

node = node->next ;

} while( node != NULL ) ;

return ( fclose( fp )) ;

}

return 0 ;

}

int recover_list( const char *filename, ROOT **root, size_t datasize )

{

FILE *fp ;

void *dptr ;

if( (fp = fopen( filename, "rb" )) == NULL )

return (-4) ;

do {

if( (dptr = malloc( datasize )) == NULL )

return (-1) ;

if( (fread( dptr, datasize, 1, fp )) != 1 )

{

if( feof( fp ) )

return 0 ;

else

{

free( dptr ) ;

return (-2) ;

}

if( dbl_insert_data( root, dptr, 1 ) != 0 )

return (-3) ;

} while( 1 ) ;

}

/*************************************/

/* Cicular_Queue */

/*************************************/

typedef ROOT CQUEUE ;

/* inserting data into a circular queue */

int insert_circ_queue( CQUEUE **cqueue, void *data, int position )

{

if( dbl_insert_data( cqueue, data, position ) != 0 )

return (-1) ;

(*cqueue)->tail->next = (*cqueue)->head ;

(*cqueue)->head->prev = (*cqueue)->tail ;

return 0 ;

}

/* deleting data from a circular queue */

void *delete_circ_queue( CQUEUE **cqueue )

{

void *p1 ;

if( (p1 = dbl_delete_node( cqueue, (*cqueue)->head )) == NULL )

return (NULL) ;

if( VALID( cqueue ) )

{

(*cqueue)->tail->next = (*cqueue)->head ;

(*cqueue)->head->prev = (*cqueue)->tail ;

}

return p1 ;

}

/* extracting and replacing data in a circular queue */

#define extract( cqueue, dptr, type ) ( (*dptr) = *(type *)((*cqueue)->head->data) )

#define replace( cqueue, dptr, type ) ( *(type *)((*cqueue)->head->data) = (*dptr) )

/* rotating a circular queue */

int rotate( CQUEUE **cqueue, int direction )

{

if( !VALID( cqueue ) )

return (-1) ;

if( direction == 0 )

(*cqueue)->head = (*cqueue)->head->next ;

else

(*cqueue)->head = (*cqueue)->head->prev ;

(*cqueue)->tail = (*cqueue)->head->prev ;

return 0 ;

}

/* traversing a circular queue */

void traverse( CQUEUE **cqueue )

{

int count = 0 ;

NODE *node = (*cqueue)->head ;

do {

printf( "Visiting Node %d\n", count++ ) ;

node = node->next ;

} while( node != (*cqueue)->head ) ;

}

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#include <limits.h>

#include "Doubly_Linked_List.h"

#include "Circular_Queue.h"

typedef struct data {

int process_id ;

int num_ticks ; /* number of ticks received by the process */

int (*function)( void ) ; /* pointer to a function that simulates the process */

clock_t time ; /* total time received by the process */

} PROCESS ;

#define ADD_JOB insert_circ_queue

#define KILL_JOB delete_circ_queue

#define SHOW_JOBS display_circ_queue

#define SWAP_JOB rotate

#define UPDATE_PROCESS replace

#define GET_NEXT_JOB extract

#define MAX_JOBS 5

int func( void )

{

static int count = 5 ;

long int i ;

for( i=0 ; i<LONG_MAX ; i++ )

;

return ( --count ) ;

}

void display( void *data )

{

printf( "%d ", ((PROCESS *)(data))->process_id ) ;

}

void display_circ_queue( CQUEUE **cqueue, void (*disp)( void *data ) )

{

NODE *node, *head ;

printf( "Process Queue = [ " ) ;

if( VALID( cqueue ) )

{

head = node = (*cqueue)->head ;

do {

disp( node->data ) ;

node = node->next ;

} while( node != head ) ;

}

printf( "]\n" ) ;

}

int main( void )

{

CQUEUE *c_queue = NULL ;

PROCESS pd, *process ;

clock_t t1, t2 ;

int i ;

int (*ptr[])( void ) = { func } ;

for( i=0 ; i<MAX_JOBS ; i++ )

{

process = NEW( PROCESS ) ;

process->process_id = i ;

process->function = ptr[ i ] ;

process->time = 0 ;

process->num_ticks = 0 ;

ADD_JOB( &c_queue, process, 1 ) ;

SHOW_JOBS( &c_queue, display ) ;

}

while( VALID( &c_queue ))

{

GET_NEXT_JOB( &c_queue, &pd, PROCESS ) ;

printf( "Running Process [ %d ] : ", pd.process_id ) ;

SHOW_JOBS( &c_queue, display ) ;

t1 = clock() ;

i = pd.function() ;

t2 = clock() ;

pd.time += (t2-t1) ;

pd.num_ticks++ ;

if( i==0 )

{

free( KILL_JOB( &c_queue ) ) ;

printf( " ... Process %d Died after %g seconds of CPU time and %d ticks\n", pd.process_id, pd.time/CLK_TCK, pd.num_ticks ) ;

}

else

{

UPDATE_PROCESS( &c_queue, &pd, PROCESS ) ;

SWAP_JOB( &c_queue, 0 ) ;

}

printf( "\n\n\nProcess Queue is Empty ...\n" ) ;

return 0 ;

}

euxaristo ek ton proteron .

( na simeioso oti trexei sosta stis 2 protes epanalipseis k meta ... exception )

Directx · 12 Ιανουαρίου 2007

Δεν έχω ασχοληθεί με το συγκεκριμένο ζήτημα (task scheduling) εντούτοις στην CodeGear Turbo C++ Explorer το σφάλμα προερχότανε από την εντολή process->function = ptr[ i ] ; όπου το i υποδεικνύει εκτός του ptr[ ] array, μια πολύ γρήγορη λύση (πλην του να δεσμεύσουμε σωστά τον πίνακα ptr[]) είναι να ανακατευθύνουμε το process->function στο func (process->function = func;) οπότε ο κώδικας δουλεύει -τώρα αν δουλεύει σωστά το αφήνω σε σένα.

Επίσης για να δούμε σχετικά γρήγορα το rounding ας αντικαταστήσουμε το for( i=0 ; i<LONG_MAX ; i++ ) της func από LONG_MAΧ (υπερβολικός χρόνος) σε 50 (for( i=0 ; i<50; i++ ).

>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>

/******************************************/
/* Doubly_Linked_List */
/******************************************/
typedef struct node {
struct node *next ;
struct node *prev ;
void *data ;
} NODE ;

typedef struct {
long num ;
NODE *head ;
NODE *tail ;
} ROOT ;

#define NEW( x ) (x *)malloc( sizeof( x ))
#define VALID( x ) ( (*x) != NULL )
#define NUM( x ) ( (*x)->num )

typedef int DATA ;

/* making a root node */
ROOT *make_root( void )
{
ROOT *root ;

if( (root = NEW( ROOT )) != NULL )
 {
	root->head = root->tail = NULL ;
	root->num = 0 ;
 }
  return root ;
}

/* making a node for a doubly linked list */
NODE *dbl_make_node( void *data )
{
NODE *node ;
if( (node = NEW( NODE )) != NULL )
 {
	node->data = data ;
	node->next = NULL ;
	node->prev = NULL ;
}
  return node ;
}

/* inserting data into a doubly linked list */
int dbl_insert_data( ROOT **root, void *data, int position )
{
NODE *temp ;

if( !VALID( root ) )
 if( (*root = make_root()) == NULL )
  return (-1) ;

if( (temp = dbl_make_node( data )) == NULL )
 {
	if( NUM( root ) ==0 )
	 {
	   free( *root ) ;
	  *root = NULL ;
	}
   return (-1) ;
}

  if( NUM(root) == 0 )
(*root)->head = (*root)->tail = temp ;
  else
{
	if( position == 0 )
	{
		temp->next = (*root)->head ;
		(*root)->head->prev = temp ;
		(*root)->head = temp ;
	}
	else
	{
		(*root)->tail->next = temp ;
		temp->prev = (*root)->tail ;
		(*root)->tail = temp ;
	}
}

NUM( root )++ ;

return 0 ;
}

int dbl_insert_at_position( ROOT **root, NODE *node, void *data, int position )
{
int flag = 0 ;
NODE *temp, *prev ;

if( !VALID( root ) )
 return (-1) ;
if( ((*root)->head == node) && (position == 0) )
 flag = dbl_insert_data( root, data, 0 ) ;
else if( ((*root)->tail == node) && (position == 1) )
 flag = dbl_insert_data( root, data, 1 ) ;
else
 {
	prev = node->prev ;
	if( (temp = dbl_make_node( data )) == NULL )
	 return (-1) ;
	if( position == 1 )
	{
		temp->next = node->next ;
		temp->next->prev = temp ;
		node->next = temp ;
		temp->prev = node ;
	}
	else
	{
		temp->next = node ;
		node->prev = temp ;
		prev->next = temp ;
		temp->prev = prev ;
	}

	NUM( root )++ ;
}

return flag ;
}

/* deleting a node from a doubly linked list */
void *dbl_delete_node( ROOT **root, NODE *that )
{
void *data_ptr ;
if( !VALID( root ) )
 return (NULL) ;
if( NUM(root) > 1 )
{
	 if( (*root)->head == that )
		{
			(*root)->head = that->next ;
			that->next->prev = NULL ;
		}
	else if( (*root)->tail == that )
	{
		(*root)->tail = that->prev ;
		that->prev->next = NULL ;
	}
	else
	{
		that->next->prev = that->prev ;
		that->prev->next = that->next ;
	}
}

data_ptr = that->data ;
free( that ) ;

if( --NUM( root ) == 0 )
{
  *root = NULL ;
  free( *root ) ;
}

return (data_ptr) ;
}

/* traversal of a doubly linked list */
void display_list_tail( ROOT **root, void (*disp)( void *data ) )
{
NODE *node ;

if( VALID( root ) )
{
	printf( "Backwards : " ) ;
	node = (*root)->tail ;
	do {
		disp( node->data ) ;
		node = node->prev ;
	   } while( node != NULL ) ;
}
}

/* save and recover a doubly linked list */
int save_list( const char *filename, ROOT **root, size_t datasize )
{
FILE *fp ;
NODE *node = (*root)->head ;

if( VALID( root ) )
{
	if( (fp = fopen( filename, "wb" )) == NULL )
		return (-1) ;

	do {
			if( fwrite( node->data, datasize, 1, fp ) != 1 )
			 return (-1) ;
			node = node->next ;
	   } while( node != NULL ) ;

	return ( fclose( fp )) ;
}

return 0 ;
}

int recover_list( const char *filename, ROOT **root, size_t datasize )
{
FILE *fp ;
void *dptr ;

if( (fp = fopen( filename, "rb" )) == NULL )
 return (-4) ;

do {
		if( (dptr = malloc( datasize )) == NULL )
		 return (-1) ;
		if( (fread( dptr, datasize, 1, fp )) != 1 )
		 {
			if( feof( fp ) )
			 return 0 ;
			else
			 {
				free( dptr ) ;
				return (-2) ;
			 }
		}

		if( dbl_insert_data( root, dptr, 1 ) != 0 )
		 return (-3) ;
} while( 1 ) ;
}

/*************************************/
/* Cicular_Queue */
/*************************************/
typedef ROOT CQUEUE ;

/* inserting data into a circular queue */
int insert_circ_queue( CQUEUE **cqueue, void *data, int position )
{
if( dbl_insert_data( cqueue, data, position ) != 0 )
 return (-1) ;

(*cqueue)->tail->next = (*cqueue)->head ;
(*cqueue)->head->prev = (*cqueue)->tail ;

return 0 ;
}

/* deleting data from a circular queue */
void *delete_circ_queue( CQUEUE **cqueue )
{
void *p1 ;

if( (p1 = dbl_delete_node( cqueue, (*cqueue)->head )) == NULL )
 return (NULL) ;

if( VALID( cqueue ) )
{
	(*cqueue)->tail->next = (*cqueue)->head ;
	(*cqueue)->head->prev = (*cqueue)->tail ;
}

return p1 ;
}

/* extracting and replacing data in a circular queue */
#define extract( cqueue, dptr, type ) ( (*dptr) = *(type *)((*cqueue)->head->data) )
#define replace( cqueue, dptr, type ) ( *(type *)((*cqueue)->head->data) = (*dptr) )

/* rotating a circular queue */
int rotate( CQUEUE **cqueue, int direction )
{
if( !VALID( cqueue ) )
 return (-1) ;
if( direction == 0 )
 (*cqueue)->head = (*cqueue)->head->next ;
else
 (*cqueue)->head = (*cqueue)->head->prev ;

(*cqueue)->tail = (*cqueue)->head->prev ;

return 0 ;
}

/* traversing a circular queue */
void traverse( CQUEUE **cqueue )
{
int count = 0 ;
NODE *node = (*cqueue)->head ;

do {
		printf( "Visiting Node %d\n", count++ ) ;
		node = node->next ;
   } while( node != (*cqueue)->head ) ;
}

typedef struct data
{
int process_id ;
int num_ticks ; /* number of ticks received by the process */
int (*function)( void ) ; /* pointer to a function that simulates the process */
clock_t time ; /* total time received by the process */
} PROCESS ;

#define ADD_JOB insert_circ_queue
#define KILL_JOB delete_circ_queue
#define SHOW_JOBS display_circ_queue
#define SWAP_JOB rotate
#define UPDATE_PROCESS replace
#define GET_NEXT_JOB extract
#define MAX_JOBS 5


int func( void )
{
static int count = 5 ;
long int i ;

for( i=0 ; i<50/*LONG_MAX*/ ; i++ )
 ;

return ( --count ) ;
}

void display( void *data )
{
printf( "%d ", ((PROCESS *)(data))->process_id ) ;
}

void display_circ_queue( CQUEUE **cqueue, void (*disp)( void *data ) )
{
NODE *node, *head ;

printf( "Process Queue = [ " ) ;
if( VALID( cqueue ) )
{
	head = node = (*cqueue)->head ;
	do {
			disp( node->data ) ;
			node = node->next ;
	   } while( node != head ) ;
}
printf( "]\n" ) ;
}

int main( void )
{
CQUEUE *c_queue = NULL ;
PROCESS pd, *process ;
clock_t t1, t2 ;
int i ;

int (*ptr[])( void ) = { func } ;

for( i=0 ; i<MAX_JOBS ; i++ )
{
	process = NEW( PROCESS ) ;
	process->process_id = i ;
	process->function = func;
	process->time = 0 ;
	process->num_ticks = 0 ;
	ADD_JOB( &c_queue, process, 1 ) ;
	SHOW_JOBS( &c_queue, display ) ;
}

while( VALID( &c_queue ))
{
	GET_NEXT_JOB( &c_queue, &pd, PROCESS ) ;
	printf( "Running Process [ %d ] : ", pd.process_id ) ;
	SHOW_JOBS( &c_queue, display ) ;

	t1 = clock() ;
	i = pd.function() ;
	t2 = clock() ;
	pd.time += (t2-t1) ;
	pd.num_ticks++ ;

	if( i==0 )
	{
		free( KILL_JOB( &c_queue ) ) ;
		printf( " ... Process %d Died after %g seconds of CPU time and %d ticks\n", pd.process_id, pd.time/CLK_TCK, pd.num_ticks ) ;
	}
	else
	{
		UPDATE_PROCESS( &c_queue, &pd, PROCESS ) ;
		SWAP_JOB( &c_queue, 0 ) ;
	}
}

printf( "\n\n\nProcess Queue is Empty ...\n" ) ;

return 0 ;
}

I_Choose_Noise · 13 Ιανουαρίου 2007

euxaristo Directx gia ti voi8eia , den katalava akomi giati den pernaei o ptr

alla grafontas process->function = func ; opos eipes ekteleitai men ,

xanei ti leitourgikotita tou de

alla 3exnontas- diagrafontas ti metavliti static int count

kai kanontas tin global , as tin poume callie

kai an orisoume episis mia global ( axi aparaitita ) as poume killed

pou deixnei tis diergasies pou exoun termatistei

kai me mia alximeia stin main :

if( i==0 )

{

free( KILL_JOB( &c_queue ) ) ;

printf( " ... Process %d Died after %g seconds of CPU time and %d ticks\n", pd.process_id, pd.time/CLK_TCK, pd.num_ticks ) ;

killed++ ;

if ( MAX_JOBS-killed == 1 )

callie = 1 ;

else

callie = 5 ;

}

diladi an pros8esoume tis 4 teleutaies grammes

einai ola OK

euxaristo ton Directx gia ti voi8eia kai tous upoloipous gia to endiaferon

:-D :-D :-D :-D :-D :-D :-D :-D :-D

Σύνδεση

C : round robin

Προτεινόμενες αναρτήσεις

I_Choose_Noise

Directx

I_Choose_Noise

Αρχειοθετημένο

Σύνδεση