Thread: 3 types of processes accessing shared memory

  1. #1
    Registered User
    Join Date
    Dec 2011
    Posts
    8

    3 types of processes accessing shared memory

    Hello! I am trying to write a program in c, where you have a linked list and 3 processes share it, one inserts stuff the other deletes and the third reads at the same time. I am a bit confused as to how to define those processes. Will they work with execl()? Since they are different kind processes, I can't fork them right?

    Thanks in advance for your time and excuse my noob-iness!

  2. #2
    Registered User
    Join Date
    Dec 2011
    Posts
    795
    Quote Originally Posted by Joanna91 View Post
    Since they are different kind processes, I can't fork them right?
    You can fork() them, and they are the same type of process. They have different functions, but that's not relevant.

    Quote Originally Posted by Joanna91 View Post
    I am a bit confused as to how to define those processes.
    I'm not exactly sure what you mean by "define", but here's a *short* example of forking in C: fork.c



  3. #3
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Don't use fork, because the memory in each fork is a copy, ie, after the fork, the child's linked list will not be the same as that of the parent.

    Use clone() or pthreads. You could also use completely separate programs with mmap or shmem; you would then need to use semaphores for locking.

    Locking is very important (with clone, you'd also use semaphores; with pthreads, you could use semaphores or mutexes). This is because no matter what, processes actually cannot be accessing the linked list at exactly the same time using, eg, different processor cores. However, what they can do is aquire a lock on part of the list while other processes have locks on some other part. That may be what you want the reader process to do. This would mean having a unique lock for each node. The reader would aquire that and either do what it does, or else make a copy of the node for whatever purpose, then release the lock.

    Changing a node would require that you lock it while the change is being made.

    You will have to think about how insertions and deletions are performed -- those, and traversal (eg, finding/searching), must use a single lock, because it cannot be possible for one process to be traversing the list while another one is changing links somewhere. It might not be necessary or desirable to use a lock for each node at all, but you must have one for insertion/deletion/find. That's the simplest way, because then there is only one lock, for the whole list. The process that inserts can prepare a new node on its own, but then locks the list while inserting. The process that reads would lock, find the node it wants, make a copy, unlock (this depends on the purpose of the reader).

    Do not try and invent your own system for locking. A lot of people think this is possible because they have an idea that seems logically sound. You can't. You must use semaphores or mutexes. They are fairly simple once you understand them, which might take a few hours experimenting. Write a very basic program implementing threads or whatever and using some form of lock and get that to work. I'd recommend then posting it here, because a lot of people (including myself) have gotten this wrong the first time without knowing it.
    Last edited by MK27; 12-16-2011 at 07:40 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  4. #4
    Registered User
    Join Date
    Dec 2011
    Posts
    795
    I was under the impression that there was a special reason they wanted to use fork, sorry. But yeah, MK27 is right about pthreads, here's a quick example I wrote a while ago that you can play with to understand threading:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <unistd.h>
    #include <pthread.h>
    #include <sys/time.h>
    #include <string.h>
    #include <semaphore.h>
    
    
    #define MAX_SEQ 25
    #define SEQ_1 5
    #define SEQ_2 10
    #define NT 2
    
    
    #define SUB_TIME(a, b) (((a).tv_sec - (b).tv_sec) * 1000000L + (a).tv_usec - (b).tv_usec)
    
    
    struct syn_t {
    	pthread_mutex_t mutex;
    	pthread_cond_t cond; 
    	char t_a, kill;
    	pthread_t threads[2];
    	void *ret_1, *ret_2;
    };
    
    
    void synch(void *vd) {
        struct syn_t *syn = (struct syn_t *)vd;
    	while (1) {
    		pthread_mutex_lock(&syn->mutex);
    		while (syn->t_a != 2) {
    			if (syn->kill == 1) {pthread_exit(NULL);}
    			pthread_cond_wait(&syn->cond, &syn->mutex);
    			syn->t_a = 0;
    		}
        	pthread_mutex_unlock(&syn->mutex);
        }	
    	pthread_exit(NULL);
    }
    
    
    void func_1(void *vd) {
        struct syn_t *syn = (struct syn_t *)vd;
    	struct timeval now, wait;
    	int ret_1;
    	for (ret_1=0; ret_1<MAX_SEQ;ret_1++) {
    		gettimeofday(&wait, NULL);
    		pthread_mutex_lock(&syn->mutex);
    		
    		printf("doing work on %s, (%d) ",__func__,ret_1);
    		//insert work
    		
    		
    		syn->t_a = syn->t_a+1;
    		gettimeofday(&now, NULL);
        	long mstask = SUB_TIME(now,wait);
        	printf("work took %ld long..\n",SUB_TIME(now,wait));
    		syn->ret_1 = (void *)&ret_1;
    		if (ret_1 == SEQ_1 || ret_1 == SEQ_2) {
    			syn->kill=1; 
    			pthread_cond_signal(&syn->cond);
    			pthread_exit(NULL);
    		}
        	if ( 1000000-mstask > 0 ) usleep(1000000-(unsigned int)mstask);
        	pthread_cond_signal(&syn->cond);
        	pthread_mutex_unlock(&syn->mutex);
        }		
    	pthread_exit(NULL);
    }
    
    
    void func_2(void *vd) {
        struct syn_t *syn = (struct syn_t *)vd;
    	struct timeval now, wait;
    	int ret_2;
    	for (ret_2=0; ret_2<MAX_SEQ;ret_2++) {
    		gettimeofday(&wait, NULL);
    		pthread_mutex_lock(&syn->mutex);
    		
    		printf("doing work on %s, (%d) ",__func__,ret_2);
    		//insert work
    		
    		
    		syn->t_a = syn->t_a+1;
    		gettimeofday(&now, NULL);
        	long mstask = SUB_TIME(now,wait);
        	printf("work took %ld long..\n",SUB_TIME(now,wait));
    		syn->ret_2 = (void *)&ret_2;
    		if (ret_2 == SEQ_1 || ret_2 == SEQ_2) {
    			syn->kill=1; 
    			pthread_cond_signal(&syn->cond);
    			pthread_exit(NULL);
    		}
        	if ( 1000000-mstask > 0 ) usleep(1000000-(unsigned int)mstask);
        	pthread_cond_signal(&syn->cond);
        	pthread_mutex_unlock(&syn->mutex);
        }		
    	pthread_exit(NULL);
    }
    
    
    int main(int argc, char **argv) {
        struct syn_t *syn = (struct syn_t *)malloc(sizeof(*syn));
        memset(syn,0x00,sizeof(*syn));
    	syn->ret_1 = malloc(5);
    	syn->ret_2 = malloc(5);
    	
        pthread_mutex_init(&syn->mutex, NULL);
        pthread_cond_init(&syn->cond, NULL);
    	
        pthread_create(&syn->threads[0], NULL, (void *)&func_1, (void *)&syn);
        pthread_create(&syn->threads[1], NULL, (void *)&func_2, (void *)&syn);
        pthread_create(&syn->threads[2], NULL, (void *)&synch,  (void *)&syn);
    	
        pthread_join(syn->threads[0], NULL);
    	pthread_join(syn->threads[1], NULL);
    	pthread_join(syn->threads[2], NULL);
    	
    	int ret_1 = *(int *)syn->ret_1;
    	int ret_2 = *(int *)syn->ret_2;
    	
    	printf("Finished all threads! Returned: %d (1) | %d (2)\n",ret_1,ret_2);
    	
    	pthread_mutex_destroy(&syn->mutex);
    	pthread_cond_destroy(&syn->cond);
    	
    	free(syn);
    	
    	return 1;
    }

  5. #5
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    >> I am a bit confused as to how to define those processes.
    Process creation in *nix is achieved via fork(). Then once you have a new process, you can call one of the exec functions to run another process-image, or executable file.
    Delve into UNIX process creation

    Quote Originally Posted by MK27 View Post
    Don't use fork, because the memory in each fork is a copy, ie, after the fork, the child's linked list will not be the same as that of the parent.
    >> 3 types of processes accessing shared memory
    fork() does create a copy of your process, but some things are inherited like shared memory objects. If you really do want multiple processes accessing the same "linked list", then it would be through a shared memory object. The alternative is to use a single process with multiple threads.

    >> here's a quick example...
    Code review:
    SUB_TIME(a, b) is incorrect, when b.tv_usec > a.tv_usec

    >> &syn->threads[2]
    Index out of bounds.

    >> (void *)&func_1
    pthread_create() expects a function pointer type, not a void*. The cast shouldn't be there.

    >> void func_1(void *vd)
    Incorrect signature. It should return a void*. This return value can then be accessed by pthread_join(), which could be used instead of ret_1 and ret_2.

    >> syn->ret_1 = (void *)&ret_1;
    This is incorrect. The memory location for the local ret_1 is not valid once the function exits.

    All 3 thread functions contain logic that allows the thread to exit while still holding the lock. This will deadlock any thread that tries to acquire the lock - including those inside a pthread_cond_wait.

    >> here's a quick example I wrote a while ago that you can play with to understand threading:
    I have no idea what the code is trying to accomplish, but if you tell us we'll help make it right.

    gg

  6. #6
    Registered User
    Join Date
    Dec 2011
    Posts
    8
    Thank you everyone! Actually memcpy was right, I can't use threads, probably forks. But I don't know how to avoid messing them all up xD Making seperate programms with mmap or shmem sounds like a good idea, could you give me more info? Do they need seperate terminals to run? Because mine has to be run from the same terminal =/
    The information about locking really helps thank you!
    Last edited by Joanna91; 12-17-2011 at 05:03 AM.

  7. #7
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Making seperate programms with mmap or shmem sounds like a good idea, could you give me more info?
    Whether you use completely separate programs or fork depends on how much common ground there is between the processes. At the very least, they would be compiled with a common object file for the mmap and list handling. That's all there is to my demo, so I used fork.

    In real life I would do this kind of thing with threads, so this was a good exercise for me as I've never done it. It works, but there could be an easier way, and there could be problems with this I don't see.

    The big issue with mmap is that you have to decide how much space you will need in advance, because

    Quote Originally Posted by POSIX
    If the size of the mapped file changes after the call to mmap() as a result of some other operation on the mapped file, the effect of references to portions of the mapped region that correspond to added or removed portions of the file is unspecified.
    I actually did try a version that dynamically grew the file, it definitely led to "unspecified", lol.

    The basic idea here is that the first 4 bytes of the mmap contain an offset to the end of the used space, and after those four bytes a pointer value to the current list head. This would make deletions very awkward; it would be a better idea to write a memory pool using the mmap space and then have the linked list use that interface. Which is a lot more work.

    The sleep() call is not necessary, but without it, what will most likely happen is one process will accomplish everything it needs to do in one go (it will keep re-aquiring the lock it releases) because the task here is so simple. So for the demo, sleep() allows them to alternate.

    There is not much point to this unless you actually have something for the processes to do outside the locked section, eg, rather than being handed all the input up front, they might be reading it from a socket or other external source. But anything that actually involves the mmap (which is where the list is) must be done inside the locked section.

    This must be linked to the "real time" lib for semaphores, so compile -lrt. You may also need -std=gnu99 because of the declarations.

    Code:
    #include <stdio.h>
    #include <unistd.h>
    #include <stdlib.h>
    #include <string.h>
    #include <semaphore.h>
    #include <sys/mman.h>
    #include <fcntl.h>
    #include <inttypes.h>
    #include <sys/wait.h>
    
    /* compile -lrt */
    
    #define MMAPSZ 1024
    
    typedef struct _node {
    	char *data;
    	struct _node *next;
    } node;
    
    int addNode (node *addr, node *head, char *data) {
    	fprintf(stderr,"Adding %s...\n", data);
    	addr->data = strcpy((char*)(addr + sizeof(node)), data);
    	addr->next = head;
    	return sizeof(node) + strlen(data) + 1;
    }
    
    void process (int fd, sem_t *lock, void *map, char *words[], int n) {
    	uint32_t *offset = map;
    	int i;
    	node **head = map + 4, *cur;
    	for (i = 0; i < n; i++) {
    		sem_wait(lock);
    /*********  LOCKED SECTION *********/
    	// set address for new node
    		cur = map + *offset;
    	// add node
    		*offset += addNode(cur, *head, words[i]);
    	// set head to new node address
    		*head = cur;
    		sem_post(lock);
    /***********************************/
    		sleep(1);
    	}
    }
    
    int main(int argc, const char *argv[]) {
    // file for map
    	int mfd = open("mmap", O_CREAT | O_RDWR | O_TRUNC);
    	int32_t i;
    	if (mfd < 0) {
    		perror("open() 'mmap'");
    		return -1;
    	}
    	// file must sized before mmap call
    	for (i = 0; i < MMAPSZ; i += 4) write(mfd, &i, 4);
    
    // semaphore for locking list
    	sem_unlink("/listlock");
    	sem_t *listLock = sem_open("/listlock", O_CREAT | O_EXCL, S_IRUSR | S_IWUSR, 0);
    	if (listLock == SEM_FAILED) {
    		perror("sem_open() '/listLock'");
    		return -1;
    	}
    	sem_post(listLock);  // unlocked
    
    
    // mmap file
    	void *map = mmap(0, MMAPSZ, PROT_READ | PROT_WRITE, MAP_SHARED, mfd, 0);
    	if (map == MAP_FAILED) {
    		perror("mmap()");
    		return -1;
    	}
    	// use first 4 bytes to indicate current offset
    	i = 4 + sizeof(node*);
    	memcpy(map, &i, 4);
    	// then pointer to list head, initially NULL
    	memset(map+4, 0, sizeof(node*));
    
    // fork into two processes
    	pid_t pid = fork();
    	if (!pid) {
    	// child
    		char *words[5] = { "one", "two", "three", "four", "five" };
    		process(mfd, listLock, map, words, 5);
    		exit(0);
    	} else {
    	//parent
    		char *words[5] = { "six", "seven", "eight", "nine", "ten" };
    		int status;
    		process(mfd, listLock, map, words, 5);
    
    		waitpid(pid, &status, 0);
    
    	// everybody's done, walk list
    		node *cur;
    		memcpy(&cur, map+4, sizeof(node*));
    		while (cur) {
    			puts(cur->data);
    			cur = cur->next;
    		}
    
    		sem_close(listLock);
    		sem_unlink("/listLock");
    		close(mfd);
    	}
    
    	return 0;
    }
    Example output:
    Adding six...
    Adding one...
    Adding seven...
    Adding two...
    Adding eight...
    Adding three...
    Adding nine...
    Adding four...
    Adding ten...
    Adding five...
    five
    ten
    four
    nine
    three
    eight
    two
    seven
    one
    six


    Notice the list has a FILO ordering.

    You should consult the linux man pages for all the unfamiliar commands. I'd also recommend the POSIX pages as they provide more depth:

    The Open Group Base Specifications Issue 7
    Last edited by MK27; 12-17-2011 at 10:35 AM. Reason: reduced use of memcpy
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  8. #8
    Registered User
    Join Date
    Dec 2011
    Posts
    8
    Quote Originally Posted by MK27 View Post
    Whether you use completely separate programs or fork depends on how much common ground there is between the processes. At the very least, they would be compiled with a common object file for the mmap and list handling. That's all there is to my demo, so I used fork.

    In real life I would do this kind of thing with threads, so this was a good exercise for me as I've never done it. It works, but there could be an easier way, and there could be problems with this I don't see.

    The big issue with mmap is that you have to decide how much space you will need in advance, because



    I actually did try a version that dynamically grew the file, it definitely led to "unspecified", lol.

    The basic idea here is that the first 4 bytes of the mmap contain an offset to the end of the used space, and after those four bytes a pointer value to the current list head. This would make deletions very awkward; it would be a better idea to write a memory pool using the mmap space and then have the linked list use that interface. Which is a lot more work.

    The sleep() call is not necessary, but without it, what will most likely happen is one process will accomplish everything it needs to do in one go (it will keep re-aquiring the lock it releases) because the task here is so simple. So for the demo, sleep() allows them to alternate.

    There is not much point to this unless you actually have something for the processes to do outside the locked section, eg, rather than being handed all the input up front, they might be reading it from a socket or other external source. But anything that actually involves the mmap (which is where the list is) must be done inside the locked section.

    This must be linked to the "real time" lib for semaphores, so compile -lrt. You may also need -std=gnu99 because of the declarations.

    Code:
    #include <stdio.h>
    #include <unistd.h>
    #include <stdlib.h>
    #include <string.h>
    #include <semaphore.h>
    #include <sys/mman.h>
    #include <fcntl.h>
    #include <inttypes.h>
    #include <sys/wait.h>
    
    /* compile -lrt */
    
    #define MMAPSZ 1024
    
    typedef struct _node {
        char *data;
        struct _node *next;
    } node;
    
    int addNode (node *addr, node *head, char *data) {
        fprintf(stderr,"Adding %s...\n", data);
        addr->data = strcpy((char*)(addr + sizeof(node)), data);
        addr->next = head;
        return sizeof(node) + strlen(data) + 1;
    }
    
    void process (int fd, sem_t *lock, void *map, char *words[], int n) {
        uint32_t *offset = map;
        int i;
        node **head = map + 4, *cur;
        for (i = 0; i < n; i++) {
            sem_wait(lock);
    /*********  LOCKED SECTION *********/
        // set address for new node
            cur = map + *offset;
        // add node
            *offset += addNode(cur, *head, words[i]);
        // set head to new node address
            *head = cur;
            sem_post(lock);
    /***********************************/
            sleep(1);
        }
    }
    
    int main(int argc, const char *argv[]) {
    // file for map
        int mfd = open("mmap", O_CREAT | O_RDWR | O_TRUNC);
        int32_t i;
        if (mfd < 0) {
            perror("open() 'mmap'");
            return -1;
        }
        // file must sized before mmap call
        for (i = 0; i < MMAPSZ; i += 4) write(mfd, &i, 4);
    
    // semaphore for locking list
        sem_unlink("/listlock");
        sem_t *listLock = sem_open("/listlock", O_CREAT | O_EXCL, S_IRUSR | S_IWUSR, 0);
        if (listLock == SEM_FAILED) {
            perror("sem_open() '/listLock'");
            return -1;
        }
        sem_post(listLock);  // unlocked
    
    
    // mmap file
        void *map = mmap(0, MMAPSZ, PROT_READ | PROT_WRITE, MAP_SHARED, mfd, 0);
        if (map == MAP_FAILED) {
            perror("mmap()");
            return -1;
        }
        // use first 4 bytes to indicate current offset
        i = 4 + sizeof(node*);
        memcpy(map, &i, 4);
        // then pointer to list head, initially NULL
        memset(map+4, 0, sizeof(node*));
    
    // fork into two processes
        pid_t pid = fork();
        if (!pid) {
        // child
            char *words[5] = { "one", "two", "three", "four", "five" };
            process(mfd, listLock, map, words, 5);
            exit(0);
        } else {
        //parent
            char *words[5] = { "six", "seven", "eight", "nine", "ten" };
            int status;
            process(mfd, listLock, map, words, 5);
    
            waitpid(pid, &status, 0);
    
        // everybody's done, walk list
            node *cur;
            memcpy(&cur, map+4, sizeof(node*));
            while (cur) {
                puts(cur->data);
                cur = cur->next;
            }
    
            sem_close(listLock);
            sem_unlink("/listLock");
            close(mfd);
        }
    
        return 0;
    }
    Example output:
    Adding six...
    Adding one...
    Adding seven...
    Adding two...
    Adding eight...
    Adding three...
    Adding nine...
    Adding four...
    Adding ten...
    Adding five...
    five
    ten
    four
    nine
    three
    eight
    two
    seven
    one
    six


    Notice the list has a FILO ordering.

    You should consult the linux man pages for all the unfamiliar commands. I'd also recommend the POSIX pages as they provide more depth:

    The Open Group Base Specifications Issue 7
    That is a great example thank you! Is there a way for a parent process to have two children? Or should I make "grandchilds' for the 3rd process? Thanks for all the help =)

  9. #9
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    If you fork in the parent section, the parent forks again. If you fork in the child, you produce a grandchild.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <unistd.h>
    #include <sys/wait.h>
    
    #define NCHLD 5
    
    int main(void) {
    	pid_t pid, children[NCHLD];
    	int i, count = 0, status;
    
    	while (count < NCHLD) {
    		pid = fork();
    		if (!pid) {
    			fprintf(stderr,"\tChild #%d\n", count + 1);
    			pid = fork();
    			if (!pid) {
    				fprintf(stderr,"\t\tchild of child #%d\n", count + 1);
    				exit (count + 8);
    			} else {
    				if (waitpid(pid, &status, 0) < 0) 
    					perror("waitpid");
    				else fprintf(stderr,"\t#%d reports pid %d exited %d\n", 
    					count + 1, pid, WEXITSTATUS(status));
    				exit (count);
    			}
    		}
    		children[count++] = pid;
    	}
    
    	for (i = 0; i < count; i++) {
    		if (waitpid(children[i], &status, 0) < 0)
    			perror("waitpid");
    		else fprintf(stderr,"#%d, pid %d exited %d\n", i + 1,
    			children[i], WEXITSTATUS(status));
    	}
    
    	return 0;
    }
    Example output:
    Code:
    	Child #1
    	Child #5
    	Child #4
    	Child #2
    		child of child #1
    	Child #3
    		child of child #2
    		child of child #5
    		child of child #4
    	#5 reports pid 3763 exited 12
    	#1 reports pid 3762 exited 8
    		child of child #3
    #1, pid 3757 exited 0
    	#3 reports pid 3766 exited 10
    	#4 reports pid 3764 exited 11
    	#2 reports pid 3765 exited 9
    #2, pid 3758 exited 1
    #3, pid 3759 exited 2
    #4, pid 3760 exited 3
    #5, pid 3761 exited 4
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. ICP using shared memory - how to sync child processes?
    By synthetix in forum C Programming
    Replies: 15
    Last Post: 06-15-2011, 12:59 PM
  2. multiple processes accessing same shared library
    By yogeeshgv in forum Linux Programming
    Replies: 1
    Last Post: 07-28-2010, 02:18 PM
  3. accessing shared memory via forked processes
    By rklockow in forum C Programming
    Replies: 7
    Last Post: 06-30-2010, 05:44 PM
  4. Replies: 7
    Last Post: 02-06-2009, 12:27 PM