Link Search Menu Expand Document

The thread struct

Each thread struct represents either a kernel thread or a user process. In each of the 3 projects, you will have to add your own members to the thread struct. You may also need to change or delete the definitions of existing members.

Every thread struct occupies the beginning of its own 4 KiB page of memory. The rest of the page is used for the thread’s stack, which grows downward from the end of the page. It looks like this:

                  4 kB +---------------------------------+
                       |          kernel stack           |
                       |                |                |
                       |                |                |
                       |                V                |
                       |         grows downward          |
                       |                                 |
                       |                                 |
                       |                                 |
                       |                                 |
                       |                                 |
                       |                                 |
sizeof (struct thread) +---------------------------------+
                       |              magic              |
                       |                :                |
                       |                :                |
                       |              status             |
                       |               tid               |
                  0 kB +---------------------------------+

This layout has two consequences. First, struct thread must not be allowed to grow too big. If it does, then there will not be enough room for the kernel stack. The base struct thread is only a few bytes in size. It probably should stay well under 1 kB.

Second, kernel stacks must not be allowed to grow too large. If a stack overflows, it will corrupt the thread state. Thus, kernel functions should not allocate large structures or arrays as non-static local variables. Use dynamic allocation with malloc() or palloc_get_page() instead. See the Memory Allocation section for more details.

Here are some details on the important members of struct thread:

tid_t tid

The thread’s thread identifier or tid. Every thread must have a tid that is unique over the entire lifetime of the kernel. By default, tid_t is a typedef for int and each new thread receives the numerically next higher tid, starting from 1 for the initial process.

enum thread_status status

The thread’s state. One of the following:

THREAD_RUNNING

The thread is running. Exactly one thread is running at a given time. thread_current() returns the running thread.

THREAD_READY

The thread is ready to run, but it’s not running right now. The thread could be selected to run the next time the scheduler is invoked. Ready threads are kept in a doubly linked list called ready_list.

THREAD_BLOCKED

The thread is waiting for something, e.g. a lock to become available or an interrupt to be invoked. The thread won’t be scheduled again until it transitions to the THREAD_READY state with a call to thread_unblock(). This is most conveniently done indirectly, using one of the Pintos synchronization primitives that block and unblock threads automatically.

THREAD_DYING

The thread has exited and will be destroyed by the scheduler after switching to the next thread.

char name[16]

The thread’s name as a string, or at least the first few characters of it.

uint8_t *stack

Every thread has its own stack to keep track of its state. When the thread is running, the CPU’s stack pointer register tracks the top of the stack and this member is unused. But when the CPU switches to another thread, this member saves the thread’s stack pointer. No other members are needed to save the thread’s registers, because the other registers that must be saved are saved on the stack.

When an interrupt occurs, whether in the kernel or a user program, a struct intr_frame is pushed onto the stack. When the interrupt occurs in a user program, the struct intr_frame is always at the very top of the page.

int priority

A thread priority, ranging from PRI_MIN (0) to PRI_MAX (63). Lower numbers correspond to lower priorities, so that priority 0 is the lowest priority and priority 63 is the highest. Pintos currently ignores these priorities, but you will implement priority scheduling in Project 2.

struct list_elem allelem

This “list element” is used to link the thread into the list of all threads. Each thread is inserted into this list when it is created and removed when it exits. The thread_foreach() function should be used to iterate over all threads.

struct list_elem elem

A “list element” used to put the thread into doubly linked lists, either ready_list (the list of threads ready to run) or a list of threads waiting on a semaphore in sema_down(). It can do double duty because a thread waiting on a semaphore is not ready, and vice versa.

uint32_t *pagedir

(Used in Projects Userprog and Filesys). The page table for the process, if this is a user process.

unsigned magic

Always set to THREAD_MAGIC, which is just an arbitrary number defined in threads/thread.c, and used to detect stack overflow. thread_current() checks that the magic member of the running thread’s struct thread is set to THREAD_MAGIC. Stack overflow tends to change this value, triggering the assertion. For greatest benefit, as you add members to struct thread, leave magic at the end.