Hi Goldwyn .... > There is a system, where processes keep coming at random. Most of the > processes, wait on a global wait variable. IMHO, awaiting on global wait/lock variable should be avoided at all cost whenever possible. It is bad for scalability and concurrency. > So when a wake_up is called all the processes wake up, however only a > certain number are allowed to execute. the rest go back to sleep till > the "certain number" processes have not freed the resources. You mean, "have freed" , right? Then yes, you're correct. > Can such a situation lead to starvation? Of course. The main problem is the processes are awaiting on global lock... > Of what I have found. The sleep_on and wake_up sequence uses list_add > (not list_add_tail) and list_for_each, which I think shows a LIFO > behaviour. Taking the scheduler sequence also into consideration I > think it may lead to process starvation. In some cases, doing O(n) (linear) traversing is inevitable, but in many places in Linux kernel codes, it has been replaced by O(1) (constant) traversing algorithm or something similar like hash or red black tree. In the case on wake_up, yes seems like it is a LIFO sequence. However, it won't bring a problem as long as the developers know only one process is expected to sleep on that wait queue. If not, perhaps it is better to use wake_up_all() macro. The conclusion: yes, there is a starvation. That's why: 1. Avoid big kernel lock and global lock at all cost. Better use lock free algorithm whenever possible. 2. Avoid long lock contention. If it happens, maybe you should re design your codes 3. Scheduler, no matter how good it is, only execute a thread (single flow of execution) at a time on a processor. So, better trim down the number of processes instead forking many ones but eventually landing on sleep state or mostly doing nothing. regards Mulyadi -- Kernelnewbies: Help each other learn about the Linux kernel. Archive: http://mail.nl.linux.org/kernelnewbies/ FAQ: http://kernelnewbies.org/faq/
