Problem 1: Constraint Satisfaction (50 points)

Problem G: Additional Graduate Credit Problem (20 points)

hw3.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>

#define MAX_TASKS 128
#define MAX_PROCS 64

typedef struct bin_s
{
    bool same;
    bool not_same;
    int not_proc1;
    int not_proc2;
} bin_t;

typedef struct task_s
{
    int id;
    int length;
    bool allow_proc[MAX_PROCS];
    bin_t bin[MAX_TASKS];
    int proc;
    int saved_proc;
} task_t;

int ntasks;
int nproc;
int deadline;
task_t tasks[MAX_TASKS];
int least_cost = INT_MAX;
int proc_costs[MAX_PROCS];

/* get a line from the console and strip off the trailing \n if present */
char *mygets(char *s, int size)
{
    char *ret, *p;
    ret = fgets(s, size, stdin);
    if ((p = strchr(s, '\n'))) *p = '\0';
    return ret;
}

int mygeti()
{
    char buff[256];
    mygets(buff, sizeof(buff));
    return (atoi(buff));
}

/* prompts for a nonnegative integer from the user */
int prompt_int(char *prompt)
{
    int ret;
    for (;;)
    {
 printf("%s", prompt);
 ret = mygeti();
 if (ret > 0)
     break;
 printf("please enter a positive number\n");
    }
    return ret;
}

/* gets information about the problem from the user */
void get_problem_info(void)
{
    char buff[256], *tok;
    int i, j;

    ntasks = prompt_int("number of tasks: ");
    for (i = 0; i < ntasks; i++)
    {
 tasks[i].id = i + 1;
 for (j = 0; j < MAX_PROCS; j++)
     tasks[i].allow_proc[j] = true;
 for (j = 0; j < ntasks; j++)
 {
     tasks[i].bin[j].same = false;
     tasks[i].bin[j].not_same = false;
     tasks[i].bin[j].not_proc1 = 0;
     tasks[i].bin[j].not_proc2 = 0;
 }

 sprintf(buff, "\tlength of task %d (in sec.): ", tasks[i].id);
 tasks[i].length = prompt_int(buff);
    }

    printf("\n");
    nproc = prompt_int("number of processors: ");
    for (i = 1; i <= nproc; i++)
    {
 sprintf(buff, "\tcost of processor %d (in dollars per sec.): ", i);
 proc_costs[i] = prompt_int(buff);
    }

    printf("\n");
    deadline = prompt_int("deadline (in sec.): ");

    printf("\nunary constraints:\n");
    for (i = 0; i < ntasks; i++)
    {
 int first_constraint = 0;
 printf("\tt%d: ", tasks[i].id);
 mygets(buff, sizeof(buff));
 if (!*buff || strcmp(buff, "none") == 0)
     continue;
 tok = strtok(buff, ", ");
 while (tok)
 {
     if (tok[0] == 'p' && first_constraint != 2)
     {
  int proc = atoi(tok + 1);
  if (proc >= 0)
  {
      if (first_constraint == 0)
   for (j = 0; j < nproc; j++)
       tasks[i].allow_proc[j] = false;
      tasks[i].allow_proc[proc] = true;
      first_constraint = 1;
  }
  else
      printf("warning: invalid constraint: %s\n", tok);
     }
     else if (tok[0] == '!' && tok[1] == 'p' && first_constraint != 1)
     {
  int proc = atoi(tok + 2);
  if (proc >= 0)
  {
      tasks[i].allow_proc[proc] = false;
      first_constraint = 2;
  }
  else
      printf("warning: invalid constraint: %s\n", tok);
     }
     else
  printf("warning: invalid constraint: %s\n", tok);
     tok = strtok(NULL, ", ");
 }
    }

    printf("\nbinary constraints:\n");
    for (i = 0; i < ntasks; i++)
    {
 for (;;)
 {
     int task;
     printf("\tt%d: ", tasks[i].id);
     mygets(buff, sizeof(buff));
     if (!*buff || strcmp(buff, "none") == 0)
  break;
     tok = strtok(buff, ": ");
     if (!tok || tok[0] != 't' || (task = atoi(tok + 1) - 1) <= 0)
     {
  printf("warning: invalid constraint: %s\n", tok);
  continue;
     }
     tok = strtok(NULL, ": ");
     if (!tok)
     {
  printf("warning: lack of constraint\n");
  continue;
     }
     if (strcmp(tok, "same") == 0)
     {
  tasks[i].bin[task].same = true;
  tasks[task].bin[i].same = true;
     }
     else if (strcmp(tok, "!same") == 0)
     {
  tasks[i].bin[task].not_same = true;
  tasks[task].bin[i].not_same = true;
     }
     else if ((tok[0] == '!' && tok[1] == '(' && tok[2] == 'p'))
     {
  tasks[task].bin[i].not_proc1 = atoi(strrchr(tok, 'p') + 1);
  tasks[task].bin[i].not_proc2 = atoi(strchr(tok, 'p') + 1);
     }
     else
  printf("warning: invalid constraint: %s\n", tok);
 }
    }
 

}

