1

I've made a queue header file and I've tried to use it with threads. What I'm doing is making 2 threads, 1 for reading the characters from the code file and entering the characters to the queue and the other thread is trying to print the characters to the console. The problem is that no characters are being printed to the console and I can't figure out why.

queue.h :

#ifndef QUEUE_INT
#define QUEUE_INT

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

typedef struct
{
    int *elementData;
    unsigned int queueSize;
    unsigned int capacityIncrement;
    unsigned int elementCount;
} Queue;

void queue_initialize(Queue*, unsigned int);
int queue_add(Queue*, int);
void queue_poll(Queue*);
int queue_peek(const Queue*);
void queue_destroy(Queue*);
bool queue_isEmpty(const Queue*);
void queue_setCapacityIncrement(Queue*, unsigned int);
unsigned int queue_getCapacityIncrement(const Queue*);
unsigned int queue_getNumberOfElements(const Queue*);
unsigned int queue_getSize(const Queue*);

void queue_initialize(Queue *p, unsigned int capacityIncrement)
{
    p->elementData = NULL;
    p->queueSize = 0;
    p->capacityIncrement = capacityIncrement;
    p->elementCount = 0;
}

int queue_add(Queue *p, int value)
{
    if(p->elementCount == p->queueSize)
    {
        int newQueueSize = p->queueSize + p->capacityIncrement;
        void *temp = realloc(p->elementData, sizeof(*p->elementData) * newQueueSize);
        if(temp == NULL || newQueueSize == 0)
        {
            return 1;
        }
        p->queueSize = newQueueSize;
        p->elementData = temp;
    }
    p->elementData[p->elementCount] = value;
    p->elementCount++;
    return 0;
}

void queue_poll(Queue *p)
{
    if(!queue_isEmpty(p))
    {
        p->elementCount--;
        if(p->queueSize - p->elementCount == p->capacityIncrement / 2 + p->capacityIncrement)
        {
            int newQueueSize = p->queueSize - p->capacityIncrement;
            p->elementData = realloc(p->elementData, sizeof(*p->elementData) * newQueueSize);
            p->queueSize = newQueueSize;
        }
        for(int i = 0; i < p->elementCount; i++)
        {
            p->elementData[i] = p->elementData[i + 1];
        }
    }
}

int queue_peek(const Queue *p)
{
    if(!queue_isEmpty(p))
    {
        return p->elementData[0];
    }
    return 0;
}

void queue_destroy(Queue *p)
{
    free(p);
}

bool queue_isEmpty(const Queue *p)
{
    return p->elementCount == 0;
}

void queue_setCapacityIncrement(Queue *p, unsigned int capacityIncrement)
{
    p->capacityIncrement = capacityIncrement;
}

unsigned int queue_getCapacityIncrement(const Queue *p)
{
    return p->capacityIncrement;
}

unsigned int queue_getNumberOfElements(const Queue *p)
{
    return p->elementCount;
}

unsigned int queue_getSize(const Queue *p)
{
    return p->queueSize;
}

#endif

Code file :

#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include <process.h>
#include <time.h>
#include "queue.h"

bool isFillQueueThreadRunning;
bool isQueueProcessing;

void fillQueueThread(void*);
void popQueueThread(void*);

int main()
{
    srand(time(NULL));
    Queue q1;
    queue_initialize(&q1, 4);
    HANDLE hFillQueueThread = (HANDLE)_beginthread(fillQueueThread, 0, (void*)&q1);
    HANDLE hPopQueueThread = (HANDLE)_beginthread(fillQueueThread, 0, (void*)&q1);
    WaitForSingleObject(hFillQueueThread, 1000 * 300);
    WaitForSingleObject(hPopQueueThread, 1000 * 300);
    return 0;
}

void fillQueueThread(void *p)
{
    isFillQueueThreadRunning = true;
    Queue *q = (Queue*)p;
    FILE *f = fopen(__FILE__, "r");
    int b;
    while((b = getc(f)) != EOF)
    {
        Sleep(rand() % 50);
        while(isQueueProcessing)
        {

        }
        isQueueProcessing = true;
        if (queue_add(q, b) == 1)
        {
            break;
        }
        isQueueProcessing = false;
    }

    fclose(f);
    isFillQueueThreadRunning = false;
}

