synch.h File Reference

#include <list.h>
#include <stdbool.h>

Include dependency graph for synch.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	semaphore
	A counting semaphore. More...
struct	lock
	Lock. More...
struct	condition
	Condition variable. More...

Macros
#define	barrier()   asm volatile ("" : : : "memory")
	Optimization barrier. More...

Functions
void	sema_init (struct semaphore *, unsigned value)
	This file is derived from source code for the Nachos instructional operating system. More...
void	sema_down (struct semaphore *)
	Down or "P" operation on a semaphore. More...
bool	sema_try_down (struct semaphore *)
	Down or "P" operation on a semaphore, but only if the semaphore is not already 0. More...
void	sema_up (struct semaphore *)
	Up or "V" operation on a semaphore. More...
void	sema_self_test (void)
	Self-test for semaphores that makes control "ping-pong" between a pair of threads. More...
void	lock_init (struct lock *)
	Initializes LOCK. More...
void	lock_acquire (struct lock *)
	Acquires LOCK, sleeping until it becomes available if necessary. More...
bool	lock_try_acquire (struct lock *)
	Tries to acquires LOCK and returns true if successful or false on failure. More...
void	lock_release (struct lock *)
	Releases LOCK, which must be owned by the current thread. More...
bool	lock_held_by_current_thread (const struct lock *)
	Returns true if the current thread holds LOCK, false otherwise. More...
void	cond_init (struct condition *)
	Initializes condition variable COND. More...
void	cond_wait (struct condition *, struct lock *)
	Atomically releases LOCK and waits for COND to be signaled by some other piece of code. More...
void	cond_signal (struct condition *, struct lock *)
void	cond_broadcast (struct condition *, struct lock *)
	Wakes up all threads, if any, waiting on COND (protected by LOCK). More...

Macro Definition Documentation

barrier

#define barrier

(

)

asm volatile ("" : : : "memory")

Optimization barrier.

The compiler will not reorder operations across an optimization barrier. See "Optimization Barriers" in the reference guide for more information. threads/synch.h

Definition at line 49 of file synch.h.

Function Documentation

cond_broadcast()

void cond_broadcast	(	struct condition *	cond,
		struct lock *	lock
	)

Wakes up all threads, if any, waiting on COND (protected by LOCK).

LOCK must be held before calling this function.

An interrupt handler cannot acquire a lock, so it does not make sense to try to signal a condition variable within an interrupt handler.

Definition at line 331 of file synch.c.

References ASSERT, cond_signal(), list_empty(), NULL, and condition::waiters.

Here is the call graph for this function:

cond_init()

void cond_init

(

struct condition *

cond

)

Initializes condition variable COND.

A condition variable allows one piece of code to signal a condition and cooperating code to receive the signal and act upon it.

Definition at line 260 of file synch.c.

References ASSERT, list_init(), NULL, and condition::waiters.

Referenced by test_priority_condvar().

Here is the call graph for this function:

Here is the caller graph for this function:

cond_signal()

void cond_signal	(	struct condition *	,
		struct lock *
	)

cond_wait()

void cond_wait	(	struct condition *	cond,
		struct lock *	lock
	)

Atomically releases LOCK and waits for COND to be signaled by some other piece of code.

After COND is signaled, LOCK is reacquired before returning. LOCK must be held before calling this function.

The monitor implemented by this function is "Mesa" style, not "Hoare" style, that is, sending and receiving a signal are not an atomic operation. Thus, typically the caller must recheck the condition after the wait completes and, if necessary, wait again.

A given condition variable is associated with only a single lock, but one lock may be associated with any number of condition variables. That is, there is a one-to-many mapping from locks to condition variables.

This function may sleep, so it must not be called within an interrupt handler. This function may be called with interrupts disabled, but interrupts will be turned back on if we need to sleep.

Definition at line 288 of file synch.c.

