Hot answers tagged

12

In general each thread has its own registers (including its own program counter), its own stack pointer, and its own stack. Everything else is shared between the threads sharing a process. In particular a process is generally considered to consist of a set of threads sharing an address space, heap, static data, and code segments, and file descriptors*. An ...


10

Sorry for the late reply, but I've just found the question (questions, indeed). I am studying concurrency as well and I'll try to share some ideas with you. First, let's start with sequential consistency. A model has this property if operations appear to take effect in program order. In other words, the order in which lines of code are executed is the one ...


9

Proving that a program is "thread safe" is hard. It is possible, however, to concretely and formally define the term "data race." And it is possible to determine whether an execution trace of a specific run of a program does or does not have a data race in time proportional to the size of the trace. This type of analysis goes back at least to 1988: ...


9

The main distinction, as you point out in your question, is whether or not the scheduler will ever preempt a thread. The way a programmer thinks about sharing data structures or about synchronizing between "threads" is very different in preemptive and cooperative systems. In a cooperative system (which goes by many names, cooperative multi-tasking, ...


8

It would seem that the answer, as per usual, has something to do with caches. Since hyper-threads utilize the same L1 and L2 caches, one hyper-thread can trash another's caches. In the worst case the threads take turns trashing the other's cache and performance degrades as the caches are re-filled only to be trashed again. Of course, this is likely very ...


7

Overview Multi-threaded programs are more prone to errors than single-threaded programs because of the problem of concurrency bugs. Concurrency is hard for most developers to reason about, which causes many bugs in multi-threaded programs; this issue normally doesn't arise in single-threaded programs, because single-threaded programs typically have no ...


7

Jim Sawyer's answer points to one answer: When you have threads with differing priorities, "fair" behaviour would be incorrect. When you have multiple threads which could run, the highest priority thread is generally the one that should run. However, there's a little-discussed secret of operating system implementation which you should be aware of, which is ...


6

From the pratical side, there is a verification system VCC which can be used to formally prove thread safety of C programs. This is a citation from the web site: VCC supports concurrency -- you can use VCC to verify programs that use both coarse-grained and fine-grained concurrency. You can even use it to verify your concurrency control primitives. ...


6

Since you are asking on CS.SE rather than StackOverflow, I presume you are looking for a principled look at the fundamental underlying problem and principled solutions to the general problem, from a scientific/conceptual perspective (as opposed to a "quick hack" or a engineering solution that'll work for your specific situation). So, that's what I'll try to ...


6

The answer is actually that they could, but there is a desire not to. Fibers are used because they let you control how scheduling occurs. Accordingly, it is much simpler to design some algorithms using fibers because the programmer has say in which fiber is being executed at any one time. However, if you want two fibers to be executed on two different ...


5

(Although you asked about Linux, which would be off-topic, the same principles apply on most operating systems, and general principles are on-topic here.) Threads share their code section. In many systems, even separate tasks that are executing the same program can share their code section, because the code sections are read-only, so whatever one task does ...


5

This section of the book appears to be talking about how the details of the threading and scheduling are implemented for a user mode program. When threading first became popular, most operating systems were Multi-processing OS's, but not "multithreaded" in the sense that the operating system provide support for multiple user code streams sharing the same ...


5

A process is a context with one or more threads of execution (concurrent with other threads of execution, either in the same process, or perhaps in other processes), and with its own address space (and usually other resources such as open file descriptors, IPC mechanisms, etc.). More subtle details and implications are described here So, if address space (...


4

Let me answer the last question first. It points out that the paper was written in 2002, when multi-core processors were much more expensive. I think the authors were largely concerned with optimizing for the single-core case. ... how [is] random fairness ... any better on uni-processor systems in comparison to multiprocessor systems. On a uniprocessor ...


4

Almost every modern processor has special memory instructions built in specifically to deal with this problem. For example, many processors have a swap instruction. This atomically swaps a value between a local variable in a thread and a global variable that is shared between threads. (Under the covers the "local variable" will be stored in a machine ...


4

Try identifying all dependencies between actions, then build a DAG that represents the dependencies: each vertex is an action, each edge is a dependency between two actions. From this you can identify how to perform the maximum number of actions in parallel. Basically, the algorithm is: Find all the sources. Perform all of those actions at once. Delete ...


4

If the number of threads is less than the number of values that you can hold in a memory location, then you can implement a non-overflowing test-and-test-and-set operation with atomic-fetch-and-decrement. So, for example, if you have 32-bit integers and less than 4 billion threads the following should work: initialize: x = 0 acquireLock: repeat: ...


4

Threads come up in two perspectives: operating systems, and programming languages. In both case, there is some variation in what attributes a thread has. A minimal definition of a thread is that it's stuff that happens in sequence, one thing after another. In a typical machine execution model, each thread has its own set of general-purpose registers and ...


4

As, the linked answers and the explanations provided by your textbooks describe that, user level threads are transparent to the kernel, yes they are indeed. Kernel Level threads are not transparent to the kernel, but user level threads are. Because you yourself said, that User Level Threads are managed by the User level library, and what happens is, the ...


4

'Priority inversion' is one reason that fairness can be undesirable. A low priority process hits the locked mutex and sleeps. Then a higher priority process hits it, and also sleeps. When the mutex unlocks, which process should get the lock next?


4

If I understood your question correctly, you are essentially asking: Given a piece of sequential code, if we run N instances of it in parallel on N cores (on real, modern, typical, and not-particularly-high-end CPU models), should we expect any slowdown versus running only a single instance of that program on a single core? As usual, the answer is: it ...


4

You're looking at very vague descriptions and asking "What's the difference between these things that haven't been described properly?" For a more detailed understanding, you should, well, look for more detail, which is widely available. A page is a block of memory; a thread is a sequence of instructions to be executed.


4

Here's a tricky interleaving. R1,R2 denote the independent logical registers used by the threads, while count is the shared variable in memory. Thread 1 starts its first iteration, performing only a read. count=0, R1=0, R2=? Thread 2 performs 99 iterations. count=99, R1=0, R2=99 Thread 1 completes its first iteration (increment and write). count=1, R1=1, R2=...


4

It's great that you're curious. A simplified explanation follows with a few links to delve into: All of the programs running in parallel is actually an illusion that is created by the OS. Even if we have a uniprocessor system, the OS can still achieve the same thing. For multiple programs running on the system, OS creates separate processes. Separate ...


3

There is a relationship between what Wikipedia is calling "preemptive multitasking" and running multiple threads in parallel, but it's somewhat indirect. Suppose you have two threads of computation that are independent (the memory locations they touch are non-overlapping). Then we say that those two threads can run concurrently. "Preemptive multitasking" ...


3

Some other benefits from a security point of view for running the 4 threads implementation would be : Obfuscation of the actual processors being used by the algorithm, in case an attacker is looking to interfere with the execution. If you have 8 processors you can run simultaneously the same algorithm twice using the same input to check the integrity of ...


3

Mutex For the mutex I'm going to propose a modification of the MCS spinlock that uses your sleep/wake primitives to block instead of spin while waiting to acquire the mutex. The MCS lock was introduced in Mellor-Crummey, John M; Scott, Michael L: Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors, ACM Trans. on Comp. Sys. (TOCS), 9(...


3

It is impossible to implement a mutex completely in userspace unless you have special CPU instruction that could simulate a semaphore or a lock (some "test and increment if true" instruction). pthread in Linux goes through the kernel to implement the mutex.


3

While the details will depend on the actual thread model of your thread library (eg. pthreads, the POSIX thread library), some general observations hold. Without explicit or implied syncing you have no guarantees about the serialization of threaded code. The platform running your code might execute some of the thread's code first before resuming the ...


3

As to the question what benefits it would give you, the answer is simplicity. Modern programming languages are large beasts with complicated semantics, starting with syntax, and not ending with the rules for integer and floating point arithmetic (real languages, as you know, don't work with 'mathematical' integers and reals, but rather with finite ...


Only top voted, non community-wiki answers of a minimum length are eligible