Thread: syncronization issue

  1. #1
    Registered User
    Join Date
    Oct 2007
    Posts
    100

    syncronization issue

    Hello everybody!
    Today I wanted to solve this exercise:

    Code:
    A main process opens a file (filled with bytes in the range 0-255) and then creates 2
    clone processes which have to parse (of course in parallel) the file starting respectively from
    the beginning and the end of the file: their task is to replace every byte==255 with the value 0.
     A process returns as it meets a byte already processed by the other clone.
    Here is my solution:

    Code:
    #include <fcntl.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <sys/types.h>
    #include <sched.h>
    #include <unistd.h>
    #include <errno.h>
    #include <time.h>
    #include <wait.h>
    
    int fd, indexA, indexB;
    
    struct args{
    	int *index;
    	int incdec;
    };
    typedef struct args Args;
    
    int lock(char *filename)
    {
    	int fd;
    	while (1)
    	{
    		fd=open(filename,O_CREAT|O_EXCL|O_RDWR|O_TRUNC,0666);
    		if (fd<0&&errno!=EEXIST)
    		{
    			printf("BAD LOCK OPEN\n");
    			return 0;
    		}
    		if (fd<0&&errno==EEXIST)
    		{
    			sched_yield();
    		}
    		else
    			break;
    	}
    	return fd;
    
    }
    
    int unlock (char *filename, int fd)
    {
    	if (close(fd)<0)
    	{
    		printf("BAD LOCK CLOSE\n");
    		return 0;
    	}
    	if (unlink(filename)<0)
    	{
    		printf ("BAD UNLINK\n");
    		return 0;
    	}
    	usleep(200);// SCHED_YIELD won't work!
    	return 1;
    }
    
    int cloneA(void* args)
    {
    	Args *a=(Args *)args;
    
    	printf("PID %d: index: %d incdec: %d\n",(int)getpid(),*(a->index),a->incdec);
    
    	int lockfd;unsigned char ch;
    	sleep(1);
    	while (indexA<=indexB)
    	{
    		lockfd=lock("LOCKFILE");
    		lseek(fd,*(a->index),SEEK_SET);
    		read(fd,&ch,sizeof(unsigned char));
    		printf("%d index: %d CH:%d\n",(int )getpid(),*(a->index),ch);
    		if (ch==255)
    		{
    			printf("%d has found a char == 255 in position %d\n",(int)getpid(),*(a->index));
    			lseek(fd,*(a->index),SEEK_SET);ch=0;
    			write(fd,&ch,sizeof(unsigned char));
    		}
    		*(a->index)+=a->incdec;
    		unlock("LOCKFILE",lockfd);
    		
    	}	
    	
    	return 0;
    }
    
    void fillfile(int fd, int numbytes)
    {
    	int i;
    	srand(time(NULL));
    	unsigned char ch;
    	lseek (fd,0,SEEK_SET);
    	for (i=0;i<numbytes;i++)
    	{
    		ch=rand()%256;
    		write(fd,&ch,sizeof(unsigned char));
    	}
    }
    
    void printfilenums(int fd)
    {
    	lseek(fd,0,SEEK_SET);
    	unsigned char ch;
    	while ((read(fd,&ch,sizeof(unsigned char)))==sizeof(unsigned char))
    	{
    		printf("%d ",ch);
    	}
    	printf("\n\n");
    }
    
    int main(int argc, char * argv[])
    {
    	if (argc!=2)
    	{
    		printf("USAGE: program infile\n");
    		return 1;
    	}
    	fd=open (argv[1],O_TRUNC|O_RDWR);
    	fillfile(fd,70);
    	printfilenums(fd);
    	
    	indexA=lseek(fd,0,SEEK_SET);
    	indexB=lseek(fd,-1,SEEK_END);
    
    	printf("\nIndex A=%d Index B=%d\n",indexA,indexB);
    	int stackA[1024],stackB[1024];
    	pid_t pidA,pidB;
    	
    	Args a={&indexA,1};
    	Args b={&indexB,-1};
    	
    	pidA=clone(cloneA,&stackA[1023],CLONE_VM|CLONE_FILES,&a);
    	if (pidA<0) {printf("BAD CLONE A\n");return 1;}
    	pidB=clone(cloneA,&stackB[1023],CLONE_VM|CLONE_FILES,&b);
    	if (pidB<0) {printf("BAD CLONE B\n");return 1;}
    	pid_t pid=waitpid(-1,NULL,__WCLONE);
    	printf("%d terminated\n",(int)pid);
    	pid=waitpid(-1,NULL,__WCLONE);
    	printf("%d terminated\n",(int)pid);
    	printfilenums(fd);
    	close(fd);
    	return 0;
    }
    as you can see, i implemented my lock and unlock functions, the only problem I found is that if i replace the usleep(200) with a sched_yield or a shorter time for sleeping the 1st process will win all the contents on the lock and arrive at the end of the file before the second can start its job... Can you please explain me the reason for this?
    Thanks a lot! bye!
    /* NO COMMENT */

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    The scheduling of tasks is such that you get a quanta of time (say 10 ms), which is enough to process the whole file. You need a bigger data-set, I expect.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Completlely unrealistic exercise (where do they get these things?), but I'd suggest creating two pipes between the clone processes (one for A->B communication, one for B->A communication). The two processes can bounce back and forth by taking turns writing a byte to their output pipe then reading a byte from their input pipe, in the meanwhile altering a byte of file data.

    The data I would write to the pipe would probably be the current file offset, so that either process can tell when the other one has reached the same point in the file being altered.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  4. #4
    Registered User
    Join Date
    Oct 2007
    Posts
    100
    Quote Originally Posted by matsp View Post
    The scheduling of tasks is such that you get a quanta of time (say 10 ms), which is enough to process the whole file. You need a bigger data-set, I expect.
    so we can say that the only way we can force a clone to parse 1 byte per time is to force the sleep, is that right?

    Quote Originally Posted by brewbuck View Post
    Completlely unrealistic exercise (where do they get these things?), but I'd suggest creating two pipes between the clone processes (one for A->B communication, one for B->A communication). The two processes can bounce back and forth by taking turns writing a byte to their output pipe then reading a byte from their input pipe, in the meanwhile altering a byte of file data.

    The data I would write to the pipe would probably be the current file offset, so that either process can tell when the other one has reached the same point in the file being altered.
    the same mind who wrote this book http://www.amazon.com/Understanding-...2494917&sr=8-1 can invent these exercises... and give students as preliminary test...

    I'll try later to solve with pipes, it seems a good way to review pipes.. By the way, aren't fifo in general better (also easier to use) than pipes?

    thanks again for your help!
    bye
    /* NO COMMENT */

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    There are several ways to make sure the order of threads running. Sleeping is one that is very poor in the level of control. A mutex, semaphore or similar will be a much better way. Or a pipe. Any type of global object that both threads/processes can use to communicate that "it's my turn now, next yours".

    Of course, for multitasking/multithreading, you really do NOT want to have every small operation do an interprocess communication step, because it will probably take 100x more time to communicate than to process the data in such an example as you've given here.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    Registered User
    Join Date
    Oct 2007
    Posts
    100
    Hello again! I finally tried to write another version of the program using FIFOs instead of locks and the result is this program which doesn't work.. It seems like if there is a deadlock somewhere, the while (1) loop of clone_func should have some problem, but i cannot understand why... I crossed the FIFO so that one clone writes its index where the other reads, and put write before read, but.. nothing...
    can you please help me to find out the problem with this version? Thanks!!! Bye

    Code:
    #include <sys/types.h>
    #include <sys/stat.h>
    #include <fcntl.h>
    #include <wait.h>
    #include <sched.h>
    #include <unistd.h>
    #include <time.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <errno.h>
    
    int fd; //file to be parsed 
    
    struct args{
    	char readfifoname[256],writefifoname[256];
    	int incdec, startIndex;
    };
    typedef struct args Args;
    
    int clone_func(void *ar)
    {
    	Args *a=(Args *) ar;
    	pid_t pid=getpid();
    	int myindex=a->startIndex,otherindex;
    	printf("CLONE &#37;d started. I will parse the file from offset %d and add %d at each round. I write on %s and read from %s\n",(int)pid, myindex,a->incdec,a->writefifoname,a->readfifoname);
    	
    	int fdfiforead=open (a->readfifoname,O_RDONLY), fdfifowrite=open(a->writefifoname,O_WRONLY);
    
    	if (fdfiforead==-1||fdfifowrite==-1)
    	{
    		printf("BAD OPEN FIFO\n");
    		return 1;
    	}
    
    	sleep(1); //both clones have to open the fifo before we can start
    	
    	unsigned char ch;
    
    	while (1)
    	{
    		write (fdfifowrite,&myindex,sizeof(int));
    		read (fdfiforead,&otherindex,sizeof(int));
    		
    		if (a->incdec==-1 && myindex<otherindex) //I am the clone parsing from the bottom upward and i skipped 
    		//the other clone--> end
    		{
    			close(fdfiforead);
    			close(fdfifowrite);
    			printf("Clone %d has finished\n",(int)pid);
    			return 1;	
    		}
    		if (a->incdec==1 && myindex>otherindex) //the contrary
    		{
    			close(fdfiforead);
    			close(fdfifowrite);
    			printf("Clone %d has finished\n",(int)pid);
    			return 1;	
    		}
    
    		//read from file
    		lseek(fd,myindex,SEEK_SET);
    		read(fd,&ch,1);
    		if (ch==255)
    		{
    			printf("Clone %d found a char == 255 in position %d\n",(int)pid,myindex);
    			lseek(fd,myindex,SEEK_SET);
    			ch=0;
    			write(fd,&ch,1);
    			
    		}
                   myindex+=a->incdec;
    	}
    	close(fdfiforead);
    	close(fdfifowrite);
    	return 0; //ERROR 
    }
    
    
    void fillfile(int fd, int numbytes)
    {
    	int i;
    	srand(time(NULL));
    	unsigned char ch;
    	lseek (fd,0,SEEK_SET);
    	for (i=0;i<numbytes;i++)
    	{
    		ch=rand()%256;
    		write(fd,&ch,sizeof(unsigned char));
    	}
    }
    
    void printfilenums(int fd)
    {
    	lseek(fd,0,SEEK_SET);
    	unsigned char ch;
    	while ((read(fd,&ch,sizeof(unsigned char)))==sizeof(unsigned char))
    	{
    		printf("%d ",ch);
    	}
    	printf("\n\n");
    }
    
    int main (int argc, char *argv[])
    {
    	if (argc!=2)
    	{
    		printf("USAGE: progname filename\n");
    		return 1;
    	}
    	int stack1[1024],stack2[1024];
    	pid_t pid1,pid2;
    	int ret=mkfifo("FIFOUPWARD",0666);
    	if (ret==-1 && errno == EEXIST)
    		printf("Notice: FIFOUPWARD ALREADY EXISTS\n");
    	ret=mkfifo("FIFODOWNWARD",0666);
    	if (ret==-1 && errno == EEXIST)
    		printf("Notice: FIFODOWNWARD ALREADY EXISTS\n");
    	
    	else 
    		if (ret==-1)
    		{
    			printf("BAD MKFIFO\n");
    			return 1;
    		}
    	 fd= open (argv[1],O_CREAT|O_TRUNC|O_RDWR,0666);
    	if (fd<0)
    	{
    		printf("Bad file open\n");
    		return 1;
    	}
    	fillfile(fd,90);
    	printfilenums(fd);
    	Args a={"FIFODOWNWARD","FIFOUPWARD",1,0};
    	int startb=lseek(fd,-1,SEEK_END);
    	Args b={"FIFOUPWARD","FIFODOWNWARD",-1,startb};
    
    	pid1=clone (clone_func,&stack1[1023],CLONE_VM|CLONE_FILES,&a);
    	if (pid1<0)
    	{
    		printf("BAD CLONE\n"); 
    		return 1;
    	}
    	pid2=clone (clone_func,&stack2[1023],CLONE_VM|CLONE_FILES,&b);
    	if (pid1<0)
    	{
    		printf("BAD CLONE\n"); 
    		return 1;
    	}
    	pid_t pid= waitpid(-1,NULL,__WCLONE);
    	pid=waitpid(-1,NULL,__WCLONE);
    	printf("END\n");
    	close(fd);
    	return 0;
    }
    Last edited by smoking81; 09-28-2008 at 03:35 AM.
    /* NO COMMENT */

  7. #7
    Registered User
    Join Date
    Oct 2007
    Posts
    100
    Finally I found out the problem: open on a FIFO is blocking as well as read and write.. So I caused a deadlock which could be avoided simply opening the files in the same order.. This lead me to admit that it'd have been much better to make use of 2 clone_func (cloneA and cloneB) to keep the code simpler...
    Anyway, here is the working clone_func:

    Code:
    int clone_func(void *ar)
    {	
    	Args *a=(Args *) ar;
    	pid_t pid=getpid();
    	int myindex=a->startIndex,otherindex;
    	unsigned char ch;int fdfiforead,fdfifowrite;
    	int r,w;
    	printf("CLONE %d started. I will parse the file from offset %d and add %d at each round. 
    I write on %s and read from %s\n",(int)pid, myindex,a->incdec,a->writefifoname,a->readfifoname);
    	if (a->incdec==1)
    	{
    		fdfiforead=open (a->readfifoname,O_RDONLY);
    		fdfifowrite=open(a->writefifoname,O_WRONLY);
    	}
    	else
    	{
    		fdfifowrite=open(a->writefifoname,O_WRONLY);		
    		fdfiforead=open (a->readfifoname,O_RDONLY);
    				
    	}
    	if (fdfiforead<0||fdfifowrite<0)
    	{
    		printf("BAD OPEN FIFO\n");
    		return 1;
    	}
    
    	while (1)
    	{
    		w=write (fdfifowrite,&myindex,sizeof(int));
    		r=read (fdfiforead,&otherindex,sizeof(int));
    		
    		if (a->incdec==-1 && myindex<otherindex) //I am the clone parsing from the bottom upward and i skipped 
    		//the other clone--> end
    		{
    			close(fdfiforead);
    			close(fdfifowrite);
    			printf("Clone %d has finished\n",(int)pid);
    			return 0;	
    		}
    		if (a->incdec==1 && myindex>otherindex) //the contrary
    		{
    			close(fdfiforead);
    			close(fdfifowrite);
    			printf("Clone %d has finished\n",(int)pid);
    			return 0;	
    		}
    
    		//read from file
    		lseek(fd,myindex,SEEK_SET);
    		read(fd,&ch,1);
    		printf("%d read in position %d: %d\n",pid,myindex,ch);
    		if (ch==255)
    		{
    			printf("Clone %d found a char == 255 in position %d\n",(int)pid,myindex);
    			lseek(fd,myindex,SEEK_SET);
    			ch=0;
    			write(fd,&ch,1);
    		}
    		myindex+=a->incdec;
    	}
    	close(fdfiforead);
    	close(fdfifowrite);
    	return 1; //ERROR 
    }
    Last edited by smoking81; 09-28-2008 at 04:34 AM.
    /* NO COMMENT */

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. float calculation issue
    By George2 in forum C# Programming
    Replies: 1
    Last Post: 05-26-2008, 04:56 AM
  2. type safe issue
    By George2 in forum C++ Programming
    Replies: 4
    Last Post: 02-12-2008, 09:32 PM
  3. directsound issue
    By valis in forum Tech Board
    Replies: 0
    Last Post: 06-25-2006, 09:28 PM
  4. Idle Issue.
    By Charmy in forum C++ Programming
    Replies: 7
    Last Post: 06-24-2005, 06:10 AM
  5. my first issue of GDM
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 0
    Last Post: 09-12-2002, 04:02 PM