#include "threads/thread.h"
#include <debug.h>
#include <stddef.h>
#include <random.h>
#include <stdio.h>
#include <string.h>
#include "threads/flags.h"
#include "threads/interrupt.h"
#include "threads/intr-stubs.h"
#include "threads/palloc.h"
#include "threads/switch.h"
#include "threads/synch.h"
#include "threads/vaddr.h"

Include dependency graph for thread.c:

Data Structures
struct	kernel_thread_frame
	Stack frame for kernel_thread(). More...

Macros
#define	THREAD_MAGIC 0xcd6abf4b
	Random value for struct thread's ‘magic’ member. More...

#define	TIME_SLICE 4
	Scheduling. More...

Functions
static void	kernel_thread (thread_func function, void aux)
	Function used as the basis for a kernel thread. More...

static void	idle (void *aux UNUSED)

static struct thread *	running_thread (void)
	Returns the running thread. More...

static struct thread *	next_thread_to_run (void)
	Chooses and returns the next thread to be scheduled. More...

static void	init_thread (struct thread t, const char name, int priority)
	Does basic initialization of T as a blocked thread named NAME. More...

static bool	is_thread (struct thread *)
	Initializes the threading system by transforming the code that's currently running into a thread. More...

void	thread_start (void)
	Starts preemptive thread scheduling by enabling interrupts. More...

void	thread_tick (void)
	Called by the timer interrupt handler at each timer tick. More...

void	thread_print_stats (void)
	Prints thread statistics. More...

tid_t	thread_create (const char name, int priority, thread_func function, void *aux)
	Creates a new kernel thread named NAME with the given initial PRIORITY, which executes FUNCTION passing AUX as the argument, and adds it to the ready queue. More...

void	thread_block (void)
	Puts the current thread to sleep. More...

void	thread_unblock (struct thread *t)
	Transitions a blocked thread T to the ready-to-run state. More...

const char *	thread_name (void)
	Returns the name of the running thread. More...

struct thread *	thread_current (void)
	Returns the running thread. More...

tid_t	thread_tid (void)
	Returns the running thread's tid. More...

void	thread_exit (void)
	Deschedules the current thread and destroys it. More...

void	thread_yield (void)
	Yields the CPU. More...

void	thread_foreach (thread_action_func func, void aux)
	Invoke function 'func' on all threads, passing along 'aux'. More...

void	thread_set_priority (int new_priority)
	Sets the current thread's priority to NEW_PRIORITY. More...

int	thread_get_priority (void)
	Returns the current thread's priority. More...

void	thread_set_nice (int nice UNUSED)
	Sets the current thread's nice value to NICE. More...

int	thread_get_nice (void)
	Returns the current thread's nice value. More...

int	thread_get_load_avg (void)
	Returns 100 times the system load average. More...

int	thread_get_recent_cpu (void)
	Returns 100 times the current thread's recent_cpu value. More...

static void	idle (void *idle_started_ UNUSED)
	Idle thread. More...

static void *	alloc_frame (struct thread *t, size_t size)
	Allocates a SIZE-byte frame at the top of thread T's stack and returns a pointer to the frame's base. More...

void	thread_schedule_tail (struct thread *prev)
	Completes a thread switch by activating the new thread's page tables, and, if the previous thread is dying, destroying it. More...

static void	schedule (void)
	Schedules a new process. More...

static tid_t	allocate_tid (void)
	Returns a tid to use for a new thread. More...

Variables
static struct list	ready_list
	List of processes in THREAD_READY state, that is, processes that are ready to run but not actually running. More...

static struct list	all_list
	List of all processes. More...

static struct thread *	idle_thread
	Idle thread. More...

static struct thread *	initial_thread
	Initial thread, the thread running init.c:main(). More...

static struct lock	tid_lock
	Lock used by allocate_tid(). More...

static long long	idle_ticks
	Statistics. More...

static long long	kernel_ticks

static long long	user_ticks

static unsigned	thread_ticks

bool	thread_mlfqs
	If false (default), use round-robin scheduler. More...

uint32_t	thread_stack_ofs = offsetof (struct thread, stack)
	Offset of ‘stack’ member within ‘struct thread’. More...

Macro Definition Documentation

◆ THREAD_MAGIC

#define THREAD_MAGIC 0xcd6abf4b

Random value for struct thread's ‘magic’ member.

Used to detect stack overflow. See the big comment at the top of thread.h for details.

