Chaoes

               When chaos begin...

Here it goes....

         The code from P.P.

hi,

I hope you can help me to solve this puzzle in programming assignment1.

1. I think when a thread is interrupted by "yield", it should be put back on the ready queue and the next thread who is in head of ready queue will be executed, right?

2. I only observed this for the first "interrupt" and all other interruption doesn't follow this.

---a) I changed the "Deamon" array to be {0, 4, 4, 4, 6, 4, 6, 4, 6}; so that worker 8, 6, 4 will be interrupted.

---b) I add one output inside Daemon's interrupt function to help reading:

    public synchronized void interrupt (int tid) {
    if ( d[tid] > 4 )
    {
      System.out.println("worker "+tid+ " is interrupted.");
      Thread.yield ();
    }
3) Please see following result:

---a) Worker 8 is interrupted and worker 7 is invoked to execute. This is ok.

---b) Worker 6 is interrupted and instead worker 5 is invoked, worker 6 continues to "set neighbour's array!!!!

---c) Worker 4 is interrupted and instead worker 3 is invoked, worker 4 continues to "set neighbour's array!!!!

[qingz_hu@alpha ~/Java] % javac Future.java
[qingz_hu@alpha ~/Java] % java Future
Eight workers have started.
Main thread continues work.
Main thread waits on semaphore 1.
Worker 8 begins execution.
Worker 7 begins execution.
Worker 6 begins execution.
Worker 5 begins execution.
Worker 4 begins execution.
Worker 3 begins execution.
Worker 2 begins execution.
Worker 1 begins execution.
Worker 8 doubles own array component.
worker 8 is interrupted.
Worker 7 doubles own array component.
Worker 6 doubles own array component.
Worker 5 doubles own array component.
Worker 4 doubles own array component.
Worker 3 doubles own array component.
Worker 2 doubles own array component.
Worker 1 doubles own array component.
Worker 8 sets neighbor's array component.
Worker 8 signals semaphore 8.
Worker 8 terminates.
Worker 7 sets neighbor's array component.
Worker 7 signals semaphore 7.
Worker 7 terminates.
worker 6 is interrupted.
Worker 6 sets neighbor's array component.
Worker 6 signals semaphore 6.
Worker 6 terminates.
Worker 5 sets neighbor's array component.
Worker 5 signals semaphore 5.
Worker 5 terminates.
worker 4 is interrupted.
Worker 4 sets neighbor's array component.
Worker 4 signals semaphore 4.
Worker 4 terminates.
Worker 3 sets neighbor's array component.
Worker 3 signals semaphore 3.
Worker 3 terminates.
Worker 2 sets neighbor's array component.
Worker 2 signals semaphore 2.
Worker 2 terminates.
Worker 1 sets neighbor's array component.
Worker 1 signals semaphore 1.
Worker 1 terminates.
Main thread reads 1 from position 1.
Main thread waits on semaphore 2.
Main thread reads 1 from position 2.
Main thread waits on semaphore 3.
Main thread reads 1 from position 3.
Main thread waits on semaphore 4.
Main thread reads 1 from position 4.
Main thread waits on semaphore 5.
Main thread reads 1 from position 5.
Main thread waits on semaphore 6.
Main thread reads 1 from position 6.
Main thread waits on semaphore 7.
Main thread reads 1 from position 7.
Main thread waits on semaphore 8.
Main thread reads 2 from position 8.
Sum = 9
System terminates normally.
[qingz_hu@alpha ~/Java] %
　

4) This is unexplainable and puzzled me for long. Can you explain this?

5) By the way, I thought the code for Semaphore is meaningless because main thread starts waiting on semaphore from "1" to "8" and thread is start running from "8" to "1". That is the thread is doing useless job by sending signals and the only signal can be read by the main thread is the thread "1" which starts lastly. I think professor might plan to sum up immediately after one thread finishes by reading the signal. But the code for starting sequence of thread is just opposite.

Thank you for your time,

Nick Huang/Qingzhe Huang

Here it comes....

your basic understanding of what yield (); does is correct

I can't debug your code over e-mail
　

Here it goes....

hi professor,

Thank you for your mail!
Enclosed pls find my source file. I didn't change anything from your source
code except:
1. Initialize the Deamon's array to be {0, 4, 4, 4, 6, 4, 6, 4, 6};
2. Insert one display statement inside Deamon's interrupt function:
if ( d[tid] > 4 )
    {
      System.out.println("worker "+tid+ " is interrupted.");
      Thread.yield ();
    }

3. All others are unchanged.
4. There is one more thing I observed that when thread sends out signal, it
only wake up the waiting thread (in this case main thread) next round. That
is suppose thread 8 is sends out signal and terminate, the next running
thread is thread 7 instead of signaled thread----main thread.
5. According to your lecture, I guess that when a process is doing the I/O
CPU schedule should then place it into a waiting queue. So, I think
similarly when a thread is doing the output of messages which is very slow,
it also should be relinquished from CPU, and next thread at head of ready
queue should run. But it doesn't seem so from my result. Is it because Java
thread is user thread instead of kernel thread?

Thank you for your time,

Nick Huang/Qingzhe Huang
　

Here it comes...

I think you are mixing tons of different things

for example, these aren't Unix signals; they're semaphore signals

thread 8 provides a token for semaphore 8

the main program tries, in order, to acquire tokens 1 through 8

if the main program is blocked waiting for token 1, it has no
effect if thread 8 stockpiles an "8" token for later use

these are Java threads, not OS anythings; I/O shouldn't change
anything

you can't translate lectures about a real OS into the semantics
of a programming language

thread 7 runs after thread 8 because it is next on the ready
queue; the main thread doesn't become unblocked until all
workers have signalled

　

Here it goes...

Hi Professor,

Thank you so much for your message and I can't agree with you more!
1. Surely the class Semaphore is not what the name implies. It is not Unix
signals.
2. Java thread is user thread (at least it is true for version 1.2) and OS
is not aware the existence of thread. So, I/O operation won't be blocked.
3. And all other things are not important except my question about the
yielded thread in my first email. That is why the yielded thread continues
work.
4. I now repeat the whole question as following:

