Journal/Paper.thy
changeset 130 0f124691c191
parent 127 38c6acf03f68
child 134 8a13b37b4d95
--- a/Journal/Paper.thy	Tue Jun 14 15:06:16 2016 +0100
+++ b/Journal/Paper.thy	Fri Jun 17 09:46:25 2016 +0100
@@ -33,18 +33,21 @@
   vt ("valid'_state") and
   Prc ("'(_, _')") and
   holding_raw ("holds") and
-  holding ("Holds") and
+  holding ("holds") and
   waiting_raw ("waits") and
-  waiting ("Waits") and
+  waiting ("waits") and
   dependants_raw ("dependants") and
-  dependants ("Dependants") and
+  dependants ("dependants") and
+  RAG_raw ("RAG") and
+  RAG ("RAG") and
   Th ("T") and
   Cs ("C") and
   readys ("ready") and
   preced ("prec") and
   preceds ("precs") and
   cpreced ("cprec") and
-  cp ("cprec") and
+  wq_fun ("wq") and
+  cprec_fun ("cp") and
   holdents ("resources") and
   DUMMY  ("\<^raw:\mbox{$\_\!\_$}>") and
   cntP ("c\<^bsub>P\<^esub>") and
@@ -455,7 +458,7 @@
   \noindent
   Using @{term "holding_raw"} and @{term waiting_raw}, we can introduce \emph{Resource Allocation Graphs} 
   (RAG), which represent the dependencies between threads and resources.
-  We represent RAGs as relations using pairs of the form
+  We choose to represent RAGs as relations using pairs of the form
 
   \begin{isabelle}\ \ \ \ \ %%%
   @{term "(Th th, Cs cs)"} \hspace{5mm}{\rm and}\hspace{5mm}
@@ -524,8 +527,6 @@
   that the resource is locked. In this way we can always start at a thread waiting for a 
   resource and ``chase'' outgoing arrows leading to a single root of a tree. 
   
-
-
   The use of relations for representing RAGs allows us to conveniently define
   the notion of the \emph{dependants} of a thread using the transitive closure
   operation for relations, written ~@{term "trancl DUMMY"}. This gives
@@ -545,14 +546,14 @@
   there is a circle of dependencies in a RAG, then clearly we have a
   deadlock. Therefore when a thread requests a resource, we must
   ensure that the resulting RAG is not circular. In practice, the
-  programmer has to ensure this.
-
+  programmer has to ensure this. Our model will assume that critical 
+  reseources can only be requested provided no circularity can arise.
 
   Next we introduce the notion of the \emph{current precedence} of a thread @{text th} in a 
   state @{text s}. It is defined as
 
   \begin{isabelle}\ \ \ \ \ %%%
-  @{thm cpreced_def2}\hfill\numbered{cpreced}
+  @{thm cpreced_def}\hfill\numbered{cpreced}
   \end{isabelle}
 
   \noindent
@@ -568,13 +569,17 @@
   lowered prematurely. We again introduce an abbreviation for current precedeces of
   a set of threads, written @{term "cprecs wq s ths"}.
   
+  \begin{isabelle}\ \ \ \ \ %%%
+  @{thm cpreceds_def}
+  \end{isabelle}
+
   The next function, called @{term schs}, defines the behaviour of the scheduler. It will be defined
   by recursion on the state (a list of events); this function returns a \emph{schedule state}, which 
   we represent as a record consisting of two
   functions:
 
   \begin{isabelle}\ \ \ \ \ %%%
-  @{text "\<lparr>wq_fun, cprec_fun\<rparr>"}
+  @{text "\<lparr>wq, cp\<rparr>"}
   \end{isabelle}
 
   \noindent