• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 3287
  • Last Modified:

dining philosophers problem

hi this is rajesh,
                           the following code is the dining philosophers problem.For that problem  I want
answer for the following questions and I want to know why the dead lock is occcuring in
that problem.The questions are,
Q1. The program as initially written creates and runs only 2
philosophers (and 2 forks).  Run the program multiple times.  What
happens, and does this surprise you?  What is the longest that the
program runs in the trials you perform?  The shortest?


Q2. The header file philo.h contains the definition of constants used
by the program. What happens if you increase the number of
philosophers to 5? to 10? to 100? to 200?  Does this have any effect.
Does the effect surprise you, or not?  Explain your answer.

Caution: When you make a change to a constant, you need to make sure
that you recompile the program.  Changes are of course not actually
reflected in a compiled language, like C, until the program is
recompiled and those changes are added.  If you forget to recompile
while experimenting, you may think you are testing 1 value of the
parameter, when you are actually testing something else.


Q3. What happens if you increase/decrease the think and eat random times of the philosophers?  Does it appear to affect the running of the problem?  Is this$


Q4. Sometimes the output sequence of the thinking or eating messages
appears to be out of order.  For example, with 3 philosophers I saw
this output:


Philosopher <0> is thinking... (entered 262)
Philosopher <1> is thinking... (entered 261)
    philosopher <2> pickedup fork <0>
Philosopher <2> is eating... (entered 260)
    philosopher <2> released fork <0>
    philosopher <2> released fork <2>
Philosopher <2> is thinking... (entered 263)
    philosopher <0> pickedup fork <0>
    philosopher <2> pickedup fork <2>
    philosopher <1> pickedup fork <1>

e.g. The 261'st thinking session appeared after 262 in the output log.

Is this surprising or not.  What is the reason that the output
sequence can appear out of order on the standard output of these
messages?


/*
About this program:
- Implementation of the Dining Philosophers problem,
  - Fig 6.12, Operating Systems, Stallings
 
- Example implementation using Posix threads and semaphores
 
- Each philosopher is assigned a philosopher identification number (pid)
  - pids range from 0 to N-1 (where N is the number of philosophers)
  - likewise forst range from 0 to M-1 where M is the number of forks, and in the
    classic dining philosophers problems M is always equal to N
 
- Each philosopher is implemented as a separate posix thread
 
- Each fork is associated with a Posix semaphore, and accessing a fork by a
  philosopher requires the philosopher to sem_wait() until the fork is available,
  and to sem_post() (e.g. signal) when they are done eating and have put the fork
  back on the table.
 
- Messages are displayed on standard output by the philosopher threads when the
  perform events such as picking up and putting down a fork, and when eating and
  thinking.
 
- This initial implementation has 2 philosophers and 2 forks.
 
 */
 
#include "philo.h"
 
// global arrays, hold the fork semaphores (using Posix sem_t semaphores)
// and the philosopher thread data structures (Posix pthread_t thread structures)
sem_t forks[NUM_FORKS];
pthread_t philosopherThread[NUM_PHILOSOPHERS];
 
 
/*
  Cause philosopher pid to think.  We pick some random amount of time from 0 to
  MAX_THINK_TIME and do a busy wait in this function to represent the philosopher
  thinking.
 
  Parameters:
    pid  An integer, the philosopher identification number of the philosopher who is
         to think.
 */
void think(int pid)
{
    fprintf(stdout, "Philosopher <%d> is thinking... (entered %d)\n", pid, thinkCount++);
 
    // do a spin wait
    int i;
    int thinktime = rand() % MAX_THINK_TIME;
    for (i=0; i<thinktime; i++);
}
 
 
/*
  Cause philosopher pid to eat.  We pick some random amount of time from 0 to
  MAX_EAT_TIME and do a busy wait in this function to represent the philosopher
  eating.  This function is identical to thinking, but we split apart to alow
  easier understanding of the different tasks of the philosopher, and to allow for
  different think/eat times to be easily set and experimented with.
 
  Parameters:
    pid  An integer, the philosopher identification number of the philosopher who is
         to eat.
 */