References ASSERT, semaphore_elem::elem, intr_context(), list_push_back(), lock_acquire(), lock_held_by_current_thread(), lock_release(), NULL, sema_down(), sema_init(), semaphore_elem::semaphore, and condition::waiters.

Referenced by priority_condvar_thread().

Here is the call graph for this function:

Here is the caller graph for this function:

lock_acquire()

void lock_acquire

(

struct lock *

lock

)

Acquires LOCK, sleeping until it becomes available if necessary.

The lock must not already be held by the current thread.

This function may sleep, so it must not be called within an interrupt handler. This function may be called with interrupts disabled, but interrupts will be turned back on if we need to sleep.

Definition at line 193 of file synch.c.

References ASSERT, lock::holder, intr_context(), lock_held_by_current_thread(), NULL, sema_down(), lock::semaphore, and thread_current().

Referenced by a_thread_func(), acquire1_thread_func(), acquire2_thread_func(), acquire_console(), acquire_thread_func(), allocate_tid(), b_thread_func(), block_thread(), cond_wait(), donor_thread_func(), free(), h_thread_func(), high_thread_func(), ide_read(), ide_write(), intq_getc(), intq_putc(), l_thread_func(), malloc(), medium_thread_func(), palloc_get_multiple(), priority_condvar_thread(), simple_thread_func(), sleeper(), test_mlfqs_block(), 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(), and test_sleep().

Here is the call graph for this function:

Here is the caller graph for this function:

lock_held_by_current_thread()

bool lock_held_by_current_thread

(

const struct lock *

lock

)

Returns true if the current thread holds LOCK, false otherwise.

(Note that testing whether some other thread holds a lock would be racy.)

Definition at line 242 of file synch.c.

References ASSERT, lock::holder, NULL, and thread_current().

Referenced by acquire_console(), cond_signal(), cond_wait(), console_locked_by_current_thread(), lock_acquire(), lock_release(), and lock_try_acquire().

Here is the call graph for this function:

Here is the caller graph for this function:

lock_init()

void lock_init

(

struct lock *

lock

)

Initializes LOCK.

A lock can be held by at most a single thread at any given time. Our locks are not "recursive", that is, it is an error for the thread currently holding a lock to try to acquire that lock.

A lock is a specialization of a semaphore with an initial value of 1. The difference between a lock and such a semaphore is twofold. First, a semaphore can have a value greater than 1, but a lock can only be owned by a single thread at a time. Second, a semaphore does not have an owner, meaning that one thread can "down" the semaphore and then another one "up" it, but with a lock the same thread must both acquire and release it. When these restrictions prove onerous, it's a good sign that a semaphore should be used, instead of a lock.

Definition at line 176 of file synch.c.

References ASSERT, lock::holder, NULL, sema_init(), and lock::semaphore.

Referenced by console_init(), ide_init(), init_pool(), intq_init(), malloc_init(), test_mlfqs_block(), 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(), and test_sleep().

Here is the call graph for this function:

Here is the caller graph for this function:

lock_release()

void lock_release

(

struct lock *

lock

)

Releases LOCK, which must be owned by the current thread.

An interrupt handler cannot acquire a lock, so it does not make sense to try to release a lock within an interrupt handler.

Definition at line 229 of file synch.c.

References ASSERT, lock::holder, lock_held_by_current_thread(), NULL, sema_up(), and lock::semaphore.

Referenced by a_thread_func(), acquire1_thread_func(), acquire2_thread_func(), acquire_thread_func(), allocate_tid(), b_thread_func(), cond_wait(), donor_thread_func(), free(), h_thread_func(), high_thread_func(), ide_read(), ide_write(), intq_getc(), intq_putc(), l_thread_func(), malloc(), medium_thread_func(), palloc_get_multiple(), priority_condvar_thread(), release_console(), simple_thread_func(), sleeper(), test_mlfqs_block(), 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(), and test_sleep().

Here is the call graph for this function:

Here is the caller graph for this function:

lock_try_acquire()

bool lock_try_acquire

(

struct lock *

lock

)

