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.

please help me out with this.. i'm kinda stuck...

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.

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?

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, 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.

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.

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...

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.

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...

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.

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.

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.