void popQueueThread(void *p)
{
    Queue *q = (Queue*)p;
    Sleep(10);
    int b;
    while(isFillQueueThreadRunning || q->elementCount > 0)
    {
        while(isQueueProcessing)
        {

        }
        isQueueProcessing = true;
        b = queue_peek(q);
        queue_poll(q);
        putchar(b);
        isQueueProcessing = false;
    }
}
Akes55
  • 95
  • 1
  • 1
  • 5
  • 2
    you `_beginthread` `fillQueueThread` twice. – loa_in_ Sep 12 '14 at 21:24
  • Run your code in a debugger. First step through one threads code, line by line, then step through the other threads code. Doing that you should probably find what the problem is quite easily. – Some programmer dude Sep 12 '14 at 21:26
  • You also have a race condition. Uninitialized global variables will be zero-initialized, that means both threads compete to set `isQueueProcessing` first. – Some programmer dude Sep 12 '14 at 21:29
  • And since you don't protect the assignment of `isQueueProcessing` with a semaphore, think about what happens if one thread gets halfway through the assignment, and then is preempted and the other thread does its assignment, then both threads are running simultaneously. You simply can not use boolean variables and assignment for thread synchronization. You have to use proper primitives like semaphores. – Some programmer dude Sep 12 '14 at 21:31
  • @loa_in_ yes, thanks for spotting that, that solve one problem, but now for some reason I'm printing single character and then alot of spaces in between. – Akes55 Sep 12 '14 at 21:35
  • @JoachimPileborg Not sure I've understood your second explanation, I'm a beginner at coding so it wasn't that clear to me what you meant. – Akes55 Sep 12 '14 at 21:38
  • While assignments in C might look simple and small, they are in fact not. An assignment can be quite a few assembler instructions. This means that one assignment expression in one thread may be interrupted in the middle, and then another thread will run for a while. If that other thread is assigning to the same variable, and finishes the assignment before it's preempted, then the second thread will continue with the assignment to the exact same variable, causing a [*data race*](http://en.wikipedia.org/wiki/Race_condition), leading to undefined behavior when both threads continues. – Some programmer dude Sep 12 '14 at 21:51
  • @JoachimPileborg but that's why I have the bool flag isQueueProcessing so when one thread reads/writes from/to the queue the other is waiting for that thread to finish it's task, am I missing here something ? – Akes55 Sep 12 '14 at 22:03
  • WTB a mutex, critical-section, and/or some atomics. – WhozCraig Sep 13 '14 at 02:12

2 Answers2

0

you _beginthread the fillQueueThread twice.

and

you never initialize isFillQueueThreadRunning reliably. Code may depend on uninitialized variable.

from what I've seen

loa_in_
  • 1,030
  • 9
  • 20
  • Thanks for noting those things. About not initializing isFillQueueThreadRunning correctly, can it affect something even if I'm doing Sleep(10); in the popThread ? So I'm letting the fillThread time to initialize it. Also after fixing those problems instead of printing the code nicely there's ton of space between characters, sometimes characters can be printed like couple of lines from each other and I don't understand why this is happening? – Akes55 Sep 12 '14 at 21:47
  • Sleep() never fixes race conditions, it only makes them harder to find :( – Jeremy Friesner Sep 13 '14 at 05:06
  • @JeremyFriesner what if instead of the Sleep in the popQueueThread I'll do while(!isFillQueueRunning) {} ? – Akes55 Sep 13 '14 at 11:42
  • @Akes55 No, that won't work either, because you can't guarantee that thread A will "see" the value set by thread B soon enough to do the right thing. You have to use a mutex or critical section; they are designed to do the right thing across all hardware; and nothing less will work reliably. (Well, that's not 100% true; there are some ways to do lock-free thread-safe data structures using special atomic primitives, but they are extremely tricky to get right and if you haven't mastered locking primitives yet, the chances of employing them correctly is near-zero) – Jeremy Friesner Sep 13 '14 at 13:33
  • @JeremyFriesner So I've read what mutex is and what is race condition between threads but I understand what should I do to solve this ? Can you link me to something that will teach me about this ? – Akes55 Sep 13 '14 at 13:37
  • Identify the data items that can be read or written by both threads. Before a thread accesses one of those items, have it lock the mutex. When it's done accessing, have it unlock the mutex so the other thread can proceed. – Jeremy Friesner Sep 14 '14 at 14:19
0

Your queue implementation is far from thread safe. As Joachim mentioned, please education yourself with thread synchronization primitives. A simple mutex would go a long way here.

See: What is a mutex?

As to your large blocks of spaces, you use the output of queue_peek() unconditionally which can (and will frequently) be NULL.

Do you know that the result of putchar(NULL) is?

Community
  • 1
  • 1
Rich
  • 640
  • 5
  • 12
  • I've placed my putchar between an if statement if(b !=0), still the result is that characters are missing when trying to print them. About mutex, I understand what it is, in my code it's basically the isQueueProcessing variable so I don't see what's wrong with it ? – Akes55 Sep 13 '14 at 12:06
  • queue_add() and queue_poll() both depend on queue state variables being immutable for the duration of the methods, when they are not. Why are you avoiding using a mutex? – Rich Sep 15 '14 at 21:23
  • Since you appear to be using Windows, I would recommend this: http://msdn.microsoft.com/en-us/library/windows/desktop/ms686927%28v=vs.85%29.aspx – Rich Sep 19 '14 at 04:38