Tries to acquires LOCK and returns true if successful or false on failure.

The lock must not already be held by the current thread.

This function will not sleep, so it may be called within an interrupt handler.

Definition at line 210 of file synch.c.

References ASSERT, lock::holder, lock_held_by_current_thread(), NULL, sema_try_down(), lock::semaphore, and thread_current().

Here is the call graph for this function:

sema_down()

void sema_down

(

struct semaphore *

sema

)

Down or "P" operation on a semaphore.

Waits for SEMA's value to become positive and then atomically decrements it.

This function may sleep, so it must not be called within an interrupt handler. This function may be called with interrupts disabled, but if it sleeps then the next scheduled thread will probably turn interrupts back on.

Definition at line 61 of file synch.c.

References ASSERT, intr_context(), intr_disable(), intr_set_level(), list_push_back(), NULL, sema, thread_block(), thread_current(), semaphore::value, and semaphore::waiters.

Referenced by cond_wait(), ide_read(), ide_write(), identify_ata_device(), l_thread_func(), lock_acquire(), m_thread_func(), priority_sema_thread(), sema_self_test(), sema_test_helper(), test_alarm_priority(), and thread_start().

Here is the call graph for this function:

Here is the caller graph for this function:

sema_init()

void sema_init	(	struct semaphore *	sema,
		unsigned	value
	)

This file is derived from source code for the Nachos instructional operating system.

The Nachos copyright notice is reproduced in full below. Copyright (c) 1992-1996 The Regents of the University of California. All rights reserved.

Permission to use, copy, modify, and distribute this software and its documentation for any purpose, without fee, and without written agreement is hereby granted, provided that the above copyright notice and the following two paragraphs appear in all copies of this software.

IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. Initializes semaphore SEMA to VALUE. A semaphore is a nonnegative integer along with two atomic operators for manipulating it:

• down or "P": wait for the value to become positive, then decrement it.
• up or "V": increment the value (and wake up one waiting thread, if any).

Definition at line 45 of file synch.c.

References ASSERT, list_init(), NULL, sema, semaphore::value, and semaphore::waiters.

Referenced by cond_wait(), ide_init(), lock_init(), sema_self_test(), test_alarm_priority(), test_priority_donate_sema(), test_priority_sema(), and thread_start().

Here is the call graph for this function:

Here is the caller graph for this function:

sema_self_test()

void sema_self_test

(

void

)

Self-test for semaphores that makes control "ping-pong" between a pair of threads.

Insert calls to printf() to see what's going on.

Definition at line 129 of file synch.c.

References PRI_DEFAULT, printf(), sema, sema_down(), sema_init(), sema_test_helper(), sema_up(), and thread_create().

Here is the call graph for this function:

sema_try_down()

bool sema_try_down

(

struct semaphore *

sema

)

Down or "P" operation on a semaphore, but only if the semaphore is not already 0.

Returns true if the semaphore is decremented, false otherwise.

This function may be called from an interrupt handler.

Definition at line 84 of file synch.c.

References ASSERT, intr_disable(), intr_set_level(), NULL, sema, and semaphore::value.

Referenced by lock_try_acquire().

Here is the call graph for this function:

Here is the caller graph for this function:

sema_up()

void sema_up

(

struct semaphore *

sema

)

Up or "V" operation on a semaphore.

Increments SEMA's value and wakes up one thread of those waiting for SEMA, if any.

This function may be called from an interrupt handler.

Definition at line 109 of file synch.c.

References ASSERT, intr_disable(), intr_set_level(), list_empty(), list_entry, list_pop_front(), NULL, sema, thread_unblock(), semaphore::value, and semaphore::waiters.

Referenced by alarm_priority_thread(), cond_signal(), h_thread_func(), idle(), interrupt_handler(), lock_release(), sema_self_test(), sema_test_helper(), test_priority_donate_sema(), and test_priority_sema().

Here is the call graph for this function:

Here is the caller graph for this function: