Thread scheduling Round Robin / scheduling dispatch

Question

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <semaphore.h> 
#define NUM_THREADS  4
#define COUNT_LIMIT 13
int     done = 0;
int     count = 0;
int     quantum = 2;
int     thread_ids[4] = {0,1,2,3};
int     thread_runtime[4] = {0,5,4,7};
pthread_mutex_t count_mutex;
pthread_cond_t count_threshold_cv;

void * inc_count(void * arg);


static sem_t count_sem;


 int quit = 0;

///////// Inc_Count////////////////
void *inc_count(void *t) 
{
   long my_id = (long)t;
   int i;
   sem_wait(&count_sem);   /////////////CRIT SECTION//////////////////////////////////      
   printf("run_thread = %d\n",my_id);
   printf("%d \n",thread_runtime[my_id]);
   for( i=0; i < thread_runtime[my_id];i++)
      {
         printf("runtime= %d\n",thread_runtime[my_id]);
         pthread_mutex_lock(&count_mutex); 
         count++;
         if (count == COUNT_LIMIT) {
            pthread_cond_signal(&count_threshold_cv);
            printf("inc_count(): thread %ld, count = %d  Threshold reached.\n", my_id,
            count);
         }
      printf("inc_count(): thread %ld, count = %d, unlocking mutex\n",my_id, count);
      pthread_mutex_unlock(&count_mutex);
      sleep(1) ;
      }//End For
   sem_post(&count_sem); // Next Thread Enters Crit Section
   pthread_exit(NULL);
}

/////////// Count_Watch ////////////////
void *watch_count(void *t) 
{
  long my_id = (long)t;
  printf("Starting watch_count(): thread %ld\n", my_id);

  pthread_mutex_lock(&count_mutex);
  if (count<COUNT_LIMIT) {
     pthread_cond_wait(&count_threshold_cv, &count_mutex);
     printf("watch_count(): thread %ld Condition signal received.\n", my_id);
     printf("watch_count(): thread %ld count now = %d.\n", my_id, count);
     }
  pthread_mutex_unlock(&count_mutex);
  pthread_exit(NULL);
}


////////////////// Main ////////////////
int main (int argc, char *argv[])
{
   int i;
   long t1=0, t2=1, t3=2, t4=3;
   pthread_t threads[4];
   pthread_attr_t attr;
   sem_init(&count_sem, 0, 1);
   /* Initialize mutex and condition variable objects */
   pthread_mutex_init(&count_mutex, NULL);
   pthread_cond_init (&count_threshold_cv, NULL);
   /* For portability, explicitly create threads in a joinable state */
   pthread_attr_init(&attr);
   pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);
   pthread_create(&threads[0], &attr, watch_count, (void *)t1);
   pthread_create(&threads[1], &attr, inc_count, (void *)t2);
   pthread_create(&threads[2], &attr, inc_count, (void *)t3);
   pthread_create(&threads[3], &attr, inc_count, (void *)t4);
   /* Wait for all threads to complete */
   for (i=0; i<NUM_THREADS; i++) {
      pthread_join(threads[i], NULL);
   }
   printf ("Main(): Waited on %d  threads. Done.\n", NUM_THREADS);
   /* Clean up and exit */
   pthread_attr_destroy(&attr);
   pthread_mutex_destroy(&count_mutex);
   pthread_cond_destroy(&count_threshold_cv);
   pthread_exit(NULL);
  }

I am trying to learn thread scheduling, there is a lot of technical coding that I don't know. I do know in theory how it should work, but having trouble getting started in code...

I know, at least I think, this program is not real time and its not meant to be. Some how I need to create a scheduler dispatch to control the threads in the order they should run... RR FCFS SJF ect.

Right now I don't have a dispatcher. What I do have is semaphores/ mutex to control the threads.

This code does run FCFS... and I have been trying to use semaphores to create a RR.. but having a lot of trouble. I believe it would be easier to create a dispatcher but I dont know how.

I need help, I am not looking for answers just direction.. some sample code will help to understand a bit more.

Okay, to help understand, my first thought was using semaphores and trying to create a loop such that when one thread runs lets say 2 times that thread waits for the other threads to run two times or until the run time is up.

What I had problems with was that there seemed to be no good way of synchronizing the threads this way. Unless there is a way to make a unique semaphore for each thread. This is why I would like some help or guidance in creating a dispatcher function.

Thank you.

Answer 1

First, the OS is the only entity in your system that can actually schedule your threads to run. The most common schedulers in newer Linux kernels are static-priority FCFS and RR, as well as the SCHED_OTHER scheduler, now implemented by the completely-fair scheduler.

It seems that you are confusing the notion of "OS-level scheduling" v.s. "application-level scheduling". The former knows nothing about your application nor its semantics. The later must be implemented using tools such as semaphores, queues, etc...

One approach to implementing a set of threads executing in a FCFS manner would be create a FIFO queue, protect it with a mutex, and within this queue put tokens that allow threads to know when it is their turn to run.

The psuedo-code for a thread would be:

while (1)
   lock_mutex()
   next = pop_queue()
   if (next == me)
      do_my_work()
      unlock_mutex()
      break
   unlock_muteX()

Note that this example shouldn't be used as-is. It requires careful coordination between consumer and producer, as well as other consumers. It also doesn't address more detailed semantics such as should work be serialized, or simply the beginning of work to be FCFS, or the relation between the number of threads and available CPUs.