Many programs (processes) are usually running on a computer at the
same time. All of these processes are fighting for resources ( memory
etc). Is it possible to predict their behavior (to some level of
accuracy) somehow ?  I want a detailed answer, with pointers to
relevant references where possible. There will be a big tip if I am
satisfied (the tip will be directly proportional to my satisfaction
which means you could even get $100 and above if I’m impressed) .
Also I would like to know which class of systems are best suited for
such purposes (I mean in which systems is it easier to predict the
behavior)
*Please don’t answer if you don’t know what you are doing, I too can
go to research-index etc and search for keywords but this is not what
I want (although this would be helpful in providing references etc ),
I want someone who knows a little about all this to answer.
*You are free to give examples from any particular field/OS/group etc
i dont have any restrictions on the system under consideration but do
keep in mind the general context.

---

Clarification of Question by theorycs-ga on 30 Oct 2002 20:52 PST

Please note this is the second time I am posting this question, there
were some technical problems due to which the question was removed the
last time. I want to thank Mathtalk-ga who provided some sensible
commentary on the topic the last time I had posted this question. If
you believe that setting some particular limitations on the system
under consideration would help then please feel free to do so and
state how for this particular system (the one you have considered)
predictions can be made.

---

Request for Question Clarification by rbnn-ga on 30 Oct 2002 21:32 PST

The question is a an open-ended one; more detail on desired use of the
information; on the question provenance; on the parameters of an
acceptable answer; even on questioner background in target area, might
help. Even so, it sounds like it might prove to be too time-consuming
a problem for many researchers to tackle at the offered pricepoint; as
stated I think a complete answer would take me probably 10 or 12
hours, and I'm not sure if I could provide good answers even then.

Two axes along which an attack on the problem might proceed are the
complexity-theoretic and the concurrency-theoretical vantage.

Complexity-wise, I will mention that of course even predicting the
behavior of a single process (much less multiple ones) is Turing
complete. That is, we cannot in general even predict whether a process
will ever halt. If we bound the time or space resources of the process
we still get very high complexity bounds very quickly. Even if we
demand only approximate solutions, or only probabilistically correct
solutions, the problem remains sufficiently wide that no useful bounds
would be found - everything will be something-complete for the various
complexity classes.

OS-wise, the only thing that comes to mind is the banker's algorithm
for deadlock detection, and some other deadlock detection algorithms.
I have seen some learning algorithms in OS theory that do things like
try and out-do the performance of LRU in cache management by
predictive analysis.

There is a field of concurrency research that deals with the logic of
what "might ever" or "will eventually always" happen; see for example
the Milner work and his school on concurrency semantics.
Notable here is the use of modal logic, (many different logics,
typically), but its efficacy for this problem is something on which I
have insufficient information to comment. Such logics are typically
used to analyze specific protocols, rather than concrete running
systems.

---

Clarification of Question by theorycs-ga on 30 Oct 2002 22:27 PST

Hey rbnn-ga! Nice try :) ! 

You can forget the complexity approach because the halting problem etc
are not so relevant in this case.

Now then if you have time to spend then try see what you can do. Don’t
worry about the cost cos I’ll give a big tip if I’m satisfied and I’ll
surely give 5 stars whatever your answer so you can just improve ur
rating and the $9.oo + small tip wont hurt. i could have put the price
at $50 or more and then in the end maybe ur answer would not have
satisfied me but i choose not to do that so if you give me a
satisfactory enough answer i'll put in a good tip you can be sure of
that !



Try to keep your answer relevant to the OS domain. What I actually
want to know, without giving any further information, is that in which
cases or in which systems can I predict (at least something) about how
some program(s) might behave in the future? or if you can give me
particular examples of systems where this sort of predicitive analysis
is most appropriate, would also be helpful.

Hello CS Theory ,

 The theory used to solve such problems is called the Theory of
Queues.

  Here is a brief  bibliography of that field:
http://www2.uwindsor.ca/~hlynka/qbook.html

   I will not expand on that because
