Our new Indie Games subforum is now open for business in G&T. Go and check it out, you might land a code for a free game. If you're developing an indie game and want to post about it,
follow these directions. If you don't, he'll break your legs! Hahaha! Seriously though.
Our rules have been updated and given
their own forum. Go and look at them! They are nice, and there may be new ones that you didn't know about! Hooray for rules! Hooray for The System! Hooray for Conforming!
SELECT * FROM posts WHERE tid = 'PA PROGRAMMING THREAD'
Posts
In fact when I had to write a scheduler simulator using Pthreads in C in my operating systems class, the first thing I did was write a blocking queue for ints so I could pass messages between threads.
EDIT: Here it is, actually. It might not actually compile because I just merged the header into it, but you can get the basic idea.
#define TRUE -1 #define FALSE 0 #include<stdlib.h> #include <pthread.h> #include <semaphore.h> typedef struct queue_tag { int *array; //The circular array int head; //The first element of contents int tail; //The next empty element int cap; //The size of the circular array pthread_mutex_t *lock; //a mutex on this queue sem_t *size_sem; //the number of elements, == size sem_t *empty_sem; //the room left in the array, cap - size } queue_str, *queue_t; /** Creates a new BlockingQueue of the given capacity **/ queue_t queue_init(const int capacity) { queue_t queue = malloc(sizeof(queue_str)); queue->cap = capacity; queue->array = malloc(sizeof(int) * capacity); queue->head = 0; queue->tail = 0; queue->lock = (pthread_mutex_t *) malloc(sizeof(pthread_mutex_t)); queue->empty_sem = (sem_t *) malloc(sizeof(sem_t)); queue->size_sem = (sem_t *) malloc(sizeof(sem_t)); pthread_mutex_init(queue->lock, NULL); sem_init(queue->empty_sem, 0, capacity); sem_init(queue->size_sem, 0, 0); return queue; } //Frees all memory associated with queue void queue_destroy(queue_t queue) { free(queue->array); pthread_mutex_destroy(queue->lock); sem_destroy(queue->empty_sem); sem_destroy(queue->size_sem); free(queue->lock); free(queue->empty_sem); free(queue->size_sem); free(queue); } //Adds toAdd to the queue, blocking if full. void queue_put(const int toAdd, queue_t queue) { sem_wait(queue->empty_sem); //wait for room pthread_mutex_lock(queue->lock); queue->array[queue->tail] = toAdd; queue->tail = (queue->tail + 1) % queue->cap; pthread_mutex_unlock(queue->lock); sem_post(queue->size_sem); //announce new contents } //Returns the next item in the queue, blocking if empty. int queue_get(queue_t queue) { sem_wait(queue->size_sem); //wait for contents pthread_mutex_lock(queue->lock); int val = queue->array[queue->head]; queue->head = (queue->head + 1) % queue->cap; pthread_mutex_unlock(queue->lock); sem_post(queue->empty_sem); //announce room made return val; } // Attempts to add to the queue // returns TRUE if sucsessful, FLASE if not int queue_tryput(const int toAdd, queue_t queue) { if (sem_trywait(queue->empty_sem)) { return FALSE; } pthread_mutex_lock(queue->lock); queue->array[queue->tail] = toAdd; queue->tail = (queue->tail + 1) % queue->cap; pthread_mutex_unlock(queue->lock); sem_post(queue->size_sem); //announce new contents return TRUE; } // Attempts to dequeue the next item in the queue, setting it in the given address // returns TRUE if sucsessful, FLASE if not int queue_tryget(int * value, queue_t queue) { if (sem_trywait(queue->size_sem)) { return FALSE; } pthread_mutex_lock(queue->lock); *value = queue->array[queue->head]; queue->head = (queue->head + 1) % queue->cap; pthread_mutex_unlock(queue->lock); sem_post(queue->empty_sem); //announce room made return TRUE; }The Objectives for the Java exam (in regards to Threads) are:
I think I can agree with that. Knowing how to use them, and actually using them when easier structures will work are two different things.
I would say the two most important concepts here are mutexes and semaphores. Spinlocks are more of an antipattern, and events are language-specific abstractions of simple message passing between threads.
public static void main(String[] args) { (new Thread(new Question6(0))).start(); } @Override public void run() { System.out.println(Thread.currentThread().getName() + " Start"); synchronized (this) { if (index<2) { index++; (new Thread(this)).start(); try { wait(); } catch (InterruptedException e) {} } else { notifyAll(); } } System.out.println(Thread.currentThread().getName() + " End"); }Yeah, I use the ever living shit out of the Tasks library in .NET, which is a fancy scheduled thread pool. It's not for the most complex threading issues, but for worker-task style stuff, it's phenomenal.
You still have to worry about shared state and all that, but it makes it easier to reason about parallel tasks. I normally try to design the concurrent part of my apps to not share any state and then combine the results back together when it's running in a single thread again. It's not always possible, but it makes it 1000 times easier if you don't have to worry about locks and synchronization.
Thread t = new Thread(); try{ t.sleep(5000); } catch(Exception e){}A very, very simple example obviously. But the t.sleep(5000) doesn't actually get called on the t Thread, but on the currently running Thread.
e: I should clarify: The fact that sleep blocks the current thread is not illogical, it's required. You can't sleep a thread at some random instruction from outside that thread. The fact that sleep is an instance method, implying that you can call it on a thread object that represents a thread different than the call site, is illogical. While you can call it, it's just going to block the current thread, which is likely not the correct behavior. I know why it's an instance method, but it should be protected, not public.
Yeah it just basically caused my brain to shut down for a second or two. And I do believe that sleep is a static method in Java as well.
I agree that the confusion is not worth it.
I also found out that an operating system gets cranky when you spawn over 1000 threads. Although, when you are running that many, at least it's easy to spot nondeterministic behaviour.
edit: I ended up encapsulating the synchronization in a dinky little C-pseudoclass called Mailbox which just holds a single int. This was years ago, but it still seems remarkably readable. Here it is:
#include <pthread.h> typedef struct { int value; int hasValue; int closed; pthread_mutex_t lock; pthread_cond_t susp; } mailbox_t; mailbox_t* mailbox_create() { mailbox_t* this = (mailbox_t*)malloc(sizeof(mailbox_t)); pthread_mutex_init(&this->lock, NULL); pthread_cond_init(&this->susp, NULL); this->closed = 0; this->hasValue = 0; return this; } void mailbox_close(mailbox_t* this) { pthread_mutex_lock(&this->lock); this->closed = 1; pthread_cond_signal(&this->susp); pthread_mutex_unlock(&this->lock); } void mailbox_waitForClose(mailbox_t* this) { pthread_mutex_lock(&this->lock); while (!this->closed) { pthread_cond_wait(&this->susp, &this->lock); } pthread_mutex_unlock(&this->lock); } void mailbox_enter(mailbox_t* this, int value) { pthread_mutex_lock(&this->lock); while (this->hasValue) { pthread_cond_wait(&this->susp, &this->lock); } this->hasValue = 1; this->value = value; pthread_cond_signal(&this->susp); pthread_mutex_unlock(&this->lock); } int mailbox_remove(mailbox_t* this) { int value; pthread_mutex_lock(&this->lock); while (!this->hasValue) { pthread_cond_wait(&this->susp, &this->lock); } value = this->value; this->hasValue = 0; pthread_cond_signal(&this->susp); pthread_mutex_unlock(&this->lock); return value; }Easily readable! Good stuff for a 20 hour Eureka moment!
Just a note if you do something like this again, because you were this close to having a bug in your mailbox_waitForClose(), enter(), and remove() functions.
Specifically, the looping on while( this->variable ) should probably have been something like:
void mailbox_waitForClose(mailbox_t* this) { volatile int *pThisClosed = &this->closed; // volatile because this->closed is designed to be changed by another thread in another function pthread_mutex_lock(&this->lock); while (!*pThisClosed) { pthread_cond_wait(&this->susp, &this->lock); } pthread_mutex_unlock(&this->lock); }To see the problem, you need to keep in mind that the optimising C/C++ compiler implicitly assumes single threaded operation. With that in mind, have a look at this simplified loop:
while (!this->closed) {}The pseudo-assembly for this loop would have gone something like:
The optimising compiler will assume single threaded operation by default and say "Hang on! Nothing in this while loop changes the value of this->closed! Why bother reloading something from memory that couldn't possibly have changed?" This will produce optimised code like:
It can even go one step further:
In other words - you'll end up with an infinite loop. A very very common symptom of this bug is that things will work fine in debug mode with no optimisations, but when optimisations are turned on, calling these functions will hang in these loops.
Now, I believe where you may have avoided the bug was by calling pthread_cond_wait(), because the compiler is unable to prove that pthread_cond_wait() will leave this->closed untouched. In other words, when it hits the loop, it says, "Hmm... calling pthread_cond_wait() might change the value of this->closed, so I should keep the memory access.". I am not certain about how far the compiler has to go to prove to itself that there are no aliases to variables in functions being called - this bit here is me guessing.
If my guess is true, then this is probably because pthread_cond_wait() is externally linked, and so the compiler cannot (will not?) statically analyse it. If pthread_cond_wait() was replaced by one of your internal functions, certain compilers are able to do full programme optimisations and prove that this->closed will remain untouched, and optimise to the infinite loop above. (Alternatively, the compiler might have to meet a lesser burden of proof than I was expecting).
Adding the 'volatile' keyword explicitly tells the compiler that the variable can change at any time for whatever reason (in your case, due to another thread). This means that the optimising compiler should not cache the variable in a CPU register, and so prevent the infinite loop optimisation.
Like, you can tell I was just doing it on the fly and had no real plan, and got halfway and kind of wanted to go back and make it all better but there wasn't time and... blegh...
I have a function which is 200+ lines of nested if statements. Good god.
Don't feel bad I have seen production code that is thousand's of lines of nested if statements that created a poor file syntax parser.
Does that just mean I could do:
Person person = new Person("Asshole",24); Person person2 = new Person("Poopybutt", 1); ArrayList<Person> personList = new ArrayList<Person(); personList.add(person); personList.add(person2); Collections.sort(personList, new NameComparator()); System.out.println(personList); Collections.sort(personList, new AgeComparator()); System.out.println(personList);Somehow I keep reading that as you can do something like:
Collections.sort(personList, newNameComparator(), new AgeComparator());
But I know that's wrong. Is that the only benefit of Comparator vs Comparable? I think I MAY have just answered my question.
class Animal { @Override public String toString(){ return this.getClass().getSimpleName(); }} class Dog extends Animal{} class Cat extends Animal{} class Truck{}And the following method:
public static void go(ArrayList<? extends Animal> list){ for(Object o : list.toArray()){ System.out.println(o.getClass().getSimpleName()); } }Why does the following still work?
ArrayList animalList = new ArrayList(); animalList.add(new Animal()); animalList.add(new Dog()); animalList.add(new Cat()); animalList.add(new Truck()); go(animalList);Truck doesn't extend Animal, so it should've at least given me a warning or something right? It happens even if I change the ArrayList to:
ArrayList<Animal> animalList = new ArrayList<Animal>(); (Which surprised me even more since Truck isn't even an Animal... I didn't think it would allow me to do that.)
I’m guessing it’s because your arraylist isn’t the generic version, so it’s storing everything as an Object.
Forgetting my syntax but something like:
ArrayList <? extends Animal> animalList = new ArrayList <? extends Animal> (); animalList.add(new Animal()); animalList.add(new Dog()); animalList.add(new Cat()); animalList.add(new Truck()); go(animalList);I think what they mean by 'multiple Comparators' is that a single class can have multiple Comparators associated with it, such as sorting on different fields, or in ascending or descending order, while a class can only implement Comparable one way, and is thus stuck with a particular order.
So, if you're relying on Comparable, then you can only call:
But with Comparator, you can also call:
Does that help?
And it looks like I'm going to spend longer on Generics / Collections than I'd previously expected. Thanks for the heads up @centraldogma
Are you sure about that last part? When I try that out, I get a compile error adding Truck.
This example probably isn't so great since you'd be calculating distances N times for each planet, but hopefully that makes the idea somewhat clear.
Good call! As a class assignment, this never had optimizations enabled, so that must be why that problem never appeared. That class was about operating systems in general rather than concurrent programming in particular, so threading in C was not covered extensively. I've known about this particular problem (and the need for volatile) for a while, but I must have learned about it some time after I wrote this. Your explanation is very clear though; that's a good way to explain the need for the qualifier.
"volatile" is simply the "never optimize" flag.
Obviously it is a poor decision to throw it around willy-nilly. :lol:
The PhalLounge :: Chat board for Phalla discussion and Secret Santas :: PhallAX 2013
Critical Failures IRC! :: #CriticalFailures and #mafia on irc.slashnet.org