diff mbox series

[3/3] doc/rcu: add lib_rcu documentation

Message ID 20190319045228.46879-4-honnappa.nagarahalli@arm.com
State New
Headers show
Series lib/rcu: add RCU library supporting QSBR mechanism | expand

Commit Message

Honnappa Nagarahalli March 19, 2019, 4:52 a.m. UTC 
Add lib_rcu QSBR API and programmer guide documentation.

Signed-off-by: Honnappa Nagarahalli <honnappa.nagarahalli@arm.com>


---
 doc/api/doxy-api-index.md                     |   3 +-
 doc/api/doxy-api.conf.in                      |   1 +
 .../prog_guide/img/rcu_general_info.svg       | 494 ++++++++++++++++++
 doc/guides/prog_guide/index.rst               |   1 +
 doc/guides/prog_guide/rcu_lib.rst             | 179 +++++++
 5 files changed, 677 insertions(+), 1 deletion(-)
 create mode 100644 doc/guides/prog_guide/img/rcu_general_info.svg
 create mode 100644 doc/guides/prog_guide/rcu_lib.rst

-- 
2.17.1

Comments

Kovacevic, Marko March 25, 2019, 11:34 a.m. UTC | #1 
> Subject: [dpdk-dev] [PATCH 3/3] doc/rcu: add lib_rcu documentation

> 

> Add lib_rcu QSBR API and programmer guide documentation.

> 

> Signed-off-by: Honnappa Nagarahalli <honnappa.nagarahalli@arm.com>

> 

> ---

>  doc/api/doxy-api-index.md                     |   3 +-

>  doc/api/doxy-api.conf.in                      |   1 +

>  .../prog_guide/img/rcu_general_info.svg       | 494 ++++++++++++++++++

>  doc/guides/prog_guide/index.rst               |   1 +

>  doc/guides/prog_guide/rcu_lib.rst             | 179 +++++++

>  5 files changed, 677 insertions(+), 1 deletion(-)  create mode 100644

> doc/guides/prog_guide/img/rcu_general_info.svg

>  create mode 100644 doc/guides/prog_guide/rcu_lib.rst

>

 
<...>

> diff --git a/doc/guides/prog_guide/index.rst

> b/doc/guides/prog_guide/index.rst index 6726b1e8d..6fb3fb921 100644

> --- a/doc/guides/prog_guide/index.rst

> +++ b/doc/guides/prog_guide/index.rst

> @@ -55,6 +55,7 @@ Programmer's Guide

>      metrics_lib

>      bpf_lib

>      ipsec_lib

> +    rcu_lib

>      source_org

>      dev_kit_build_system

>      dev_kit_root_make_help

> diff --git a/doc/guides/prog_guide/rcu_lib.rst

> b/doc/guides/prog_guide/rcu_lib.rst

> new file mode 100644

> index 000000000..5155dd35c

> --- /dev/null

> +++ b/doc/guides/prog_guide/rcu_lib.rst

> @@ -0,0 +1,179 @@

> +..  SPDX-License-Identifier: BSD-3-Clause

> +    Copyright(c) 2019 Arm Limited.

> +

> +.. _RCU_Library:

> +

> +RCU Library

> +============

> +

> +Lock-less data structures provide scalability and determinism.

> +They enable use cases where locking may not be allowed (for ex:

> +real-time applications).

> +

> +In the following paras, the term 'memory' refers to memory allocated by

> +typical APIs like malloc or anything that is representative of memory,

> +for ex: an index of a free element array.

> +

> +Since these data structures are lock less, the writers and readers are

> +accessing the data structures concurrently. Hence, while removing an

> +element from a data structure, the writers cannot return the memory to

> +the allocator, without knowing that the readers are not referencing

> +that element/memory anymore. Hence, it is required to separate the

> +operation of removing an element into 2 steps:

> +

> +Delete: in this step, the writer removes the reference to the element

> +from the data structure but does not return the associated memory to

> +the allocator. This will ensure that new readers will not get a

> +reference to the removed element. Removing the reference is an atomic

> operation.

> +

> +Free(Reclaim): in this step, the writer returns the memory to the

> +memory allocator, only after knowing that all the readers have stopped

> +referencing the deleted element.

> +

> +This library helps the writer determine when it is safe to free the

> +memory.

> +

> +This library makes use of thread Quiescent State (QS).

> +

> +What is Quiescent State

> +-----------------------

> +Quiescent State can be defined as 'any point in the thread execution

> +where the thread does not hold a reference to shared memory'. It is

> +upto the application to determine its quiescent state.

> +

> +Let us consider the following diagram:

> +

> +.. figure:: img/rcu_general_info.*

> +

> +

> +As shown, reader thread 1 acesses data structures D1 and D2. When it is


Spelling  acesses / accesses 

> +accessing D1, if the writer has to remove an element from D1, the

> +writer cannot free the memory associated with that element immediately.

> +The writer can return the memory to the allocator only after the reader

> +stops referencng D1. In other words, reader thread RT1 has to enter a


Spelling referencng / referencing 

> +quiescent state.

> +

> +Similarly, since reader thread 2 is also accessing D1, writer has to

> +wait till thread 2 enters quiescent state as well.

> +

> +However, the writer does not need to wait for reader thread 3 to enter

> +quiescent state. Reader thread 3 was not accessing D1 when the delete

> +operation happened. So, reader thread 1 will not have a reference to

> +the deleted entry.

> +

> +It can be noted that, the critical sections for D2 is a quiescent state

> +for D1. i.e. for a given data structure Dx, any point in the thread

> +execution that does not reference Dx is a quiescent state.

> +

> +Since memory is not freed immediately, there might be a need for

> +provisioning of additional memory, depending on the application

> requirements.

> +

> +Factores affecting RCU mechanism

> +---------------------------------


Spelling Factores/ Factors

> +

> +It is important to make sure that this library keeps the over head of

 
Over head / overhead 

> +identifying the end of grace period and subsequent freeing of memory,

> +to a minimum. The following paras explain how grace period and critical

> +section affect this overhead.

> +

> +The writer has to poll the readers to identify the end of grace period.

> +Polling introduces memory accesses and wastes CPU cycles. The memory is

> +not available for reuse during grace period. Longer grace periods

> +exasperate these conditions.

> +

> +The length of the critical section and the number of reader threads is

> +proportional to the duration of the grace period. Keeping the critical

> +sections smaller will keep the grace period smaller. However, keeping

> +the critical sections smaller requires additional CPU cycles(due to

> +additional

> +reporting) in the readers.

> +

> +Hence, we need the characteristics of small grace period and large

> +critical section. This library addresses this by allowing the writer to

> +do other work without having to block till the readers report their

> +quiescent state.

> +

> +RCU in DPDK

> +-----------

> +

> +For DPDK applications, the start and end of while(1) loop (where no

> +references to shared data structures are kept) act as perfect quiescent

> +states. This will combine all the shared data structure accesses into a

> +single, large critical section which helps keep the over head on the


Over head / overhead

> +reader side to a minimum.

> +

> +DPDK supports pipeline model of packet processing and service cores.

> +In these use cases, a given data structure may not be used by all the

> +workers in the application. The writer does not have to wait for all

> +the workers to report their quiescent state. To provide the required

> +flexibility, this library has a concept of QS variable. The application

> +can create one QS variable per data structure to help it track the end

> +of grace period for each data structure. This helps keep the grace

> +period to a minimum.

> +

> +How to use this library

> +-----------------------

> +

> +The application has to allocate memory and initialize a QS variable.

> +


Maybe instead of making the call below bold using `` `` might be better to use

**rte_rcu_qsbr_get_memsize**
``rte_rcu_qsbr_get_memsize``
 
For all of them below

> +Application can call **rte_rcu_qsbr_get_memsize** to calculate the size

> +of memory to allocate. This API takes maximum number of reader threads,

> +using this variable, as a parameter. Currently, a maximum of 1024

> +threads are supported.

> +

> +Further, the application can initialize a QS variable using the API

> +**rte_rcu_qsbr_init**.

> +

> +Each reader thread is assumed to have a unique thread ID. Currently,

> +the management of the thread ID (for ex: allocation/free) is left to

> +the application. The thread ID should be in the range of 0 to maximum

> +number of threads provided while creating the QS variable.

> +The application could also use lcore_id as the thread ID where applicable.

> +

> +**rte_rcu_qsbr_thread_register** API will register a reader thread to

> +report its quiescent state. This can be called from a reader thread.

> +A control plane thread can also call this on behalf of a reader thread.

> +The reader thread must call **rte_rcu_qsbr_thread_online** API to start

> +reporting its quiescent state.

> +

> +Some of the use cases might require the reader threads to make blocking

> +API calls (for ex: while using eventdev APIs). The writer thread should

> +not wait for such reader threads to enter quiescent state.

> +The reader thread must call **rte_rcu_qsbr_thread_offline** API, before

> +calling blocking APIs. It can call **rte_rcu_qsbr_thread_online** API

> +once the blocking API call returns.

> +

> +The writer thread can trigger the reader threads to report their

> +quiescent state by calling the API **rte_rcu_qsbr_start**. It is

> +possible for multiple writer threads to query the quiescent state

> +status simultaneously. Hence,

> +**rte_rcu_qsbr_start** returns a token to each caller.

> +

> +The writer thread has to call **rte_rcu_qsbr_check** API with the token

> +to get the current quiescent state status. Option to block till all the

> +reader threads enter the quiescent state is provided. If this API

> +indicates that all the reader threads have entered the quiescent state,

> +the application can free the deleted entry.

> +

> +The APIs **rte_rcu_qsbr_start** and **rte_rcu_qsbr_check** are lock

> free.

> +Hence, they can be called concurrently from multiple writers even while

> +running as worker threads.

> +

> +The separation of triggering the reporting from querying the status

> +provides the writer threads flexibility to do useful work instead of

> +blocking for the reader threads to enter the quiescent state or go

> +offline. This reduces the memory accesses due to continuous polling for the

> status.

> +

> +**rte_rcu_qsbr_synchronize** API combines the functionality of

> +**rte_rcu_qsbr_start** and blocking **rte_rcu_qsbr_check** into a single

> API.

> +This API triggers the reader threads to report their quiescent state

> +and polls till all the readers enter the quiescent state or go offline.

> +This API does not allow the writer to do useful work while waiting and

> +also introduces additional memory accesses due to continuous polling.

> +

> +The reader thread must call **rte_rcu_qsbr_thread_offline** and

> +**rte_rcu_qsbr_thread_unregister** APIs to remove itself from reporting

> +its quiescent state. The **rte_rcu_qsbr_check** API will not wait for

> +this reader thread to report the quiescent state status anymore.

> +

> +The reader threads should call **rte_rcu_qsbr_update** API to indicate

> +that they entered a quiescent state. This API checks if a writer has

> +triggered a quiescent state query and update the state accordingly.

> --


If it's possible to enlarge the image a bit it would be good to be able to read the lower text
I need to enlarge it to 175% maybe I'm just blind but if it's possible it would be great

Reviewed-by: Marko Kovacevic <marko.kovacevic@intel.com>
Honnappa Nagarahalli March 26, 2019, 4:43 a.m. UTC | #2 
Hi Marko,
	Thank you for your comments. I will make all the suggested changes in the next version.

<snip>

> > --

> 

> If it's possible to enlarge the image a bit it would be good to be able to read

> the lower text I need to enlarge it to 175% maybe I'm just blind but if it's

> possible it would be great

I also think the image size is small. I had tried few things which did not work. I have few more ideas (may be just draw a bigger picture), I will try them out.

> 

> Reviewed-by: Marko Kovacevic <marko.kovacevic@intel.com>
diff mbox series

Patch

diff --git a/doc/api/doxy-api-index.md b/doc/api/doxy-api-index.md
index d95ad566c..5c1f6b477 100644
--- a/doc/api/doxy-api-index.md
+++ b/doc/api/doxy-api-index.md
@@ -54,7 +54,8 @@  The public API headers are grouped by topics:
   [memzone]            (@ref rte_memzone.h),
   [mempool]            (@ref rte_mempool.h),
   [malloc]             (@ref rte_malloc.h),
-  [memcpy]             (@ref rte_memcpy.h)
+  [memcpy]             (@ref rte_memcpy.h),
+  [rcu]                (@ref rte_rcu_qsbr.h)
 
 - **timers**:
   [cycles]             (@ref rte_cycles.h),
diff --git a/doc/api/doxy-api.conf.in b/doc/api/doxy-api.conf.in
index a365e669b..0b4c248a2 100644
--- a/doc/api/doxy-api.conf.in
+++ b/doc/api/doxy-api.conf.in
@@ -51,6 +51,7 @@  INPUT                   = @TOPDIR@/doc/api/doxy-api-index.md \
                           @TOPDIR@/lib/librte_port \
                           @TOPDIR@/lib/librte_power \
                           @TOPDIR@/lib/librte_rawdev \
+                          @TOPDIR@/lib/librte_rcu \
                           @TOPDIR@/lib/librte_reorder \
                           @TOPDIR@/lib/librte_ring \
                           @TOPDIR@/lib/librte_sched \