----a) The original source code attached is same as I sent last mail.
----b) The running result is like following:
----c) The Deamon array is {0, 4, 4, 4, 6, 4, 6, 4, 6} which implies the
thread "8", "6","4" will be interrupted by Deamon or in other words, should
yield.
----d) The yielded thread should relinquish CPU and be placed on back of
ready queue.
----e) Thread "8" gets the the first interrupt as shown below and it is in
consistence as our expectation.
----f) Thread "6", "4" get interrupt as shown below and they both continue
as if interrupt doesn't happen!!!!This makes no senses!!! Can you explain
this?
----g) I compiled this code in server "alpha" through "SSH" client, and I
also changed code in many tests and get similar results.
----h) Can you check the result by yourself? And I will be very grateful.

Thank you in advance for your attention.

Have a nice day,

p.s. The following is the running results based on attached source code in
which I only add one more displaying statement within "interrupt function"
of Daemon class.

Eight workers have started.
Main thread continues work.
Main thread waits on semaphore 1.
Worker 8 begins execution.
Worker 7 begins execution.
Worker 6 begins execution.
Worker 5 begins execution.
Worker 4 begins execution.
Worker 3 begins execution.
Worker 2 begins execution.
Worker 1 begins execution.
Worker 8 doubles own array component.
worker 8 is interrupted.                   //-------------------This is
first interrupt of thread "8", and thread "7" continues instead.
Worker 7 doubles own array component.
Worker 6 doubles own array component.
Worker 5 doubles own array component.
Worker 4 doubles own array component.
Worker 3 doubles own array component.
Worker 2 doubles own array component.
Worker 1 doubles own array component.
Worker 8 sets neighbor's array component.
Worker 8 signals semaphore 8.
Worker 8 terminates.
Worker 7 sets neighbor's array component.
Worker 7 signals semaphore 7.
Worker 7 terminates.
worker 6 is interrupted.                              //---------This is
second interrupt of thread "6", but it continues!!!!
Worker 6 sets neighbor's array component.
Worker 6 signals semaphore 6.
Worker 6 terminates.
Worker 5 sets neighbor's array component.
Worker 5 signals semaphore 5.
Worker 5 terminates.
worker 4 is interrupted.                         //---------This is third
interrupt of thread "4", but it continues!!!!
Worker 4 sets neighbor's array component.
Worker 4 signals semaphore 4.
Worker 4 terminates.
Worker 3 sets neighbor's array component.
Worker 3 signals semaphore 3.
Worker 3 terminates.
Worker 2 sets neighbor's array component.
Worker 2 signals semaphore 2.
Worker 2 terminates.
Worker 1 sets neighbor's array component.
Worker 1 signals semaphore 1.
Worker 1 terminates.
Main thread reads 1 from position 1.
Main thread waits on semaphore 2.
Main thread reads 1 from position 2.
Main thread waits on semaphore 3.
Main thread reads 1 from position 3.
Main thread waits on semaphore 4.
Main thread reads 1 from position 4.
Main thread waits on semaphore 5.
Main thread reads 1 from position 5.
Main thread waits on semaphore 6.
Main thread reads 1 from position 6.
Main thread waits on semaphore 7.
Main thread reads 1 from position 7.
Main thread waits on semaphore 8.
Main thread reads 2 from position 8.
Sum = 9
System terminates normally.

Nick Huang/Qingzhe Huang

Here it comes....

when thread 8 yields, control goes to thead 7 earlier (i.e., before
more statements of thread 8) than it otherwise would
compare thread 8's behavior (_all_ its behavior) in your printout
with the all 4s printout

see how long it takes thread 8 to circle around before setting
its neighbor's array component

THAT'S the result of the interrupt!
　

Here it goes...

Hi Professor,

I cannot follow your explanation either because my English is too poor or we
are not talking about the same question. To eliminate the second
possibility, I indexed all results as following.
1) The problem is not that thread "8" doesn't behave well. On the contrary,
it is exact what we expect for it.
2) The problem is thread "6" and thread"4".
3) On "output 27", thread "6" is interrupted because we see it displayed
this line BEFORE it is interrupted.
4) On "output 28" we don't see thread "5", instead thread "6" continues to
be alive!!This is the problem!
5) Similar situation happens on "output 34" where thread "4" claims it will
be interrupted in next CPU execution, however, on next "output" which is
"output 35" thread "4" claims it is still alive.
6) I checked MSDN and function "yield" is exactly what its name implies
which is same as Unix: "Causes the currently executing thread object to
temporarily pause and allow other threads to execute. "
7) Function "yield" would not change the sequence of execution of these same
priority threads, that is in a sequence of
8,7,6,5,4,3,2,1,8,7,6,5,4,3,2,1,8,7,6,5,4,3,2,1... It only forces the
current thread to relinquish the controling of CPU from the rest of time
slice.

Thank you so much for your time and attention,

Nick Huang/Qingzhe Huang

p.s. The following results are indexed by me for references.