void eat(int pid)
{
    fprintf(stdout, "Philosopher <%d> is eating... (entered %d)\n", pid, eatCount++);
 
    // do a spin wait
    int i;
    int eattime = rand() % MAX_EAT_TIME;
    for (i=0; i<eattime; i++);
}
/*
  The main function run by a philosopher's thread.  This is an
  implementation from fig 6.12 of Stalling's Operating Systems
  textbook.  The philosopher simply performs an infinite loop of
  thinking, followed by eating, forever an ever (what a life!)  In
  order to eat, the philosopher needs 2 forks, so he/she first tries
  to pick up the fork to their right (where the forkd id is equal to
  the philosopher id), and then tries to get the fork to his/her left
  (fork id = philosopher id + 1).
 
  Parameters:
 
    arg A pointer to (potentially a while array) of arguments.  This
        is part of the defined Posix thread interface.  The main
        function of a Posix thread accepts a single void* arg
        parameter, through which we can pass parameters initially into
        the thread.  We pass the philosopher identification number
        (pid) which is the first thing that the thread extracts and
        saves away before the philosopher starts running.
 */
void *philosophosize(void *arg)
{
    int pid = *((int *)(arg)); // philosopher id
    int fork;
    fprintf(stdout, "Entered philosopher <%d>\n", pid);
 
    while (1)
    {
        think(pid);
 
        fork = pid;
        sem_wait(&forks[fork]);
        fprintf(stdout, "    philosopher <%d> pickedup fork <%d>\n", pid, fork);
        fork = (pid+1) % NUM_FORKS;
        sem_wait(&forks[fork]);
        fprintf(stdout, "    philosopher <%d> pickedup fork <%d>\n", pid, fork);
 
        eat(pid);
 
        fork = (pid+1) % NUM_FORKS;
        sem_post(&forks[fork]);
        fprintf(stdout, "    philosopher <%d> released fork <%d>\n", pid, fork);
        fork = pid;
        sem_post(&forks[fork]);
        fprintf(stdout, "    philosopher <%d> released fork <%d>\n", pid, fork);
 
    }
 
   return NULL;
}
 
/*
  Program main function.  We create the semaphores and threads to be
  run by the program, then perform joins to wait for all the threads
  to finish (not really relevant in this program, as the threads are
  programmed to run forever, so they never finsih, and the joins never
  return).
 
  One note: when creating the threads using pthread_create, note that
  we initialize the arg integer array with the the philosopher id
  number.  this arg is passed into the newly created thread, so that
  it knows what its pid is when it begins executing.
 
  Parameters:
    argc The number of command line arguments, unused in this program
    argv An array of strings containing the command line arguments, also unused
 
 */
int main(int argc, char **argv)
{
 
 
    // create the semaphores for the forks
    int i;
    for (i=0; i<NUM_FORKS; i++)
    {
        if (sem_init(&forks[i], 0, 1))
        {
            perror("Unable to initialize fork semaphore");
        }
    }
 
    // let's create our threads
    int arg[NUM_PHILOSOPHERS];
    for (i=0; i<NUM_PHILOSOPHERS; i++)
    {
        arg[i] = i;
        if (pthread_create(&philosopherThread[i], NULL, philosophosize, &arg[i]))
        {
            perror("Unable to create philosopher thread");
        }
    }
 
    // join threads, waits till all threads are done
    for (i=0; i<NUM_PHILOSOPHERS; i++)
    {
        pthread_join(philosopherThread[i], NULL);
    }
 
    // everything is finished, print out the number of operations performed
    fprintf(stdout, "Philosophsizing is done\n");
    return EXIT_SUCCESS;
}

Open in new window

0
annerajgadu
Asked:
annerajgadu
  • 9
  • 2
5 Solutions
 
Duncan RoeSoftware DeveloperCommented:
Is this a college assignment or what? Experts cannot do your homework for you. Anyway, you need to post philo.h
0
 
annerajgaduAuthor Commented:
No it's not a college assignment .I saw this problem in compitetive book in practice.here I am attaching philo.h...............plz give me answer as fast as possible.........I am waiting for u r solution.........


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <sched.h>
#include <ctype.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>

const int NUM_PHILOSOPHERS = 100;
const int MAX_THINK_TIME = 100;
const int MAX_EAT_TIME = 100;

const int NUM_FORKS = NUM_PHILOSOPHERS;  // should always be equal in classic dining philosophers problem

int thinkCount = 0;
int eatCount = 0;

void *philosophosize(void *arg);

int main(int argc, char **argv);




0
 
annerajgaduAuthor Commented:

   Hiii following is the code for dining philosophers problem...can u help me in finding the part of code where dead lock occurs?I tried a lot..but may be I misunderstood the code..also are the functions sem_wait,sem_post...are in-built??Please clarify my doubt
