Deadlock prevention in C

This is a discussion on Deadlock prevention in C within the C Programming forums, part of the General Programming Boards category; Here is a classical deadlock that wouldn't exist in Java (I think). How can I get around it? Code: struct ...

  1. #1
    Registered User
    Join Date
    Mar 2009
    Location
    Bozen
    Posts
    95

    Deadlock prevention in C

    Here is a classical deadlock that wouldn't exist in Java (I think). How can I get around it?

    Code:
    struct Vertex {
    	char label; // label
    	color clr; // color
    	List* adj; // adjacency list
    	struct Vertex* pred; // predecessor
    	bool critical; // flag if critical vertex
    	int dTime; // discovery time
    	int dist;
    	int ind;
    }; typedef struct Vertex Vertex;
    
    struct List{
    	Vertex* v;
    	struct List* next;
    }; typedef struct List List;
    List* q;

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,258
    You might want to elaborate. I am sure that the wizards in this area would instantly know what you are talking about, but rest of us need to figure out the words of the incantation before we can understand the deep magic.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Yeah I don't see a way out of that either, but I don't think it matters much -- you can just use a void pointer:
    Code:
    struct Vertex {
    	char label; // label
    	color clr; // color
            void *adj; // adjacency list
    [...]
    List *q;
    Vertex V;
    V.adj=q;
    This doesn't require typecasting or anything, so the difference is only noticeable in the definition. Kind of cosmetic.

    [edit] I guess a more proper way would be to use a forward declaration as described by ಠ_ಠ below.
    Last edited by MK27; 05-04-2009 at 08:59 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
    May 2007
    Posts
    147
    [The] rest of us need to figure out the words of the incantation before we can understand the deep magic.
    Poetry


    Deadlock usually refers to threaded programming, where two threads lock against the same resource in such a way that neither will ever release.

    This is a data structure, which offers a containment puzzle - and I 'divine' that's really the point of your inquiry.

    If this is about the compiler not yet being aware of List, is it such a problem to provide a forward declaration?


    As to containment, in this case there's a list of type vertex, where each vertex may have a list.

    The problem relates to 'what owns the Vertex' - since it's likely that the Vertex pointer owned as an "adjacency list" refers to Vertex instances already 'owned' by a list elsewhere (that is, pointers to one Vertex may appear in multiple lists).

    In Java and C# (and a host of similar languages sans pointers), this isn't a problem because every instance is contained by a reference counted containment system kept "under the hood" by the language itself.

    I have to remind myself this is a subject about C, where it's not possible to automatically manage this kind of containment. Indeed, it's a classic problem in C development. Still, there are libraries that manage reference counted pointers in C, and that would solve the problem - or, a list would have to be 'tagged' in such a way that it's configured NOT to contain (that is, not delete) it's references - or containment would have to recognize the difference between a "primary list" and an "adjacency list" with respect to deletion.

    In C++ one would select a reference counted smart pointer from any number of sources (boost, tr1, etc) which provide services quite similar to Java and C# with respect to the containment management (obviously, not garbage collection, though there are libraries for that, too).
    Last edited by JVene; 05-04-2009 at 08:53 AM.

  5. #5
    Banned ಠ_ಠ's Avatar
    Join Date
    Mar 2009
    Posts
    687
    Quote Originally Posted by simpatico_qa View Post
    Here is a classical deadlock that wouldn't exist in Java (I think). How can I get around it?

    Code:
    struct Vertex {
    	char label; // label
    	color clr; // color
    	List* adj; // adjacency list
    	struct Vertex* pred; // predecessor
    	bool critical; // flag if critical vertex
    	int dTime; // discovery time
    	int dist;
    	int ind;
    }; typedef struct Vertex Vertex;
    
    struct List{
    	Vertex* v;
    	struct List* next;
    }; typedef struct List List;
    List* q;

    put this above your structures
    Code:
    struct List;
    typedef struct List List;
    struct Vertex;
    typedef struct Vertex Vertex;

    Quote Originally Posted by laserlight View Post
    You might want to elaborate. I am sure that the wizards in this area would instantly know what you are talking about, but rest of us need to figure out the words of the incantation before we can understand the deep magic.
    he put the problem in bold
    Last edited by ಠ_ಠ; 05-04-2009 at 08:57 AM.
    ╔╗╔══╦╗
    ║║║╔╗║║
    ║╚╣╚╝║╚╗
    ╚═╩══╩═╝

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,258
    Quote Originally Posted by ಠ_ಠ
    he put the problem in bold
    Oh, now I understand. I was trying to figure out if the critical member variable had anything to do with a critical section.

    Quote Originally Posted by ಠ_ಠ
    put this above your structures
    It would only be necessary to write:
    Code:
    typedef struct List List;
    typedef struct Vertex Vertex;
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by JVene View Post
    As to containment, in this case there's a list of type vertex, where each vertex may have a list.

    The problem relates to 'what owns the Vertex' - since it's likely that the Vertex pointer owned as an "adjacency list" refers to Vertex instances already 'owned' by a list elsewhere (that is, pointers to one Vertex may appear in multiple lists).
    I don't see any "problem" at all (maybe you could explain?) -- this concept of ownership seems out-of-place, and the only sensible issue I can conceive of in relation to this is about the scope of individual instances. Which should be easy to keep track of, right?
    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
    May 2007
    Posts
    147
    My C thinking is rusty, I admit - I have to go back over a decade.

    To a C++ 'thinker' the issue of having a pointer refer to an instance which is contained by something else brings up the question, is the pointer a container or not? That is, will delete have to be called on that pointer.

    In the adjacency list, the vertices included there are not 'owned' by that list - they are for reference only and don't act as containers, but this isn't obvious (and I must assume that's the intent with this snippet). It is by context that one realizes the difference.

    In C++, where one might have containment management in List, the issue would require consideration - when does the list delete a vertex and when does it not?

    In C, functions that manage containment would 'know' which is why by context, whether the list to be deleted was a member of a vertex or some other container.

    But then, too, my point was relative to laserlight's post - we weren't entirely sure what "deadlock" really meant - a term usually used to refer to threaded programming, where the issues of containment are more pertinent.

    This was an issue of declaration order - how the compiler would know what a list was. My point is a tributary based on the ambiguity of 'deadlock'
    Last edited by JVene; 05-04-2009 at 09:40 AM.

  9. #9
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by JVene View Post
    My C thinking is rusty, I admit - I have to go back over a decade.

    To a C++ 'thinker' the issue of having a pointer refer to an instance which is contained by something else brings up the question, is the pointer a container or not? That is, will delete have to be called on that pointer.
    It sounded like you meant something like that; I don't know C++ but I know OO from elsewhere. Since there is no reference counting, etc, in C (unless you impliment it), this is kind of non-sensical in context.

    If you delete/destroy/nullify a struct holding an allocated pointer, even if that pointer is not "referenced" anywhere else nor "owned" by anything else, you still have to free the pointer*. And a pointer will not be allocated anything other than a pointer automatically. So the question "will delete have to be called?" is easy to answer...the answer is always YES.

    *hopefully first, or you will have no handle on it. Which would be a leak. Which means "garbage collection" must be done by the programmer.
    Last edited by MK27; 05-04-2009 at 09:55 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

  10. #10
    Registered User
    Join Date
    Mar 2009
    Location
    Bozen
    Posts
    95
    If I may ask a related pointers question:

    Code:
    void eQ(List* l, Vertex* v){
    	List* new = malloc(sizeof(List*)); new->v = v;
    	if (l == NULL) l = new;
    	else{
    		List* temp = l;
    		while (temp->next != NULL) temp = temp->next;
    		temp->next = new;
    	}
    }
    void connect(Vertex* v, Vertex* u){
    	int i = vIndex(v); int j = vIndex(u);
    	AC[i][j] = 1; AC[j][i] = 1;
    	eQ(v->adj, u); eQ(u->adj, v);
    }
    Now unfortunately exiting eq(..) v->adj and u->adj remain unchanged pointing to null. I know of the solution: v->adj = eQ(v->adj, u) but I'd like to get the 'pointers' solution to work as well. Could someone suggest the code modifications to make to achieve that?

  11. #11
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by simpatico_qa View Post
    Could someone suggest the code modifications to make to achieve that?
    This is where C starts to seem obscure. You need to pass a pointer to a pointer and then dereference it in the function, eg:
    Code:
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    struct this {
    	char *ptr;
    };
    
    void test2 (char **ptr) {
    	*ptr=malloc(12);
    	strcpy(*ptr,"hello world");
    }
    
    void test1 (struct this *ptr) {
    	test2(&ptr->ptr);
    }
    
    int main () {
    	struct this that;
    	test1(&that);
    	printf("%s\n",that.ptr);
    	return 0;
    }
    So going back to your example, the prototype for eQ would be:
    Code:
    	
    void eQ(List** l, Vertex* v);
    and in "connect"
    Code:
    eQ(&v->adj, u); eQ(&u->adj, v);
    Get it?
    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

  12. #12
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by JVene View Post
    Quite certainly not.

    If two pointers identify the same instance, which is likely the case in an adjacency list which may not be a hierarchical storage, but a reference of adjacent items which are contained by a different list, then deletion of what the pointer is pointing to in all cases would lead to double deletions, and crashes - the point I was making.
    Sorry, I misunderstood you rather badly.
    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

  13. #13
    Registered User
    Join Date
    Mar 2009
    Location
    Bozen
    Posts
    95
    fair enough, what about this then:

    Code:
    void dQ(List** l){ if (*l != NULL) *l = *l->next;
    adding brackets around *l should do the trick? What's the logic? This stuff I seem only to learn from other experienced developers and from trial and error.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 10
    Last Post: 07-17-2008, 12:21 PM
  2. Deadlock - graph/edge/cycle - help with terminology
    By patricio2626 in forum C++ Programming
    Replies: 4
    Last Post: 11-24-2006, 04:22 PM
  3. Can i get a deadlock?
    By johny145 in forum Windows Programming
    Replies: 2
    Last Post: 09-18-2005, 07:43 PM
  4. Deadlock
    By Claudigirl in forum C Programming
    Replies: 2
    Last Post: 11-06-2003, 03:11 PM
  5. Guys, need help RE: deadlock avoidance
    By tribal in forum C++ Programming
    Replies: 2
    Last Post: 11-20-2001, 03:31 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21