1    Eight workers have started.
2    Main thread continues work.
3    Main thread waits on semaphore 1.
4    Worker 8 begins execution.
5    Worker 7 begins execution.
6    Worker 6 begins execution.
7    Worker 5 begins execution.
8    Worker 4 begins execution.
9    Worker 3 begins execution.
10 Worker 2 begins execution.
11 Worker 1 begins execution.
12 Worker 8 doubles own array component.
13 worker 8 is interrupted.
14 Worker 7 doubles own array component.
15 Worker 6 doubles own array component.
16 Worker 5 doubles own array component.
17 Worker 4 doubles own array component.
18 Worker 3 doubles own array component.
19 Worker 2 doubles own array component.
20 Worker 1 doubles own array component.
21 Worker 8 sets neighbor's array component.
22 Worker 8 signals semaphore 8.
23 Worker 8 terminates.
24 Worker 7 sets neighbor's array component.
25 Worker 7 signals semaphore 7.
26 Worker 7 terminates.
27 worker 6 is interrupted.
28 Worker 6 sets neighbor's array component.
29 Worker 6 signals semaphore 6.
30 Worker 6 terminates.
31 Worker 5 sets neighbor's array component.
32 Worker 5 signals semaphore 5.
33 Worker 5 terminates.
34 worker 4 is interrupted.
35 Worker 4 sets neighbor's array component.
36 Worker 4 signals semaphore 4.
37 Worker 4 terminates.
38 Worker 3 sets neighbor's array component.
39 Worker 3 signals semaphore 3.
40 Worker 3 terminates.
41 Worker 2 sets neighbor's array component.
42 Worker 2 signals semaphore 2.
43 Worker 2 terminates.
44 Worker 1 sets neighbor's array component.
45 Worker 1 signals semaphore 1.
46 Worker 1 terminates.
47 Main thread reads 1 from position 1.
48 Main thread waits on semaphore 2.
49 Main thread reads 1 from position 2.
50 Main thread waits on semaphore 3.
51 Main thread reads 1 from position 3.
52 Main thread waits on semaphore 4.
53 Main thread reads 1 from position 4.
54 Main thread waits on semaphore 5.
55 Main thread reads 1 from position 5.
56 Main thread waits on semaphore 6.
57 Main thread reads 1 from position 6.
58 Main thread waits on semaphore 7.
59 Main thread reads 1 from position 7.
60 Main thread waits on semaphore 8.
61 Main thread reads 2 from position 8.
62 Sum = 9
63 System terminates normally.
　

Here it goes...

Hi professor,

Regarding the programming assignment1, I have observed a strange result which needs your explanations. The problem is that when the thread is interrupted by Deamon or in other words, it yields, in 2/3 cases the yielded thread continues to work as if there is no interruption! And according to my understanding and explanation from MSDN, "yield" function will "Causes the currently executing thread object to temporarily pause and allow other threads to execute. "(quoted from MSDN)

The following is explanantion of environment where the problem happens and attachment is the source code from assignment with minor changes:

1) To achieve the result of following, I only change the source code in two places:

----- a) I set up the Deamon's array as {0, 4, 4, 4, 6, 4, 6, 4, 6}. This will cause interruption on thread "8","6","4" only.

----- b) I inserted one displaying statement for better reading JUST BEFORE the "yield" in Deamon's "interrupt" function.

------c) All others remain same.

2) I connected to "alpha" server through "SSH" and my Java version is 1.2.1. And I indexed all "output" for better referencing.

The following is the problem description:

1) On "output 13" thread "8" behaves as we expected, it relinquish the CPU control and we see on next output thread "7" continues working.

2) On "output 27" the problem begins with the interruption of thread "6", because on next output thread "6" continues to work instead of letting thread "5" to work!! This is what I don't understand.

3) Similar thing happens on "output 34" where thread "4" behaves exactly like thread "6" by continuing working!!!!

4) If you compile and run the attached source code to get the same result, then I need a explanation if it is bug from Java package or it is resulted from some reason beyond my observations.

Thank you for your time and attentions

B.rgds.

Nick Huang/Qingzhe Huang

p.s. The following is results from running attached source code and indexed by me.

1    Eight workers have started.
2    Main thread continues work.
3    Main thread waits on semaphore 1.
4    Worker 8 begins execution.
5    Worker 7 begins execution.
6    Worker 6 begins execution.
7    Worker 5 begins execution.
8    Worker 4 begins execution.
9    Worker 3 begins execution.
10 Worker 2 begins execution.
11 Worker 1 begins execution.
12 Worker 8 doubles own array component.
13 worker 8 is interrupted.

14 Worker 7 doubles own array component.
15 Worker 6 doubles own array component.
16 Worker 5 doubles own array component.
17 Worker 4 doubles own array component.
18 Worker 3 doubles own array component.
19 Worker 2 doubles own array component.
20 Worker 1 doubles own array component.
21 Worker 8 sets neighbor's array component.
22 Worker 8 signals semaphore 8.
23 Worker 8 terminates.
24 Worker 7 sets neighbor's array component.
25 Worker 7 signals semaphore 7.
26 Worker 7 terminates.
27 worker 6 is interrupted.

28 Worker 6 sets neighbor's array component.
29 Worker 6 signals semaphore 6.
30 Worker 6 terminates.
31 Worker 5 sets neighbor's array component.
32 Worker 5 signals semaphore 5.
33 Worker 5 terminates.
34 worker 4 is interrupted.

35 Worker 4 sets neighbor's array component.
36 Worker 4 signals semaphore 4.
37 Worker 4 terminates.
38 Worker 3 sets neighbor's array component.
39 Worker 3 signals semaphore 3.
40 Worker 3 terminates.
41 Worker 2 sets neighbor's array component.
42 Worker 2 signals semaphore 2.
43 Worker 2 terminates.
44 Worker 1 sets neighbor's array component.
45 Worker 1 signals semaphore 1.
46 Worker 1 terminates.
47 Main thread reads 1 from position 1.
48 Main thread waits on semaphore 2.
49 Main thread reads 1 from position 2.
50 Main thread waits on semaphore 3.
51 Main thread reads 1 from position 3.
52 Main thread waits on semaphore 4.
53 Main thread reads 1 from position 4.
54 Main thread waits on semaphore 5.
55 Main thread reads 1 from position 5.
56 Main thread waits on semaphore 6.
57 Main thread reads 1 from position 6.
58 Main thread waits on semaphore 7.
59 Main thread reads 1 from position 7.
60 Main thread waits on semaphore 8.
61 Main thread reads 2 from position 8.
62 Sum = 9
63 System terminates normally.
　

Here it comes...

On Sat, 31 Jan 2004, Hotmail wrote:

> hi,
>
> I hope you can help me to solve this puzzle in programming assignment1.
> 1. I think when a thread is interrupted by "yield", it should be put back on
> the ready queue and the next thread who is in head of ready queue will be
> executed, right?

Under Java 1.2.1 scheduling, yes.

