Process starvation
We can demonstrate this condition by showing a simple process containing two threads that use mutual exclusion locks to manage a critical section. Thread 1 runs at a high priority, while Thread 2 runs at a lower priority. Essentially, each thread runs through a segment of code that looks like this:
Thread1 Thread 2
... ...
(Run at high priority) (Run at low priority)
while true while true
do do
obtain lock a obtain lock a
(compute section1) (compute section1)
release lock a release lock a
done done
... ...
The code segments for each thread is shown below; the only difference being the priorities of the two threads. Upon execution, Thread 2 eventually starves.
/* mutexstarvation.c */
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <signal.h>
#include <pthread.h>
#include <process.h>
#include <sys/neutrino.h>
#include <sys/procfs.h>
#include <sys/procmgr.h>
#include <ha/ham.h>
pthread_mutex_t mutex_a = PTHREAD_MUTEX_INITIALIZER;
FILE *logfile;
int doheartbeat=0;
#define COMPUTE_DELAY 900
void *func1(void *arg)
{
int id;
id = pthread_self();
while (1) {
pthread_mutex_lock(&mutex_a);
fprintf(logfile, "Thread 1: Locking lock a\n");
delay(rand()%COMPUTE_DELAY+50); /* delay for computation */
fprintf(logfile, "Thread 1: Unlocking lock a\n");
pthread_mutex_unlock(&mutex_a);
}
return(NULL);
}
void *func2(void *arg)
{
int id;
id = pthread_self();
while (1) {
pthread_mutex_lock(&mutex_a);
fprintf(logfile, "\tThread 2: Locking lock a\n");
if (doheartbeat)
ham_heartbeat();
delay(rand()%COMPUTE_DELAY+50); /* delay for computation */
fprintf(logfile, "\tThread 2: Unlocking lock a\n");
pthread_mutex_unlock(&mutex_a);
}
return(NULL);
}
int main(int argc, char *argv[])
{
pthread_attr_t attrib;
struct sched_param param;
ham_entity_t *ehdl;
ham_condition_t *chdl;
ham_action_t *ahdl;
int i=0;
char c;
pthread_attr_t attrib2;
struct sched_param param2;
pthread_t threadID;
pthread_t threadID2;
logfile = stderr;
while ((c = getopt(argc, argv, "f:l" )) != -1 ) {
switch(c) {
case 'f': /* log file */
logfile = fopen(optarg, "w");
break;
case 'l': /* do liveness heartbeating */
if (access("/proc/ham",F_OK) == 0)
doheartbeat=1;
break;
}
}
setbuf(logfile, NULL);
srand(time(NULL));
fprintf(logfile, "Creating separate competing compute thread\n");
if (doheartbeat) {
/* attach to ham */
ehdl = ham_attach_self("mutex-starvation",1000000000UL, 5, 5, 0);
chdl = ham_condition(ehdl, CONDHBEATMISSEDHIGH, "heartbeat-missed-high", 0);
ahdl = ham_action_execute(chdl, "terminate",
"/proc/boot/mutex-starvation-heartbeat.sh", 0);
}
/* create competitor thread */
pthread_attr_init (&attrib2);
pthread_attr_setinheritsched (&attrib2, PTHREAD_EXPLICIT_SCHED);
pthread_attr_setschedpolicy (&attrib2, SCHED_RR);
param2.sched_priority = sched_get_priority_min(SCHED_RR);
pthread_attr_setschedparam (&attrib2, ¶m2);
pthread_create (&threadID2, &attrib2, func2, NULL);
delay(3000); /* let the other thread go on for a while... */
pthread_attr_init (&attrib);
pthread_attr_setinheritsched (&attrib, PTHREAD_EXPLICIT_SCHED);
pthread_attr_setschedpolicy (&attrib, SCHED_RR);
param.sched_priority = sched_get_priority_max(SCHED_RR);
pthread_attr_setschedparam (&attrib, ¶m);
pthread_create (&threadID, &attrib, func1, NULL);
pthread_join(threadID, NULL);
pthread_join(threadID2, NULL);
exit(0);
}
Upon execution, here's what we see:
- Starting two-threaded process.
The threads will execute as described earlier, but eventually Thread 2 will starve. We'll wait for a reasonable amount of time (some seconds) until Thread 2 ends up starving. The threads write a simple execution log in /dev/shmem/mutex-starvation.log.
- Waiting for them to run for a while.
Here's the current state of the threads in process 622610:
pid tid name prio STATE Blocked 622610 1 t/mutex-starvation 10r JOIN 3 622610 2 t/mutex-starvation 1r MUTEX 622610-03 #-2147 622610 3 t/mutex-starvation 63r NANOSLEEP
And here's the tail from the threads' log file:
Thread 1: Unlocking lock a Thread 1: Locking lock a Thread 1: Unlocking lock a Thread 1: Locking lock a Thread 1: Unlocking lock a Thread 1: Locking lock a Thread 1: Unlocking lock a Thread 1: Locking lock a Thread 1: Unlocking lock a Thread 1: Locking lock a
- Extracting core current process information:
/tmp/mutex-starvation.core: processor=ARM num_cpus=2 cpu 1 cpu=602370 name=604e speed=299 flags=0xc0000001 FPU MMU EAR cpu 2 cpu=602370 name=604e speed=299 flags=0xc0000001 FPU MMU EAR cyc/sec=16666666 tod_adj=999522656000000000 nsec=5561011550640 inc=999960 boot=999522656 epoch=1970 intr=-2147483648 rate=600000024 scale=-16 load=16666 MACHINE="mtx604-smp" HOSTNAME="localhost" hwflags=0x000004 pretend_cpu=0 init_msr=36866 pid=622610 parent=598033 child=0 pgrp=622610 sid=1 flags=0x000300 umask=0 base_addr=0x48040000 init_stack=0x4803fa10 ruid=0 euid=0 suid=0 rgid=0 egid=0 sgid=0 ign=0000000006801000 queue=ff00000000000000 pending=0000000000000000 fds=4 threads=3 timers=0 chans=1 thread 1 REQUESTED ip=0xfe32f8c8 sp=0x4803f8a0 stkbase=0x47fbf000 stksize=528384 state=JOIN flags=0 last_cpu=1 timeout=00000000 pri=10 realpri=10 policy=RR thread 2 ip=0xfe32f838 sp=0x47fbef80 stkbase=0x47f9e000 stksize=135168 state=MUTEX flags=4000000 last_cpu=2 timeout=00000000 pri=1 realpri=1 policy=RR thread 3 ip=0xfe32f9a0 sp=0x47f9df20 stkbase=0x47f7d000 stksize=135168 state=NANOSLEEP flags=4000000 last_cpu=2 timeout=0x1001000 pri=63 realpri=63 policy=RR