/*
About this program:
- Implementation of the Dining Philosophers problem,
  - Fig 6.12, Operating Systems, Stallings
 
- Example implementation using Posix threads and semaphores
 
- Each philosopher is assigned a philosopher identification number (pid)
  - pids range from 0 to N-1 (where N is the number of philosophers)
  - likewise forst range from 0 to M-1 where M is the number of forks, and in the
    classic dining philosophers problems M is always equal to N
 
- Each philosopher is implemented as a separate posix thread
 
- Each fork is associated with a Posix semaphore, and accessing a fork by a
  philosopher requires the philosopher to sem_wait() until the fork is available,
  and to sem_post() (e.g. signal) when they are done eating and have put the fork
  back on the table.
 
- Messages are displayed on standard output by the philosopher threads when the
  perform events such as picking up and putting down a fork, and when eating and
  thinking.
 
- This initial implementation has 2 philosophers and 2 forks.
 
 */
 
#include "philo.h"
 
// global arrays, hold the fork semaphores (using Posix sem_t semaphores)
// and the philosopher thread data structures (Posix pthread_t thread structures)
sem_t forks[NUM_FORKS];
pthread_t philosopherThread[NUM_PHILOSOPHERS];
 
 
/*
  Cause philosopher pid to think.  We pick some random amount of time from 0 to
  MAX_THINK_TIME and do a busy wait in this function to represent the philosopher
  thinking.
 
  Parameters:
    pid  An integer, the philosopher identification number of the philosopher who is
         to think.
 */
void think(int pid)
{
    fprintf(stdout, "Philosopher <%d> is thinking... (entered %d)\n", pid, thinkCount++);
 
    // do a spin wait
    int i;
    int thinktime = rand() % MAX_THINK_TIME;
    for (i=0; i<thinktime; i++);
}
 
 
/*
  Cause philosopher pid to eat.  We pick some random amount of time from 0 to
  MAX_EAT_TIME and do a busy wait in this function to represent the philosopher
  eating.  This function is identical to thinking, but we split apart to alow
  easier understanding of the different tasks of the philosopher, and to allow for
  different think/eat times to be easily set and experimented with.
 
  Parameters:
    pid  An integer, the philosopher identification number of the philosopher who is
         to eat.
 */
void eat(int pid)
{
    fprintf(stdout, "Philosopher <%d> is eating... (entered %d)\n", pid, eatCount++);
 
    // do a spin wait
    int i;
    int eattime = rand() % MAX_EAT_TIME;
    for (i=0; i<eattime; i++);
}
/*
  The main function run by a philosopher's thread.  This is an
  implementation from fig 6.12 of Stalling's Operating Systems
  textbook.  The philosopher simply performs an infinite loop of
  thinking, followed by eating, forever an ever (what a life!)  In
  order to eat, the philosopher needs 2 forks, so he/she first tries
  to pick up the fork to their right (where the forkd id is equal to
  the philosopher id), and then tries to get the fork to his/her left
  (fork id = philosopher id + 1).
 
  Parameters:
 
    arg A pointer to (potentially a while array) of arguments.  This
        is part of the defined Posix thread interface.  The main
        function of a Posix thread accepts a single void* arg
        parameter, through which we can pass parameters initially into
        the thread.  We pass the philosopher identification number
        (pid) which is the first thing that the thread extracts and
        saves away before the philosopher starts running.
 */
void *philosophosize(void *arg)
{
    int pid = *((int *)(arg)); // philosopher id
    int fork;
    fprintf(stdout, "Entered philosopher <%d>\n", pid);
 
    while (1)
    {
        think(pid);
 
        fork = pid;
        sem_wait(&forks[fork]);
        fprintf(stdout, "    philosopher <%d> pickedup fork <%d>\n", pid, fork);
        fork = (pid+1) % NUM_FORKS;
        sem_wait(&forks[fork]);
        fprintf(stdout, "    philosopher <%d> pickedup fork <%d>\n", pid, fork);
 
        eat(pid);
 
        fork = (pid+1) % NUM_FORKS;
        sem_post(&forks[fork]);
        fprintf(stdout, "    philosopher <%d> released fork <%d>\n", pid, fork);
        fork = pid;
        sem_post(&forks[fork]);
        fprintf(stdout, "    philosopher <%d> released fork <%d>\n", pid, fork);
 
    }
 
   return NULL;
}
 
