Page 1 of 2 12 Last
  • Jump to page:
    #1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2010
    Posts
    7
    Rep Power
    0

    Detecting "deadlock" - Interesting question real-time C programming


    I need to detect a deadlock by adding some code to the process's main function or inside his handler (HandleEvent()) using only: NewThread, Semaphore, GetMessage, Write2memory, ReadFromMemory.

    There are 5 processes with their priority:
    processes: t1 t2 t3 t4 t5
    priority: 2 3 4 5 6

    lets say that every process main function looks something like:
    void main()
    {
    GetEvent(event e); //get event from the event's queue.
    HandleEvent(event e); //treat the event and handle it.
    }

    There is a budget of 10 second for all the 5 processes. In other words, we are sure that all 5 processes got CPU's time during 10 sec. If 10 second passed and 2 or more of the processes didn't handle their events, that means they got stuck and they are in "deadlock" position. We want to add some code that eventually we get a message that says "Process X in deadlock". We want to know that when this happens.
    This should be Real-Time in C programming. The solution should be easy and simple, but I haven't found it yet.. Please guys, tell me what you think.. Thanks in advance.
    Daniel.
  2. #2
  3. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2010
    Posts
    7
    Rep Power
    0
    please help me out with this.. i'm kinda stuck...
  4. #3
  5. Transforming Moderator
    Devshed Supreme Being (6500+ posts)

    Join Date
    Mar 2007
    Location
    Washington, USA
    Posts
    14,294
    Rep Power
    9400
    Tell you what. I'll give you a chance to fix this.

    You made three threads. Pick the one you like most - this one, the one in Linux, or the one in Unix - and close the others.

    And for crying out loud, it's only 9am on the East Coast. Expecting an answer in less than 10 minutes is a silly idea.

    Comments on this post

    • nattylife agrees : i still havent had coffee yet
  6. #4
  7. No Profile Picture
    Closet coder
    Devshed Beginner (1000 - 1499 posts)

    Join Date
    Feb 2005
    Location
    Plantation, FL <---south florida
    Posts
    1,431
    Rep Power
    153
    im kinda confused, are you trying to code it so that all processes get equal timeslices and finish properly or are you just trying to see if all processes get their share then debug which processes didnt get any slice?
  8. #5
  9. kill 9, $$;
    Devshed Supreme Being (6500+ posts)

    Join Date
    Sep 2001
    Location
    Shanghai, An tSín
    Posts
    6,898
    Rep Power
    3887
    Originally Posted by requinix
    You made three threads. Pick the one you like most - this one, the one in Linux, or the one in Unix - and close the others.
    I've deleted the Linux one and requested deletion of the one in Unix (this appears to have most relevance to C Programming). Please stick to this this thread. It can be moved to another forum at a later date if it's deemed necessary.
  10. #6
  11. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2010
    Posts
    7
    Rep Power
    0

    Lightbulb


    Originally Posted by nattylife
    im kinda confused, are you trying to code it so that all processes get equal timeslices and finish properly or are you just trying to see if all processes get their share then debug which processes didnt get any slice?

    hi, and thanks for replying.
    this is a question that i had in an interview. its a theoretic question. all i needed was adding something to the processes main functions (it could be: thread, semaphore, messages, read/write).
    I don't need to make sure they get their slice because I know for sure the CPU gives them a slice sometime during every 10 second. its a given data. Therefore, in case a process didn't do anything (didn't take an event from its queue..) for 10 second, then I know it is stuck and in a deadlock mode. i want to know when its a deadlock by printing a message. thanks again.
  12. #7
  13. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2010
    Posts
    7
    Rep Power
    0
    Originally Posted by ishnid
    I've deleted the Linux one and requested deletion of the one in Unix (this appears to have most relevance to C Programming). Please stick to this this thread. It can be moved to another forum at a later date if it's deemed necessary.
    hi ishnid,
    I'm sorry for the 3 threads... i thought it might be belong to the 3 of them. thanks for leaving the one in the C forum. once again. I'm sorry.
  14. #8
  15. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2010
    Posts
    7
    Rep Power
    0
    Originally Posted by requinix
    Tell you what. I'll give you a chance to fix this.

    You made three threads. Pick the one you like most

    And for crying out loud, it's only 9am on the East Coast. Expecting an answer in less than 10 minutes is a silly idea.
    hey requinix,
    I'm sorry for the 3 threads... i thought it might be belong to the 3 of them. thanks for leaving the one in the C forum. once again. I'm sorry.
    and p.s. i wasn't expecting for an answer during the 10 minutes.. i just wanted to see how/if it works...
  16. #9
  17. Contributing User

    Join Date
    Aug 2003
    Location
    UK
    Posts
    5,117
    Rep Power
    1803
    Without knowing the platform (or caring) or what forms of IPC are available, I suggest you create a sixth "watchdog process" that is scheduled at 10 second intervals, all other processes register with the watchdog process, and each time they are scheduled they increment a watchdog counter (which both the watchdog and the application process can access. When the watchdog runs it checks all process counters, any that have not run will have the same count as the last check.

    The counter access should be atomic and non blocking, otherwise you may end up in a state where the watchdog process is deadlocked.
  18. #10
  19. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2010
    Posts
    7
    Rep Power
    0
    Originally Posted by clifford
    Without knowing the platform (or caring) or what forms of IPC are available, I suggest you create a sixth "watchdog process" that is scheduled at 10 second intervals, all other processes register with the watchdog process, and each time they are scheduled they increment a watchdog counter (which both the watchdog and the application process can access. When the watchdog runs it checks all process counters, any that have not run will have the same count as the last check.

    The counter access should be atomic and non blocking, otherwise you may end up in a state where the watchdog process is deadlocked.
    hi clifford,
    thanks for replying. that could be a good idea, but I'm not sure if i can create a new process... i can do new thread. do you think it still works? I though maybe every process writes to a file the clock tick every time the process call the GetEvent() function. then, the sixth process (the watchdog) that runs in 1 priority runs over the 5 files all the time and compare the tick current time with the tick that the process wrote in the last time and check if the delta is over than 10 sec. if it dose, the watchdog print a message about the stuck process. what do you think? could it work with a thread instead of process? can I give priority to a thread? I'm a little confuse of what i can do and what not with threads. anyway if i use a thread i cant let it be deadlock. it must runs all the time with the highest priority.
  20. #11
  21. No Profile Picture
    Contributing User
    Devshed Loyal (3000 - 3499 posts)

    Join Date
    May 2004
    Posts
    3,417
    Rep Power
    887
    There's lots of ways you can solve this problem, but the best way depends on the OS you are targeting. Clifford's concept is very general and applicable in most cases, but you could also have each application run two threads, one for event handling and as a watchdog that would detect the other threads dead-lock state. It's a very simple concept actually, just have the event handling thread mark the time before calling any event handling related functions. Have the other thread compare that time to the current time every second or so and when it's more than 10 seconds difference the watchdog thread issues an error message and kills its application (or just waits to be debugged).

    On Windows, you could register a timer call-back function that would perform the watchdog logic.

    You obviously don't know this subject area well enough to be hired for a job that requires multi-thread/process knowledge or experience. Even if you take our answers and write them down on your pre-interview quiz, you are likely to fail the interview anyway.
    I no longer wish to be associated with this site.
  22. #12
  23. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2010
    Posts
    7
    Rep Power
    0
    Originally Posted by jwdonahue
    There's lots of ways you can solve this problem, but the best way depends on the OS you are targeting. Clifford's concept is very general and applicable in most cases, but you could also have each application run two threads, one for event handling and as a watchdog that would detect the other threads dead-lock state. It's a very simple concept actually, just have the event handling thread mark the time before calling any event handling related functions. Have the other thread compare that time to the current time every second or so and when it's more than 10 seconds difference the watchdog thread issues an error message and kills its application (or just waits to be debugged).

    On Windows, you could register a timer call-back function that would perform the watchdog logic.

    You obviously don't know this subject area well enough to be hired for a job that requires multi-thread/process knowledge or experience. Even if you take our answers and write them down on your pre-interview quiz, you are likely to fail the interview anyway.

    hi,
    thanks for the motivation.. haha..
    i have another question. lets say there is a process that runs two threads. if the process goes into deadlock mode, are the other 2 threads get CPU time or they are stuck as well as the process??? that would help me a lot. i understand that if they get CPU time even if the process is in deadlock then your answer is understandable and you helped me a lot understanding this subject.
    thanks for replying me...
  24. #13
  25. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,645
    Rep Power
    4248
    I think you meant thread rather than process. Here's where it helps to understand threads. There are two types of threads:
    1. Kernel Level Threads - i.e. the OS understands the concept of threads and processes
    2. User Level Threads - i.e. OS only knows about processes, not threads

    With Kernel level threads, the OS knows about threads and context switching between threads happens at OS level. Thread switching takes a little more overhead than user level threads because of the extra overhead of switching from user-mode to kernel-mode and back. On the other hand when you use kernel threads, if one thread does an operation that requires it to block, only that thread is blocked and the other threads in the process continue to run.

    With user level threads, the threading is provided by a third party library. This allows one to run threads even if the OS doesn't support them. A while back, many OSs such as Linux ( <= kernel versions 2.2.xx), NetBSD (< 1.6), OpenBSD, FreeBSD etc. only supported user-level threads via a third party pthread library. User level threads switch faster because there is no need to execute context-switching code to switch from user-mode to kernel-mode. On the other hand, when one thread blocks, the kernel doesn't understand threads and so it sees the process as blocked. Since the OS marks the process as blocked, none of the other threads in the process get a chance to run. There are ways to get around these restrictions. For instance, use non-blocking sockets instead of blocking sockets and before doing a recv(), one could use select() to see if there's data to read or not and so on.
    Last edited by Scorpions4ever; February 23rd, 2010 at 08:28 PM.
    Up the Irons
    What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
    "Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
    Down with Sharon Osbourne

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo
  26. #14
  27. Contributing User

    Join Date
    Aug 2003
    Location
    UK
    Posts
    5,117
    Rep Power
    1803
    Originally Posted by Daniel Drori
    I'm not sure if i can create a new process... i can do new thread. do you think it still works?
    Thread as part of which process? You could do that it may make sense of one of thee processes is responsible for creating the others.

    The issue of threading priority is down to the system you are running it on. Typically I work with embedded systems and RTOSes where everything is a thread rather than a process.
  28. #15
  29. No Profile Picture
    Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    Oct 2007
    Posts
    921
    Rep Power
    537
    Originally Posted by Daniel Drori
    hi, and thanks for replying.
    this is a question that i had in an interview. its a theoretic question.
    Generally, if I was trying to detect a deadlock situation, I'd use some sort of watchdog process (like Clifford suggested). Of course, that is not exclusive to detecting deadlocks - it also detects any circumstance where a thread/process takes longer to do something than expected.

    Even more broadly, the way to detect a deadlock situation is through careful analysis of how the threads/processes interact. That means identifying the circumstances in which one waits on another and, among those circumstances, looking for any potential circular dependencies. (A waiting on B waiting on C ...... waiting on A). That sort of analysis can be difficult but, if done properly, will identify any potential deadlocks.
    Right 98% of the time, and don't care about the other 3%.

    “It has been said that the great scientific disciplines are examples of giants standing on the shoulders of other giants. It has also been said that the software industry is an example of midgets standing on the toes of other midgets.” (Alan Cooper)
Page 1 of 2 12 Last
  • Jump to page:

IMN logo majestic logo threadwatch logo seochat tools logo