How does an OS implement or maintain a stack for each thread?

Question

There have been various questions on SO on whether or not threads get their own stack. However I fail to understand how the OS implements or how do OSs generally implement one stack per thread. In OS books the memory layout of a program is shown as thus:

Note that it can be considered as a contiguous block of memory ( virtual memory). I would imagine some part of the virtual memory space is divided among the stacks for the threads. Which brings me to the second part of this question: a popular technical interview question involves trying to implement 3 stacks using a single array. Is this problem directly related to solving the implementation of thread stacks.

I summarize my questions thus:

1. How does a modern day OS, say Linux divide the memory space for stacks of different threads?
2. Is the "3 stacks using 1 array" directly related to or an answer for the above question?

PS: Perhaps images to explain how the memory is divided for different thread stacks would be best to explain.

Divan

Answer 1

The picture shown above is totally obsolete on both Windows and Linux. It doesn't really matter at what addresses the individual allocations are located. Virtual address space is big on 32 bit and vast on 64 bit. The OS just needs to carve out some chunk of it somewhere and hand it out.

Each stack is an independent virtual memory allocation that can be placed at arbitrary locations. It is important to note that stacks are generally finite in size. The OS reserves a certain maximum size (such a 1MB or 8MB). The stack cannot exceed that size. This is suggested differently in the (obsolete) picture above. The stack indeed grows down, but when the fixed space is exhausted a stack overflow is triggered. This is not a concern in practice. In fact, exceeding a reasonable stack size is considered to be a bug.

Binary images (above: text, initialized data and bss) are also just placed anywhere. They are fixed in size as well.

The heap consists of multiple segments. It can grow arbitrarily by just adding more segments. The heap is managed by user-mode libraries. The kernel doesn't know about it. All the kernel does is provide slabs of virtual memory at locations chosen at will.

Kovrov

Wow. Yes it becomes quite simple. Another benefit of using virtual memory. =) – Divan

Answer 2

1)Thread's stack is just a contiguous block in virtual memory. It's maximal size is fixed. It may look like that:

2)I don't think it is directly related to this problem because thread's stack size limit is known when a thread is created, but nothing is known about each of 3 stack's sizes in a problem about "3 stacks using 1 array".

Helmand

Answer 3

Complementing usr's answer, here's a view of the stack using virtual memory:

Original image found in https://en.wikipedia.org/wiki/Virtual_address_space

Squatter