diff --git a/doc/guides/prog_guide/img/rcu_general_info.svg b/doc/guides/prog_guide/img/rcu_general_info.svg
new file mode 100644
index 000000000..3ae53bdc2
--- /dev/null
+++ b/doc/guides/prog_guide/img/rcu_general_info.svg
@@ -0,0 +1,494 @@ 
+<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
+<!-- Generated by Microsoft Visio, SVG Export rcu_general_info.svg Page-1 -->
+
+<!-- SPDX-License-Identifier: BSD-3-Clause -->
+<!-- Copyright(c) 2019 Arm Limited -->
+
+<svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:ev="http://www.w3.org/2001/xml-events"
+		xmlns:v="http://schemas.microsoft.com/visio/2003/SVGExtensions/" width="21.5in" height="16.5in" viewBox="0 0 1548 1188"
+		xml:space="preserve" color-interpolation-filters="sRGB" class="st21">
+	<v:documentProperties v:langID="1033" v:viewMarkup="false">
+		<v:userDefs>
+			<v:ud v:nameU="msvSubprocessMaster" v:prompt="" v:val="VT4(Rectangle)"/>
+			<v:ud v:nameU="msvNoAutoConnect" v:val="VT0(1):26"/>
+		</v:userDefs>
+	</v:documentProperties>
+
+	<style type="text/css">
+	<![CDATA[
+		.st1 {fill:#92d050;stroke:none;stroke-linecap:round;stroke-linejoin:round;stroke-width:0.75}
+		.st2 {fill:#ff0000;stroke:none;stroke-linecap:round;stroke-linejoin:round;stroke-width:0.75}
+		.st3 {stroke:none;stroke-linecap:round;stroke-linejoin:round;stroke-width:0.75}
+		.st4 {fill:#ffffff;font-family:Calibri;font-size:1.81435em}
+		.st5 {fill:#333e48;font-family:Century Gothic;font-size:1.81435em}
+		.st6 {fill:#333e48;font-family:Calibri;font-size:2.11672em}
+		.st7 {stroke:#000000;stroke-linecap:round;stroke-linejoin:round;stroke-width:1.45071}
+		.st8 {fill:#000000;font-family:Century Gothic;font-size:1.20955em}
+		.st9 {font-size:1em}
+		.st10 {stroke:#000000;stroke-linecap:round;stroke-linejoin:round;stroke-width:2.90143}
+		.st11 {fill:#333e48;font-family:Calibri;font-size:2.11672em;font-weight:bold}
+		.st12 {fill:#000000;font-family:Calibri;font-size:1.99578em;font-weight:bold}
+		.st13 {stroke:#651beb;stroke-linecap:round;stroke-linejoin:round;stroke-width:2.90143}
+		.st14 {stroke:#b31166;stroke-linecap:round;stroke-linejoin:round;stroke-width:0.725356}
+		.st15 {fill:#feffff;font-family:Calibri;font-size:1.16666em;font-weight:bold}
+		.st16 {marker-end:url(#mrkr5-240);marker-start:url(#mrkr5-238);stroke:#000000;stroke-linecap:round;stroke-linejoin:round;stroke-width:3}
+		.st17 {fill:#000000;fill-opacity:1;stroke:#000000;stroke-opacity:1;stroke-width:0.54347826086957}
+		.st18 {marker-end:url(#mrkr5-249);marker-start:url(#mrkr5-247);stroke:#651beb;stroke-linecap:round;stroke-linejoin:round;stroke-width:3}
+		.st19 {fill:#651beb;fill-opacity:1;stroke:#651beb;stroke-opacity:1;stroke-width:0.67567567567568}
+		.st20 {marker-end:url(#mrkr5-240);stroke:#000000;stroke-linecap:round;stroke-linejoin:round;stroke-width:3}
+		.st21 {fill:none;fill-rule:evenodd;font-size:12px;overflow:visible;stroke-linecap:square;stroke-miterlimit:3}
+	]]>
+	</style>
+
+	<defs id="Markers">
+		<g id="lend5">
+			<path d="M 2 1 L 0 0 L 1.98117 -0.993387 C 1.67173 -0.364515 1.67301 0.372641 1.98465 1.00043 " style="stroke:none"/>
+		</g>
+		<marker id="mrkr5-238" class="st17" v:arrowType="5" v:arrowSize="2" v:setback="3.1" refX="3.1" orient="auto"
+				markerUnits="strokeWidth" overflow="visible">
+			<use xlink:href="#lend5" transform="scale(1.84) "/>
+		</marker>
+		<marker id="mrkr5-240" class="st17" v:arrowType="5" v:arrowSize="2" v:setback="3.22" refX="-3.22" orient="auto"
+				markerUnits="strokeWidth" overflow="visible">
+			<use xlink:href="#lend5" transform="scale(-1.84,-1.84) "/>
+		</marker>
+		<marker id="mrkr5-247" class="st19" v:arrowType="5" v:arrowSize="0" v:setback="2.47" refX="2.47" orient="auto"
+				markerUnits="strokeWidth" overflow="visible">
+			<use xlink:href="#lend5" transform="scale(1.48) "/>
+		</marker>
+		<marker id="mrkr5-249" class="st19" v:arrowType="5" v:arrowSize="0" v:setback="2.59" refX="-2.59" orient="auto"
+				markerUnits="strokeWidth" overflow="visible">
+			<use xlink:href="#lend5" transform="scale(-1.48,-1.48) "/>
+		</marker>
+	</defs>
+	<g v:mID="0" v:index="1" v:groupContext="foregroundPage">
+		<v:userDefs>
+			<v:ud v:nameU="msvThemeOrder" v:val="VT0(0):26"/>
+		</v:userDefs>
+		<title>Page-1</title>
+		<v:pageProperties v:drawingScale="1" v:pageScale="1" v:drawingUnits="0" v:shadowOffsetX="9" v:shadowOffsetY="-9"/>
+		<v:layer v:name="Connector" v:index="0"/>
+		<g id="shape3-1" v:mID="3" v:groupContext="shape" transform="translate(240.681,-1012.22)">
+			<title>Sheet.3</title>
+			<path d="M0 1155.34 C0 1151.76 2.95 1148.81 6.52 1148.81 L88.45 1148.81 C92.07 1148.81 94.97 1151.76 94.97 1155.34 L94.97
+						 1181.47 C94.97 1185.1 92.07 1188 88.45 1188 L6.52 1188 C2.95 1188 0 1185.1 0 1181.47 L0 1155.34 Z"
+					class="st1"/>
+		</g>
+		<g id="shape4-3" v:mID="4" v:groupContext="shape" transform="translate(335.653,-1010.77)">
+			<title>Sheet.4</title>
+			<path d="M0 1155.34 C0 1151.76 2.95 1148.81 6.52 1148.81 L100.77 1148.81 C104.4 1148.81 107.3 1151.76 107.3 1155.34 L107.3
+						 1181.47 C107.3 1185.1 104.4 1188 100.77 1188 L6.52 1188 C2.95 1188 0 1185.1 0 1181.47 L0 1155.34 Z"
+					class="st2"/>
+		</g>
+		<g id="shape5-5" v:mID="5" v:groupContext="shape" transform="translate(377.387,-1014.99)">
+			<title>Sheet.5</title>
+			<desc>D1</desc>
+			<v:textBlock v:margins="rect(0,0,0,0)"/>
+			<v:textRect cx="16.8796" cy="1174.93" width="33.76" height="26.1305"/>
+			<path d="M33.76 1161.87 L0 1161.87 L0 1188 L33.76 1188 L33.76 1161.87" class="st3"/>
+			<text x="4.66" y="1181.47" class="st4" v:langID="1033"><v:paragraph v:horizAlign="1"/><v:tabList/>D1</text>		</g>
+		<g id="shape6-9" v:mID="6" v:groupContext="shape" transform="translate(443.674,-1010.77)">
+			<title>Sheet.6</title>
+			<path d="M0 1154.98 C0 1151.58 2.76 1148.81 6.16 1148.81 L30.81 1148.81 C34.26 1148.81 36.97 1151.58 36.97 1154.98 L36.97
+						 1181.83 C36.97 1185.28 34.26 1188 30.81 1188 L6.16 1188 C2.76 1188 0 1185.28 0 1181.83 L0 1154.98 Z"
+					class="st1"/>
+		</g>
+		<g id="shape7-11" v:mID="7" v:groupContext="shape" transform="translate(480.648,-1011.5)">
+			<title>Sheet.7</title>
+			<path d="M0 1155.34 C0 1151.76 2.95 1148.81 6.52 1148.81 L100.77 1148.81 C104.4 1148.81 107.3 1151.76 107.3 1155.34 L107.3
+						 1181.47 C107.3 1185.1 104.4 1188 100.77 1188 L6.52 1188 C2.95 1188 0 1185.1 0 1181.47 L0 1155.34 Z"
+					class="st2"/>
+		</g>
+		<g id="shape8-13" v:mID="8" v:groupContext="shape" transform="translate(522.382,-1015.49)">
+			<title>Sheet.8</title>
+			<desc>D2</desc>
+			<v:textBlock v:margins="rect(0,0,0,0)"/>
+			<v:textRect cx="16.8796" cy="1174.93" width="33.76" height="26.1305"/>
+			<path d="M33.76 1161.87 L0 1161.87 L0 1188 L33.76 1188 L33.76 1161.87" class="st3"/>
+			<text x="4.66" y="1181.47" class="st4" v:langID="1033"><v:paragraph v:horizAlign="1"/><v:tabList/>D2</text>		</g>
+		<g id="shape9-17" v:mID="9" v:groupContext="shape" transform="translate(587.22,-1011.5)">
+			<title>Sheet.9</title>
+			<path d="M0 1154.98 C0 1151.58 2.76 1148.81 6.16 1148.81 L30.81 1148.81 C34.26 1148.81 36.97 1151.58 36.97 1154.98 L36.97
+						 1181.83 C36.97 1185.28 34.26 1188 30.81 1188 L6.16 1188 C2.76 1188 0 1185.28 0 1181.83 L0 1154.98 Z"
+					class="st1"/>
+		</g>
+		<g id="shape10-19" v:mID="10" v:groupContext="shape" transform="translate(27,-1016.39)">
+			<title>Sheet.10</title>
+			<desc>Reader Thread 1</desc>
+			<v:textBlock v:margins="rect(0,0,0,0)"/>
+			<v:textRect cx="104.097" cy="1174.93" width="208.2" height="26.1302"/>
+			<path d="M208.19 1161.87 L0 1161.87 L0 1188 L208.19 1188 L208.19 1161.87" class="st3"/>
+			<text x="16.59" y="1181.47" class="st5" v:langID="1033"><v:paragraph v:horizAlign="1"/><v:tabList/>Reader Thread 1</text>		</g>
+		<g id="shape11-23" v:mID="11" v:groupContext="shape" transform="translate(277.655,-952.713)">
+			<title>Sheet.11</title>
+			<path d="M0 1155.34 C0 1151.76 2.95 1148.81 6.52 1148.81 L88.45 1148.81 C92.07 1148.81 94.97 1151.76 94.97 1155.34 L94.97
+						 1181.47 C94.97 1185.1 92.07 1188 88.45 1188 L6.52 1188 C2.95 1188 0 1185.1 0 1181.47 L0 1155.34 Z"
+					class="st1"/>
+		</g>
+		<g id="shape12-25" v:mID="12" v:groupContext="shape" transform="translate(372.627,-951.261)">
+			<title>Sheet.12</title>
+			<path d="M0 1155.34 C0 1151.76 2.95 1148.81 6.52 1148.81 L100.77 1148.81 C104.4 1148.81 107.3 1151.76 107.3 1155.34 L107.3
+						 1181.47 C107.3 1185.1 104.4 1188 100.77 1188 L6.52 1188 C2.95 1188 0 1185.1 0 1181.47 L0 1155.34 Z"
+					class="st2"/>
+		</g>
+		<g id="shape13-27" v:mID="13" v:groupContext="shape" transform="translate(414.386,-955.425)">
+			<title>Sheet.13</title>
+			<desc>D1</desc>
+			<v:textBlock v:margins="rect(0,0,0,0)"/>
+			<v:textRect cx="16.8796" cy="1174.93" width="33.76" height="26.1305"/>
+			<path d="M33.76 1161.87 L0 1161.87 L0 1188 L33.76 1188 L33.76 1161.87" class="st3"/>
+			<text x="4.66" y="1181.47" class="st4" v:langID="1033"><v:paragraph v:horizAlign="1"/><v:tabList/>D1</text>		</g>
+		<g id="shape14-31" v:mID="14" v:groupContext="shape" transform="translate(480.648,-951.261)">
+			<title>Sheet.14</title>
+			<path d="M0 1154.98 C0 1151.58 2.76 1148.81 6.16 1148.81 L30.81 1148.81 C34.26 1148.81 36.97 1151.58 36.97 1154.98 L36.97
+						 1181.83 C36.97 1185.28 34.26 1188 30.81 1188 L6.16 1188 C2.76 1188 0 1185.28 0 1181.83 L0 1154.98 Z"
+					class="st1"/>
+		</g>
+		<g id="shape15-33" v:mID="15" v:groupContext="shape" transform="translate(517.622,-951.987)">
+			<title>Sheet.15</title>
+			<path d="M0 1155.34 C0 1151.76 2.95 1148.81 6.52 1148.81 L100.77 1148.81 C104.4 1148.81 107.3 1151.76 107.3 1155.34 L107.3
+						 1181.47 C107.3 1185.1 104.4 1188 100.77 1188 L6.52 1188 C2.95 1188 0 1185.1 0 1181.47 L0 1155.34 Z"
+					class="st2"/>
+		</g>
+		<g id="shape16-35" v:mID="16" v:groupContext="shape" transform="translate(559.381,-955.926)">
+			<title>Sheet.16</title>
+			<desc>D2</desc>
+			<v:textBlock v:margins="rect(0,0,0,0)"/>
+			<v:textRect cx="16.8796" cy="1174.93" width="33.76" height="26.1305"/>
+			<path d="M33.76 1161.87 L0 1161.87 L0 1188 L33.76 1188 L33.76 1161.87" class="st3"/>
+			<text x="4.66" y="1181.47" class="st4" v:langID="1033"><v:paragraph v:horizAlign="1"/><v:tabList/>D2</text>		</g>
+		<g id="shape17-39" v:mID="17" v:groupContext="shape" transform="translate(624.194,-951.987)">
+			<title>Sheet.17</title>
+			<path d="M0 1154.98 C0 1151.58 2.76 1148.81 6.16 1148.81 L30.81 1148.81 C34.26 1148.81 36.97 1151.58 36.97 1154.98 L36.97
+						 1181.83 C36.97 1185.28 34.26 1188 30.81 1188 L6.16 1188 C2.76 1188 0 1185.28 0 1181.83 L0 1154.98 Z"
+					class="st1"/>
+		</g>
+		<g id="shape18-41" v:mID="18" v:groupContext="shape" transform="translate(109.808,-959.83)">
+			<title>Sheet.18</title>
+			<desc>T 2</desc>
+			<v:textBlock v:margins="rect(0,0,0,0)"/>
+			<v:textRect cx="19.2022" cy="1174.93" width="38.41" height="26.1302"/>
+			<path d="M38.4 1161.87 L0 1161.87 L0 1188 L38.4 1188 L38.4 1161.87" class="st3"/>
+			<text x="5.52" y="1181.47" class="st5" v:langID="1033"><v:paragraph v:horizAlign="1"/><v:tabList/>T 2</text>		</g>
+		<g id="shape19-45" v:mID="19" v:groupContext="shape" transform="translate(345.278,-891.751)">
+			<title>Sheet.19</title>
+			<path d="M0 1155.98 C0 1152.44 2.9 1149.54 6.43 1149.54 L88.58 1149.54 C92.12 1149.54 94.97 1152.44 94.97 1155.98 L94.97
+						 1181.6 C94.97 1185.14 92.12 1188 88.58 1188 L6.43 1188 C2.9 1188 0 1185.14 0 1181.6 L0 1155.98 Z"
+					class="st1"/>
+		</g>
+		<g id="shape20-47" v:mID="20" v:groupContext="shape" transform="translate(440.975,-890.3)">
+			<title>Sheet.20</title>
+			<path d="M0 1155.34 C0 1151.76 2.95 1148.81 6.52 1148.81 L100.77 1148.81 C104.4 1148.81 107.3 1151.76 107.3 1155.34 L107.3
+						 1181.47 C107.3 1185.1 104.4 1188 100.77 1188 L6.52 1188 C2.95 1188 0 1185.1 0 1181.47 L0 1155.34 Z"
+					class="st2"/>
+		</g>
+		<g id="shape21-49" v:mID="21" v:groupContext="shape" transform="translate(482.409,-894.363)">
+			<title>Sheet.21</title>
+			<desc>D1</desc>
+			<v:textBlock v:margins="rect(0,0,0,0)"/>
+			<v:textRect cx="16.8796" cy="1174.93" width="33.76" height="26.1305"/>
+			<path d="M33.76 1161.87 L0 1161.87 L0 1188 L33.76 1188 L33.76 1161.87" class="st3"/>
+			<text x="4.66" y="1181.47" class="st4" v:langID="1033"><v:paragraph v:horizAlign="1"/><v:tabList/>D1</text>		</g>
+		<g id="shape22-53" v:mID="22" v:groupContext="shape" transform="translate(548.996,-890.3)">
+			<title>Sheet.22</title>
+			<path d="M0 1154.98 C0 1151.58 2.76 1148.81 6.16 1148.81 L30.81 1148.81 C34.26 1148.81 36.97 1151.58 36.97 1154.98 L36.97
+						 1181.83 C36.97 1185.28 34.26 1188 30.81 1188 L6.16 1188 C2.76 1188 0 1185.28 0 1181.83 L0 1154.98 Z"
+					class="st1"/>
+		</g>
+		<g id="shape23-55" v:mID="23" v:groupContext="shape" transform="translate(585.97,-891.025)">
+			<title>Sheet.23</title>
+			<path d="M0 1155.34 C0 1151.76 2.95 1148.81 6.52 1148.81 L100.77 1148.81 C104.4 1148.81 107.3 1151.76 107.3 1155.34 L107.3
+						 1181.47 C107.3 1185.1 104.4 1188 100.77 1188 L6.52 1188 C2.95 1188 0 1185.1 0 1181.47 L0 1155.34 Z"
+					class="st2"/>
+		</g>
+		<g id="shape24-57" v:mID="24" v:groupContext="shape" transform="translate(627.404,-894.864)">
+			<title>Sheet.24</title>
+			<desc>D2</desc>
+			<v:textBlock v:margins="rect(0,0,0,0)"/>
+			<v:textRect cx="16.8796" cy="1174.93" width="33.76" height="26.1305"/>
+			<path d="M33.76 1161.87 L0 1161.87 L0 1188 L33.76 1188 L33.76 1161.87" class="st3"/>
+			<text x="4.66" y="1181.47" class="st4" v:langID="1033"><v:paragraph v:horizAlign="1"/><v:tabList/>D2</text>		</g>
+		<g id="shape25-61" v:mID="25" v:groupContext="shape" transform="translate(692.542,-891.025)">
+			<title>Sheet.25</title>
+			<path d="M0 1154.98 C0 1151.58 2.76 1148.81 6.16 1148.81 L30.81 1148.81 C34.26 1148.81 36.97 1151.58 36.97 1154.98 L36.97
+						 1181.83 C36.97 1185.28 34.26 1188 30.81 1188 L6.16 1188 C2.76 1188 0 1185.28 0 1181.83 L0 1154.98 Z"
+					class="st1"/>
+		</g>
+		<g id="shape26-63" v:mID="26" v:groupContext="shape" transform="translate(109.308,-898.768)">
+			<title>Sheet.26</title>
+			<desc>T 3</desc>
+			<v:textBlock v:margins="rect(0,0,0,0)"/>
+			<v:textRect cx="19.2022" cy="1174.93" width="38.41" height="26.1302"/>
+			<path d="M38.4 1161.87 L0 1161.87 L0 1188 L38.4 1188 L38.4 1161.87" class="st3"/>
+			<text x="5.52" y="1181.47" class="st5" v:langID="1033"><v:paragraph v:horizAlign="1"/><v:tabList/>T 3</text>		</g>
+		<g id="shape28-67" v:mID="28" v:groupContext="shape" transform="translate(636.118,-747)">
+			<title>Sheet.28</title>
+			<desc>Time</desc>
+			<v:textBlock v:margins="rect(0,0,0,0)"/>
+			<v:textRect cx="32.7073" cy="1172.76" width="65.42" height="30.4844"/>
+			<path d="M65.41 1157.52 L0 1157.52 L0 1188 L65.41 1188 L65.41 1157.52" class="st3"/>
+			<text x="7.14" y="1180.38" class="st6" v:langID="1033"><v:paragraph v:horizAlign="1"/><v:tabList/>Time</text>		</g>
+		<g id="shape29-71" v:mID="29" v:groupContext="shape" transform="translate(306.386,-808.107)">
+			<title>Sheet.29</title>
+			<path d="M0 1157.52 L0 1188 L0 1157.52" class="st7"/>
+		</g>
+		<g id="shape30-74" v:mID="30" v:groupContext="shape" transform="translate(306.386,-825.66)">
+			<title>Sheet.30</title>
+			<path d="M0 1188 L58.86 1187.55 L107.61 1176.66" class="st7"/>
+		</g>
+		<g id="shape31-77" v:mID="31" v:groupContext="shape" transform="translate(162,-808.107)">
+			<title>Sheet.31</title>
+			<desc>Remove reference to entry1</desc>
+			<v:textBlock v:margins="rect(0,0,0,0)"/>
+			<v:textRect cx="68.8761" cy="1174.8" width="137.76" height="26.4087"/>
+			<path d="M137.75 1161.59 L0 1161.59 L0 1188 L137.75 1188 L137.75 1161.59" class="st3"/>
+			<text x="5.63" y="1170.44" class="st8" v:langID="1033"><v:paragraph v:horizAlign="2"/><v:tabList/>Remove reference <tspan
+						x="75.92" dy="1.2em" class="st9">to entry1</tspan></text>		</g>
+		<g id="shape33-82" v:mID="33" v:groupContext="shape" transform="translate(414.386,-823.2)">
+			<title>Sheet.33</title>
+			<path d="M0 868.2 L0 1188" class="st10"/>
+		</g>
+		<g id="shape34-85" v:mID="34" v:groupContext="shape" transform="translate(374.334,-1143)">
+			<title>Sheet.34</title>
+			<desc>Delete</desc>
+			<v:textBlock v:margins="rect(0,0,0,0)"/>
+			<v:textRect cx="43.2194" cy="1172.76" width="86.44" height="30.4844"/>
+			<path d="M86.44 1157.52 L0 1157.52 L0 1188 L86.44 1188 L86.44 1157.52" class="st3"/>
+			<text x="8.51" y="1180.38" class="st11" v:langID="1033"><v:paragraph v:horizAlign="1"/><v:tabList/>Delete</text>		</g>
+		<g id="shape35-89" v:mID="35" v:groupContext="shape" transform="translate(316.939,-1118.91)">
+			<title>Sheet.35</title>
+			<path d="M0 1164.05 L0 1188 L0 1164.05" class="st7"/>
+		</g>
+		<g id="shape36-92" v:mID="36" v:groupContext="shape" transform="translate(316.939,-1121.45)">
+			<title>Sheet.36</title>
+			<path d="M0 1176.52 L60.17 1176.07 L97.1 1188" class="st7"/>
+		</g>
+		<g id="shape37-95" v:mID="37" v:groupContext="shape" transform="translate(158.718,-1119.3)">
+			<title>Sheet.37</title>
+			<desc>Delete entry1 from D1</desc>
+			<v:textBlock v:margins="rect(0,0,0,0)"/>
+			<v:textRect cx="76.724" cy="1179.29" width="153.45" height="17.4211"/>
+			<path d="M153.45 1170.58 L0 1170.58 L0 1188 L153.45 1188 L153.45 1170.58" class="st3"/>
+			<text x="0.09" y="1183.64" class="st8" v:langID="1033"><v:paragraph v:horizAlign="1"/><v:tabList/>Delete entry1 from D1</text>		</g>
+		<g id="shape38-99" v:mID="38" v:groupContext="shape" transform="translate(516.172,-819)">
+			<title>Sheet.38</title>
+			<path d="M0 864 L0 1188" class="st10"/>
+		</g>
+		<g id="shape39-102" v:mID="39" v:groupContext="shape" transform="translate(574.306,-792.296)">
+			<title>Sheet.39</title>
+			<path d="M0 1134.3 L0 1188 L0 1134.3" class="st7"/>
+		</g>
+		<g id="shape40-105" v:mID="40" v:groupContext="shape" transform="translate(517.939,-819)">
+			<title>Sheet.40</title>
+			<path d="M56.37 1188 L37.52 1187.95 L0 1158.97" class="st7"/>
+		</g>
+		<g id="shape41-108" v:mID="41" v:groupContext="shape" transform="translate(579.283,-793.278)">
+			<title>Sheet.41</title>
+			<desc>Free memory for entries1 and 2 after every reader has gone th...</desc>
+			<v:textBlock v:margins="rect(0,0,0,0)"/>
+			<v:textRect cx="122.717" cy="1162.74" width="245.44" height="50.5152"/>
+			<path d="M245.43 1137.48 L0 1137.48 L0 1188 L245.43 1188 L245.43 1137.48" class="st3"/>
+			<text x="0" y="1149.68" class="st8" v:langID="1033"><v:paragraph/><v:tabList/>Free memory for entries1 and 2 <tspan
+						x="0" dy="1.2em" class="st9">after every reader has gone </tspan><tspan x="0" dy="1.2em" class="st9">through at least 1 quiescent state </tspan> </text>		</g>
+		<g id="shape46-114" v:mID="46" v:groupContext="shape" transform="translate(492.33,-1143)">
+			<title>Sheet.46</title>
+			<desc>Free</desc>
+			<v:textBlock v:margins="rect(0,0,0,0)"/>
+			<v:textRect cx="29.9047" cy="1172.76" width="59.81" height="30.4844"/>
+			<path d="M59.81 1157.52 L0 1157.52 L0 1188 L59.81 1188 L59.81 1157.52" class="st3"/>
+			<text x="6.77" y="1180.38" class="st11" v:langID="1033"><v:paragraph v:horizAlign="1"/><v:tabList/>Free</text>		</g>
+		<g id="shape48-118" v:mID="48" v:groupContext="shape" transform="translate(585,-1128.34)">
+			<title>Sheet.48</title>
+			<path d="M0 1157.52 L0 1188 L0 1157.52" class="st7"/>
+		</g>
+		<g id="shape49-121" v:mID="49" v:groupContext="shape" transform="translate(476.536,-1109.79)">
+			<title>Sheet.49</title>
+			<path d="M108.93 1160.69 L80.93 1160.65 L0 1188" class="st7"/>
+		</g>
+		<g id="shape50-124" v:mID="50" v:groupContext="shape" transform="translate(576,-1128.63)">
+			<title>Sheet.50</title>
+			<desc>Grace Period</desc>
+			<v:textBlock v:margins="rect(0,0,0,0)"/>
+			<v:textRect cx="76.724" cy="1173.63" width="153.45" height="28.7428"/>
+			<path d="M153.45 1159.26 L0 1159.26 L0 1188 L153.45 1188 L153.45 1159.26" class="st3"/>
+			<text x="12.72" y="1180.81" class="st12" v:langID="1033"><v:paragraph v:horizAlign="1"/><v:tabList/>Grace Period</text>		</g>
+		<g id="shape51-128" v:mID="51" v:groupContext="shape" transform="translate(434.25,-810)">
+			<title>Sheet.51</title>
+			<path d="M0 864 L0 1188" class="st13"/>
+		</g>
+		<g id="shape52-131" v:mID="52" v:groupContext="shape" transform="translate(338.689,-1087.7)">
+			<title>Sheet.52</title>
+			<path d="M0 1164.05 L0 1188 L0 1164.05" class="st7"/>
+		</g>
+		<g id="shape53-134" v:mID="53" v:groupContext="shape" transform="translate(338.689,-1090.24)">
+			<title>Sheet.53</title>
+			<path d="M0 1176.52 L60.17 1176.07 L97.1 1188" class="st7"/>
+		</g>
+		<g id="shape54-137" v:mID="54" v:groupContext="shape" transform="translate(180.467,-1088.46)">
+			<title>Sheet.54</title>
+			<desc>Delete entry2 from D1</desc>
+			<v:textBlock v:margins="rect(0,0,0,0)"/>
+			<v:textRect cx="76.724" cy="1179.29" width="153.45" height="17.4211"/>
+			<path d="M153.45 1170.58 L0 1170.58 L0 1188 L153.45 1188 L153.45 1170.58" class="st3"/>
+			<text x="0.09" y="1183.64" class="st8" v:langID="1033"><v:paragraph v:horizAlign="1"/><v:tabList/>Delete entry2 from D1</text>		</g>
+		<g id="shape56-141" v:mID="56" v:groupContext="shape" transform="translate(513.997,-810)">
+			<title>Sheet.56</title>
+			<path d="M0 864 L0 1188" class="st13"/>
+		</g>
+		<g id="shape57-144" v:mID="57" v:groupContext="shape" transform="translate(481.011,-1082.26)">
+			<title>Sheet.57</title>
+			<path d="M-0 1188 L104.45 1134.58" class="st14"/>
+		</g>
+		<g id="shape58-147" v:mID="58" v:groupContext="shape" transform="translate(448.387,-942.326)">
+			<title>Sheet.58</title>
+			<path d="M307.61 1185.32 L-0 1188" class="st7"/>
+		</g>
+		<g id="shape59-150" v:mID="59" v:groupContext="shape" transform="translate(747,-934.257)">
+			<title>Sheet.59</title>
+			<desc>Critical sections</desc>
+			<v:textBlock v:margins="rect(0,0,0,0)"/>
+			<v:textRect cx="92.5251" cy="1173.63" width="185.06" height="28.7428"/>
+			<path d="M185.05 1159.26 L0 1159.26 L0 1188 L185.05 1188 L185.05 1159.26" class="st3"/>
+			<text x="14.78" y="1180.81" class="st12" v:langID="1033"><v:paragraph v:horizAlign="1"/><v:tabList/>Critical sections</text>		</g>
+		<g id="shape60-154" v:mID="60" v:groupContext="shape" transform="translate(450.199,-942.417)">
+			<title>Sheet.60</title>
+			<path d="M0 1177.7 L0 1188" class="st7"/>
+		</g>
+		<g id="shape61-157" v:mID="61" v:groupContext="shape" transform="translate(594.47,-943.142)">
+			<title>Sheet.61</title>
+			<path d="M0 1177.7 L0 1188" class="st7"/>
+		</g>
+		<g id="shape62-160" v:mID="62" v:groupContext="shape" transform="translate(254.002,-1002.43)">
+			<title>Sheet.62</title>
+			<path d="M502 1188 L0 1187.59" class="st7"/>
+		</g>
+		<g id="shape63-163" v:mID="63" v:groupContext="shape" transform="translate(747,-990)">
+			<title>Sheet.63</title>
+			<desc>Quiescent states</desc>
+			<v:textBlock v:margins="rect(0,0,0,0)"/>
+			<v:textRect cx="97.9986" cy="1173.63" width="196" height="28.7428"/>
+			<path d="M196 1159.26 L0 1159.26 L0 1188 L196 1188 L196 1159.26" class="st3"/>
+			<text x="15.49" y="1180.81" class="st12" v:langID="1033"><v:paragraph v:horizAlign="1"/><v:tabList/>Quiescent states</text>		</g>
+		<g id="shape64-167" v:mID="64" v:groupContext="shape" transform="translate(254.455,-1001.93)">
+			<title>Sheet.64</title>
+			<path d="M0 1177.7 L0 1188" class="st7"/>
+		</g>
+		<g id="shape65-170" v:mID="65" v:groupContext="shape" transform="translate(450.199,-1002.65)">
+			<title>Sheet.65</title>
+			<path d="M0 1177.7 L0 1188" class="st7"/>
+		</g>
+		<g id="shape66-173" v:mID="66" v:groupContext="shape" transform="translate(617.669,-1003.38)">
+			<title>Sheet.66</title>
+			<path d="M0 1177.7 L0 1188" class="st7"/>
+		</g>
+		<g id="shape67-176" v:mID="67" v:groupContext="shape" transform="translate(344.304,-876.625)">
+			<title>Sheet.67</title>
+			<path d="M411.7 1188 L0 1187.59" class="st7"/>
+		</g>
+		<g id="shape68-179" v:mID="68" v:groupContext="shape" transform="translate(344.757,-876.126)">
+			<title>Sheet.68</title>
+			<path d="M0 1177.7 L0 1188" class="st7"/>
+		</g>
+		<g id="shape69-182" v:mID="69" v:groupContext="shape" transform="translate(731.524,-877.578)">
+			<title>Sheet.69</title>
+			<path d="M0 1177.7 L0 1188" class="st7"/>
+		</g>
+		<g id="shape70-185" v:mID="70" v:groupContext="shape" transform="translate(762.248,-864)">
+			<title>Sheet.70</title>
+			<desc>while(1) loop</desc>
+			<v:textBlock v:margins="rect(0,0,0,0)"/>
+			<v:textRect cx="68.8761" cy="1173.63" width="137.76" height="28.7428"/>
+			<path d="M137.75 1159.26 L0 1159.26 L0 1188 L137.75 1188 L137.75 1159.26" class="st3"/>
+			<text x="3.14" y="1180.81" class="st12" v:langID="1033"><v:paragraph v:horizAlign="1"/><v:tabList/>while(1) loop</text>		</g>
+		<g id="shape71-189" v:mID="71" v:groupContext="shape" transform="translate(143.026,-693.87)">
+			<title>Sheet.71</title>
+			<path d="M0 1165.98 C0 1163.71 2.76 1161.87 6.16 1161.87 L30.81 1161.87 C34.26 1161.87 36.97 1163.71 36.97 1165.98 L36.97
+						 1183.89 C36.97 1186.19 34.26 1188 30.81 1188 L6.16 1188 C2.76 1188 0 1186.19 0 1183.89 L0 1165.98 Z"
+					class="st1"/>
+		</g>
+		<g id="shape72-191" v:mID="72" v:groupContext="shape" transform="translate(192.124,-693.591)">
+			<title>Sheet.72</title>
+			<desc>Reader thread is not accessing any shared data structure. i.e...</desc>
+			<v:textBlock v:margins="rect(0,0,0,0)"/>
+			<v:textRect cx="209.938" cy="1174.8" width="419.88" height="26.4087"/>
+			<path d="M419.88 1161.59 L0 1161.59 L0 1188 L419.88 1188 L419.88 1161.59" class="st3"/>
+			<text x="0" y="1170.44" class="st8" v:langID="1033"><v:paragraph/><v:tabList/>Reader thread is not accessing any shared data structure.<v:newlineChar/><tspan
+						x="0" dy="1.2em" class="st9">i.e. non critical section or quiescent state.</tspan></text>		</g>
+		<g id="shape73-196" v:mID="73" v:groupContext="shape" transform="translate(144.703,-648.87)">
+			<title>Sheet.73</title>
+			<desc>Dx</desc>
+			<v:textBlock v:margins="rect(4,4,4,4)"/>
+			<v:textRect cx="17.6483" cy="1174.93" width="35.3" height="26.1302"/>
+			<path d="M0 1166.22 C0 1163.84 0.97 1161.87 2.15 1161.87 L33.15 1161.87 C34.34 1161.87 35.3 1163.84 35.3 1166.22 L35.3
+						 1183.64 C35.3 1186.06 34.34 1188 33.15 1188 L2.15 1188 C0.97 1188 0 1186.06 0 1183.64 L0 1166.22 Z"
+					class="st2"/>
+			<text x="10.02" y="1179.14" class="st15" v:langID="1033"><v:paragraph v:horizAlign="1"/><v:tabList/>Dx</text>		</g>
+		<g id="shape74-199" v:mID="74" v:groupContext="shape" transform="translate(192.124,-648.591)">
+			<title>Sheet.74</title>
+			<desc>Reader thread is accessing the shared data structure Dx. i.e....</desc>
+			<v:textBlock v:margins="rect(0,0,0,0)"/>
+			<v:textRect cx="209.938" cy="1174.8" width="419.88" height="26.4087"/>
+			<path d="M419.88 1161.59 L0 1161.59 L0 1188 L419.88 1188 L419.88 1161.59" class="st3"/>
+			<text x="0" y="1170.44" class="st8" v:langID="1033"><v:paragraph/><v:tabList/>Reader thread is accessing the shared data structure Dx.<v:newlineChar/><tspan
+						x="0" dy="1.2em" class="st9">i.e. critical section.</tspan></text>		</g>
+		<g id="shape75-204" v:mID="75" v:groupContext="shape" transform="translate(237.124,-603)">
+			<title>Sheet.75</title>
+			<desc>Point in time when the reference to the entry is removed usin...</desc>
+			<v:textBlock v:margins="rect(0,0,0,0)"/>
+			<v:textRect cx="182.938" cy="1168.41" width="365.88" height="39.1897"/>
+			<path d="M365.88 1148.81 L0 1148.81 L0 1188 L365.88 1188 L365.88 1148.81" class="st3"/>
+			<text x="0" y="1164.05" class="st8" v:langID="1033"><v:paragraph/><v:tabList/>Point in time when the reference to the entry is <tspan
+						x="0" dy="1.2em" class="st9">removed using an atomic operation.</tspan></text>		</g>
+		<g id="shape76-209" v:mID="76" v:groupContext="shape" transform="translate(135,-612)">
+			<title>Sheet.76</title>
+			<desc>Delete</desc>
+			<v:textBlock v:margins="rect(0,0,0,0)"/>
+			<v:textRect cx="43.2194" cy="1172.76" width="86.44" height="30.4844"/>
+			<path d="M86.44 1157.52 L0 1157.52 L0 1188 L86.44 1188 L86.44 1157.52" class="st3"/>
+			<text x="8.51" y="1180.38" class="st11" v:langID="1033"><v:paragraph v:horizAlign="1"/><v:tabList/>Delete</text>		</g>
+		<g id="shape77-213" v:mID="77" v:groupContext="shape" transform="translate(236.4,-561.629)">
+			<title>Sheet.77</title>
+			<desc>Point in time when the writer can free the deleted entry.</desc>
+			<v:textBlock v:margins="rect(0,0,0,0)"/>
+			<v:textRect cx="189.688" cy="1173.63" width="379.38" height="28.7428"/>
+			<path d="M379.38 1159.26 L0 1159.26 L0 1188 L379.38 1188 L379.38 1159.26" class="st3"/>
+			<text x="0" y="1169.27" class="st8" v:langID="1033"><v:paragraph/><v:tabList/>Point in time when the writer can free the deleted <tspan
+						x="0" dy="1.2em" class="st9">entry.</tspan></text>		</g>
+		<g id="shape78-218" v:mID="78" v:groupContext="shape" transform="translate(135,-565.56)">
+			<title>Sheet.78</title>
+			<desc>Free</desc>
+			<v:textBlock v:margins="rect(0,0,0,0)"/>
+			<v:textRect cx="32.7073" cy="1172.76" width="65.42" height="30.4844"/>
+			<path d="M65.41 1157.52 L0 1157.52 L0 1188 L65.41 1188 L65.41 1157.52" class="st3"/>
+			<text x="9.58" y="1180.38" class="st11" v:langID="1033"><v:paragraph v:horizAlign="1"/><v:tabList/>Free</text>		</g>
+		<g id="shape79-222" v:mID="79" v:groupContext="shape" transform="translate(237.274,-516.629)">
+			<title>Sheet.79</title>
+			<desc>Time duration between Delete and Free, during which memory ca...</desc>
+			<v:textBlock v:margins="rect(0,0,0,0)"/>
+			<v:textRect cx="189.688" cy="1173.63" width="379.38" height="28.7428"/>
+			<path d="M379.38 1159.26 L0 1159.26 L0 1188 L379.38 1188 L379.38 1159.26" class="st3"/>
+			<text x="0" y="1169.27" class="st8" v:langID="1033"><v:paragraph/><v:tabList/>Time duration between Delete and Free, during <tspan
+						x="0" dy="1.2em" class="st9">which memory cannot be freed.</tspan></text>		</g>
+		<g id="shape80-227" v:mID="80" v:groupContext="shape" transform="translate(144.15,-509.516)">
+			<title>Sheet.80</title>
+			<desc>Grace Period</desc>
+			<v:textBlock v:margins="rect(0,0,0,0)"/>
+			<v:textRect cx="43.2194" cy="1172.76" width="86.44" height="30.4844"/>
+			<path d="M86.44 1157.52 L0 1157.52 L0 1188 L86.44 1188 L86.44 1157.52" class="st3"/>
+			<text x="0" y="1165.14" class="st11" v:langID="1033"><v:paragraph/><v:tabList/>Grace <tspan x="0" dy="1.2em"
+						class="st9">Period</tspan></text>		</g>
+		<g id="shape83-232" v:mID="83" v:groupContext="shape" transform="translate(414.997,-1107)">
+			<title>Sheet.83</title>
+			<path d="M9.3 1188 L9.66 1188 L91.51 1188" class="st16"/>
+		</g>
+		<g id="shape84-241" v:mID="84" v:groupContext="shape" transform="translate(434.25,-1080)">
+			<title>Sheet.84</title>
+			<path d="M7.41 1188 L7.77 1188 L71.98 1188" class="st18"/>
+		</g>
+		<g id="shape85-250" v:mID="85" v:groupContext="shape" transform="translate(701.532,-765)">
+			<title>Sheet.85</title>
+			<path d="M0 1188 L62.81 1188" class="st20"/>
+		</g>
+	</g>
+</svg>
diff --git a/doc/guides/prog_guide/index.rst b/doc/guides/prog_guide/index.rst
index 6726b1e8d..6fb3fb921 100644
--- a/doc/guides/prog_guide/index.rst
+++ b/doc/guides/prog_guide/index.rst
@@ -55,6 +55,7 @@  Programmer's Guide
     metrics_lib
     bpf_lib
     ipsec_lib
+    rcu_lib
     source_org
     dev_kit_build_system
     dev_kit_root_make_help
diff --git a/doc/guides/prog_guide/rcu_lib.rst b/doc/guides/prog_guide/rcu_lib.rst
new file mode 100644
index 000000000..5155dd35c
--- /dev/null
+++ b/doc/guides/prog_guide/rcu_lib.rst
@@ -0,0 +1,179 @@ 
+..  SPDX-License-Identifier: BSD-3-Clause
+    Copyright(c) 2019 Arm Limited.
+
+.. _RCU_Library:
+
+RCU Library
+============
+
+Lock-less data structures provide scalability and determinism.
+They enable use cases where locking may not be allowed
+(for ex: real-time applications).
+
+In the following paras, the term 'memory' refers to memory allocated
+by typical APIs like malloc or anything that is representative of
+memory, for ex: an index of a free element array.
+
+Since these data structures are lock less, the writers and readers
+are accessing the data structures concurrently. Hence, while removing
+an element from a data structure, the writers cannot return the memory
+to the allocator, without knowing that the readers are not
+referencing that element/memory anymore. Hence, it is required to
+separate the operation of removing an element into 2 steps:
+
+Delete: in this step, the writer removes the reference to the element from
+the data structure but does not return the associated memory to the
+allocator. This will ensure that new readers will not get a reference to
+the removed element. Removing the reference is an atomic operation.
+
+Free(Reclaim): in this step, the writer returns the memory to the
+memory allocator, only after knowing that all the readers have stopped
+referencing the deleted element.
+
+This library helps the writer determine when it is safe to free the
+memory.
+
+This library makes use of thread Quiescent State (QS).
+
+What is Quiescent State
+-----------------------
+Quiescent State can be defined as 'any point in the thread execution where the
+thread does not hold a reference to shared memory'. It is upto the application
+to determine its quiescent state.
+
+Let us consider the following diagram:
+
+.. figure:: img/rcu_general_info.*
+
+
+As shown, reader thread 1 acesses data structures D1 and D2. When it is
+accessing D1, if the writer has to remove an element from D1, the
+writer cannot free the memory associated with that element immediately.
+The writer can return the memory to the allocator only after the reader
+stops referencng D1. In other words, reader thread RT1 has to enter
+a quiescent state.
+
+Similarly, since reader thread 2 is also accessing D1, writer has to
+wait till thread 2 enters quiescent state as well.
+
+However, the writer does not need to wait for reader thread 3 to enter
+quiescent state. Reader thread 3 was not accessing D1 when the delete
+operation happened. So, reader thread 1 will not have a reference to the
+deleted entry.
+
+It can be noted that, the critical sections for D2 is a quiescent state
+for D1. i.e. for a given data structure Dx, any point in the thread execution
+that does not reference Dx is a quiescent state.
+
+Since memory is not freed immediately, there might be a need for
+provisioning of additional memory, depending on the application requirements.
+
+Factores affecting RCU mechanism
+---------------------------------
+
+It is important to make sure that this library keeps the over head of
+identifying the end of grace period and subsequent freeing of memory,
+to a minimum. The following paras explain how grace period and critical
+section affect this overhead.
+
+The writer has to poll the readers to identify the end of grace period.
+Polling introduces memory accesses and wastes CPU cycles. The memory
+is not available for reuse during grace period. Longer grace periods
+exasperate these conditions.
+
+The length of the critical section and the number of reader threads
+is proportional to the duration of the grace period. Keeping the critical
+sections smaller will keep the grace period smaller. However, keeping the
+critical sections smaller requires additional CPU cycles(due to additional
+reporting) in the readers.
+
+Hence, we need the characteristics of small grace period and large critical
+section. This library addresses this by allowing the writer to do
+other work without having to block till the readers report their quiescent
+state.
+
+RCU in DPDK
+-----------
+
+For DPDK applications, the start and end of while(1) loop (where no
+references to shared data structures are kept) act as perfect quiescent
+states. This will combine all the shared data structure accesses into a
+single, large critical section which helps keep the over head on the
+reader side to a minimum.
+
+DPDK supports pipeline model of packet processing and service cores.
+In these use cases, a given data structure may not be used by all the
+workers in the application. The writer does not have to wait for all
+the workers to report their quiescent state. To provide the required
+flexibility, this library has a concept of QS variable. The application
+can create one QS variable per data structure to help it track the
+end of grace period for each data structure. This helps keep the grace
+period to a minimum.
+
+How to use this library
+-----------------------
+
+The application has to allocate memory and initialize a QS variable.
+
+Application can call **rte_rcu_qsbr_get_memsize** to calculate the size
+of memory to allocate. This API takes maximum number of reader threads,
+using this variable, as a parameter. Currently, a maximum of 1024 threads
+are supported.
+
+Further, the application can initialize a QS variable using the API
+**rte_rcu_qsbr_init**.
+
+Each reader thread is assumed to have a unique thread ID. Currently, the
+management of the thread ID (for ex: allocation/free) is left to the
+application. The thread ID should be in the range of 0 to
+maximum number of threads provided while creating the QS variable.
+The application could also use lcore_id as the thread ID where applicable.
+
+**rte_rcu_qsbr_thread_register** API will register a reader thread
+to report its quiescent state. This can be called from a reader thread.
+A control plane thread can also call this on behalf of a reader thread.
+The reader thread must call **rte_rcu_qsbr_thread_online** API to start
+reporting its quiescent state.
+
+Some of the use cases might require the reader threads to make
+blocking API calls (for ex: while using eventdev APIs). The writer thread
+should not wait for such reader threads to enter quiescent state.
+The reader thread must call **rte_rcu_qsbr_thread_offline** API, before calling
+blocking APIs. It can call **rte_rcu_qsbr_thread_online** API once the blocking
+API call returns.
+
+The writer thread can trigger the reader threads to report their quiescent
+state by calling the API **rte_rcu_qsbr_start**. It is possible for multiple
+writer threads to query the quiescent state status simultaneously. Hence,
+**rte_rcu_qsbr_start** returns a token to each caller.
+
+The writer thread has to call **rte_rcu_qsbr_check** API with the token to
+get the current quiescent state status. Option to block till all the reader
+threads enter the quiescent state is provided. If this API indicates that
+all the reader threads have entered the quiescent state, the application
+can free the deleted entry.
+
+The APIs **rte_rcu_qsbr_start** and **rte_rcu_qsbr_check** are lock free.
+Hence, they can be called concurrently from multiple writers even while
+running as worker threads.
+
+The separation of triggering the reporting from querying the status provides
+the writer threads flexibility to do useful work instead of blocking for the
+reader threads to enter the quiescent state or go offline. This reduces the
+memory accesses due to continuous polling for the status.
+
+**rte_rcu_qsbr_synchronize** API combines the functionality of
+**rte_rcu_qsbr_start** and blocking **rte_rcu_qsbr_check** into a single API.
+This API triggers the reader threads to report their quiescent state and
+polls till all the readers enter the quiescent state or go offline. This
+API does not allow the writer to do useful work while waiting and also
+introduces additional memory accesses due to continuous polling.
+
+The reader thread must call **rte_rcu_qsbr_thread_offline** and
+**rte_rcu_qsbr_thread_unregister** APIs to remove itself from reporting its
+quiescent state. The **rte_rcu_qsbr_check** API will not wait for this reader
+thread to report the quiescent state status anymore.
+
+The reader threads should call **rte_rcu_qsbr_update** API to indicate that
+they entered a quiescent state. This API checks if a writer has triggered a
+quiescent state query and update the state accordingly.