hw2_pt - HW2 implemented using protothread

Users » the729 » Code » hw2_pt

HW2 implemented using protothread

pt-sem.h@0:e2cc8ae74a24, 2010-12-01 (annotated)

Committer:: the729
Date:: Wed Dec 01 02:53:56 2010 +0000
Revision:: 0:e2cc8ae74a24

Who changed what in which revision?

User	Revision	Line number	New contents of line
the729	0:e2cc8ae74a24	1	/*
the729	0:e2cc8ae74a24	2	* Copyright (c) 2004, Swedish Institute of Computer Science.
the729	0:e2cc8ae74a24	3	* All rights reserved.
the729	0:e2cc8ae74a24	4	*
the729	0:e2cc8ae74a24	5	* Redistribution and use in source and binary forms, with or without
the729	0:e2cc8ae74a24	6	* modification, are permitted provided that the following conditions
the729	0:e2cc8ae74a24	7	* are met:
the729	0:e2cc8ae74a24	8	* 1. Redistributions of source code must retain the above copyright
the729	0:e2cc8ae74a24	9	* notice, this list of conditions and the following disclaimer.
the729	0:e2cc8ae74a24	10	* 2. Redistributions in binary form must reproduce the above copyright
the729	0:e2cc8ae74a24	11	* notice, this list of conditions and the following disclaimer in the
the729	0:e2cc8ae74a24	12	* documentation and/or other materials provided with the distribution.
the729	0:e2cc8ae74a24	13	* 3. Neither the name of the Institute nor the names of its contributors
the729	0:e2cc8ae74a24	14	* may be used to endorse or promote products derived from this software
the729	0:e2cc8ae74a24	15	* without specific prior written permission.
the729	0:e2cc8ae74a24	16	*
the729	0:e2cc8ae74a24	17	* THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
the729	0:e2cc8ae74a24	18	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
the729	0:e2cc8ae74a24	19	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
the729	0:e2cc8ae74a24	20	* ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
the729	0:e2cc8ae74a24	21	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
the729	0:e2cc8ae74a24	22	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
the729	0:e2cc8ae74a24	23	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
the729	0:e2cc8ae74a24	24	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
the729	0:e2cc8ae74a24	25	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
the729	0:e2cc8ae74a24	26	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
the729	0:e2cc8ae74a24	27	* SUCH DAMAGE.
the729	0:e2cc8ae74a24	28	*
the729	0:e2cc8ae74a24	29	* This file is part of the protothreads library.
the729	0:e2cc8ae74a24	30	*
the729	0:e2cc8ae74a24	31	* Author: Adam Dunkels <adam@sics.se>
the729	0:e2cc8ae74a24	32	*
the729	0:e2cc8ae74a24	33	* $Id: pt-sem.h,v 1.2 2005/02/24 10:36:59 adam Exp $
the729	0:e2cc8ae74a24	34	*/
the729	0:e2cc8ae74a24	35
the729	0:e2cc8ae74a24	36	/**
the729	0:e2cc8ae74a24	37	* \addtogroup pt
the729	0:e2cc8ae74a24	38	* @{
the729	0:e2cc8ae74a24	39	*/
the729	0:e2cc8ae74a24	40
the729	0:e2cc8ae74a24	41	/**
the729	0:e2cc8ae74a24	42	* \defgroup ptsem Protothread semaphores
the729	0:e2cc8ae74a24	43	* @{
the729	0:e2cc8ae74a24	44	*
the729	0:e2cc8ae74a24	45	* This module implements counting semaphores on top of
the729	0:e2cc8ae74a24	46	* protothreads. Semaphores are a synchronization primitive that
the729	0:e2cc8ae74a24	47	* provide two operations: "wait" and "signal". The "wait" operation
the729	0:e2cc8ae74a24	48	* checks the semaphore counter and blocks the thread if the counter
the729	0:e2cc8ae74a24	49	* is zero. The "signal" operation increases the semaphore counter but
the729	0:e2cc8ae74a24	50	* does not block. If another thread has blocked waiting for the
the729	0:e2cc8ae74a24	51	* semaphore that is signalled, the blocked thread will become
the729	0:e2cc8ae74a24	52	* runnable again.
the729	0:e2cc8ae74a24	53	*
the729	0:e2cc8ae74a24	54	* Semaphores can be used to implement other, more structured,
the729	0:e2cc8ae74a24	55	* synchronization primitives such as monitors and message
the729	0:e2cc8ae74a24	56	* queues/bounded buffers (see below).
the729	0:e2cc8ae74a24	57	*
the729	0:e2cc8ae74a24	58	* The following example shows how the producer-consumer problem, also
the729	0:e2cc8ae74a24	59	* known as the bounded buffer problem, can be solved using
the729	0:e2cc8ae74a24	60	* protothreads and semaphores. Notes on the program follow after the
the729	0:e2cc8ae74a24	61	* example.
the729	0:e2cc8ae74a24	62	*
the729	0:e2cc8ae74a24	63	\code
the729	0:e2cc8ae74a24	64	#include "pt-sem.h"
the729	0:e2cc8ae74a24	65
the729	0:e2cc8ae74a24	66	#define NUM_ITEMS 32
the729	0:e2cc8ae74a24	67	#define BUFSIZE 8
the729	0:e2cc8ae74a24	68
the729	0:e2cc8ae74a24	69	static struct pt_sem mutex, full, empty;
the729	0:e2cc8ae74a24	70
the729	0:e2cc8ae74a24	71	PT_THREAD(producer(struct pt *pt))
the729	0:e2cc8ae74a24	72	{
the729	0:e2cc8ae74a24	73	static int produced;
the729	0:e2cc8ae74a24	74
the729	0:e2cc8ae74a24	75	PT_BEGIN(pt);
the729	0:e2cc8ae74a24	76
the729	0:e2cc8ae74a24	77	for(produced = 0; produced < NUM_ITEMS; ++produced) {
the729	0:e2cc8ae74a24	78
the729	0:e2cc8ae74a24	79	PT_SEM_WAIT(pt, &full);
the729	0:e2cc8ae74a24	80
the729	0:e2cc8ae74a24	81	PT_SEM_WAIT(pt, &mutex);
the729	0:e2cc8ae74a24	82	add_to_buffer(produce_item());
the729	0:e2cc8ae74a24	83	PT_SEM_SIGNAL(pt, &mutex);
the729	0:e2cc8ae74a24	84
the729	0:e2cc8ae74a24	85	PT_SEM_SIGNAL(pt, &empty);
the729	0:e2cc8ae74a24	86	}
the729	0:e2cc8ae74a24	87
the729	0:e2cc8ae74a24	88	PT_END(pt);
the729	0:e2cc8ae74a24	89	}
the729	0:e2cc8ae74a24	90
the729	0:e2cc8ae74a24	91	PT_THREAD(consumer(struct pt *pt))
the729	0:e2cc8ae74a24	92	{
the729	0:e2cc8ae74a24	93	static int consumed;
the729	0:e2cc8ae74a24	94
the729	0:e2cc8ae74a24	95	PT_BEGIN(pt);
the729	0:e2cc8ae74a24	96
the729	0:e2cc8ae74a24	97	for(consumed = 0; consumed < NUM_ITEMS; ++consumed) {
the729	0:e2cc8ae74a24	98
the729	0:e2cc8ae74a24	99	PT_SEM_WAIT(pt, &empty);
the729	0:e2cc8ae74a24	100
the729	0:e2cc8ae74a24	101	PT_SEM_WAIT(pt, &mutex);
the729	0:e2cc8ae74a24	102	consume_item(get_from_buffer());
the729	0:e2cc8ae74a24	103	PT_SEM_SIGNAL(pt, &mutex);
the729	0:e2cc8ae74a24	104
the729	0:e2cc8ae74a24	105	PT_SEM_SIGNAL(pt, &full);
the729	0:e2cc8ae74a24	106	}
the729	0:e2cc8ae74a24	107
the729	0:e2cc8ae74a24	108	PT_END(pt);
the729	0:e2cc8ae74a24	109	}
the729	0:e2cc8ae74a24	110
the729	0:e2cc8ae74a24	111	PT_THREAD(driver_thread(struct pt *pt))
the729	0:e2cc8ae74a24	112	{
the729	0:e2cc8ae74a24	113	static struct pt pt_producer, pt_consumer;
the729	0:e2cc8ae74a24	114
the729	0:e2cc8ae74a24	115	PT_BEGIN(pt);
the729	0:e2cc8ae74a24	116
the729	0:e2cc8ae74a24	117	PT_SEM_INIT(&empty, 0);
the729	0:e2cc8ae74a24	118	PT_SEM_INIT(&full, BUFSIZE);
the729	0:e2cc8ae74a24	119	PT_SEM_INIT(&mutex, 1);
the729	0:e2cc8ae74a24	120
the729	0:e2cc8ae74a24	121	PT_INIT(&pt_producer);
the729	0:e2cc8ae74a24	122	PT_INIT(&pt_consumer);
the729	0:e2cc8ae74a24	123
the729	0:e2cc8ae74a24	124	PT_WAIT_THREAD(pt, producer(&pt_producer) &
the729	0:e2cc8ae74a24	125	consumer(&pt_consumer));
the729	0:e2cc8ae74a24	126
the729	0:e2cc8ae74a24	127	PT_END(pt);
the729	0:e2cc8ae74a24	128	}
the729	0:e2cc8ae74a24	129	\endcode
the729	0:e2cc8ae74a24	130	*
the729	0:e2cc8ae74a24	131	* The program uses three protothreads: one protothread that
the729	0:e2cc8ae74a24	132	* implements the consumer, one thread that implements the producer,
the729	0:e2cc8ae74a24	133	* and one protothread that drives the two other protothreads. The
the729	0:e2cc8ae74a24	134	* program uses three semaphores: "full", "empty" and "mutex". The
the729	0:e2cc8ae74a24	135	* "mutex" semaphore is used to provide mutual exclusion for the
the729	0:e2cc8ae74a24	136	* buffer, the "empty" semaphore is used to block the consumer is the
the729	0:e2cc8ae74a24	137	* buffer is empty, and the "full" semaphore is used to block the
the729	0:e2cc8ae74a24	138	* producer is the buffer is full.
the729	0:e2cc8ae74a24	139	*
the729	0:e2cc8ae74a24	140	* The "driver_thread" holds two protothread state variables,
the729	0:e2cc8ae74a24	141	* "pt_producer" and "pt_consumer". It is important to note that both
the729	0:e2cc8ae74a24	142	* these variables are declared as <i>static</i>. If the static
the729	0:e2cc8ae74a24	143	* keyword is not used, both variables are stored on the stack. Since
the729	0:e2cc8ae74a24	144	* protothreads do not store the stack, these variables may be
the729	0:e2cc8ae74a24	145	* overwritten during a protothread wait operation. Similarly, both
the729	0:e2cc8ae74a24	146	* the "consumer" and "producer" protothreads declare their local
the729	0:e2cc8ae74a24	147	* variables as static, to avoid them being stored on the stack.
the729	0:e2cc8ae74a24	148	*
the729	0:e2cc8ae74a24	149	*
the729	0:e2cc8ae74a24	150	*/
the729	0:e2cc8ae74a24	151
the729	0:e2cc8ae74a24	152	/**
the729	0:e2cc8ae74a24	153	* \file
the729	0:e2cc8ae74a24	154	* Couting semaphores implemented on protothreads
the729	0:e2cc8ae74a24	155	* \author
the729	0:e2cc8ae74a24	156	* Adam Dunkels <adam@sics.se>
the729	0:e2cc8ae74a24	157	*
the729	0:e2cc8ae74a24	158	*/
the729	0:e2cc8ae74a24	159
the729	0:e2cc8ae74a24	160	#ifndef __PT_SEM_H__
the729	0:e2cc8ae74a24	161	#define __PT_SEM_H__
the729	0:e2cc8ae74a24	162
the729	0:e2cc8ae74a24	163	#include "pt.h"
the729	0:e2cc8ae74a24	164
the729	0:e2cc8ae74a24	165	struct pt_sem {
the729	0:e2cc8ae74a24	166	unsigned int count;
the729	0:e2cc8ae74a24	167	};
the729	0:e2cc8ae74a24	168
the729	0:e2cc8ae74a24	169	/**
the729	0:e2cc8ae74a24	170	* Initialize a semaphore
the729	0:e2cc8ae74a24	171	*
the729	0:e2cc8ae74a24	172	* This macro initializes a semaphore with a value for the
the729	0:e2cc8ae74a24	173	* counter. Internally, the semaphores use an "unsigned int" to
the729	0:e2cc8ae74a24	174	* represent the counter, and therefore the "count" argument should be
the729	0:e2cc8ae74a24	175	* within range of an unsigned int.
the729	0:e2cc8ae74a24	176	*
the729	0:e2cc8ae74a24	177	* \param s (struct pt_sem *) A pointer to the pt_sem struct
the729	0:e2cc8ae74a24	178	* representing the semaphore
the729	0:e2cc8ae74a24	179	*
the729	0:e2cc8ae74a24	180	* \param c (unsigned int) The initial count of the semaphore.
the729	0:e2cc8ae74a24	181	* \hideinitializer
the729	0:e2cc8ae74a24	182	*/
the729	0:e2cc8ae74a24	183	#define PT_SEM_INIT(s, c) (s)->count = c
the729	0:e2cc8ae74a24	184
the729	0:e2cc8ae74a24	185	/**
the729	0:e2cc8ae74a24	186	* Wait for a semaphore
the729	0:e2cc8ae74a24	187	*
the729	0:e2cc8ae74a24	188	* This macro carries out the "wait" operation on the semaphore. The
the729	0:e2cc8ae74a24	189	* wait operation causes the protothread to block while the counter is
the729	0:e2cc8ae74a24	190	* zero. When the counter reaches a value larger than zero, the
the729	0:e2cc8ae74a24	191	* protothread will continue.
the729	0:e2cc8ae74a24	192	*
the729	0:e2cc8ae74a24	193	* \param pt (struct pt *) A pointer to the protothread (struct pt) in
the729	0:e2cc8ae74a24	194	* which the operation is executed.
the729	0:e2cc8ae74a24	195	*
the729	0:e2cc8ae74a24	196	* \param s (struct pt_sem *) A pointer to the pt_sem struct
the729	0:e2cc8ae74a24	197	* representing the semaphore
the729	0:e2cc8ae74a24	198	*
the729	0:e2cc8ae74a24	199	* \hideinitializer
the729	0:e2cc8ae74a24	200	*/
the729	0:e2cc8ae74a24	201	#define PT_SEM_WAIT(pt, s) \
the729	0:e2cc8ae74a24	202	do { \
the729	0:e2cc8ae74a24	203	PT_WAIT_UNTIL(pt, (s)->count > 0); \
the729	0:e2cc8ae74a24	204	--(s)->count; \
the729	0:e2cc8ae74a24	205	} while(0)
the729	0:e2cc8ae74a24	206
the729	0:e2cc8ae74a24	207	/**
the729	0:e2cc8ae74a24	208	* Signal a semaphore
the729	0:e2cc8ae74a24	209	*
the729	0:e2cc8ae74a24	210	* This macro carries out the "signal" operation on the semaphore. The
the729	0:e2cc8ae74a24	211	* signal operation increments the counter inside the semaphore, which
the729	0:e2cc8ae74a24	212	* eventually will cause waiting protothreads to continue executing.
the729	0:e2cc8ae74a24	213	*
the729	0:e2cc8ae74a24	214	* \param pt (struct pt *) A pointer to the protothread (struct pt) in
the729	0:e2cc8ae74a24	215	* which the operation is executed.
the729	0:e2cc8ae74a24	216	*
the729	0:e2cc8ae74a24	217	* \param s (struct pt_sem *) A pointer to the pt_sem struct
the729	0:e2cc8ae74a24	218	* representing the semaphore
the729	0:e2cc8ae74a24	219	*
the729	0:e2cc8ae74a24	220	* \hideinitializer
the729	0:e2cc8ae74a24	221	*/
the729	0:e2cc8ae74a24	222	#define PT_SEM_SIGNAL(pt, s) ++(s)->count
the729	0:e2cc8ae74a24	223
the729	0:e2cc8ae74a24	224	#endif /* __PT_SEM_H__ */
the729	0:e2cc8ae74a24	225
the729	0:e2cc8ae74a24	226	/** @} */
the729	0:e2cc8ae74a24	227	/** @} */
the729	0:e2cc8ae74a24	228

Repository toolbox

Export to desktop IDE

Build repository

Repository details

Type:	Program
Mbed OS support:	Mbed 2 deprecated
Created:	01 Dec 2010
Imports:	2
Forks:	0
Commits:	1
Dependents:	0
Dependencies:	1
Followers:	2

pt-sem.h@0:e2cc8ae74a24, 2010-12-01 (annotated)

Who changed what in which revision?

Repository toolbox

Repository details

Important Information for this Arm website

Access Warning