Definition at line 21 of file thread.c.

◆ TIME_SLICE

#define TIME_SLICE 4

Scheduling.

of timer ticks to give each thread.

Definition at line 54 of file thread.c.

Function Documentation

◆ alloc_frame()

static void* alloc_frame	(	struct thread *	t,
		size_t	size
	)

static

Allocates a SIZE-byte frame at the top of thread T's stack and returns a pointer to the frame's base.

Definition at line 475 of file thread.c.

References ASSERT, is_thread(), and thread::stack.

Referenced by thread_create().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ allocate_tid()

static tid_t allocate_tid ( void )

static

Returns a tid to use for a new thread.

Definition at line 570 of file thread.c.

References lock_acquire(), lock_release(), thread::tid, and tid_lock.

Referenced by thread_create().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ idle() [1/2]

static void idle ( void *aux UNUSED )

static

Referenced by thread_start().

Here is the caller graph for this function:

◆ idle() [2/2]

static void idle ( void *idle_started_ UNUSED )

static

Idle thread.

Executes when no other thread is ready to run.

The idle thread is initially put on the ready list by thread_start(). It will be scheduled once initially, at which point it initializes idle_thread, "up"s the semaphore passed to it to enable thread_start() to continue, and immediately blocks. After that, the idle thread never appears in the ready list. It is returned by next_thread_to_run() as a special case when the ready list is empty.

Definition at line 389 of file thread.c.

References idle_thread, intr_disable(), sema_up(), thread_block(), and thread_current().

Here is the call graph for this function:

◆ init_thread()

static void init_thread	(	struct thread *	t,
		const char *	name,
		int	priority
	)

static

Does basic initialization of T as a blocked thread named NAME.

Definition at line 452 of file thread.c.

References all_list, thread::allelem, ASSERT, intr_disable(), intr_set_level(), list_push_back(), thread::magic, memset(), name, thread::name, NULL, PGSIZE, PRI_MAX, PRI_MIN, thread::priority, thread::stack, thread::status, strlcpy(), THREAD_BLOCKED, and THREAD_MAGIC.

Referenced by thread_create().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ is_thread()

static bool is_thread ( struct thread * t )

static

Initializes the threading system by transforming the code that's currently running into a thread.

Returns true if T appears to point to a valid thread.

This can't work in general and it is possible in this case only because loader.S was careful to put the bottom of the stack at a page boundary.

Also initializes the run queue and the tid lock.

After calling this function, be sure to initialize the page allocator before trying to create any threads with thread_create().

It is not safe to call thread_current() until this function finishes.

Definition at line 68 of file thread.c.

Referenced by alloc_frame(), schedule(), thread_current(), and thread_unblock().

Here is the caller graph for this function:

◆ kernel_thread()

static void kernel_thread	(	thread_func *	function,
		void *	aux
	)

static

Function used as the basis for a kernel thread.

< The scheduler runs with interrupts off.

< Execute the thread function.

< If function() returns, kill the thread.

Definition at line 419 of file thread.c.

References ASSERT, intr_enable(), NULL, and thread_exit().

Referenced by thread_create().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ next_thread_to_run()

static struct thread * next_thread_to_run ( void )

static

Chooses and returns the next thread to be scheduled.

Should return a thread from the run queue, unless the run queue is empty. (If the running thread can continue running, then it will be in the run queue.) If the run queue is empty, return idle_thread.

Definition at line 491 of file thread.c.

References thread::elem, idle_thread, list_empty(), list_entry, list_pop_front(), and ready_list.

Referenced by schedule().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ running_thread()

struct thread * running_thread ( void )

static

Returns the running thread.

Definition at line 430 of file thread.c.

References pg_round_down().

Referenced by schedule(), thread_current(), and thread_schedule_tail().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ schedule()

static void schedule ( void )

static

Schedules a new process.

At entry, interrupts must be off and the running process's state must have been changed from running to some other state. This function finds another thread to run and switches to it.

It's not safe to call printf() until thread_schedule_tail() has completed.

Definition at line 553 of file thread.c.

References ASSERT, intr_get_level(), INTR_OFF, is_thread(), next(), next_thread_to_run(), NULL, running_thread(), thread::status, switch_threads(), THREAD_RUNNING, and thread_schedule_tail().

Referenced by thread_block(), thread_exit(), and thread_yield().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ thread_block()

void thread_block ( void )

Puts the current thread to sleep.

It will not be scheduled again until awoken by thread_unblock().

