The very moment I implemented pthreads in a program I was writing, (An isometric RTS - I was inspired at the time by Age Of Empires, my childhood defining game) a huge drop in stability and overall reliability happened within said source. I've read about the problems with concurrency; I've read about race conditions, deadlocks - all that, but it was still a nasty awakening to the state of concurrency in computing.
Errors began to pop up, and It seemed a gradual process, but It was definitely happening: My code was turning into a mess. I had a thread for the very engine of the game: the AI of the working villagers who provide food and all that good stuff; I had a thread for the graphics engine; a loop would be entered where a pointer would go through a linked list of graphics elements in a graphics queue and draw them all the the screen (SDL is a great library). I had a thread for handling events sent from X11 to SDL, and finally to me, which would call the function pointed to by a function pointer within a class 'C_Clickable' which held the information about the whereabouts of any clickable graphics element, among other things, and I had a main thread; a mainly idle, but necessary thread; this thread entered at call time, initialized everything and basically oversaw the workings of the other threads, and managed them.
A complicated series of instructions by any view point, but it worked nicely. Buttons would be clicked and it would be handled with a pleasing response time. It seemed to work. But as in human nature, I ignored the glaringly obvious and sinister problem: I was receiving errors from xcb and X11 when runtime ended. Of course, I passed this off as a complaint about my rebellious use of concurrency, and I expected it was merely something caused by the crude use of thread meeting and the destruction of resources by SDL which seemed nearly unhandled. This wasn't the case.
The time came to write a map generation algorithm, to give my class hierarchy a place to manifest its graphical representation. After a frustrating session of figuring out the hardly intricate mathematics of drawing an isometric tile in GIMP (A lost art; I figured this out a long time ago but had since forgotten) I began to implement a map drawing algorithm; I was leaving the creation of complex structures such as hills and forests for later, instead opting for a grass plane, so I could piece together the mechanics of the gameplay without spending so much time on something so complex.
A for loop containing a for loop incrementing values through a 2D array of tiles and coordinates through multiples of 16 and 32 was my choice, and possibly the most efficient. Compilation was an arduous ordeal of fixing issues caused by g++'s inability to generate unknown type errors after parsing all classes, but that didn't bother me. I fixed them and complied, tail between my legs, to the wishes of g++. Once compiled, errors hid under every crevice of concurrency. A BadShmGet complaint was made by X11, and an unknown request in queue assertion by xcb failed, but consistent it was not . Sometimes the window would close instantly upon depression of the lonely 'Begin' button that inhabited my underpopulated and half baked - at this point, anyway - pre-game menu and the complaint given by X11, then runtime would cease. Sometimes xcb would crash after clicking said button, causing runtime to be cut short - but there were often discrepancies beyonnd even these two pairings of behaviors.
Sometimes X11 would drop my video memory and wait for an event - such as a mouse move event, as was often the case - to send an unknown event to xcb causing a crash, and I would be presented with a blank, function-less window, which would implode upon mere movement of the mouse. Sometimes it would outright segfault, which led me to believe my algorithms were faulty, which I expected. I optimized and tweaked them into a nice state, and crossed my fingers I had overstepped no array and nullified no pointer before its time. The state of reliability in my app remained, with the exception of a 'double free or corruption' error (Whose fruit is an intimidating core dump into stdout) at one point.
It seemed the libraries I was using simply didn't like threads. But obviously this wasn't the case. SDL even has a wrapper library for pthreads - which is optional, or so I have heard. X11 has an XInitThreads function - which I called - to provide nice support for shared state memory. It may have been my implementation, or it might have been the libraries, but any person who can convince me this isn't a sorry state of affairs either has low standards but a good mouth for persuasion, or is a better programmer than I.
Simply approaching concurrency leads to complications. There are mutex locks whose purpose is to fix the problems involved in shared state memory - which they don't. In fact they cause problems on their own; deadlocks. A messy solution to a complicated problem, yet companies such as Intel still push threads as though they will save they world, when the opposite is more likely. Problems such as mine, with the world's growing love for multi-core architecture, will become more common with further adoption of threads: Highly indeterminate (As in determinism) programs where errors hide and are not consistent, therefore all the harder to debug. As the nigh on cliched expression goes, Threads are evil. They are a complicated, messy solution to a complicated problem. But complaining can only get us so far. I propose a solution.
Concurrent languages are making their presence known, but none seems to be a definite solution to the problem of concurrency. Several concepts of mine come to mine spring to mind when I ponder this problem.
Concepts such as autonomous mutexes. The very idea of mutual exclusion is one that should be simple; disallowing threads access to variables is a fix-all end-all solution to shared state memory; with this I agree. Deadlocks and thread race situations are both caused by shared state memory, but one is caused by the solution. The answer is simple, and it's not Concurrency APIs for serial languages; fully concurrent programming languages are the answer. Interpreters have much, much greater control over concurrency during runtime than would ever be possible when a language is compiled; even something as daring as autonomous mutual exclusion is possible with an interpreter. It would takes as much as 5 bytes of memory and and if statement to fix this problem: bool Locked; Thread* Owner; within a class would act as a safegaurd when used properly by an interpreter. But an important issue still stands.
Say an interpreter for a concurrent language runs, and every time a variable's value is modified, the Locked bool in the variable's class instance is set as true, then reverted to false as operations cease. Say another thread is trying to access said variable to write to it's address in memory. I'll lay it out like this, to try and explain.
Thread 1 Thread 2
Is variable is locked? false.
Function checks if variable is locked: false.
Locked = true;
Locked = true;
Function writes to variable believing it has lock
Function writes to variable
Thread race occurs
Again, the very concept of concurrency in computing catches us out. An interpreter written in a serial language with a concurrent API interpreting a concurrent language uses thread scheduling to ultimately defeat the purpose of interpreting said concurrent language. It seems to me, at the time of this writing, the very logic involved in concurrency will never be solved to the point of the reliability of serial algorithms.
"What about checking for ownership - not just locking - before writing to a variable?" You may ask. Thread scheduling is ambiguous, and a thread assuming it is the one who has lock is perfectly reasonable; it will have lock most of the time, it is only on rare occasions the kernel schedules the threads in such a way that this situation occurs.
"Well, what about writing an interpreter for a concurrent language in a concurrent language, Mr. Mcclure?" You may be asking. I'll give you a minute to think about that paradox. No concurrent language exists that doesn't rely on, at some point, concurrent APIs for serial languages. It seems that computing, at its very core, is serial, and the only was for it to function perfectly is serial methodology.
Is there a future for concurrency in computing? Yes. Is it coming soon? No. I have every intention to save the world from threads, but the only way to do so would be to implement threads. The paradox of bootstrap loading was figured out, so possibly someday this will be too, but I feel as though letting the theory simmer in my brain as I do with most concepts - to the point of definition and maturation - will not be sufficient.
A complex series of algorithms forming in my mind as I type this could hold the key to safely locking shared state memory, but It will take a lot of effort, research, and arduous testing to first implement it, then see if the results are satisfactory, despite the fact, and constantly oppressing fear I hold of said fact, that a thread race could happen at any possible given moment, and there is no perfect way to know if one may or may not happen.
No comments:
Post a Comment