> 2. I only observed this for the first "interrupt" and all other interruption
> doesn't follow this.
> ---a) I changed the "Deamon" array to be {0, 4, 4, 4, 6, 4, 6, 4, 6}; so
> that worker 8, 6, 4 will be interrupted.
> ---b) I add one output inside Daemon's interrupt function to help reading:
>      public synchronized void interrupt (int tid) {
>     if ( d[tid] > 4 )
>     {
>       System.out.println("worker "+tid+ " is interrupted.");
>       Thread.yield ();
>     }
> 3) Please see following result:
> ---a) Worker 8 is interrupted and worker 7 is invoked to execute. This is
> ok.
> ---b) Worker 6 is interrupted and instead worker 5 is invoked, worker 6
> continues to "set neighbour's array!!!!
> ---c) Worker 4 is interrupted and instead worker 3 is invoked, worker 4
> continues to "set neighbour's array!!!!

Okay, I now understand your question and I do have the answer.

The behaviour you are observing in your output below is caused by a subtle
mistake in the original coding of the Daemon:

>      public synchronized void interrupt (int tid) {
              ^^^^^^^^^^^^
>     if ( d[tid] > 4 )
>     {
>       System.out.println("worker "+tid+ " is interrupted.");
>       Thread.yield ();
>     }

By making the interrupt() method synchronized makes it atomic, as we have
learned. Thus, when the worker 8 in your example yields() inside of
interrupt(), it does *not* actually complete interrupt() call yet, until
the Thread.yield() returns. This means, Worker 6 and 4 in your example
will have to wait, even before entering the method, until 8 is done. Not
only that, all the others won't enter it to evaluate if ( d[tid] > 4 ).
Therefore, when 8 is done, the next thread calls this synchronized method
exclusively, and releases it afterwards. So, when it is the turn for
worker 6 to atomically enter interrup(), then yeild(), it has to come back
and finish the interrupt() method since others are waiting for 6 to be
done with it. The same happens with the worker 4.

To get the intended behaviour, comment out 'sychnronized' from
interrupt():

class Daemon {                       // you are the daemon by what you put
                                     // as the initial values of 'd'
private static int d[] = new int[] {0, 4, 4, 4, 6, 4, 6, 4, 6};

public /*synchronized*/ void interrupt (int tid) {
    if ( d[tid] > 4 )
    {
      System.out.println("worker "+tid+ " is interrupted.");
      Thread.yield ();
    }
}
}

and then you would get what you are expecting to get:

alpha.mokhov [sam] % javac Future.java
alpha.mokhov [sam] % java Future
Eight workers have started.
Main thread continues work.
Worker 8 begins execution.
Worker 7 begins execution.
Worker 6 begins execution.
Worker 5 begins execution.
Worker 4 begins execution.
Worker 3 begins execution.
Worker 2 begins execution.
Worker 1 begins execution.
Worker 8 doubles his own array component.
worker 8 is interrupted.
Worker 7 doubles his own array component.
Worker 7 sets neighbor's array component.
Worker 7 terminates.
Worker 6 doubles his own array component.
worker 6 is interrupted.
Worker 5 doubles his own array component.
Worker 5 sets neighbor's array component.
Worker 5 terminates.
Worker 4 doubles his own array component.
worker 4 is interrupted.
Worker 3 doubles his own array component.
Worker 3 sets neighbor's array component.
Worker 3 terminates.
Worker 2 doubles his own array component.
Worker 2 sets neighbor's array component.
Worker 2 terminates.
Worker 1 doubles his own array component.
Worker 1 sets neighbor's array component.
Worker 1 terminates.
Worker 8 sets neighbor's array component.
Worker 8 terminates.
Worker 6 sets neighbor's array component.
Worker 6 terminates.
Worker 4 sets neighbor's array component.
Worker 4 terminates.
Main thread reads 2 from position 1.
Main thread reads 2 from position 2.
Main thread reads 1 from position 3.
Main thread reads 2 from position 4.
Main thread reads 1 from position 5.
Main thread reads 2 from position 6.
Main thread reads 1 from position 7.
Main thread reads 2 from position 8.
Sum = 13
System terminates normally.

It is okay for this method to be not-synchronized: it has to be so, and
it's a read-only thing.

　

Here it goes...

Wonderful!!!

Hi,

A wonderful explanation! And I am totally convinced! Thank you so much for
this perfect explanation! ...

Have a nice day,
B.rgds,

Nick Huang/Qingzhe Huang
　

Here it goes...

Hi Professor,

I wrote a parsing tool which read in the grammar and automatically store them, removing left recursion, remove common left factor and now I am at the point of establishing NT-table automatically. It is now I realized that I am in trouble to build table-driven parser automatically by program. Because the scanner is written previously by hand. The type of tokens, or enumeric value of all terminals are set by me by hand, I have no way to ask my parser to map the terminals in grammar with returning types of scanner!

I hope you can understand what I am talking about:

I enumerate all terminals in scanner to a series of integers. And the function of scanner returns these enum values of token. However, my parser is writen by me as a general "grammar-reader" which will read-in both variables and terminals and stores them in an array with sequence of their appeareance in grammar. So, my parser will have no idea of what token scanner reads in.

I know it is not a common problem for others, however, I did spend more than one week to write this grammar-reader in hope to establish table-driven parser, Now I just don't want to give up. I think "Yacc", "lex" must also have this kind of problem, don't they?

Can you give me some clue of solution?

Thank you and

b.rgds,

Nick Huang/Qingzhe Huang

Here it comes...

What should be done is to express the grammar rules in terms of the token
values. The grammar can be preceded by the enumerated typy listing the
token valeus as supplied by the scanner. That's how it is done in some systems.
--
J. Opatrny
　

Here it goes...

Hi professor,

Thank you very much for your advice and it seems to be the only way.
By the way, my program found one conflict of grammar for the following:
S -> L := E ; | i ( Lp ) ;
Because of
L -> i Ar

Do you see the two rules of S makes First(S) both contains "i" and this
destroys the LL(1) grammar. Am I right?

Thank you for your attention,

Nick Huang/Qingzhe Huang
　

Here it comes...

The problem you mention with the grammar can be fixed with
factorization!
--
J. Opatrny
　

Here it goes...

Hi professor,

Sorry for stupid question. I understand it is common-left-factor problem.
The reason I didn't realized it is because I have already written
alogorithms to remove both common-left-factor and left-recursion. Though I
am confident about my program, however I didn't realize that EVEN the
indirect left-recursion can be removed by algorithms in textbook p159
(Figure4.3 Algorithm fro general left recursion removal) STILL
INDIRECR-COMMON-LEFT-FACTOR cann't be revealed by this algorithm.
You see:
S -> L := E ; | i ( Lp ) ;
L -> i Ar

Suppose L has a higher index value than S, then L won't be replaced by "i
Ar", therefore my function cannot find out this INDIRCT COMMON-LEFT-FACTOR
unless I FORCE index of L to be LOWER than S. Then it becomes something like
this after REMOVAL-LEFT-RECURSION:
S -> i Ar := E ; | i ( Lp ) ;

Then my method of removal common-left-factor can work. And it WORKS NOW.

Thank you so much for your advise,

Nick Huang/Qingzhe Huang

Here it goes...

Re: How can interrupt be disabled and context switch still be possible to happen?

Hi,

Referring to question 4-b of assignment2, suppose process P blocks on semaphore "delay", then how can P be made later "unblocked" by
other process since "all interrupts are disabled" by instruction "disable-interrupts"? It seems to me a definite dead lock, right?
So, the only possible, logical, reasonable solution is to have an "enable-interrupts" at very beginning of "wait" function.
Otherwise, context switch will never happen if procedure P is blocked after "disable-interrupts". Therefore, logically when
procedure P resumes later, it will definitely find that "interrupt" is "enabled", otherwise he cannot allow other process to run to
"unblock" him by setting "semaphore delay".

Hope you can confirm this, and many thanks.
Nick Huang/Qingzhe Huang
　

Here it comes...

Hi,

This has been mentioned in the tutorial. There is *no* deadlock there at all
and the solution is perfect for a uniprocessor system. You are missing important
point: the fact that the interrupts are disabled or enabled is part of each
process' context and is stored in th IR regiester. For simplistic example,
if bit 5 of that register is 1, the IRQ5 is enabled. I'm process A, I have my
copy of IR, you are process B, you have your own copy of IR.

When A is running P(), which is an OS procedure (hence supervisor mode),
and is about to block on wait(), simply wait() "calls" the context switch routine,
say ctsw(), and does some other stuff, like sem. queue management, etc. So, there is no
problem here. The OS (ctsw()) stores IR along with its context and loads the new values
from the context of B. At no reason, wait() should enable interrupts within.

When B makes 'delay' available and it is time to run A, A's context is restored, along
with IR (hence interrupts are disabled) and wait() now lets it through.

There is no mutual exclusion violation here as well -- two P()'s or two
V()'s cannot run concurrenly and P() only gives up control in a single
point at specific even, when it must do so.

hth,
-s
　

Here it goes...

I am almost convinced

hi,

Thanks a lot for your clear explanation. I am almost convinced except that I
always have an impression that "context switch" can only happen by
interrupt. Or in other words, I imagine that context switch is like an
"interrupt-handler" or
"interrupt-service-routine". It never hit on my mind that this kind of
high-priority "interrupt-handler" can be invoked by
any process. You see, in an pre-emptive system, context-switch should be
typically happen at each end of time slice. It is very reasonable that it is
invoked by the "timer interrupt" or whatever. And this context-switch
interrupt, I guess, should have the highest priority. Am I right?
So, my question is just that is it possible for a process to invoke an
interrupt handler like "context-switch"?

Thank you so much.

Nick Huang/Qingzhe Huang
　

Here it comes...

On Sun, 29 Feb 2004, hotmail wrote:

> hi,
>
> Thanks a lot for your clear explanation. I am almost convinced except
> that I always have an impression that "context switch" can only happen
> by interrupt.

That's a wrong impression. Any blocking system call (e.g. in I/O - read())
would cause a context switch. Otherwise, why would we invent
multiprogramming when there were no interupts?

> Or in other words, I imagine that context switch is like an
> "interrupt-handler" or
> "interrupt-service-routine". It never hit on my mind that this kind of
> high-priority "interrupt-handler" can be invoked by
> any process.

Any OS process. P(), V(), wait(), etc. are provided by the OS and the OS
may choose whatever implementation they want.

> You see, in an pre-emptive system, context-switch should be
> typically happen at each end of time slice.

Not necessarily (between app processes). Every timer interrupt the
scheduler is run that may (and yes, typically, does) context switching and
ready and others queues management.

> It is very reasonable that it is invoked by the "timer interrupt" or
> whatever. And this context-switch interrupt, I guess, should have the
> highest priority. Am I right?

Timer interrupt is the 2nd highest after power failure interrupt and is
unmaskable. Yet, you may terminate or request for I/O before your time
slice expires, hence - a context switch.

> So, my question is just that is it possible for a process to invoke an
> interrupt handler like "context-switch"?

An OS code can theoretically call any other part of the OS code.
　

Here it comes...

> hi nick,
> i just got home its around 3 right now. I tried to msg you on msn but i think your status is on away. Anyway just wanted to ask you if i can call you later about some questions.
>
>
> Question: "Consider three concurent processes", from the assignment, does this mean that the processes may run at the same time, but not necessarily start at the same time? Can two processes start EXACTLY at the same time?
>
>
> Question: does one processes start another process, like if process A comes to the instructions signal(goB), does it actually start process B or only change the value for goB from 0 to 1.
>
>
> Question: I think in his notes the teacher defines "wait" as decrementing and "signal" as incrementing. Do the values inside wait and signal always have to 0 and 1, 0 for blocked and 1 for go?
>

Here it goes...

Hi,

I am happy that you are seriously considering the questions!

1. On uniprocessor computer, there is only exactly one process running at any moment, because there is only processor. However, by context switch, one processor can run many processes "concurrently" at each interval. So, to start three "concurrent" processes, it really means the three processes run at "alternative" (if you imagine there is no other processes in O.S. which is impossible, but it helps your imaginations.:) ) intervals. Therefore you can see it is impossible to start two processes at exactly same time.

