Question

Consider the following pseudo-code:

/* Global memory area accessible by threads */
#define N 100
struct frame *emptyStack[N];
struct frame *displayQueue[N];

int main() {
  /*

  ** Initialise by allocating the memory for N frames
  ** And place the N frame addresses into the
  ** empty Stack array
  */

  Initialise();
  thread_t tid1, tid2;

  threadCreate(&tid1, GetFrame);
  threadCreate(&tid2, ShowFrame);

  sleep(300);
}

GetFrame() {
  struct frame *frame;
  struct frame local;

  while (1) {
    CameraGrab(&local);  /* get a frame from the camera store it in local */

    frame = Pop(); /* pop an empty-frame address from the empty stack */

    CopyFrame(&local, frame); /* copy data from the local frame to the frame address */

    Enqueue(frame); /* push the frame address to the display queue */
}

}

ShowFrame() {
  struct frame *frame;
  struct frame local;
  struct frame filtered;

  while (1) {
    frame=Dequeue(); /* pop the leading full frame from the full queue */

    CopyFrame(frame, &local); /* copy data to the local frame */

    Push(frame);          /* push the frame address to the empty stack */

    Solarise(&filtered, &local); /* Modify the image */

    VideoDisplay(&filtered);     /* display the image */
  }

}

This program creates two threads, one calls GetFrame(), which continually grabs frames from a camera, and the other thread callsShowFrame(), which continually displays the frames (after modification). When the program starts the emptyStack contains the addresses of N empty frames in memory.

The process runs for 5 minutes displaying the contents from the camera.

The procedures Pop() and Push() are maintaining the list of frame addresses on the empty stack. Pop() removes a frame memory address from the empty stack, and Push() adds a memory address to the empty stack.

The procedures Dequeue() and Enqueue() are maintaining the list of frame memory addresses in the display queue in display order. Dequeue() removes the memory address of the next frame to display from the display queue, and Enqueue() adds a memory address to the end of the display queue.

The stack and the queue are the same size, and are large enough to contain all available frame memory addresses.

1. Without including synchronisation code problems will occur. Discuss what could potentially go wrong?

2. Identify the critical sections in the above pseudo-code.

3. Modify the above pseudo-code using semaphores only, to ensure that problems will not occur.

   Hint: this is a variation on the Producer-Consumer problem and will require similar semaphores.

Answer 1

Without including synchronization code problems will occur. Discuss what could potentially go wrong?

Ans: If showFrame() [p1] tries to process the first image from the camera, getFrame() should wait for processing the image. So while trying to get there will be no image in the Queue. So garbage value will be displayed while dequeuing.

So getting and processing should happen simultaneously.

Identify the critical sections in the above pseudo-code.

/* Global memory area accessible by threads */
#define N 100
struct frame *emptyStack[N];
struct frame *displayQueue[N];

int main() {

  /*

  ** Initialise by allocating the memory for N frames
  ** And place the N frame addresses into the
  ** empty Stack array
  */

  Initialise();
  bool flag = FALSE;
  thread_t tid1, tid2;

  threadCreate(&tid1, GetFrame);
  threadCreate(&tid2, ShowFrame);

  sleep(300);
}

GetFrame() {
  struct frame *frame;
  struct frame local;

  while (1) {
    CameraGrab(&local);  /* get a frame from the camera store it in local */

flag= true;

    frame = Pop(); /* pop an empty-frame address from the empty stack */

flag = flase;

    CopyFrame(&local, frame); /* copy data from the local frame to the frame address */

    Enqueue(frame); /* push the frame address to the display queue */
}

}

ShowFrame() {
  struct frame *frame;
  struct frame local;
  struct frame filtered;

  while (1) {
    frame=Dequeue(); /* pop the leading full frame from the full queue */

    CopyFrame(frame, &local); /* copy data to the local frame */

if(flag == flase)

         Push(frame);          /* push the frame address to the empty stack */

    Solarise(&filtered, &local); /* Modify the image */

    VideoDisplay(&filtered);     /* display the image */
  }

}

Modify the above pseudo-code using semaphores only, to ensure that problems will not occur.

Consider the following pseudo-code:

/* Global memory area accessible by threads */
#define N 100
struct frame *emptyStack[N];
struct frame *displayQueue[N];

int main() {
  /*

  ** Initialise by allocating the memory for N frames
  ** And place the N frame addresses into the
  ** empty Stack array
  */

  Initialise();
  thread_t tid1, tid2;

  threadCreate(&tid1, GetFrame);
  threadCreate(&tid2, ShowFrame);

  sleep(300);
}

GetFrame() {
  struct frame *frame;
  struct frame local;

  while (1) {
    CameraGrab(&local);  /* get a frame from the camera store it in local */

    if (frame = Pop();)
        block();  /* pop an empty-frame address from the empty stack */

    CopyFrame(&local, frame); /* copy data from the local frame to the frame address */

    Enqueue(frame); /* push the frame address to the display queue */
}

}

ShowFrame() {
  struct frame *frame;
  struct frame local;
  struct frame filtered;

  while (1) {
    frame=Dequeue(); /* pop the leading full frame from the full queue */

    CopyFrame(frame, &local); /* copy data to the local frame */

    if(Push(frame))
        wakeup();          /* push the frame address to the empty stack */

    Solarise(&filtered, &local); /* Modify the image */

    VideoDisplay(&filtered);     /* display the image */
  }

}