This function must be called with interrupts turned off. It is usually a better idea to use one of the synchronization primitives in synch.h.

Definition at line 214 of file thread.c.

References ASSERT, intr_context(), intr_get_level(), INTR_OFF, schedule(), thread::status, THREAD_BLOCKED, and thread_current().

Referenced by idle(), sema_down(), and wait().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ thread_create()

tid_t thread_create	(	const char *	name,
		int	priority,
		thread_func *	function,
		void *	aux
	)

Creates a new kernel thread named NAME with the given initial PRIORITY, which executes FUNCTION passing AUX as the argument, and adds it to the ready queue.

Returns the thread identifier for the new thread, or TID_ERROR if creation fails.

If thread_start() has been called, then the new thread may be scheduled before thread_create() returns. It could even exit before thread_create() returns. Contrariwise, the original thread may run for any amount of time before the new thread is scheduled. Use a semaphore or some other form of synchronization if you need to ensure ordering.

The code provided sets the new thread's ‘priority’ member to PRIORITY, but no actual priority scheduling is implemented. Priority scheduling is the goal of Problem 1-3.

Definition at line 166 of file thread.c.

References alloc_frame(), allocate_tid(), ASSERT, kernel_thread_frame::aux, switch_threads_frame::ebp, switch_threads_frame::eip, switch_entry_frame::eip, kernel_thread_frame::eip, kernel_thread_frame::function, init_thread(), kernel_thread(), name, NULL, PAL_ZERO, palloc_get_page(), switch_entry(), thread_unblock(), thread::tid, and TID_ERROR.

Referenced by process_execute(), sema_self_test(), test_alarm_priority(), test_mlfqs_block(), test_mlfqs_fair(), test_mlfqs_load_60(), test_mlfqs_load_avg(), test_priority_change(), test_priority_condvar(), test_priority_donate_chain(), test_priority_donate_lower(), test_priority_donate_multiple(), test_priority_donate_multiple2(), test_priority_donate_nest(), test_priority_donate_one(), test_priority_donate_sema(), test_priority_fifo(), test_priority_preempt(), test_priority_sema(), test_sleep(), and thread_start().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ thread_current()

struct thread* thread_current ( void )

Returns the running thread.

This is running_thread() plus a couple of sanity checks. See the big comment at the top of thread.h for details.

Definition at line 256 of file thread.c.

References ASSERT, is_thread(), running_thread(), thread::status, and THREAD_RUNNING.

Referenced by idle(), install_page(), load(), lock_acquire(), lock_held_by_current_thread(), lock_try_acquire(), print_stacktrace(), process_activate(), process_exit(), sema_down(), thread_block(), thread_exit(), thread_get_priority(), thread_name(), thread_set_priority(), thread_tick(), thread_tid(), thread_yield(), tss_update(), and wait().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ thread_exit()

void thread_exit ( void )

Deschedules the current thread and destroys it.

Never returns to the caller.

Definition at line 281 of file thread.c.

References thread::allelem, ASSERT, intr_context(), intr_disable(), list_remove(), NOT_REACHED, process_exit(), schedule(), thread::status, thread_current(), and THREAD_DYING.

Referenced by kernel_thread(), kill(), pintos_init(), start_process(), and syscall_handler().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ thread_foreach()

void thread_foreach	(	thread_action_func *	func,
		void *	aux
	)

Invoke function 'func' on all threads, passing along 'aux'.

This function must be called with interrupts off.

Definition at line 320 of file thread.c.

References all_list, thread::allelem, ASSERT, intr_get_level(), INTR_OFF, list_begin(), list_end(), list_entry, and list_next().

Referenced by debug_backtrace_all().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ thread_get_load_avg()

int thread_get_load_avg ( void )

Returns 100 times the system load average.

threads/thread.h

Definition at line 365 of file thread.c.

Referenced by test_mlfqs_load_1(), test_mlfqs_load_60(), test_mlfqs_load_avg(), and test_mlfqs_recent_1().

Here is the caller graph for this function:

◆ thread_get_nice()

int thread_get_nice ( void )

Returns the current thread's nice value.

Definition at line 357 of file thread.c.

◆ thread_get_priority()

int thread_get_priority ( void )

Returns the current thread's priority.

Definition at line 343 of file thread.c.

References thread::priority, and thread_current().

