Journal/Paper.thy
changeset 156 550ab0f68960
parent 155 eae86cba8b89
child 157 029e1506477a
--- a/Journal/Paper.thy	Mon Mar 06 13:11:16 2017 +0000
+++ b/Journal/Paper.thy	Thu Mar 16 13:20:46 2017 +0000
@@ -1550,7 +1550,8 @@
   \cite{ZhangUrbanWu12} to leave out this property and let the
   programmer assume the responsibility to program threads in such a
   benign manner (in addition to causing no circularity in the
-  RAG). However, in this paper we can make an improvement: we can look
+  RAG). This was also the approach taken by Sha et al.~in their paper.
+  However, in this paper we can make an improvement: we can look
   at the \emph{events} that are happening once a Priority Inversion
   occurs. The events can be seen as a rough abstraction of the
   ``runtime behaviour'' of threads and also as an abstract notion of
@@ -1565,7 +1566,7 @@
   hibernating threads in our model, but we can create or exit threads
   arbitrarily. Consequently, in our model the avoidance of indefinite
   priority inversion we are trying to establish is not true, unless we
-  require that there number of threads is bounded in every
+  require that there number of threads created is bounded in every
   valid future state after @{term s}. So our first assumption 
   states
 
@@ -1578,11 +1579,11 @@
 
   \noindent Note that it is not enough for us to just to state that there
   are only finite number of threads created in the state @{text "s' @ s"}.  Instead, we
-  need to put a bound on the @{text "Create"} event for all valid 
+  need to put a bound on the @{text "Create"} events for all valid 
   states after @{text s}. 
 
-  For our assumption about giving up resources after a finite amount of ``time'',
-  let us introduce the following definition:
+  For our second assumption about giving up resources after a finite
+  amount of ``time'', let us introduce the following definition:
 
   \begin{isabelle}\ \ \ \ \ %%%
   @{thm blockers_def}
@@ -1594,27 +1595,36 @@
 
   \begin{quote}
   {\bf Assumptions on the threads {\boldmath{@{term "th' \<in> blockers"}}}:} 
-  There exists a finite bound @{text BND} such that for all future 
+  For each @{text "th'"} there exists a finite bound @{text "BND(th')"} 
+  such that for all future 
   valid states @{text "t @ s"},
   we have that if @{term "\<not>(detached (t @ s) th')"}, then 
-  @{term "len(actions_of th' (t @ s)) < BND"}. 
-  \end{quote}
+  @{text "len(actions_of th' (t @ s)) < BND(th')"}. 
+  \end{quote} 
 
-  \noindent
-  By this we mean that any thread that can block @{term th} must become
-  detached (that is hold no resource) after a finite number of events 
-  in @{text "t @ s"}.
+  \noindent By this assumption we enforce that any thread blocking
+  @{term th} must become detached (that is hold no resource) after a
+  finite number of events in @{text "t @ s"}. Again we have to require
+  this bound to hold in all valid states after @{text s}. The bound
+  reflects how each thread @{text "th'"} is programmed: Though we cannot
+  express what instructions a thread is executing, the events correspond 
+  to the system calls made by thread. Our @{text "BND(th')"} bounds 
+  the number of these calls.
   
-  Now we can prove a lemma which gives a upper bound
-  of the occurrence number when the most urgent thread @{term th} is blocked.
+  The main reason for these two assumptions is that we can prove: 
+  
+
+  \begin{isabelle}\ \ \ \ \ %%%
+  @{thm bound_priority_inversion}
+  \end{isabelle}
 
   It says, the occasions when @{term th} is blocked during period @{term t} 
   is no more than the number of @{term Create}-operations and 
   the operations taken by blockers plus one. 
+   
 
-  \begin{isabelle}\ \ \ \ \ %%%
-  @{thm bound_priority_inversion}
-  \end{isabelle}
+ Now we can prove a lemma which gives a upper bound
+  of the occurrence number when the most urgent thread @{term th} is blocked.
 
 
   Since the length of @{term t} may extend indefinitely, if @{term t} is full