Commits

shl...@cec68495-dca5-4e2b-845c-11fdaaa4f967  committed e25493b

Moved rwlock from vipe to t2. Also deleted some unused vipe directories.

  • Participants
  • Parent commits 8062f00

Comments (0)

Files changed (18)

File lib/MyNavData.pm

                     'text' => "FCFS RWLock",
                     'title' => "A First-Come First-Served Readers/Writers Lock",
                     'url' => "rwlock/",
-                    'host' => "vipe",
                 },
                 {
                     'text' => "Quad-Pres",
                     'text' => "Gradient-Fu",
                     'title' => "Gradient-Fu Patch for the GIMP",
                     'url' => "grad-fu/",
-                    'host' => "t2",
                     'hide' => 1,
                 },                
                 {

File lib/Shlomif/Homepage/SectionMenu/Sects/Software.pm

                 {
                     'text' => "FCFS RWLock",
                     'url' => "rwlock/",
-                    'host' => "vipe",
                     'title' => "A First-Come First-Served Readers/Writers Lock",
                 },
                 {

File t2/open-source/index.html.wml

 and to scripting interfaces.
 </p>
 
-<h2><a href="<rellink host="vipe" url="rwlock/" />">A
+<h2><a href="<rellink host="t2" url="rwlock/" />">A
 First-Come First-Served Readers/Writers Lock</a></h2>
 
 <p>

File t2/open-source/projects/index.html.wml

 and to scripting interfaces.
 </p>
 
-<h2><a href="<rellink host="vipe" url="rwlock/" />">A First-Come First-Served
+<h2><a href="<rellink host="t2" url="rwlock/" />">A First-Come First-Served
 Readers/Writers Lock</a></h2>
 
 <p>

File t2/rwlock/Scheme.txt

+The RWLock will use a queue. Each element of the queue will contain
+a condition variable and a flag that indicates if it contains a reader
+or a writer pending. 
+
+The RWLock will contain a counter that tells it how many readers are using 
+it at the moment (num_readers), and a flag that specifies if there's a 
+writer using the lock (is_writer). It also uses a common internal mutex 
+to protect against mutual exclusion (mymutex)
+
+Algorithm:
+
+accept_pending_items:
+---------------------
+
+Extracts the first element out of the queue. 
+
+If it is a writer, it sets is_writer to 1, and signals the condition 
+variable of the element.
+
+If it is a reader, it sets is_writer to 0, and polls+extracts 
+all the other items out of the head of the queue that are readers 
+(i.e it stops at the first writer or at the end of the queue).
+
+get_write_access:
+-----------------
+
+locks mymutex.
+
+Checks if is_writer is set or num_readers is greater than 0. If so, 
+it enqueues itself. (the mutex of the condition variable is mymutex)
+
+If not it sets is_writer to 1.
+
+Unlocks the mutex.
+
+
+
+get_read_access:
+----------------
+
+locks mymutex.
+
+If the queue is empty and is_writer is false it increments num_readers and unlock mutex.
+
+Else it enqueues itself, while using mymutex for waiting on the condition variable. When the condition variable is signalled, num_readers is incremented by 1.
+
+Unlocks mutex.
+
+release_write_access:
+---------------------
+
+locks mutex
+
+Sets is_writer to false. Then calls accept_pending_items.
+
+unlocks mutex
+
+release_read_access:
+--------------------
+
+locks mutex
+
+Decrements num_readers. If num_readers == 0 it calls accept_pending_items.
+
+unlocks mutex
+

File t2/rwlock/Scheme_RLE.txt

+Data Structures:
+================
+
+The RWLock will use a queue. Each element of the queue will contain:
+1. a condition variable 
+2. a flag that indicates if it contains readers or writers pending. 
+3. num_threads - an integer specifiying how many threads are waiting on it.
+4. was_first_thr_accepted - a flag that indicates if the first thread has
+already been accepted from it. (used only for a writers' pack).
+
+The RWLock will contain a counter that tells it how many readers are using 
+it at the moment (num_readers), and a flag that specifies if there's a 
+writer using the lock (is_writer). It also uses a common internal mutex 
+to protect against mutual exclusion (mymutex)
+
+Algorithm:
+==========
+
+accept_pending_items:
+---------------------
+
+Peek the first element out of the queue. 
+
+If it is a writers' pack, it decrements the number of threads by one, 
+and signals the condition variable, and sets was_first_thr_accepted to 1. 
+Afterwards, if (elem.num_threads == 0) it extracts and destroys the item.
+
+If it is a readers' pack, it broadcasts the condition variable. Then it
+extracts and destroys the item.
+
+get_write_access:
+-----------------
+
+locks mymutex.
+
+Checks if is_writer is set or num_readers is greater than 0. If so, 
+it enqueues itself. (the mutex of the condition variable is mymutex)
+
+If not it sets is_writer to 1.
+
+    Enqueuing: 
+    
+    peek the tail of the queue. If it is a writers' pack and
+    its was_first_thr_accepted is false, increase the number of threads 
+    there by 1 and wait on its condition variable. If not, enqueue a new 
+    writer's pack with a threads_num set to 1 and a new condition variable.
+
+
+Unlocks the mutex.
+
+
+get_read_access:
+----------------
+
+locks mymutex.
+
+If the queue is empty and is_writer is false it increments num_readers 
+and unlocks mutex.
+
+Else it enqueues itself, while using mymutex for waiting on the 
+condition variable. When the condition variable is signalled, 
+num_readers is incremented by 1.
+
+    Enqueueing: 
+    
+    peek the tail of the queue. If it is a readers' pack, 
+    increase the number of threads there by 1 and wait on its 
+    condition variable. If not, add a new readers pack with threads_num 
+    set to 1 and a new condition variable, which it will wait upon.
+
+Unlocks mutex.
+
+
+
+release_write_access:
+---------------------
+
+locks mutex
+
+Sets is_writer to false. Then calls accept_pending_items.
+
+unlocks mutex
+
+release_read_access:
+--------------------
+
+locks mutex
+
+Decrements num_readers. If num_readers == 0 it calls accept_pending_items.
+
+unlocks mutex
+

File t2/rwlock/index.html.wml

+#include '../template.wml'
+<latemp_subject "A First-Come First-Served Readers/Writers Lock" />
+
+<h2><a href="./linux-kernel/">New! FCFS flock for the Linux Kernel</a></h2>
+
+<p>
+<a href="pthread_rwlock_fcfs-0.4.0.tar.gz">Download the stable version source code.</a>
+</p>
+
+<!--
+	Commented out until I have a new development version
+	
+<p>
+<a href="pthread_rwlock_fcfs-0.3.5.tar.gz">Development version</a>
+</p>
+-->
+
+<p>
+This is a working implementation of a First-Come First-Served
+Readers/Writers lock for POSIX threads. It is well commented and documented
+so I believe it can also serve as a reference implementation for those
+who wish to implement such a mechanism for other platforms.
+</p>
+
+<h2>Todo List</h2>
+
+<ul>
+<li>Make an RPM SPEC/Debian Package etc.</li>
+<li>Port to Win32, ZThreads, etc.</li>
+</ul>
+
+<h2>Frequently Asked Questions</h2>
+
+<h3>What is a Readers/Writers Lock?</h3>
+
+<p>
+A Readers/Writers Lock (or RWLock for short) is a mechanism that allows an
+arbitrary number of readers or alternatively one writer to access a
+resource at any given time. It is useful in case writing may temporarily harm
+the integrity of the resource.
+</p>
+
+<h3>What is a First-Come First-Served RWLock?</h3>
+
+<p>
+Many RWLock implementations arbitrate the various readers and writers in a
+manner that may cause starvation of either readers or writers. For instance,
+a readers/writers lock that prefers readers may cause a writer to starve
+(i.e: wait for a very long time or indefinetly) if there are two and more
+competing readers.
+</p>
+
+<p>
+A First-Come First-Served (FCFS) RWLock solves this problem by making sure
+that the pending threads are served at the same order as the time of their
+arrival. Thus, starvation is eliminated assuming that a thread does not
+obtain the lock indefinetly (which in any case should not happen in a 
+well-designed system).
+</p>
+
+<h3>How does it make sure that's what going to happen?</h3>
+
+<p>
+By using a queue in which each element controls a pending thread. A detailed
+description of the algorithm can be found <a href="Scheme.txt">here</a> and
+naturally, there are also the comments in the code. If there's anything you
+don't understand, don't hesitate to 
+<a href="mailto:shlomif@vipe.technion.acil">contact me</a> 
+and ask.
+</p>
+
+<p>
+Recently, the algorithm was modified to pack several readers or several
+writers on the same queue element, which results in saving of condition
+variables. The new scheme for it (which is a bit more complex) can be found 
+<a href="Scheme_RLE.txt">here</a>.
+</p>
+
+<br />
+<br />
+
+<h2>Older Versions</h2>
+
+<p>
+<a href="pthread_rwlock_fcfs-0.2.0.tar.gz">Version 0.2.0</a>
+</p>
+

File t2/rwlock/linux-kernel/index.html.wml

+#include '../template.wml'
+
+<latemp_subject "Linux Kernel FCFS fcntl/flock Locks" />
+
+<h2><a href="linux-fcfs-rwlock.patch">Download the Patch</a></h2>
+
+<p>
+I wrote this patch (it's actually very short) with a lot of help from
+Matthew Wilcox, who is the current maintainer of the filesystem locks
+logic in the Linux Kernel. It is made against linux-2.5.30 but should
+work with more recent or later versions.
+</p>
+
+<p>
+Without this patch, the Linux kernel discriminates against writers,
+and accepts readers into a lock in readers state even if there are
+pending writers. The <a href="test_flock.c">following 
+test program</a> can demonstrate the two behaviours (try running it as 
+<tt>test_flock 20 2</tt>).
+</p>
+

File t2/rwlock/linux-kernel/linux-fcfs-rwlock.patch

+--- orig/linux-2.5.30/fs/locks.c	Fri Aug  2 00:16:39 2002
++++ linux-2.5.30/fs/locks.c	Fri Aug 16 17:48:49 2002
+@@ -510,7 +510,9 @@
+ {
+ 	switch (caller_fl->fl_type) {
+ 	case F_RDLCK:
+-		return (sys_fl->fl_type == F_WRLCK);
++		return ((sys_fl->fl_type == F_WRLCK) || 
++			(!list_empty(&sys_fl->fl_block))
++		);
+ 
+ 	case F_WRLCK:
+ 		return (1);

File t2/rwlock/pthread_rwlock_fcfs-0.2.0.tar.gz

Binary file added.

File t2/rwlock/pthread_rwlock_fcfs-0.4.0.tar.gz

Binary file added.

File vipe/rwlock/Scheme.txt

-The RWLock will use a queue. Each element of the queue will contain
-a condition variable and a flag that indicates if it contains a reader
-or a writer pending. 
-
-The RWLock will contain a counter that tells it how many readers are using 
-it at the moment (num_readers), and a flag that specifies if there's a 
-writer using the lock (is_writer). It also uses a common internal mutex 
-to protect against mutual exclusion (mymutex)
-
-Algorithm:
-
-accept_pending_items:
----------------------
-
-Extracts the first element out of the queue. 
-
-If it is a writer, it sets is_writer to 1, and signals the condition 
-variable of the element.
-
-If it is a reader, it sets is_writer to 0, and polls+extracts 
-all the other items out of the head of the queue that are readers 
-(i.e it stops at the first writer or at the end of the queue).
-
-get_write_access:
------------------
-
-locks mymutex.
-
-Checks if is_writer is set or num_readers is greater than 0. If so, 
-it enqueues itself. (the mutex of the condition variable is mymutex)
-
-If not it sets is_writer to 1.
-
-Unlocks the mutex.
-
-
-
-get_read_access:
-----------------
-
-locks mymutex.
-
-If the queue is empty and is_writer is false it increments num_readers and unlock mutex.
-
-Else it enqueues itself, while using mymutex for waiting on the condition variable. When the condition variable is signalled, num_readers is incremented by 1.
-
-Unlocks mutex.
-
-release_write_access:
----------------------
-
-locks mutex
-
-Sets is_writer to false. Then calls accept_pending_items.
-
-unlocks mutex
-
-release_read_access:
---------------------
-
-locks mutex
-
-Decrements num_readers. If num_readers == 0 it calls accept_pending_items.
-
-unlocks mutex
-

File vipe/rwlock/Scheme_RLE.txt

-Data Structures:
-================
-
-The RWLock will use a queue. Each element of the queue will contain:
-1. a condition variable 
-2. a flag that indicates if it contains readers or writers pending. 
-3. num_threads - an integer specifiying how many threads are waiting on it.
-4. was_first_thr_accepted - a flag that indicates if the first thread has
-already been accepted from it. (used only for a writers' pack).
-
-The RWLock will contain a counter that tells it how many readers are using 
-it at the moment (num_readers), and a flag that specifies if there's a 
-writer using the lock (is_writer). It also uses a common internal mutex 
-to protect against mutual exclusion (mymutex)
-
-Algorithm:
-==========
-
-accept_pending_items:
----------------------
-
-Peek the first element out of the queue. 
-
-If it is a writers' pack, it decrements the number of threads by one, 
-and signals the condition variable, and sets was_first_thr_accepted to 1. 
-Afterwards, if (elem.num_threads == 0) it extracts and destroys the item.
-
-If it is a readers' pack, it broadcasts the condition variable. Then it
-extracts and destroys the item.
-
-get_write_access:
------------------
-
-locks mymutex.
-
-Checks if is_writer is set or num_readers is greater than 0. If so, 
-it enqueues itself. (the mutex of the condition variable is mymutex)
-
-If not it sets is_writer to 1.
-
-    Enqueuing: 
-    
-    peek the tail of the queue. If it is a writers' pack and
-    its was_first_thr_accepted is false, increase the number of threads 
-    there by 1 and wait on its condition variable. If not, enqueue a new 
-    writer's pack with a threads_num set to 1 and a new condition variable.
-
-
-Unlocks the mutex.
-
-
-get_read_access:
-----------------
-
-locks mymutex.
-
-If the queue is empty and is_writer is false it increments num_readers 
-and unlocks mutex.
-
-Else it enqueues itself, while using mymutex for waiting on the 
-condition variable. When the condition variable is signalled, 
-num_readers is incremented by 1.
-
-    Enqueueing: 
-    
-    peek the tail of the queue. If it is a readers' pack, 
-    increase the number of threads there by 1 and wait on its 
-    condition variable. If not, add a new readers pack with threads_num 
-    set to 1 and a new condition variable, which it will wait upon.
-
-Unlocks mutex.
-
-
-
-release_write_access:
----------------------
-
-locks mutex
-
-Sets is_writer to false. Then calls accept_pending_items.
-
-unlocks mutex
-
-release_read_access:
---------------------
-
-locks mutex
-
-Decrements num_readers. If num_readers == 0 it calls accept_pending_items.
-
-unlocks mutex
-

File vipe/rwlock/index.html.wml

-#include '../template.wml'
-<latemp_subject "A First-Come First-Served Readers/Writers Lock" />
-
-<h2><a href="./linux-kernel/">New! FCFS flock for the Linux Kernel</a></h2>
-
-<p>
-<a href="pthread_rwlock_fcfs-0.4.0.tar.gz">Download the stable version source code.</a>
-</p>
-
-<!--
-	Commented out until I have a new development version
-	
-<p>
-<a href="pthread_rwlock_fcfs-0.3.5.tar.gz">Development version</a>
-</p>
--->
-
-<p>
-This is a working implementation of a First-Come First-Served
-Readers/Writers lock for POSIX threads. It is well commented and documented
-so I believe it can also serve as a reference implementation for those
-who wish to implement such a mechanism for other platforms.
-</p>
-
-<h2>Todo List</h2>
-
-<ul>
-<li>Make an RPM SPEC/Debian Package etc.</li>
-<li>Port to Win32, ZThreads, etc.</li>
-</ul>
-
-<h2>Frequently Asked Questions</h2>
-
-<h3>What is a Readers/Writers Lock?</h3>
-
-<p>
-A Readers/Writers Lock (or RWLock for short) is a mechanism that allows an
-arbitrary number of readers or alternatively one writer to access a
-resource at any given time. It is useful in case writing may temporarily harm
-the integrity of the resource.
-</p>
-
-<h3>What is a First-Come First-Served RWLock?</h3>
-
-<p>
-Many RWLock implementations arbitrate the various readers and writers in a
-manner that may cause starvation of either readers or writers. For instance,
-a readers/writers lock that prefers readers may cause a writer to starve
-(i.e: wait for a very long time or indefinetly) if there are two and more
-competing readers.
-</p>
-
-<p>
-A First-Come First-Served (FCFS) RWLock solves this problem by making sure
-that the pending threads are served at the same order as the time of their
-arrival. Thus, starvation is eliminated assuming that a thread does not
-obtain the lock indefinetly (which in any case should not happen in a 
-well-designed system).
-</p>
-
-<h3>How does it make sure that's what going to happen?</h3>
-
-<p>
-By using a queue in which each element controls a pending thread. A detailed
-description of the algorithm can be found <a href="Scheme.txt">here</a> and
-naturally, there are also the comments in the code. If there's anything you
-don't understand, don't hesitate to 
-<a href="mailto:shlomif@vipe.technion.acil">contact me</a> 
-and ask.
-</p>
-
-<p>
-Recently, the algorithm was modified to pack several readers or several
-writers on the same queue element, which results in saving of condition
-variables. The new scheme for it (which is a bit more complex) can be found 
-<a href="Scheme_RLE.txt">here</a>.
-</p>
-
-<br />
-<br />
-
-<h2>Older Versions</h2>
-
-<p>
-<a href="pthread_rwlock_fcfs-0.2.0.tar.gz">Version 0.2.0</a>
-</p>
-

File vipe/rwlock/linux-kernel/index.html.wml

-#include '../template.wml'
-
-<latemp_subject "Linux Kernel FCFS fcntl/flock Locks" />
-
-<h2><a href="linux-fcfs-rwlock.patch">Download the Patch</a></h2>
-
-<p>
-I wrote this patch (it's actually very short) with a lot of help from
-Matthew Wilcox, who is the current maintainer of the filesystem locks
-logic in the Linux Kernel. It is made against linux-2.5.30 but should
-work with more recent or later versions.
-</p>
-
-<p>
-Without this patch, the Linux kernel discriminates against writers,
-and accepts readers into a lock in readers state even if there are
-pending writers. The <a href="test_flock.c">following 
-test program</a> can demonstrate the two behaviours (try running it as 
-<tt>test_flock 20 2</tt>).
-</p>
-

File vipe/rwlock/linux-kernel/linux-fcfs-rwlock.patch

---- orig/linux-2.5.30/fs/locks.c	Fri Aug  2 00:16:39 2002
-+++ linux-2.5.30/fs/locks.c	Fri Aug 16 17:48:49 2002
-@@ -510,7 +510,9 @@
- {
- 	switch (caller_fl->fl_type) {
- 	case F_RDLCK:
--		return (sys_fl->fl_type == F_WRLCK);
-+		return ((sys_fl->fl_type == F_WRLCK) || 
-+			(!list_empty(&sys_fl->fl_block))
-+		);
- 
- 	case F_WRLCK:
- 		return (1);

File vipe/rwlock/pthread_rwlock_fcfs-0.2.0.tar.gz

Binary file removed.

File vipe/rwlock/pthread_rwlock_fcfs-0.4.0.tar.gz

Binary file removed.