Referenced by donor_thread_func(), medium_thread_func(), test_priority_donate_chain(), test_priority_donate_lower(), test_priority_donate_multiple(), test_priority_donate_multiple2(), test_priority_donate_nest(), test_priority_donate_one(), test_priority_donate_sema(), test_priority_fifo(), and test_priority_preempt().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ thread_get_recent_cpu()

int thread_get_recent_cpu ( void )

Definition at line 373 of file thread.c.

Referenced by test_mlfqs_recent_1().

Here is the caller graph for this function:

◆ thread_name()

const char* thread_name ( void )

Returns the name of the running thread.

Definition at line 247 of file thread.c.

References thread::name, and thread_current().

Referenced by alarm_priority_thread(), donor_thread_func(), interloper_thread_func(), kill(), priority_condvar_thread(), priority_sema_thread(), simple_thread_func(), and test_priority_donate_chain().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ thread_print_stats()

void thread_print_stats ( void )

Prints thread statistics.

Definition at line 144 of file thread.c.

References idle_ticks, kernel_ticks, printf(), and user_ticks.

Referenced by print_stats().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ thread_schedule_tail()

void thread_schedule_tail ( struct thread * prev )

Completes a thread switch by activating the new thread's page tables, and, if the previous thread is dying, destroying it.

At this function's invocation, we just switched from thread PREV, the new thread is already running, and interrupts are still disabled. This function is normally invoked by thread_schedule() as its final action before returning, but the first time a thread is scheduled it is called by switch_entry() (see switch.S).

It's not safe to call printf() until the thread switch is complete. In practice that means that printf()s should be added at the end of the function.

After this function and its caller returns, the thread switch is complete.

Definition at line 516 of file thread.c.

References ASSERT, initial_thread, intr_get_level(), INTR_OFF, NULL, palloc_free_page(), process_activate(), running_thread(), thread::status, THREAD_DYING, THREAD_RUNNING, and thread_ticks.

Referenced by schedule().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ thread_set_nice()

void thread_set_nice ( int nice UNUSED )

Sets the current thread's nice value to NICE.

Definition at line 350 of file thread.c.

Referenced by load_thread(), test_mlfqs_fair(), and test_mlfqs_load_avg().

Here is the caller graph for this function:

◆ thread_set_priority()

void thread_set_priority ( int new_priority )

Sets the current thread's priority to NEW_PRIORITY.

Definition at line 336 of file thread.c.

References thread::priority, and thread_current().

Referenced by changing_thread(), test_alarm_priority(), test_priority_change(), test_priority_condvar(), test_priority_donate_chain(), test_priority_donate_lower(), test_priority_fifo(), and test_priority_sema().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ thread_start()

void thread_start ( void )

Starts preemptive thread scheduling by enabling interrupts.

Also creates the idle thread.

Definition at line 106 of file thread.c.

References idle(), intr_enable(), PRI_MIN, sema_down(), sema_init(), and thread_create().

Referenced by pintos_init().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ thread_tick()

void thread_tick ( void )

Called by the timer interrupt handler at each timer tick.

Thus, this function runs in an external interrupt context.

Definition at line 123 of file thread.c.

References idle_thread, idle_ticks, intr_yield_on_return(), kernel_ticks, NULL, thread_current(), thread_ticks, TIME_SLICE, and user_ticks.

Referenced by timer_interrupt().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ thread_tid()

tid_t thread_tid ( void )

Returns the running thread's tid.

Definition at line 273 of file thread.c.

References thread_current(), and thread::tid.

Here is the call graph for this function:

◆ thread_unblock()

void thread_unblock ( struct thread * t )

Transitions a blocked thread T to the ready-to-run state.

This is an error if T is not blocked. (Use thread_yield() to make the running thread ready.)

This function does not preempt the running thread. This can be important: if the caller had disabled interrupts itself, it may expect that it can atomically unblock a thread and update other data.

Definition at line 232 of file thread.c.

References ASSERT, thread::elem, intr_disable(), intr_set_level(), is_thread(), list_push_back(), ready_list, thread::status, THREAD_BLOCKED, and THREAD_READY.

Referenced by sema_up(), signal(), and thread_create().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ thread_yield()

void thread_yield ( void )

Yields the CPU.

The current thread is not put to sleep and may be scheduled again immediately at the scheduler's whim.

Definition at line 302 of file thread.c.

References ASSERT, thread::elem, idle_thread, intr_context(), intr_disable(), intr_set_level(), list_push_back(), ready_list, schedule(), thread::status, thread_current(), and THREAD_READY.