If you are careful enough to see our Programming assignment1, you will see that we "create" threads one by one. and then "start" them one by one by calling the thread's "start" method. Still the threads will "start" at differently intervals. But we consider them to be "concurrently" because they are in a very fast context-switching-mode which looks like "concurrent".

2. The signal or semaphore in essential is only a integer or a bit which has some special meaning to some processes. It does not have the ability to create a thread or process. It only indicating those who want to see his value that some states have been changed. That's all. So, "signal" only changes the "goB" from 0 to 1.

3. Your question is a very good question. If you look carefully at the pseudocode of "wait" you will see that the value can never go below 0. see below:

wait()

{

while (value<=0) //if it is 0 at beginning, it will stay here forever.

{ ; //do nothing

}

value--; //it comes here only if value IS NOT 0, or value==1

//value becomes 0 again

}

signal()

{

value++;//it has no upper limits

}

So, this kind of "wait" will only keep "value" as non-negative.

However, "signal" function can increment "value" without limit. So, for this kind of "wait" and "signal", the possible value of "value" are any non-negative.

4. Furthre to question 3, you must keep in mind that the pseudocode of teacher's version is only one solution to semaphore. In fact you can find in industry they use many different semaphores with similar functionalities. Suppose you restrict the "value" in both "wait" and "signal", you will always get 0 or 1 for "value". This makes you feel "value" is like a boolean. So, it is called "binary semaphore".

