UNIX Socket FAQ

A forum for questions and answers about network programming on Linux and all other Unix-like systems

You are not logged in.

#1 2008-05-12 10:43 AM

shivamasam
Member
Registered: 2007-03-13
Posts: 8

Re: Mutex locked element Queue

Hi

I am trying to create a queue, where in each element is mutex locked. This exercise is intended to perform any operation on the Queue to be in the following way.

1. Acquire a mutex lock for that element.
2. Perform the necessary action (like insertion or deletion or displaying on screen).
3. Unlock the mutex lock.

I have written some code to acheive this. but however only insertion process seems to be working fine but when i try other operation (like deletion or display) it is entering into a dead lock situation. I have tried a lot, but not able to find out the loop hole in my program.

Please take a look at the program and help in finding the fault.

#include<stdio.h>
#include<pthread.h>


#define FALSE 0
#define NULL 0

typedef struct list
        {
                pthread_mutex_t mp;
                int     dataitem;
                struct listelement *link;
        }listelement;
    listelement listmember, *listpointer;

void Menu (int *choice);
listelement * AddItem (listelement * listpointer, int data);
listelement * RemoveItem (listelement * listpointer);
void PrintQueue (listelement * listpointer);
void ClearQueue (listelement * listpointer);

main ()
{
    int     data,choice;

    listpointer = NULL;
    do {
        Menu (&choice);
        switch (choice) {
            case 1:
                printf ("Enter data item value to add  ");
                scanf ("%d", &data);
                listpointer = (listelement *) malloc(sizeof(struct list));
                if(listpointer == NULL)
                {
                        printf("\n unable to allocate memory...");
                        exit(1);
                }
                pthread_mutex_init(&listpointer->mp,NULL);
                listpointer = AddItem (listpointer, data);
                break;
            case 2:
                if (listpointer == NULL)
                    printf ("Queue empty!\n");
                else
                    listpointer = RemoveItem (listpointer);
                break;
            case 3:
                PrintQueue (listpointer);
                break;

            case 4:
                break;

            default:
                printf ("Invalid menu choice - try again\n");
                break;
        }
    } while (choice != 4);
    ClearQueue (listpointer);
}                               /* main */
void Menu (int *choice)
{

    char    local;

    printf ("\nEnter\t1 to add item,\n\t2 to remove item\n\t3 to print queue\n\t4 to quit\n");
    do {
        local = getchar ();
        if ((isdigit (local) == FALSE) && (local != '\n')) {
            printf ("\nyou must enter an integer.\n");
            printf ("Enter 1 to add, 2 to remove, 3 to print, 4 to quit\n");
        }
    } while (isdigit ((unsigned char) local) == FALSE);
    *choice = (int) local - '0';
}

listelement * AddItem (listelement * listpointer, int data)
{

    listelement * lp = listpointer;

    if (listpointer != NULL)
    {
        while (listpointer -> link != NULL)
        {
                pthread_mutex_lock(&listpointer->mp);
            listpointer = listpointer -> link;
                pthread_mutex_unlock(&listpointer->mp);
        }
        pthread_mutex_lock(&listpointer->mp);
        listpointer -> link = (listelement  *) malloc (sizeof (listelement));
        listpointer = listpointer -> link;
        listpointer -> link = NULL;
        listpointer -> dataitem = data;
        pthread_mutex_unlock(&listpointer->mp);
        return lp;
    }
    else
    {
        pthread_mutex_lock(&listpointer->mp);
        listpointer -> link = NULL;
        listpointer -> dataitem = data;
        pthread_mutex_unlock(&listpointer->mp);
        return listpointer;
    }
}
listelement * RemoveItem (listelement * listpointer)
{

    listelement * tempp;
            pthread_mutex_lock(&listpointer->mp);
    printf ("Element removed is %d\n", listpointer -> dataitem);
    tempp = listpointer -> link;
        pthread_mutex_unlock(&listpointer->mp);
        pthread_mutex_destroy(&listpointer->mp);
    free (listpointer);
    return tempp;

}