Referenced by intr_handler(), medium_thread_func(), simple_thread_func(), sleeper(), test_priority_donate_nest(), and timer_sleep().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

◆ all_list

struct list all_list

static

List of all processes.

Processes are added to this list when they are first scheduled and removed when they exit.

Definition at line 29 of file thread.c.

Referenced by init_thread(), and thread_foreach().

◆ idle_thread

struct thread* idle_thread

static

Idle thread.

Definition at line 32 of file thread.c.

Referenced by idle(), next_thread_to_run(), thread_tick(), and thread_yield().

◆ idle_ticks

long long idle_ticks

static

Statistics.

of timer ticks spent idle.

Definition at line 49 of file thread.c.

Referenced by thread_print_stats(), and thread_tick().

◆ initial_thread

struct thread* initial_thread

static

Initial thread, the thread running init.c:main().

Definition at line 35 of file thread.c.

Referenced by thread_schedule_tail().

◆ kernel_ticks

long long kernel_ticks

static

of timer ticks in kernel threads.

Definition at line 50 of file thread.c.

Referenced by thread_print_stats(), and thread_tick().

◆ ready_list

struct list ready_list

static

List of processes in THREAD_READY state, that is, processes that are ready to run but not actually running.

Definition at line 25 of file thread.c.

Referenced by next_thread_to_run(), thread_unblock(), and thread_yield().

◆ thread_mlfqs

bool thread_mlfqs

If false (default), use round-robin scheduler.

If true, use multi-level feedback queue scheduler. Controlled by kernel command-line option "-o mlfqs".

Definition at line 60 of file thread.c.

Referenced by parse_options(), test_alarm_priority(), test_mlfqs_block(), test_mlfqs_fair(), test_mlfqs_load_1(), test_mlfqs_load_60(), test_mlfqs_load_avg(), test_mlfqs_recent_1(), test_priority_change(), test_priority_condvar(), test_priority_donate_chain(), test_priority_donate_lower(), test_priority_donate_multiple(), test_priority_donate_multiple2(), test_priority_donate_nest(), test_priority_donate_one(), test_priority_donate_sema(), test_priority_fifo(), test_priority_preempt(), test_priority_sema(), and test_sleep().

◆ thread_stack_ofs

uint32_t thread_stack_ofs = offsetof (struct thread, stack)

Offset of ‘stack’ member within ‘struct thread’.

Used by switch.S, which can't figure it out on its own.

Definition at line 584 of file thread.c.

◆ thread_ticks

unsigned thread_ticks

static

of timer ticks since last yield.

Definition at line 55 of file thread.c.

Referenced by thread_schedule_tail(), and thread_tick().

◆ tid_lock

struct lock tid_lock

static

Lock used by allocate_tid().

Definition at line 38 of file thread.c.

Referenced by allocate_tid().

◆ user_ticks

long long user_ticks

static

of timer ticks in user programs.

Definition at line 51 of file thread.c.

Referenced by thread_print_stats(), and thread_tick().

Data Structures

Macros

Functions

Variables

Macro Definition Documentation

◆ THREAD_MAGIC

◆ TIME_SLICE

of timer ticks to give each thread.

Function Documentation

◆ alloc_frame()

◆ allocate_tid()

◆ idle() [1/2]

◆ idle() [2/2]

◆ init_thread()

◆ is_thread()

◆ kernel_thread()

◆ next_thread_to_run()

◆ running_thread()

◆ schedule()

◆ thread_block()

◆ thread_create()

◆ thread_current()

◆ thread_exit()

◆ thread_foreach()

◆ thread_get_load_avg()

◆ thread_get_nice()

◆ thread_get_priority()

◆ thread_get_recent_cpu()

◆ thread_name()

◆ thread_print_stats()

◆ thread_schedule_tail()

◆ thread_set_nice()

◆ thread_set_priority()

◆ thread_start()

◆ thread_tick()

◆ thread_tid()

◆ thread_unblock()

◆ thread_yield()

Variable Documentation

◆ all_list

◆ idle_thread

◆ idle_ticks

of timer ticks spent idle.

◆ initial_thread

◆ kernel_ticks

of timer ticks in kernel threads.

◆ ready_list

◆ thread_mlfqs

◆ thread_stack_ofs

◆ thread_ticks

of timer ticks since last yield.

◆ tid_lock

◆ user_ticks

of timer ticks in user programs.