However, there is another kind of semaphore like following:

wait()

{

value--;

while (value<0)

{ ; //do nothing and wait here

}

signal()

{

value++;

}

This semaphore has the ability to record how many times "wait" function has been called. You see the absolution of "value" is equal to how many times the "wait" has been called. Therefore, it is called "counting" semaphore which "counts" how many process has been waiting for the "semaphore". This is only to demonstrate you some usage of semaphore, don't go into too deep unless you understand the basic semaphore.

If you have any question or are not clear about what I said, just call me.

have a nice day,

Nick Huang/Qingzhe Huang

The professor is ... on programming

The professor is ... on programming and do you think what he is thinking is always reasonable? Sometimes the word puzzle given by him seems to be extremely unexplainable to me.

I don't bother to guess everything as long as my program works.

Sure I will go to class on Wednesday,it is the only way to learn something from other teacher.

see you,

Nick Huang/Qingzhe Huang

public class Cyclic {
  static int P         = 8;                         // number of workers
  static int logP      = 3;
  static int Pplus1    = 9;                         // 0-indexed array
  static int logPplus1 = 4;                         // lengths

  static Daemon        daemon = new Daemon ();
  static Semaphore[][]  future = new Semaphore[logP][P];
  static int[][]        a      = new int[logP][P];
  static int col;
  //static ...

  public static void main (String[] args) {

    Worker w[] = new Worker[P];

    for (int k=0; k<logP; k++)
    {
	future[k]=new Semaphore[P];

	//for( int j=0; j<e.length; j++ )
	for (int j=0; j<P; j++)
      	{
	    future[k][j]  = new Semaphore(0);
       	}
    }

    for( int j=0; j<P; j++ ) {
      //test
	//System.out.println("test signal here");
	future[0][3].Signal();
	
	col = daemon.column (j);
      w[col] = new Worker (col);
      w[col].start ();
    }

    for( int j=0; j<P; j++ ) {                      // wait for workers
      try { w[j].join (); }                         // to terminate
      catch (InterruptedException exc) { };
    }
    for( int j=1; j<Pplus1; j++ )
      System.out.println ("Sum " + j + " = "+ a[logP-1][j-1]);
    System.out.println ("System terminates normally.");
  }
}

class Daemon {
  private static int[] w = new int[] {3, 6, 5, 7, 4, 2, 1, 0};
  private static int[] d = new int[] {0, 7, 4, 5, 4, 4, 9, 4, 1};

  public int column (int j) {
    return w[j];
  }

  public void interrupt (int j) {
    if ( d[j] > 4 )
      Thread.yield ();
  }
}

class Semaphore {
  private int value;
  Semaphore (int value1) {
    value = value1;
  }

  public synchronized void Wait () {
    while( value <= 0 ) {
      try { wait (); }
      catch (InterruptedException e) { };
    }
    value--;
  }

  public synchronized void Signal () {
    ++value;
    notify ();
  }
}

class Worker extends Thread {
  private int j;
  private int sum;
  private int hop = 1;
  Worker (int col) {
    sum = col+1;
    j  = col;
  }

  public void run () {
    System.out.println ("Worker " + (j) + " begins execution.");
    yield ();
    for (int level=0; level<Cyclic.logP; level++) {
     // if (j <= (Cyclic.P-hop))
      {
        System.out.println ("Worker " + j + " defines a[" + (level) + ","
                           + j +"].");
        Cyclic.a[level][j] = sum;
	//System.out.println("a["+level+"]["+j+"]="+Cyclic.a[level][j]);
	//System.out.println("exactly here before signal "+j);
	Cyclic.future[level][j].Signal();
	//System.out.println("exactly after signal of "+j);

	// ...
      }
      if (j >= hop)
	{
	     //   ...
	//test
	//System.out.println("before wait of "+j);

	Cyclic.future[level][j-hop].Wait();
	    	
        System.out.println ("Worker " + j + " uses    a[" + (level) + ","
                           + (j-hop) +"].");
        sum += Cyclic.a[level][j-hop];
	System.out.println("worker "+(j)+" has sum of "+ sum);
      }
	//test	
	//System.out.println("before interrupt");

      Cyclic.daemon.interrupt (j);
	//test
	//System.out.println("after interrupt");
	
      hop = 2*hop;
    }
    Cyclic.a[Cyclic.logP-1][j]=sum;
    System.out.println("Worker " + j + " terminates.");
  }
}

The following is the running result:

[qingz_hu@alpha PA2] % java Cyclic
Worker 3 begins execution.
Worker 6 begins execution.
Worker 5 begins execution.
Worker 7 begins execution.
Worker 4 begins execution.
Worker 2 begins execution.
Worker 1 begins execution.
Worker 0 begins execution.
Worker 3 defines a[0,3].
Worker 6 defines a[0,6].
Worker 5 defines a[0,5].
Worker 7 defines a[0,7].
Worker 7 uses a[0,6].
worker 7 has sum of 15
Worker 7 defines a[1,7].
Worker 4 defines a[0,4].
Worker 4 uses a[0,3].
worker 4 has sum of 9
Worker 4 defines a[1,4].
Worker 2 defines a[0,2].
Worker 1 defines a[0,1].
Worker 0 defines a[0,0].
Worker 0 defines a[1,0].
Worker 0 defines a[2,0].
Worker 0 terminates.
Worker 6 uses a[0,5].
worker 6 has sum of 13
Worker 5 uses a[0,4].
worker 5 has sum of 11
Worker 5 defines a[1,5].
Worker 3 uses a[0,2].
worker 3 has sum of 7
Worker 2 uses a[0,1].
worker 2 has sum of 5
Worker 2 defines a[1,2].
Worker 2 uses a[1,0].
worker 2 has sum of 6
Worker 2 defines a[2,2].
Worker 2 terminates.
Worker 1 uses a[0,0].
worker 1 has sum of 3
Worker 6 defines a[1,6].
Worker 6 uses a[1,4].
worker 6 has sum of 22
Worker 7 uses a[1,5].
worker 7 has sum of 26
Worker 7 defines a[2,7].
Worker 3 defines a[1,3].
Worker 4 uses a[1,2].
worker 4 has sum of 14
Worker 4 defines a[2,4].
Worker 4 uses a[2,0].
worker 4 has sum of 15
Worker 4 terminates.
Worker 1 defines a[1,1].
Worker 6 defines a[2,6].
Worker 6 uses a[2,2].
worker 6 has sum of 28
Worker 5 uses a[1,3].
worker 5 has sum of 18
Worker 5 defines a[2,5].
Worker 3 uses a[1,1].
worker 3 has sum of 10
Worker 1 defines a[2,1].
Worker 6 terminates.
Worker 3 defines a[2,3].
Worker 5 uses a[2,1].
worker 5 has sum of 21
Worker 5 terminates.
Worker 1 terminates.
Worker 7 uses a[2,3].
worker 7 has sum of 36
Worker 7 terminates.
Worker 3 terminates.
Sum 1 = 1
Sum 2 = 3
Sum 3 = 6
Sum 4 = 10
Sum 5 = 15
Sum 6 = 21
Sum 7 = 28
Sum 8 = 36
System terminates normally.

Is algorithms in PA2 more efficient than that in PA1?

Hi,
 
Maybe I am still not quite clear about the algorithms of programming assignment2 because I am still not sure about if
the way PA2 is better than what we did in PA1. See below, is it correct about PA2? That is each column will calculate
its "sum" with "previous-hop-column"  (sum+=a[level][j-hop]). You can see the total sum operation is FIVE.
 

           col0       col1              col2                     col3
level 0     a0         a1                  a2                      a3
level 1     a0       a01=a0+a1           a12=a1+a2            a23=a2+a3  
level 2     a0       a01                a012=a0+a12           a0123=a01+a23
 

And please see the following which is the PA1 model which only requires THREE sum operations. I agree that in multi-
processor-situation PA2 has some advantages such that each thread don't have to wait each other at each LEVEL. But the
total number of sum operation is also a factor when considering the efficiency of algorithms.  
 

             col0       col1                 col2                    col3
level 0     a0         a1                  a2                       a3
level 1     a0       a01=a0+a1       a2                       a3  
level 2     a0       a01            a012=a01+a2             a3
level 3     a0       a01                a012                      a0123=a012+a3
 
I have no idea of parallel computation, so what I am thinking maybe garbage, however, if you can justify for me I would 
be grateful:
 
PA2 has total LEVEL of computations of Log(N) where N stands for number of column or threads. But the total sum operation
is: 
Assume N=2^k    (2^k means 2 to the power of k)
 
Sum(N) = (N-2^0) + (N-2^1) + (N- 2^2) ...+ (N- 2^(k-1))==N*k - ( 2^k - 1 )
 
In case of N=8, Sum(8) = 8*3 - (2^3 - 1)=17
 
PA1 has total LEVEL of computation of N-1 and the total sum operation is N-1.
 
So, the time complexity of PA2 is O(N*Log(N)), while PA1 is always  O(N-1) or O(N). 
 
I am not sure which algorithm is better under multi-processor-situation, but it seems to me that in PA2 still some column
need to wait previous-hop-column to be finished first. Therefore, the benifit of PA2 is even less.
 
Thank you for your time,
 
Nick Huang/Qingzhe Huang

Here it comes...

> Hi Huang,
>
> Consider that you are running this algorithm on a parallel computer
> where all instructions are executing in synchronous manner (there is
> a model for such parallel computers and it is called PRAM model).
> The given algorithm can run in O(lg(n)) time, where you algorithm
> needs a time of O(n).So the given algorithm takes less time than the
> second one. In fact, the secone one is equivalent to the sequential
> algorithm. This is a very important factor, if buying processor is
> inexpensive than buying time.
>
> Given, I am not very good at math, the number of additions in the
> first algorithm is O(nlg(n)) and for the second one is O(n). If my
> calculation is correct, the first algorithm is not a 'cost optimal'
> parallel algorithm. But as I mentioned, sometimes 'time' costs more
> money.
>
> I hope you got the point.
>
> Good luck,
> Akon.
　

Here it goes...

Hi Akon,

Thank you so much for your prompt reply!

I fully understand your point. Indeed when the given algorithm can "truly synchronously" run on N processors, the

original O(N*Log(N)) can be reduced to O(Log(N)) by N processors' execution at same time. However, what I concern is

that the situation is not really "concurrent" for N processors. You see still that a thread or a processor need to wait for a

previous-hop-thread to finish first. ( sum += a[level][j-hop]. ) That is for some time, some of N processors might still have to

wait some other processors to finish first. And this situation becomes similar to my FIRST algorithm to some extent in which

every j-indexed thread need to wait (j-1)-indexed thread to finish first. So, if taking this factor into consideration, can the second

algorithm still efficient? My intuition tells me yes, and I am just not sure.

Thank you again for your time,

Nick Huang/Qingzhe Huang

Assignment 3

Name: Qingzhe Huang ID: 5037735

COMP 346 Assignment 3 Winter 2004

Issued: Week of March 15 Due: Week of March 29

All questions have equal weight.

Answer: Assuming the paged memory access means that we fetch a data or an instruction from main memory.

a) Though the page table is permanently in main memory, the frame pointed by page table entry may not be in memory. That is the frame may be swapped out to second store. Suppose this is not the case, a memory access includes memory access to page table to fetch the entry in page table, then second memory access would fetch the data. The total time is 2x200ns.