/*
  Program main function.  We create the semaphores and threads to be
  run by the program, then perform joins to wait for all the threads
  to finish (not really relevant in this program, as the threads are
  programmed to run forever, so they never finsih, and the joins never
  return).
 
  One note: when creating the threads using pthread_create, note that
  we initialize the arg integer array with the the philosopher id
  number.  this arg is passed into the newly created thread, so that
  it knows what its pid is when it begins executing.
 
  Parameters:
    argc The number of command line arguments, unused in this program
    argv An array of strings containing the command line arguments, also unused
 
 */
int main(int argc, char **argv)
{
 
 
    // create the semaphores for the forks
    int i;
    for (i=0; i<NUM_FORKS; i++)
    {
        if (sem_init(&forks[i], 0, 1))
        {
            perror("Unable to initialize fork semaphore");
        }
    }
 
    // let's create our threads
    int arg[NUM_PHILOSOPHERS];
    for (i=0; i<NUM_PHILOSOPHERS; i++)
    {
        arg[i] = i;
        if (pthread_create(&philosopherThread[i], NULL, philosophosize, &arg[i]))
        {
            perror("Unable to create philosopher thread");
        }
    }
 
    // join threads, waits till all threads are done
    for (i=0; i<NUM_PHILOSOPHERS; i++)
    {
        pthread_join(philosopherThread[i], NULL);
    }
 
    // everything is finished, print out the number of operations performed
    fprintf(stdout, "Philosophsizing is done\n");
    return EXIT_SUCCESS;
}
 
 
 
 
 
 
The philo.h file is below..
 
 
 
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <sched.h>
#include <ctype.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
 
const int NUM_PHILOSOPHERS = 100;
const int MAX_THINK_TIME = 100;
const int MAX_EAT_TIME = 100;
 
const int NUM_FORKS = NUM_PHILOSOPHERS;  // should always be equal in classic dining philosophers problem
 
int thinkCount = 0;
int eatCount = 0;
 
void *philosophosize(void *arg);
 
int main(int argc, char **argv);

Open in new window

0
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
Duncan RoeSoftware DeveloperCommented:
Some general observations:
- This is a very interesting problem, but also a huge waste of time when I meant to be gardening.
- I modified the source as in the box:
-- Have the compile line as a comment
-- Added prototypes to eliminate compiler warnings
-- Set line buffering on stdout, even when output goes to a file
-- NUM_PHILOSOPHERS needs to be #defined to compile with my gcc rev (also in box). Alternatively NUM_FORKS could have been a #define. Changed both.
12:57:38$ rcsdiff -r1.1 -c ee36.c
===================================================================
RCS file: RCS/ee36.c,v
retrieving revision 1.1
diff -c -r1.1 ee36.c
*** ee36.c      2008/11/08 13:44:25     1.1
--- ee36.c      2008/11/09 01:47:23
***************
*** 1,4 ****
--- 1,7 ----
  /*
+ gcc -g3 -ggdb -Wall -Wmissing-prototypes -Wstrict-prototypes -o ee36 ee36.c -lpthread
+ */
+ /*
  About this program:
  - Implementation of the Dining Philosophers problem,
    - Fig 6.12, Operating Systems, Stallings
***************
*** 26,31 ****
--- 29,37 ----
   */
   
  #include "ee36.h"
+ 
+ static void eat(int pid);
+ static void think(int pid);
   
  // global arrays, hold the fork semaphores (using Posix sem_t semaphores)
  // and the philosopher thread data structures (Posix pthread_t thread structures)