void PrintQueue (listelement * listpointer) {

    if (listpointer == NULL)
        printf ("queue is empty!\n");
    else
        while (listpointer != NULL)
        {
                pthread_mutex_lock(&listpointer->mp);
            printf ("%d\t", listpointer -> dataitem);
            listpointer = listpointer -> link;
                pthread_mutex_unlock(&listpointer->mp);
        }
    printf ("\n");
}

void ClearQueue (listelement * listpointer) {

    while (listpointer != NULL) {
        listpointer = RemoveItem (listpointer);
    }
}

Offline

#2 2008-05-12 12:01 PM

i3839
Oddministrator
From: Amsterdam
Registered: 2003-06-07
Posts: 2,230

Re: Mutex locked element Queue

First fix all compiler warnings. Especially the "assignment from incompatible
pointer type" ones. Compile with most warnings enabled, so -Wall, -W for gcc.
You also forgot to include stdlib.h and ctype.h.

Also, are you trying to make a linked list and also use it as a queue, or do you just
want to make a queue? If you're using it strictly as a queue, only adding items at
the end and removing them at the front, you just need to keep track of a head and
a tail pointer (or use a circular list) and lock those instead of all elements, which
you never need to touch anyway. So having a separate head and tail mutex is
enough to protect the queue. That makes your code much simpler and struct list
a lot smaller. Assuming no one touches items while they are in the queue, but only
adds them or removes them. If they do it's more a linked list any way.