If the frame is not in main memory then a page fault will happen and all that page fault penalty have to be added into total access time.

As for the question “acceptable”, I think it is not acceptable because usually a CPU execution cycle is much less than memory access time, maybe only a few ns which is much less than 200ns. Every instruction cycle, CPU needs fetch instruction which involves two memory access, then operand fetch which involves another two memory access and maybe operand store so on. So, for most of instruction cycle, CPU are always waiting for memory access. This is of course not acceptable.

b) Assume TLB fault is essentially a TLB miss. The difference of TLB fault between page fault is that TLB fault is very fast. Because TLB is close to CPU and implemented with hardware so that it is not like page fault which is essentially a software interrupt. TLB fault happens when the target is not found in TLB, it is purely a miss. However, page fault happens only after a TLB fault because TLB is always searched first. It happens when target frame is not stored in main memory. Therefore a software interrupt or trap is generated to request O.S. to swap in requested frame from second store.

It is possible to have 0 fault. That is the target address is found in TLB.

It is possible to have 1 fault. That is the target is not found in TLB and TLB fault is generated. Then system continues to search in page table and find the target frame address.

It is possible to have 2 faults. That is when TLB fault happens, and searching in page table also results in a page fault, that is the target frame is not in main memory.

c) when n=512: (Assume that target frame is always in main memory. So no swapping needed.)