***************
*** 144,149 ****
--- 150,156 ----
  int main(int argc, char **argv)
  {
   
+    setvbuf(stdout, NULL, _IOLBF, 0);
   
      // create the semaphores for the forks
      int i;
12:58:52$ 
12:58:54$ 
12:58:54$ rcsdiff -r1.1 -c ee36.h
===================================================================
RCS file: RCS/ee36.h,v
retrieving revision 1.1
diff -c -r1.1 ee36.h
*** ee36.h      2008/11/08 13:45:08     1.1
--- ee36.h      2008/11/09 01:56:58
***************
*** 8,18 ****
  #include <semaphore.h>
  #include <unistd.h>
  
! const int NUM_PHILOSOPHERS = 100;
  const int MAX_THINK_TIME = 100;
  const int MAX_EAT_TIME = 100;
  
! const int NUM_FORKS = NUM_PHILOSOPHERS;  // should always be equal in classic dining philosophers problem
  
  int thinkCount = 0;
  int eatCount = 0;
--- 8,18 ----
  #include <semaphore.h>
  #include <unistd.h>
  
! #define NUM_PHILOSOPHERS 2
  const int MAX_THINK_TIME = 100;
  const int MAX_EAT_TIME = 100;
  
! #define NUM_FORKS NUM_PHILOSOPHERS  // should always be equal in classic dining philosophers problem
  
  int thinkCount = 0;
  int eatCount = 0;
12:59:00$ gcc --version
gcc (GCC) 3.3.3 20040412 (Red Hat Linux 3.3.3-7)
Copyright (C) 2003 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 
12:59:20$

Open in new window

0
 
Duncan RoeSoftware DeveloperCommented:
I have spent a lot of time working out answers to this Q.
0
 
Duncan RoeSoftware DeveloperCommented:
Q1: the program is deadlocked. pid1 has fork 1, pid 0 has fork 0. pid 1 is now waiting for fork 0 and vice versa. This is most easily seen in a gdb session (box). N.b the frames below clone() displayed by gdb are bogus - I don't know why it shows them.
(In this run, I had the think and eat counts thread-local. Then I realised they shouldn't be for Q4, so I undid that).
12:37:48$ gdb ee36
GNU gdb 6.3
Copyright 2004 Free Software Foundation, Inc.
GDB is free software, covered by the GNU General Public License, and you are
welcome to change it and/or distribute copies of it under certain conditions.
Type "show copying" to see the conditions.
There is absolutely no warranty for GDB.  Type "show warranty" for details.
This GDB was configured as "x86_64-unknown-linux-gnu"...Using host libthread_db library "/lib64/libthread_db.so.1".
 
(gdb) run
Starting program: /home/dunc/tests/ee36 
[Thread debugging using libthread_db enabled]
[New Thread 139640359483104 (LWP 4290)]
[New Thread 1086458208 (LWP 4293)]
Entered philosopher <0>
Philosopher <0> is thinking... (entered 0)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 0)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 1)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 1)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 2)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 2)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 3)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 3)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 4)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 4)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 5)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 5)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 6)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 6)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 7)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 7)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 8)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 8)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 9)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 9)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 10)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 10)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 11)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 11)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 12)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 12)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 13)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 13)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 14)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 14)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 15)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 15)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 16)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 16)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 17)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 17)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 18)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 18)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 19)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 19)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 20)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 20)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 21)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 21)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 22)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 22)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 23)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 23)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 24)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 24)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 25)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 25)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 26)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 26)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 27)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 27)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 28)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 28)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 29)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 29)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 30)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 30)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 31)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 31)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 32)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 32)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 33)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 33)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 34)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 34)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 35)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 35)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 36)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 36)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 37)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 37)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 38)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 38)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 39)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 39)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 40)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 40)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 41)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 41)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 42)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 42)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 43)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 43)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 44)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 44)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 45)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 45)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 46)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 46)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 47)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 47)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 48)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 48)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 49)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 49)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 50)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 50)
    philosopher <0> released fork <1>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 51)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 51)
    philosopher <0> released fork <1>
[New Thread 1110096224 (LWP 4294)]
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 52)
    philosopher <0> pickedup fork <0>
    philosopher <0> pickedup fork <1>
Philosopher <0> is eating... (entered 52)
    philosopher <0> released fork <1>
Entered philosopher <1>
Philosopher <1> is thinking... (entered 0)
    philosopher <1> pickedup fork <1>
    philosopher <1> pickedup fork <0>
Philosopher <1> is eating... (entered 0)
    philosopher <1> released fork <0>
    philosopher <1> released fork <1>
Philosopher <1> is thinking... (entered 1)
    philosopher <1> pickedup fork <1>
    philosopher <1> pickedup fork <0>
Philosopher <1> is eating... (entered 1)
    philosopher <1> released fork <0>
    philosopher <1> released fork <1>
Philosopher <1> is thinking... (entered 2)
    philosopher <1> pickedup fork <1>
    philosopher <1> pickedup fork <0>
Philosopher <1> is eating... (entered 2)
    philosopher <1> released fork <0>
    philosopher <1> released fork <1>