1) You can type this search term  into a search engine  yourself and
     get many resources which exist online.
2) The analytical approach is not useful any more, except as
   a means of verification of numerical models and for teaching.

   In other words: As with differential equations, theory has been
   replaced by computer models which use numerical algorithms in 
   just about all non-trivial applications.

   Engineering problems are solved by DE models and I will expand on
those:

 DE models, that is Discrete Event models, are a vast field,
 used to model queues in a supermarket, assembly lines, and also
 computer systems and networks. We want to focuse on the later and so,
 in the following, I am using as search terms DE  in conjunction with 
terms,
 such as computer systems, OS or networks, to select references
relevant to digital systems.

 Here is an overall introduction to DE simulation:
http://www.frontrunnercpc.com/info/simulation.htm

 Here are some academic studies and description of tools:
http://www.cl.cam.ac.uk/Research/SRG/netos/plana/PDES.html

  Analysisng a real system well is a complex problem, which
  (like most models) requires good characterization of the load,
  of the scheduling algorithms, and of the capabilities of the
hardware.

 There are (some free) simulation programs, and even special
languages,
 ,such as Simula or  Simscrit written for this type of studies.
  However,having used several of them, I would recommend a general
 purpose language like C or C++, with a special package (library).
  Object Oriented (OO) aspect is very useful for these applications.
  (Actually and BTW, Simula, which was written for such studies,
   was one of the important sources of the OO concept.)

 The DE (or DES) models are ideal for simulation of digital systems.
 They differ from most models (CS or continuos system models)by using
 time as a dependent variable. The independent variables are tasks
 to be performed. It is an interesting concept, a new process-oriented
 worldview, interesting in itself, and essential for the study of
behavior
 of the computer systems.


Here is a very simple introduction to DE simulation
http://www.cis.um.edu.mt/~jskl/simul.html

Here a bit more, with a reference to Simscript:
http://ubmail.ubalt.edu/~harsham/simulation/sim.htm

 Good academic sites for DE are UC Berkeley and U of Calgary in
Canada,
 and the most sophisticated system for DE simulations is SWARM,
developed at
 LANL:
http://www.c3.lanl.gov/~rocha/complex/talks/swarmteam.html

 Swarm may be too much for a simple task. There is a learning curve
 associated with the use of these tools, and since I do not know
whether
 you are contemplating building a model, and what scale of effort
 you would use, I will stop here.

  DE, is used not just in academia, but in
 real applications such as the evaluation the performance of computer
systems and
 networks, including the evaluation of LAN protocols, under different
loads and
 running on diverse hardware.

 You may want to further describe what computer system or OS you are
 interested in.  In that case, there may be more specific references
available.

  In any case, the search terms

   Discrete Event Simulationh
   Computer system,
   Network (or OS)

 plus terms describing your specific system of interest
 should bring a wealth of references of work done in that
 particular subfield of computer performance studies.

 Hedgie

---

Request for Answer Clarification by theorycs-ga on 31 Oct 2002 18:36 PST

Hello hedgie

“If you study hard you will get good marks” this is not what I was
looking for. If I had wanted an introduction to queuing theory or
Discrete system modeling I would have asked for it. The question
clearly states that “in which systems can we predict the behavior of
processes" - can U give examples? “how can we do this if at all and
with what accuracy” Has someone tried this earlier ?  ? Or be more
specific on “Which properties are the most relevant while constructing
a model” ?

You seem to be in a hurry to get the $9.00 well I don’t mind but at
least you could have tried to give something useful like the mathtalk
or duncan2 well if you want a good rating and a small tip please try
again.

Theorycs

---

Request for Answer Clarification by theorycs-ga on 01 Nov 2002 00:02 PST