Effective memory access time= 200(0.95 * (1-512/2560)) + (200*2)*(1- 0.95 * (1-512/2560))

=152 + 96 = 248

when n=1024

EAT = 200*(0.95*(1-1024/2560)) + (200*2)*(1-0.95*(1-1024/2560))=114+172=286

Answer: In order to share the segment between two processes, the segment table of two process should each have one entry in its segment table to point to same physical memory address. For example, process p1 has a segment table entry i pointing to physical address x and p2 in its each segment table entry j pointing to physical address x. Therefore both processes share the segment.

If the shared segment has code referring to address in that segment, usually the both processes should have the same name for that shared segment. Because the shared code would be executed both in two share processes and shared code is referring to that particular segment. Of course the “particular reference of segment” would become part of code of each process. This means in each process the segment name is referring some segment in that process. For example, the share code is referring name of that shared segment as “sharedSeg” then in both process “sharedSeg” is referring to that shared segment. It is for sure that the name “sharedSeg” must appear in both segment table of two process.

However, this assumption is that the reference of address is in “direct addressing mode”. If the reference is done by “indirect addressing mode”, say the offset from the beginning of that segment, then the name of shared segment would not be necessarily same.

Usually the shared segment has a similar purpose in two processes, so naturally the protection status should be same. But it is not necessarily same. For example, the segment shared is purely data and one process want to write in it whereas another process simply wants to read it. In this case the protection status is different from two processes.

Answer:

LRU with 3 frame: the page fault number is 15

1	1	1	4	4	4	5	5	5	1	1	1	7	7	7	2	2	2	2	2
	2	2	2	2	2	2	6	6	6	6	3	3	3	3	3	3	3	3	3
		3	3	3	1	1	1	2	2	2	2	2	6	6	6	1	1	1	6

LRU with 4 frames: the number of page fault is 11

1	1	1	1	1	1	5	5	5	5	5	3	3	3	3	3	3	3	3	3
	2	2	2	2	2	2	6	6	6	6	6	7	7	7	7	1	1	1	1
		3	3	3	3	3	3	2	2	2	2	2	2	2	2	2	2	2	2
			4	4	4	4	4	4	1	1	1	1	6	6	6	6	6	6	6

LRU with 5 frames: 9 page faults

1	1	1	1	1	1	1	6	6	6	6	6	6	6	6	6	6	6	6	6
	2	2	2	2	2

1	1	1	1	1	1	5	5	5	5	5	3	3	3	3	3	3	3	3	3
	2	2	2	2	2	2	6	6	6	6	6	7	7	7	7	1	1	1	1
		3	3	3	3	3	3	2	2	2	2	2	2	2	2	2	2	2	2
			4	4	4	4	4	4	1	1	1	1	6	6	6	6	6	6	6

1	1	1	1	1	1	5	5	5	5	5	3	3	3	3	3	3	3	3	3
	2	2	2	2	2	2	6	6	6	6	6	7	7	7	7	1	1	1	1
		3	3	3	3	3	3	2	2	2	2	2	2	2	2	2	2	2	2
			4	4	4	4	4	4	1	1	1	1	6	6	6	6	6	6	6

1	1	1	1	1	1	5	5	5	5	5	3	3	3	3	3	3	3	3	3
	2	2	2	2	2	2	6	6	6	6	6	7	7	7	7	1	1	1	1
		3	3	3	3	3	3	2	2	2	2	2	2	2	2	2	2	2	2
			4	4	4	4	4	4	1	1	1	1	6	6	6	6	6	6	6