Your locking scheme doesn't seem to make much sense, what are the locks
trying to protect exactly? (ignoring it's a single threaded app for the moment.)
Just look at AddItem(), for instance: You uses mutexes to read the link pointer
savely. So apparently link can be invalidated at any time. But if so, you need to
hold the lock until you're done with it, and not release it inbetween like you do
now.

You also return lp instead of listpointer, sure that's what you want?

Offline

#3 2008-05-12 01:39 PM

RobSeace
Administrator
From: Boston, MA
Registered: 2002-06-12
Posts: 3,826
Website

Re: Mutex locked element Queue

Yeah, that code just looks all kinds of wrong...  In your switch() case 1, you malloc()
and assign directly to the global variable "listpointer"...  You never set "link" to NULL,
yet AddItem() checks that, so it may be traversing bogus pointers...  Also, AddItem()'s
argument is named "listpointer", which is rather confusing given the global variable of
the same name...  Are you sure you're refering to the correct thing in there??  Also,
every time you add a new item in case 1 of your switch(), you're trashing that global
"listpointer", so your list is never more than 1 element long (while you're leaking the
memory for all previously added elements)...

Not to mention your strange use of mutexes for seemingly no reason, as i3839 says...

Offline

#4 2008-05-12 03:21 PM

mlampkin
Administrator
From: Sol 3
Registered: 2002-06-12
Posts: 911
Website

Re: Mutex locked element Queue

Moved these posts as they seemed more inline with threading ref. pthreads / mutexes than processes...

Not a whole lot to add other than what has already been said...

Other than re-iterating using locks like this on a queue ( actually a list ) doesn't make a lot of sense especially if the items in the list are simple data... 

On the other hand it is fairly common to see this type of setup for structures such as trees - where the intent is not so much to lock the individual nodes as to lock a node so that it and all nodes under it are locked... e.g. if doing an insert and you know its on the left branch(es) then you could lock that temporarily while still allowing all reads / a single insert to still occur on the right side at the same time ( and possibly defer balancing until after the fact )...

So for me the question becomes... are you just testing the idea before moving on to move complex structures or... ?


Michael


"The only difference between me and a madman is that I'm not mad."

Salvador Dali (1904-1989)

Offline

#5 2008-05-13 04:46 AM

shivamasam
Member
Registered: 2007-03-13
Posts: 8

Re: Mutex locked element Queue

Hi All for ur suggestions... Well let me expalin the scenario of what I am trying to do here. I am trying to create a linked list of elements where in each element is mutex locked. Apparently in doing so, It diverted to become a queue... well that was my mistake and it was not the requirement... As michael said... this is only an initial level exercise in  a way of solving complex requirement, where in I have to maitain a linked list of elemnts as a shared resource among multiple threads..and to achieve an optimal performance I want locking to be at an element level, for parallel processing of different  elements of the list by other threads and Use CPU upto its maximum capacity.......  As I understand the current code is not meeting this requirement... I will come up with an another version of code soooon.... Bu let me tell you one thing that if we remove mutex concept from the below code the Queue works fine.... there are no memory leaks and no bogus pointer traversings....

Thanks

Offline

#6 2008-05-13 05:39 AM

jfriesne
Administrator
From: California
Registered: 2005-07-06
Posts: 348
Website

Re: Mutex locked element Queue

If you're planning to let threads modify the list while other threads are reading from it, you'll need to use a mutex to lock access to the list as well.  Otherwise your app will occasionally crash when one thread modifies a pointer just before another thread tries to follow that pointer, etc.

And once you've designated that access to the linked list requires that a list-specific mutex be locked, there's probably not much point to having a mutex per item any more, since it would be redundant with the list's mutex.

I suspect that the idea of having a mutex per item is a case of premature optimization, and that you'd be better off without it.

-Jeremy

Offline

#7 2008-05-13 06:54 AM

shivamasam
Member
Registered: 2007-03-13
Posts: 8

Re: Mutex locked element Queue

Well.... a mutex at an element level  is necessary for some situations. consider a situation like this.

[A] -->1--->2--->3---------------->n
|
[B]--->1--->2--->3---------------->n
|
[C]--->1--->2--->3---------------->n
|
|
|
|
[n]---->1--->2--->3---------------->n

Here first node of each list is a pointer to a linear linked list. This entire list of linked lsits is accessed by multiple threads. suppose one thread is accessing the nth element of list n, then it does not make sense to lock that entire chain.. which will block other threads from accessing that chain list. I agree with u that the lock should be on the link between nodes rather than on the node itself, which willl say, if u are able to access the link to next element it means, the element is not locked by any other, otherwise wait until u acquire a mutex lock for that link.
Suppose a thread is accessing list [A]-->2 element, first it tries to traverse through the list elements until it reaches the desired element position. here the traversal is made atomic by acquiring a mutex lock of link to its next element, which will make sure any other thread is not trying to delete that node at the same time. once we reach the desired element position, perform the necessary action and release the mutex lock for that element. this mechanism makes the entire shared memory of lists [except the current mutex locked node] to be accessible by all other threads, which keep on performing necessary actions on this shared memory, thus utilizing the CPU at its best.

I hope my explanation makes some sense.

Thanks

Offline

#8 2008-05-13 08:46 AM

mlampkin
Administrator
From: Sol 3
Registered: 2002-06-12
Posts: 911
Website

Re: Mutex locked element Queue

Actually I had thought of that...

But then figured if you had a larger data set ( heads ) that it would have been either hashed with 'bit buckets' hanging off the end i.e. a hash was actually keyed to a linked list... or distinctively keyed ( indexed ) instead of being accessed by a queue...

Each to their own I guess... ;-)


Michael


"The only difference between me and a madman is that I'm not mad."

Salvador Dali (1904-1989)

Offline

#9 2008-05-13 11:58 AM

RobSeace
Administrator
From: Boston, MA
Registered: 2002-06-12
Posts: 3,826
Website

Re: Mutex locked element Queue

Bu let me tell you one thing that if we remove mutex concept from the below code the Queue works fine.... there are no memory leaks and no bogus pointer traversings....

I find that hard to believe, if you're talking about exactly the same code you posted...
Because, that will definitely destroy the list with each new addition...  Look at your
switch() case 1, where you add a new item: you trash the global variable "listpointer",
which is presumably meant to be the head of your list, with new malloc()'d memory...
You never save the old listpointer anywhere first; and, you never set or clear the "link"
element of that newly allocated node...  Yet, in AddItem(), you assume "link" contains
valid data, and traverse it to reach the end of the list...  Where you malloc() yet
ANOTHER new node...

Offline

#10 2008-05-13 12:43 PM

i3839
Oddministrator
From: Amsterdam
Registered: 2003-06-07
Posts: 2,230

Re: Mutex locked element Queue

Try running it through Valgrind just for kicks. You might be surprised.