Oh! Yes and another thing I forgot to write in response to your advise
on modeling discrete systems well the problem is that some of the
systems I am considering are too complex to be modeled by discrete
systems what I mean to say is that even if I do model them I don’t get
the required results because all of the model checking techniques
suffer from the “state space explosion problem” which means the number
of states to be verified for a reasonable purpose is too many or I
have to simplify the model which leads to information loss. Either way
this was not what I was asking for in the question I am very familiar
with model checking and also with theorem proving so please try and
keep to the question.

Have a look at what mathtalk has done he’s chose one example and
researched it and explained it very well, I am not trying to make any
comparisons its just that you’ve steered off the topic a bit, I want
you to just answer me on the prediction part.

---

Clarification of Answer by hedgie-ga on 01 Nov 2002 05:05 PST

Hello CS theory
                   
                I apologize that I did not guess from your question that
 you are well versed in Queue Theory and construction of the DS models.

 The references and search terms I have provided do lead to specific case
 histories. I wrote few such models myself for diverse clients but it would
 not be proper for me to discuss those.

 I have learned that  success of every  modelling project depends on two things:

 1) ability of the consultant to understand the client,  
   ability to develop a good model and then explain  it to the client and 
2) on the ability of the client to explain what he wants, 
   willingnes to listen and to learn.

  Mutual respect is essential for both things.

 Art of the modelling includes art to simplify, to fit the problem to the
 capabilities of the hardware. For a skilled modeller DS is a sufficient 
 tool. You  do not neeed to look any further. I mean for tools. You need
 to look for another researcher, since I do not think that I can help you.

 Kindly proceed to the URL:
 https://answers.google.com/answers/main?cmd=refundrequest
  and ask for a refund. You may then repost your question,
 same way, or with more details. I would recommend to leave out
 the discussion of the tip. Researchers usually know the rules.

 good luck

 hedgie

Hi, theorycs-ga:

I'm glad you were able to read my comments on working set modelling to
your last post, before it was removed.

rbnn-ga's comments about cache management reminded me of a low-level
aspect of program behavior predictions, namely branch prediction (for
instruction pre-fetch).  While certainly more art than science, this
topic is at the forefront of competition between Intel and AMD.  As
CPU pipelines lengthen, prediction accuracy becomes more critical to
performance improvements.

hedgie-ga's comments about queuing theory certainly bring up an
important tool in understanding the behavior of computer systems.  It
brought back memories of trying to explain to management, using
queuing theory, why high CPU utilization is not the best basis for
cost recovery of an interactive mainframe.

To throw yet another log on the fire, security considerations define
respects in which it is desirable to predict program behavior. 
Firewalls may check programs' permissions to use certain TCP/IP ports.
 Language implementations may guarantee "safe" behavior of programs
memory access by throwing exceptions. Database management software may
limit a program's access to avoid deadlocks or to enforce a user's
role permissions.  Implicit in all these is a form of rules based
modelling of acceptable vs. unacceptable program behavior.  Certainly
by circumscribing a program's behavior, it becomes easier to predict. 
E.g. if programs launched from a given queue are terminated on
consumption of a maximum amount of CPU time, you can predict the
average CPU consumption of programs in that queue will not exceed that
maximum.

regards, mathtalk-ga

If anyone is interested in reading them, my comments and reply to
theorycs-ga's original post appear to be in the Science > Math
subsection.  At least I can see them there... under basically the same
title as this posting.

If anyone finds that they cannot see them, I'd be curious to know
that, too.  As this is a new process, I think we are all still
struggling with how to make it work well.

regards, mathtalk-ga

theorycs-ga: 

A little known option in google answers is to specify that a question
can only be answered by a particular researcher. Thus, if you wanted
to specify that a question be answered by mathtalk-ga, you can just
add the words (for mathtalk-ga only) in the subject line of the
question .

Mathtalk-ga 
             your answer is visible, both in that category and also 
 directly at:
 https://answers.google.com/answers/main?cmd=threadview&id=92961


  I wonder what is the history of this 'question' . Were there
  other answers which are not 'there' any more? 

hedgie

Hi, hedgie:

Thanks for checking.  It looks intact, from what I can recall.

regards, mathtalk