Answers/Solutions to Exercises in Chapter 11, Exercise 7
E7: Write a simple multithreaded C program in which some
linked data structure is built. Then the data structure is destroyed. Write
the program intentionally so that a memory leak can happen. It should be a more
sophisticated version of the example from this chapter.
S7: Consider the following program (do not pay attention to colours). It works
fine and the two threads are building a doubly-linked ordered list of names entered by the
user. When done, main() shows the list using the function Show().
Now consider the program without the read code for starting and ending the critical
section. Now the program will behave erratically. Why? Let us first discuss when it will
work fine. If one thread has enough time (and that is why we put sleep(1) in the program) to complete insertion of the name,
everything will be fine. However, if a thread is interrupted before it has time to
complete the insertion, it may corrupt the list causing some links to be "lost":
for instance thread T1 will find out that the list is empty, then it is interrupted by T2
that finds the list to be empty, than T1 executes and makes the entry pointer of the list
point to the node with the name it received as the very first one, then T2 executes and
makes the entry pointer of the list point to the node with the name it received as the
very first one, in essence "loosing" the previous very first node. This can
happen anywhere in the list, "loosing" one or more nodes. If the circumstances
are favourable, the program will not crash, but the list will not be complete and there
will be some "leaked" nodes. If this repeats many time, the memory is leaking in
a grandiose way.
extern "C" { #include <stdio.h> #include <stdlib.h> #include <string.h> #include <pthread.h> } #include "log.h" //variables for indexing of messages by logging functions int logindex=0; int *logi = &logindex; //thread mutex lock for access to the log pthread_mutex_t tlock = PTHREAD_MUTEX_INITIALIZER; //thread mutex lock for critical sections pthread_mutex_t tlock1 = PTHREAD_MUTEX_INITIALIZER; struct DLIST_NODE_STRUCT { char* name; struct DLIST_NODE_STRUCT* next; struct DLIST_NODE_STRUCT* prev; }; typedef struct DLIST_NODE_STRUCT DLIST_NODE; void* doit(void*); void doit1(DLIST_NODE** p); void Insert(char* name,DLIST_NODE** p); void Show(DLIST_NODE* p); pthread_t tid1, tid2; // function main ------------------------------------------------- int main() { DLIST_NODE* p=0; create_log("log.txt"); Msg("going to create the first thread"); pthread_create(&tid1,NULL,doit,(void*)&p); Msg("going to create the second thread"); pthread_create(&tid2,NULL,doit,(void*)&p); Msg("going to wait for the first thread to exit"); pthread_join(tid1,NULL); Msg("the first thread exited"); Msg("going to wait for the second thread to exit"); pthread_join(tid2,NULL); Msg("the second thread exited"); Show(p); Delete(p); exit(0); }//end main // function doit -------------------------------------------------- void* doit(void* p) { doit1((DLIST_NODE**)p); pthread_exit(NULL); return NULL; }//end doit // function doit1 ----------------------------------------------------- void doit1(DLIST_NODE** p) { char buf[100]; int i; for(i = 0; i < 3; i++) { pthread_mutex_lock(&tlock1); // critical section starts printf("thread %u -- enter name: ",pthread_self()); fgets(buf,100,stdin); buf[strlen(buf)-1]='\0'; Insert(buf,p); Msg("thread %u inserted \"%s\" in the list",pthread_self(),buf); pthread_mutex_unlock(&tlock1); // critical section ends sleep(1); } }//end doit1 // function Insert ----------------------------------------------------- void Insert(char* name,DLIST_NODE** p) { DLIST_NODE *q, *q1, *q2; if (*p==0) { *p = (DLIST_NODE*) malloc(sizeof(DLIST_NODE)); (*p)->name = (char*) malloc(strlen(name)+1); strcpy((*p)->name,name); (*p)->next=(*p)->prev=0; return; } if (strcmp(name,(*p)->name)<0) { q = (DLIST_NODE*) malloc(sizeof(DLIST_NODE)); q->name = (char*) malloc(strlen(name)+1); strcpy(q->name,name); q->prev=0; q->next=(*p); (*p)->prev=q; *p=q; return; } for(q1=*p, q=(*p)->next; q!=0 && strcmp(name,q->name)>0; q1=q, q=q->next); q2 = (DLIST_NODE*) malloc(sizeof(DLIST_NODE)); q2->name = (char*) malloc(strlen(name)+1); strcpy(q2->name,name); q2->prev=q1; q2->next=q; q1->next=q2; if (q) q->prev=q2; }// end Insert // function Show -------------------------------------------------------- void Show(DLIST_NODE* p) { for(; p!=0; p=p->next) printf("name=\"%s\"\n",p->name); }//end Show// function Delete ------------------------------------------------------ void Delete(DLIST_NODE* p) { if (p==0) return; Delete(p->next); free((void*)p); }
output on screen:
franek@moore[131] prog11 thread 4 -- enter name: 1 thread 5 -- enter name: 2 thread 4 -- enter name: 3 thread 5 -- enter name: 4 thread 4 -- enter name: 5 thread 5 -- enter name: 6 name="1" name="2" name="3" name="4" name="5" name="6" franek@moore[132]
output in log:
message number = 0, process id = 28465, time and date = 10:44:59 05/09/04 going to create the first thread message number = 1, process id = 28465, time and date = 10:44:59 05/09/04 going to create the second thread message number = 2, process id = 28465, time and date = 10:44:59 05/09/04 going to wait for the first thread to exit message number = 3, process id = 28465, time and date = 10:45:03 05/09/04 thread 4 inserted "1" in the list message number = 4, process id = 28465, time and date = 10:45:05 05/09/04 thread 5 inserted "2" in the list message number = 5, process id = 28465, time and date = 10:45:09 05/09/04 thread 4 inserted "3" in the list message number = 6, process id = 28465, time and date = 10:45:13 05/09/04 thread 5 inserted "4" in the list message number = 7, process id = 28465, time and date = 10:45:15 05/09/04 thread 4 inserted "5" in the list message number = 8, process id = 28465, time and date = 10:45:16 05/09/04 the first thread exited message number = 9, process id = 28465, time and date = 10:45:17 05/09/04 going to wait for the second thread to exit message number = 10, process id = 28465, time and date = 10:45:18 05/09/04 thread 5 inserted "6" in the list message number = 11, process id = 28465, time and date = 10:45:19 05/09/04 the second thread exited
Back to Answers/Solutions Index Back to Answers/Solutions for Chapter 11 Index