Offline

#11 2008-05-13 12:55 PM

shivamasam
Member
Registered: 2007-03-13
Posts: 8

Re: Mutex locked element Queue

yes you are right......

listelement listmember, *listpointer;

this should not be a global declaration.... initially it was declared locally inside main..... then after I have moved it to a global one... it's a mistake....

Thanks

Offline

#12 2008-05-14 08:46 PM

Nope
Administrator
From: Germany
Registered: 2004-01-24
Posts: 385
Website

Re: Mutex locked element Queue

Well.

You have a list of lists. You have to lock the parent list for the search of the right child list. Once you've found that you have to lock the child list, then free the parent one.
There's no other way when you need to keep the data consistent while working with it. And that's for "search" alone. When the list is non-static, meaning you might modify the child list, you'll also modify it's head (which is the entry within the parent list), so you have to keep the parent lock in place.

If you intend to use that as some kind of cache, then you might want to add  a simple "in use" counter to each element to ensure it's not deleted while accessed. No need for a mutex/semaphore here since you already have to serialize the whole list during modify/read anyway.

I've done sth alike in my webserver. But the caches are bound to the virtual server entries. So the cache is part of a class which is in turn in a static list. Perhaps sth alike is more to your needs. (the cache uses a tree for the search and one or several queues for the chache management).

Offline

#13 2008-05-16 07:14 PM

mlampkin
Administrator
From: Sol 3
Registered: 2002-06-12
Posts: 911
Website

Re: Mutex locked element Queue

Just an additional couple of thoughts...

There is yet another reason for using something like a tree in preference over a list in these situations... and ok - I've already stated this but the point of the current message is to provide a bit more detail...

Consider if you had a list with three items A, B and C... and you were actually removing the ( list within the list ) at location B... such an operation will also cause items A and ( possibly ) C to be modified i.e. their next and previous pointers...

There are also concerns if B isn't being removed... even things such as changing the head ( date ) in list B could cause issues...

Due to this you would have two additional duties to perform in such situations...

First is that you really should be locking the main indexes immediately prior to and immediately following the one being manipulated... also for any 'group' operations you have to do an intersection check and locking... e.g. if the main list is A->B->C->D->E ... and you are modifying C... then you have to realize that B, C and D would ( should ) get locked... and so ( again as an example ) understand that a modification of A would cause B to lock and have an overlap...

Now its also easy to see how this design quickly degrades... with potentially 3x more the number of locking checks / ops than are necessary... e.g. A->B->C->D->E->F with mods being performed at the upper level on B and E will cause every node ( 6 of them ) to be locked... and while this situation remains stable no matter how many primary nodes there are i.e. it doesn't necessarily get any worse - it certainly doesn't get any better...

So back to the tree style...

- C
  - B
 |    - D
A 
 |    - E
  - C
      - F

In this style... if we were going to manipulate C then we can simply lock C... if we were possibly going to remove C then we only have to lock B as traversal to both C and D are 'protected' by B's lock...

Not only are the number of lock / unlock operations vastly decreased... but also the number checks for locks is decrease... specifically a list will require on average something along the lines of ( n/2 ) checks... while a tree will require something along ( log n ) checks... both of these ( usually ) inline with the requirements for a normal item search in the specific type of structure...

Just my thoughts...


Michael


"The only difference between me and a madman is that I'm not mad."

Salvador Dali (1904-1989)

Offline

#14 2009-07-30 05:06 PM

i3839
Oddministrator
From: Amsterdam
Registered: 2003-06-07
Posts: 2,230

Re: Mutex locked element Queue

Thanks auzzi.

Just for the record, the problems noted with the posted code don't seem to apply to the original code.

Shivamasam probably got an assignment to extend Dave Marshall's original code to include locking. It's also understandable that he posted the code here when asking for help. But technically that is not legal because of copyright. Whether the code may have been used for the assignment in the first place is unclear too.

I'll email Dave Marshall and ask whether to remove the posted code or not.

UPDATE: Dave Marshall replied that he has no problem with any use of his code for educational purposes.

Offline

Board footer

Powered by FluxBB