Philosopher <1> is thinking... (entered 3)
    philosopher <1> pickedup fork <1>
    philosopher <1> pickedup fork <0>
Philosopher <1> is eating... (entered 3)
    philosopher <1> released fork <0>
    philosopher <0> released fork <0>
Philosopher <0> is thinking... (entered 53)
    philosopher <1> released fork <1>
Philosopher <1> is thinking... (entered 4)
    philosopher <1> pickedup fork <1>
    philosopher <0> pickedup fork <0>
^C
Program received signal SIGINT, Interrupt.
[Switching to Thread 139640359483104 (LWP 4290)]
0x00007f008de7a177 in pthread_join (threadid=1086458208, thread_return=0x0) at pthread_join.c:86
86        lll_wait_tid (pd->tid);
(gdb) bt
#0  0x00007f008de7a177 in pthread_join (threadid=1086458208, thread_return=0x0) at pthread_join.c:86
#1  0x0000000000400b67 in main (argc=1, argv=0x7fff96077558) at ee36.c:179
(gdb) thread 2
[Switching to thread 2 (Thread 1086458208 (LWP 4293))]#0  sem_wait () at ../nptl/sysdeps/unix/sysv/linux/x86_64/sem_wait.S:85
85              movq    %rax, %r12
Current language:  auto; currently asm
(gdb) bt
#0  sem_wait () at ../nptl/sysdeps/unix/sysv/linux/x86_64/sem_wait.S:85
#1  0x00000000004009a7 in philosophosize (arg=0x7fff96077440) at ee36.c:116
#2  0x00007f008de799a2 in start_thread (arg=0x5012a0) at pthread_create.c:261
#3  0x00007f008dd1b373 in clone () from /lib64/libc.so.6
#4  0x0000000000000000 in ?? ()
#5  0x0000000000000000 in ?? ()
---Type <return> to continue, or q <return> to quit---q
Quit
(gdb) up
#1  0x00000000004009a7 in philosophosize (arg=0x7fff96077440) at ee36.c:116
116             sem_wait(&forks[fork]);
Current language:  auto; currently c
(gdb) p pid
$1 = 0
(gdb) p fork
$2 = 1
(gdb) thr 3
[Switching to thread 3 (Thread 1110096224 (LWP 4294))]#0  sem_wait () at ../nptl/sysdeps/unix/sysv/linux/x86_64/sem_wait.S:85
85              movq    %rax, %r12
Current language:  auto; currently asm
(gdb) up
#1  0x00000000004009a7 in philosophosize (arg=0x7fff96077444) at ee36.c:116
116             sem_wait(&forks[fork]);
Current language:  auto; currently c
(gdb) p pid
$3 = 1
(gdb) p fork
$4 = 0
(gdb) q
The program is running.  Exit anyway? (y or n) y
12:40:26$ 

Open in new window

0
 
Duncan RoeSoftware DeveloperCommented:
Q2 the program runs for much longer, even with output redirected to a file. This is to be expected owing to the required termination condition (each philosopher has picked up his own fork and no other).
0
 
Duncan RoeSoftware DeveloperCommented:
Q3 the program runs much longer again. As before, it runs for much less time on 2nd invocation, due I believe to their being less for the operating system to do.
0
 
Duncan RoeSoftware DeveloperCommented:
Q1 revisited: when sending output to a file, the program generally ends in the minimum possible time, except on invocation after a lengthy delay (or after re-compiling). I have 2 cpus, so both threads can start at once.
0
 
Duncan RoeSoftware DeveloperCommented:
Q4. To ensure in-sequence numbers, the counters would have to be protected by mutexes. Otherwise one thread might increment a counter then another thread gets to use it before the originally incrementing thread.
0
 
Duncan RoeSoftware DeveloperCommented:
After an early exchange of posts, it was night-time here. The next day, I spent some hours researching a full answer to all the points in this multi-part question. I first posted an introduction http:#22914792 and on posting it noticed the first delete request. Naturally I objected to that. Having objected, I proceeded to post the answers which were a result of my research.  The answer is split over the following: http:#a22914808 http:#a22914816 http:#a22914827 http:#a22914832http:#a22914834
0

Featured Post

Get your Conversational Ransomware Defense e‑book

This e-book gives you an insight into the ransomware threat and reviews the fundamentals of top-notch ransomware preparedness and recovery. To help you protect yourself and your organization. The initial infection may be inevitable, so the best protection is to be fully prepared.

  • 9
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now