/* compare routine used for sorting tasks
 * longer tasks come before shorter ones */
int task_compar(const void *a, const void *b)
{
    const task_t *ta = a, *tb = b;

    if (ta->length > tb->length)
 return -1;
    if (ta->length < tb->length)
 return 1;
    return 0;
}

/* time used by processes already scheduled on p */
int time_on_proc(int after_task, int p)
{
    int i, ret = 0;
    for (i = 0; i < after_task; i++)
    {
 if (tasks[i].proc == p)
     ret += tasks[i].length;
    }
    return ret;
}

/* print out the assignment found */
void print_assignment(void)
{
    int p, i, offset;

    printf("\n");
    for (p = 1; p <= nproc; p++)
    {
 printf("processor %d: ", p);
 i = 0;
 offset = 0;
 for (i = 0; i < ntasks; i++)
 {
     if (tasks[i].saved_proc == p)
  printf("t%d ", tasks[i].id);
 }
 printf("\n");
    }
    printf("\n");
}

/* find the cost of a given assignment */
int cost_assignment(void)
{
    int i, cost = 0;
    for (i = 0; i < ntasks; i++)
 cost += tasks[i].length * proc_costs[tasks[i].proc];

    return cost;
}

/* find an assignment, assuming that all tasks before first_task are already assigned */
void find_assignment(int first_task)
{
    int p, i, t;

    /* recursive base case
     * if this assignment is cheaper than any so far, save it */
    if (first_task >= ntasks)
    {
 int cost;
 if ((cost = cost_assignment()) < least_cost)
 {
     least_cost = cost;
     for (i = 0; i < ntasks; i++)
  tasks[i].saved_proc = tasks[i].proc;
 }
 return;
    }

    /* look for processor to schedule this task on */
    for (p = 1; p <= nproc; p++)
    {
 /* unary constraints */
 if (!tasks[first_task].allow_proc[p])
     continue;

 /* deadline constraint */
 t = time_on_proc(first_task, p);
 if (tasks[first_task].length > deadline - t)
     continue;

 /* binary constraints */
 for (i = 0; i < first_task; i++)
 {
     if (tasks[first_task].bin[tasks[i].id - 1].same &&
  tasks[i].proc != p)
  break;

     if (tasks[first_task].bin[tasks[i].id - 1].not_same &&
  tasks[i].proc == p)
  break;

     if (tasks[first_task].bin[tasks[i].id - 1].not_proc2 == tasks[i].proc &&
  tasks[first_task].bin[tasks[i].id - 1].not_proc1 == p)
  break;
 }
 if (i < first_task)
     continue;

 /* schedule this task on this processor */
 tasks[first_task].proc = p;

 /* recurse */
 find_assignment(first_task + 1);
    }

    /* out of options */
    return;
}

int main(void)
{
    get_problem_info();

    /* sort tasks using the heuristic:
     * longer tasks get assigned before shorter ones */
    qsort(tasks, ntasks, sizeof(tasks[0]), task_compar);

    find_assignment(0);

    if (least_cost != INT_MAX)
 print_assignment();   /* found one */
    else
 printf("no assignment possible\n");

    return 0;
}
 

Case 1 :
 

number of tasks: 5
        length of task 1 (in sec.): 7
        length of task 2 (in sec.): 8
        length of task 3 (in sec.): 6
        length of task 4 (in sec.): 7
        length of task 5 (in sec.): 9

number of processors: 3
        cost of processor 1 (in dollars per sec.): 1
        cost of processor 2 (in dollars per sec.): 1
        cost of processor 3 (in dollars per sec.): 1

deadline (in sec.): 20

unary constraints:
        t1: !p1
        t2: p2
        t3: !p3
        t4: none
        t5: p1

binary constraints:
        t1: t2: !same
        t1: none
        t2: none
        t3: t4: same
        t3: none
        t4: none
        t5: none

processor 1: t5
processor 2: t1 t4 t3
processor 3: t2
 
 

 
number of tasks: 5
        length of task 1 (in sec.): 9
        length of task 2 (in sec.): 8
        length of task 3 (in sec.): 9
        length of task 4 (in sec.): 8
        length of task 5 (in sec.): 9

number of processors: 3
        cost of processor 1 (in dollars per sec.): 1
        cost of processor 2 (in dollars per sec.): 1
        cost of processor 3 (in dollars per sec.): 1

deadline (in sec.): 16
unary constraints:
        t1: p1
        t2: p2
        t3: !p2
        t4: p3
        t5: none

binary constraints:
        t1: t5: !same
        t1: none
        t2: none
        t3: t5: same
        t3: none
        t4: t3: same
        t4: none
        t5: none
no assignment possible