数理解析研究所講究録
第 586 巻 1986 年 134-152

134

On the concurrency
anda yet another standard form of concurrent programsofSmalltalk-80 \dag er

Norihisa Doi
土居範久

Institute of Information Science, Keio University
Kiyoshi Segawa
瀬川清Jobu College of Commerce
Abstract
In this paper, the concurrency of Smalltalk-80 is clarified by examining the execution results of the several programs, and a standard form of concurrent programs is presented
by using the classical concurrent problems in Smalltalk-80. A scheme to enrich the concurrency in Smalltalk-80 is also proposed.
0. Introduction
In this paper, the concurrency of Smalltalk-80 is clarified by examining the execution results of several
concurrent programs, not by looking into the Smalltalk-80 system itself (as physicians do, not as surgeonsdo). Then, using the classical concurrent problems, such as Producer Consumer Problem and Readers andWriter’s Problem, a standard form of concurrent programs of Smalltalk-80 is presented. Finally, the scheme
to enrich the concurrency in Smalltalk-80 is proposed.

1. class Process
In Smalltalk-80, a process is a sequence of actions described by expressions and performed by the Smalltalk-80
virtual machine. Each process is represented by an;nstance of class Process.
A process is created by sending the message fork. fo $rkAt:$ newProcess and newProcessWith; to a
block. The process created by fork or forkAt: is scheduled to be executed by the virtual machine (but it
is not always executed immediately), so such a process is called sched uled. On the other hand, the processcreated by newProcess or newProcessWith: is not scheduled to be executed and is called suspended. A
suspended process scheduled by sending the message resum to it.

.

$i\epsilon$$e$Example 1.1[actionA]

$f$

ork.

act ionB.

In this example, actionA and actionB are executed concurrently.

.

Example 1.2$processarrow$ [actionA]

newProcess.

actionB.

process resume.
actionC.

In this example, actionB is executed alone, then actionA and actionC are executed concurrently.

.

The return value of [actionAlfork is the block [actionA] itself, not the created process. So if thecreated process is referred to later, the process must be created by newProcess or newProcessWith: as inexample 1.2.
There is only one processor capable of carrying out the sequence of actions a process represented. Thatis, in spite of saying “be execu $tedconc$ urren $tly$ ,“ there is only one process actually being executed. The
process which is currently being executed is called active.
There exists only one instance of class ProcessorScheduler globally named Processor. Processor
selects the active process among the scheduled processes. Moreover, there are some messages for Processor
to inquire about or change the state of the system. For example, the priority of the active process is returned\dag er Smalltalk-80 is a trademark of Xerox Corporation1

135
by sending activePriority to Processor and the active process is terminated by sending terminateActive
to Processor.
To select the active process, Processor uses a FCFS(First-Come, First-Serve) ready queue with priorities. More strictly speaking, it adopts the multi-queue scheduling algorithm which uses a FCFS ready queue
for each priority. The process waiting for the processor longest becomes active first among the processes withthe same priority, and the processes with the highest priority become active before the processes with lower
priorities. Once a process becomes active, it will be active continuously unless it relinquishes the processor byitself or a process with the higher priority is scheduled (The processor will never be assigned to processes ina time-slicing manner). When a process whose priority is higher than that of the active process is scheduled,
the new scheduled process preempts the processor. The situation, however, is slightly different if the priorityof the scheduled but not ac ive process is changed by the message $pr$ iority:. In example 1.1, actionBis executed before actionA and in example 1.2 the execution order is “actionB,actionC and actionA,“
unless each process relinquishes the processor by itself.
A process created by fork, newProcess or newProcessWith: receives the same priority as the processthat creates it. On the other hand, a process created by forkAt: level receives the priority level. By
sending priority: level to the process, its priority becomes leve1.
$t$

Example 1.3[actionA] forkAt: levell.

actionB.

Assume that the above program is executed in the process with priority leve12. If
leve12,levellactionA is executed before actio $nB$ , and if
leve12,levellactionB is executed before actionA.
$>$$\leq$.

There are a fixed number of priority levels numbered by ascending integers. Ordinarily, user processes
are executed at priority 4. Even if a process whose priority is less than 4 is created in a user process, it
is uncertain when the process will be executed (The process created in the user process might be executed
after the user process terminates, but it is not correct).
If Processor receives the message yield, Processor suspends the active process and places it at theend of the ready list pertaining to its priority (There are as many lists as priority levels). Then the firstprocess $on$ that list becomes active. If there are no other processes $on$ that list, the process just suspended
becomes active again, so yield has no effect in such a case. Sending yield to Processor is one of themethods for relinquishing the processor.
If the blo $ck$ representing the process has arguments, the message newProcessWith: must be used tocreate the process. The argument of this message must be an instance of Array and the elements of it are
given to the block arguments.

2136
2. class Semaphore
A semaphore is used as a synchronization primitive in Smalltalk-80. An in stance of a semaphore is createdby sending the message new to class Semaphore, and the value of the created semaphore is . A semaphoreis also created by the message forMutualExclusion instead of new, and its initial value is 1.
Sending the message wait to an instance of Semaphore corresponds to a P-operation, and sending
signal corresponds to a V-operation. A semaphore in Smalltalk-80 is a counting semaphore whose value
is a non-negative integer. So, if several signal exceed wait, the semaphore remembers the number of the$0$

excess signal.
A semaphore queue in Smalltalk-80 is a FIFO queue, so the processes suspended in the queue will beresumed in the same order in which they were suspended independently of the priority. If the priority of theprocess resumed by signaI is higher than that of the process which sends signal, the resumed process will
become active.
In Smalltalk-80, there are two special messages for the mutual exclusion. For an instance creation, themessage fo MutualExclusion is prepared. By this message, as stated before, semaphore whose valu is
1 is created. To execute a block, aBlock, mutual exclusively, the message critical: aBlock is sent to thesemaphore. This message is implemented as follows:
$r$

$a$

$e$

critical: aBlockvalue
self wait.
value
aBlock value.
self signal.
$|$

$|$

$arrow$$\uparrow value$

3. class Delay
In Smalltalk-80, semaphores are used to handle hardware interrupts. Each process handling a hardwareinterrupt sends wait to the appropriate semaphore and suspends itself. When an interrupt occurs, theSmalltalk-80 virtual machine detects it and sends signal to the appropriate semaphore to resume theinterrupt handling process. The Smalltalk-80 virtual machine detects the following three conditions[Gol]:
1. user event: a key has been pressed on the keyboard, button has been pressed on the pointing device,or the pointing device as moved,
2. timeout: specific value of the millisecond clock has been reached, and3. low space: available object memory has fallen below certain limits.
$a$

$h$

$a$

A class Delay is prepared to handle the second condition. Using this class, the active process might besuspended for a specified amount of time. An instance of Delay is created by the following messages.
forMilliseconds: time
to suspend the active process for time milliseconds.
forSeconds: time –to suspend the active process for time seconds.
untilMillisecondg: time
to suspend the active process until the millisecond clock $re$ aches tim .
-

-

$e$

The active process is actually suspended when the message wait is sent to an instance of Delay. The
suspended process will be scheduled when the specified amount of time elapses.
The following two examples show how to suspend the active process for 1 second.
Example 3.1

sleepingTime
sleepingTime $arrow Delay$ forSeconds: 1.
sleepingTime wait..
$|$

$|$

Example 3.2(Delay forSeconds: 1) wait..

3

137
4. State transition of a process

The following is a state transition diagram of a process.

5. Carrying out concurrent processes

4138
5.1 Selection of the active process

As stated before, a preemptive, priori $ty$ based FCFS ready queue is used to select the active process among
the scheduled processes in Smalltalk-80. In principle, the active process can be continuously executed to its
end. If we run the program:
1:
2:
3:
4:

[10 timesRepeat:[Transcript show: ‘forked $proce\epsilon s$ ;10 timesRepeat:[ $Tr$ anscript show: ‘main process;the child process created by fork
result of this program is as follows:$at$$cr$ ]

fork.

$cr$ ]

line 2 $wiU$ become active when the parent process terminates. So themain process
main process

main process
forked proc $ess$
forked $pr$ ocess

forked process

To execute two processes –parent and child
Processor yield must be used as follows:
1:
2:
3:
4:
5:
6:

–

concurrently, that is, to activate them alternately,[10 timesRepeat:[Transcript show: ‘forked process‘ ; $cr$ .
Processor yield]] fork.
10 timesRepeat:[Transcript show: ’main $pr$ ocess ‘ ; $cr$
Processor yield].

.

Each process relinquishes the processor at lines 3 and 6 in its own loop, so each process alternately executes
its own loop. The result of this program is as follows:main $pr$ ocess
forked process
main $pr$ ocess
forked process

main $pr$ ocess
forked process

Instead of Processor yield at lines 3 and 6, (Delay forSeconds: ) $wait$ can also be used. If theactive process wants to be suspended even for seconds, the context switching occurs and this process
becomes inactive. Thus, to exchange the active process, (Delay...)wait may be used(Note that, in somecases, it is better to use (Delay...)wait instead of Processor yield. See the section 7.1).
$0$

$0$

$s$

139
S.2 Changing priority
The priority of a process can be changed by sending the message priority: to it. This message, however,does not take effect immediately. The priority of the process will be changed to the specified level after theprocess becomes active.
1 :
2:
3:
4 :
5:
6:

7:
8 :
9:

procl proc2
procl[ $Tr$ anscript show:
$|$

$|$

$arrow$

$pr$

ocl

–

start ‘ ;Processor yield.
$Tr$ anscript show:‘procl -end“ ;

.

$cr$

$cr$ ]

newProcess.

$proc2arrow$[ $Tr$ anscript show:‘proc2– start ‘ ;Processor yield.
$Tr$ anscript show:’proc2-$e$nd ‘ ;

10:

procl resume.

11:
12:
13:
14:
15:
16:
17:

Transcript show: ‘main
1 ; $cr$proc2 $pr$ iority: 5.
Transcript show: ‘main
2 ‘ ; cr.
Processor yield.
Transcript show: ‘main $-3$ ; cr.
Processor yield.
Transcript show: ‘main -end‘ ; cr.

$cr$$cr$ ].

newP rocess.

proc2 resume.
-

‘

.

-

‘

The result is as follows:
main
main
procl

1
2

-

-

start

$arrow$

proc2
start
proc2 -end
main$arrow$$arrow 3$

procl
main

-

-

end
end

6

140
5.3 Implementation of mutual exclusion by semaphores
The following example shows how to implement a mutual exclusion by Semaphore.
1 :
2 :
3:

4:
5 :
6 :
7:
8 :
9 :
10:

sem procl proc2
sem\leftarrow Semaphore new.
procl $arrow[1to;20$ do:[ $:c1|$ sem wait.
cl $pr$ intString displayAt: $1000100$ .
sem signal]] newProcess.
proc2 $arrow[1to:20$ do:[: c2
sem wait.
c2 printString displayAt: $100Q150$ .
sem signal]] newProcess.

11:
12:
13:

proc2 resum
procl resume.
Processor yield.
em ignal.

$|$

$|$

$|$

$s$

$e$

.

$s$

This program alternately displays the numbers from 1 to 20 at the two points (coordinates $(100,100)$ andyield at line 12 activatesprocl, but the value of the semaphore em is , so procl is suspended at line 4. Then proc2 becomes active
and for the same reason becomes suspended at line 8. Now the main process which executes the whole
program becomes active again. Sem signal at line 13 is executed and procl is scheduled. At this point,
the main process terminates and procl becomes active. By line 5, 1 is displayed at the points $(100,100)$ andby line 6 proc2 is scheduled (Note that the value of $sem$ is ). Then, procl is suspended at line 4. In turn,proc2 becomes active. By line 9, 1 is displayed at the point $(100,150)$ and by line 10, procl is scheduled.
Then, proc2 is suspended at line 8. Procl becomes active again and so on.
Now, line 12 is assumed to be omitted. After the execution of line 13, procl becomes active. The
value of sem is 1, so procl sets it to and displays 1 on the display. By sem signal at line 6, the valueof sem becomes 1 because there are no processes in the semaphore queue(proc2 is waiting in the readyqueue). Procl can pass through sem wait at line 4 again and display 2. After procl has displayed thenumbers from 1 to 20, $pr$ oc2 becomes active. So if Processor yield is lacking, the numbers from 1 to 20
are displayed at point $(100,100)$ and then at point $(100,150)$ .
Two special messages for mutual exclusion are provided in Smalltalk-80. Using these messages, theabove program can be rewritten as foliows:$(100,150))$ on bit mapped display. The heart of this program is line 12. Proces $sor$
$s$

$0$

$0$

$0$

1 :
2:
3:
4 :
5 :
6 :

7:
8 :
9 :
$i0$ ;

11:$|$

sem procl proc2

$|$

sem
Semaphore forMutualExclusion.
procl $arrow[1$ to: 20 do:[: cl
sem critical: [cl printString displayAt: $1000100$ ]]] newProcess.
$arrow$$|$$proc2arrow[1to:20$ do:[: c2
sem critical: [c2 printString displayAt: $100Q150$ ]]] newProcess.
proc2 $res$ ume.
procl resume.
$|$

By these messages, the structure of the program is made clear. Procl, however, precedes proc2, because
there are no essential differences between this program and the former one without line 12. To activate procl
and proc2 alternately, Processor yield must be inserted after displaying the number as stated in 5.1 or
the following three lines must be added after line 11 to make this program functionally same as the first one.

12:
13:
14:

sem wait.
Processor yield.
$sem$ signal

7

141
6. Sharing resources among objects
In sequential programs or concurrent programs, there are two common standard ways to share resourcesamong objects:
1. using shared variables, and2. passing resources (which are also objects) to objects by messages.

6.1 Using shared variables
There are five kinds of variables in Smalltalk-80. They are distinguished by their scopes and lifetimes. Tbese
variables may be grouped in two categories, private (variables) and shared (variables).
A private variable can be accessed by only one object, and instance variables and temporary variables
are private variables. Instance variables are existed during the lifetime of the object which accesses themand temporary variabies are existed during the activation of one action(e.g. a message). Private variablenames must be begun by the lower alphabetical characters.
On the other hand, a shared variable can be accessed by more than one object. Shared variables may
be grouped, and each group is called as a pool. A pool can be named and the name of the pool is called asname of pool.
The following three variables are shared variables:
A class variable is shared among all instances of one class. Class variables are declared(1) class variablesin the class definitio . Each class has a special pool in which all class variables of it are kept.
(2) global variables –A global variable is shared among all instances of all classes. To use glob variables,
they must be added into the special pool named Smalltalk.
A pool variable is shared among the instances of more than one class. To use pool(3) pool variables
variables, the name of the pool must be declared in the class definition, the pool variables must be
added into the pool and the name of the pool must be added into the pool Smalltalk.
Shared variable ames must be begun by the uppercase alphabetical characters.
Moreover, in Smalltalk-80, the hierarchy among classes may be defined. The child process (subclass)inherits the variables and the methods of the parent class (superclass) in principle(If the superclass as themethod whose pattern is sam as the one of the superclass, the subclass uses the own method according to
the rewriting rule in Smalltalk-80. On the other hand, the subclass can not have the variable whose nameis same as the one of the superclass). So, the instances and whose classes have the same superclass canshare the variable , which is the class variable of the superclass(Note that the contents of the instance ofthe subclass are constructed of the subciass and all of its ancestor classes).
–

$n$

$a1$

–

$n$

$h$

$e$

$\alpha$$\beta$$\Sigma$

The instance variables of the superclass can not be shared between
each time when the instance of the subclasses are created.

8$\alpha$and$\beta$because they are created1$4\ulcorner d$

6.2 Passing the shared object by message

To accomplish the situation in which the object is $sl_{1}ared$$ob$
en the$eoJ^{ects}\alpha$betweenand , the followin way
can be used. At first, the object is created, thenwhen the objects a and are created, it is passed asargument inaninstance creation message. In
classes, which are the templates of and , theth shared
object isargument in the instance creation methods$theinstancesthep\alpha anh$and in the bodies ofare $dob$ .
accessed by sendmg messages to this argument.
$\Sigma$$\beta$$g$$\Sigma$$\beta$$t1_{1}e$$t1_{1}e$$\beta$$t1_{1}\epsilon$

$s$

$1S$

$oJec\downarrow$

By this way, the information about the shared object
is hidden automatically(Of course, the classes
whose lstances areandcan be defined only when it is known that the $objecty\Sigma$
is passedthargument).
$Z$$\dot{N}$$\alpha$$\beta$$b$

7. A yet another standard form of concurrent$y$programs$e$

In this cbapter, we consider the method in which
the relation between the shared
are resources and its users
is deled by the-subclass relationship. This method basically uses thesharedvariables ut, different
from the usual methods, it may be expected that thereadabdity of programs is increcrease ecause the sharedresource-users relationship is clarified. This method canberams anand conrurrent
programs, and here tbis method is used for the classical used for both sequential$roblmp$concurrent
process
processin$ng$ pro$ems$ . For each problem,
the Smalltalk-80 program is presented at first to clarify
the problem accordinng to $te$ procedural orientcd
programming. Then, the program is examined and thesolutionn accor in$ngo$
to the$eo$$ob$ject oriented programmingis presented.
$s$$\iota lass$$b$$r_{d^{la}b^{e8}’ u}$

$ro$

$r$

$h$

$d$

7.1 Producer Consumer Problem
process producer and a process con umer
ca through shared bounded
communicate$t^{o}dmun$
ducer sends data to buffer an consumer gets
buffer buffer. Proata from buffer. The following is
the solution based on
the procedural oriented programming concept.
$A$

$e$

$a$

$d$

and 10 as its data and that he size of buffer

Suppose that
aproducer sends arandom
number between 1
is$\epsilon^{pose}$

9

143
1:
2:
3:
4 :
5 :
6:
7:
8 :
9 :
10:

buffer bufferSize valueAvailable gpaceAvailable mutex
readPosition $writePosition$ producer consumer count value rand

$|$

$|$

$producerarrow$[ $[true]$ whileT rue:[(Delay forSeconds: and next $*10$ ) wait.
spaceAvailable wait.
mutex critical:[count(rand next $*10$ ) truncated $+1$
buffer at: writePosition put: count.
$r$$arrow$.

$writePositionarrow writePoBition\backslash \backslash buffer8ize+1$ ].

valueAvailable signal]] ne $wP$ rocess.

11:
12:
13:
14:
15:
16:
17:
18:
19:
20:

consumer

21:
22:
23:
24:
25:
26:
27:
28:
29:

bufferSize\leftarrow 5.
$bufferarrow Array$ new: bufferSize.
valueAvailable \leftarrow Semaphore new.
$spaceAvailablearrow 8emaphore$ new.

$arrow$[[true] whileTrue:[valueAvailable

wai

$t.$

.

mutex critical:[value $arrow buffer$ at: readPosition.

.

value $pr$ intString; $cr$
anscript show: ‘get
readP $ositionarrow readPosition\backslash \backslash bufferSlze+1$ ].
$Tr$spaceAvailable signal.
(Delay forSeconds: and next $*10$ ) wait]] newProcees.
$r$bufferSize timesRepeat: [spaceAvailable gignal].
mut $exarrow Semaphore$ forMutualExclusion.
$readPositionarrow writePositionarrow 1$.

new.
producer resum . consumer resume.
$randarrow Random$$e$

If tbere are no spaces buff er, producer will be suspended in the $semap1_{1}ore$ queue of spac eAvailable,
and if buff er is empty, consumer will be suspended in the semaphore queue of valueAvailable. Semaphore
mutex is used to accomplish mutually exclusive execution of the critical sectio $ns$ , but in these sections two
processes ever relinquish the processor, so there is no need to construct these parts as critical sections by
mutexl(Delay ...) wait at line 5 determines the timne needed to prepare data by a random number and line 20
determines theneeded to process data. Tltey only simulate the situation of takin some time to prepare)wait or Processor yieldor process data, and in red program
are no triggers such as (Delay
to exchange
active process. So, if producer becomes active prior to consum $er$ , it is being active until
buffer is full. Then consumer becomes active and remains active until buffer is empty. On the other hand,
if consumer becomes active prior to producer, it will be suspended at line 14, and after that the situation
will be same as before. To activate producer and consumer alternately, it is necessary to insert either
Procesgor yield or (Delay...)wait at the points where data is prepared and where data is processed in
the program. if Processor yield is sitnply inserted at each point, however, the number of data in buf $fer$
is at most one.
object oriented $vers|on$ of this program. BoundedBuffer, Producer and
We are ready to consider
three objects is as followg:
cts inproblem. The relation among
Consumer might be seen as main$\dot{u}\iota$$n$$ti_{1}ne$$g$$t]_{1ere}$$t1_{1}e$$t1_{1}e$$ob_{f}e$$T1_{1}el1$, the relatiolls[tip among these$t1_{1}ese$$t1_{1}is$$t1_{1}ree$objects might be seen as follows.

10

144
The shared resources–bounded buffer which is $an$ instance of BoundedBuffer might be assigned to aclass variable of BoundedBuffer. If the bounded buffer is assigned to an instance variable of BoundedBuffer
instead of a class variable, then the instance of BoundedBuffer might be created each time the instanceof Producer or Consumer is created and these bounded buffers can not be shared among producers andconsumers.
In Smalltalk-80, subclass in herits all the variables and the methods of its superclass. In this case, thevariables of BoundedBuffer for implementing the buffer, such as the buffer area and pointers, are in thescope of Producer or Consumer. That is, the information about the bounded buffer can not be hidden fromits users –Producer and Consumer.
Then, let define BoundedBuffer as an independent class and ProducerConsum $er$ as a superclass of Producer and Conaumer. The instance of BoundedBuffer is assigned to a class variable of ProducerConsumer.
–

By this, the information about the bounded buffer can be hidden from its users. Moreover, as a side
effect, the multiple instances of Producer and Coneumer can be created if necessary.
The following Smalltalk-80 program is constructed according to this idea. In this cas , each of the
producers and consumers is given its identification number. Each producer repeats sending its identification
number to the bounded buffer, and each consumer repeats getting it from the bounded buffer and displays
it with its own identification number.
$e$

1 : class
2:superclass
3 : inst vars

BoundedBuffer
Obj ect
buffer bufferSize readPosition writeposition
valueAvailable spaceAvailable mutex

4 :5 : class method
6: instance creation
7:
new: size
8 :new init: size$\uparrow super$

9 : instance methods
10: accessing
11:
removevalue
12:valueAvailable wait.
13:
14:
mut $ex$ critical:[value $arrow buffer$ at: $re$ adPosition.
15:$readPositionarrow readPosition\backslash \backslash bufferSize+1$ ].
16:
17:
spaceAvailable signal.
18:
$|$

$|$

$\uparrow value$

19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:

deposit: value
spaceAvailable wait.
mutex critical:[buffer at: writePosition put: value.
$writePositionarrow writePosition\backslash \backslash bufferSize+1$ ].

valu Available signal.
”no need to return value”$e$$\uparrow value$

privateinit: size
$bufferarrow Arr$ ay new: size.

.

bufferSize $arrow size$$readpositionarrow writePositionarrow 1$
valueAvailable $arrow Semapbore$ new.
$spaceAvailablearrow Semaphore$ new.
size timesRepeat: [gpaceAvailable signal].

.

11

145
mut $exarrow Semaphore$ forMutualExclusion

34:

Produ erConsumer$1:class$
2 : superclass
3 : class vars$c$

Obj ect
Buffer Rand

4 : class method
5: initialization
initialize
6:$Bufferarrow BoundedBuffer$ new: 5.
7 :$Randarrow Random$ new.
8 :Producer initialize.
9:
Consumer initialize
10:

11:
12:
13:
14:
15:
16:

exampleexamplepl p2 $c1$ c2
ProducerConsumer initialize.
pl $arrow Producer$ new.
$|$

$|$

$p2arrow Producer$ new.
$c1arrow Consumer$ new.
$c2arrow Consumer$ new.

17:
18:
19:
20:

pl resum$e$.

p2 resume.
c2 resume$c1re$ sume.

$1:class$

Producer2 : superclass ProducerConsumer
3 : class var
NoOfProducer
4 : inst var myName$5:class$ methods
6:
7:
8 :

initialization
initialize

9:
10:

instance $cre$ ation$NoOfProducerarrow 0$

newnewProdu er$No0fProducerarrow No0fProducer+1$ .
newProduc $erarrow super$ new.
newProducer setName.
wProduc $er$ define

11:
12:
13:
14:
15:

$|$

$|$

$c$

$\uparrow ne$

16: instance methods
17: private
18:
setNam19:
No0fProducer
myName$e$$arrow$

20:
21:
22:
23:
24:
25:

def inenewProducer
newProduc $erarrow$[[true] whileTrue:
$|$

$|$

[Buffer deposit: myName.

myName printString; $cr$
Transcript show: ’Producer(Delay forSeconds: Rand next $*10$ ) wait]] newProcess.
-

26:
27:

$\uparrow newProduc$$1:class$
2 : superclass
3 : lass var
4 : inst var$c$er

Consume
ProducerConsumer
No0fConsumer
myName$r$$5:class$ methods
6:

7:
8 :

initialization
initialize$No0fConsumerarrow$

$0$

12

.

146
9:
10:
11:
12:
13:
14:
15:

instance creation

new
newConsum er

$|$

$|$

$NoOfConsumerarrow NoOfConsumer+1$

newConsum$erarrow super$ new.

.

newConsumer setNam .
$\uparrow newConsumer$ define$e$16: instanc methods
17: privat
18:
setNam
$myNamearrow No0fConsumer$
19:
$e$

$e$

$e$

20:
21:
22:
23:
24:
25:
26:
27:
28:

definenewConsumer data
$|$

$|$

$newConsumerarrow$[[true] whileTrue:[ $dataarrow Buffer$ remove.

Transcript show: ’Consumer’. myName $pr$ intString,: ’. data $pr$ intString; $cr$ .
(Delay forSeconds: Rand next $*10$ ) wait]] ne $wPr$ ocess.
-$\uparrow newConsumer$

An example of using these classes is shown as a class method example in the class ProducerConsumer,
and two instances of Producer and Consumer are created. The following is one of the results of this example:
1
Producer
Producer -2
Consume2:
Consumer
1
Producer
1
Producer2
Producer
Consumer $-1$ :2:Consumer
Producer –2
1:
Consumer-$r-1:1$
-

2

-

-

-

-

-

1
1
2

There is no need to use a semaphore mutex in the instance methods remove and deposit: if theseclasses are used as in example. lf the priorities of producers and consumers are different, mutex becomes
necessary. For example, suppose that the priority of pl is higher than that of $p2$ . Now pl is suspended
during the time determined by a random number, and p2 is active and begins to execute deposit:. $At$ thispoint, if the waiting time of pl expires, pl becomes active and then executes deposit:. So, to preserve theconsistency, we can not omit mutex. (Incidentally, note that pl, $p2$ , cl and c2 are the instances of class
Process, not class Producer or Consumer.)

13

147
7.2 Readers and Writer’s Problem
The following is the solution for this problem based on the procedural oriented programming $concept[Cou]$ .
In this solution, it is assumed that two readers and one writer access the shared resource.
1 :
2:
3 :
4 :
5:
6:
7 :

$|$

readCount mutex

readerl$w$

readerl reader2 writer

$r$

and

$|$

$arrow$[[true] whileTrue:[mutex wait.

readCount$arrow$(readCount.

readCount $+1$
ifTrue: [ wait].

$=1$ )$w$

mutex signal.
start’; $cr$ .
Trans $cr$ ipt show: ‘readerl(Delay orSec onds: rand next $*10$ ) wait.
$Tr$ anscript show:
readerlend ‘ ; $cr$ .

8:9 :$arrow$$f$

10:$arrow$

11:
12:
13:
14:

mutex wait.

15:(Delay forSeconds:.

readCount $arrow readCountarrow 1$(readCount $-0$ ) ifTrue: [ signal].
mutex signal.
$w$

$r$

and next $*10$ ) wait]] newProcess.

reader2 same as readerl

16:
17:
18:
19:
20:
21:
22:

$writerarrow$[[true] whileTrue:[ wait.
$w$

$w$

23:
24:
25:
26:
27:
28:

anscript show: $wr$ iter –start ‘ ; $cr$ .
(Delay forSeconds: rand next $*10$ ) wait.
‘$Tr$ anscript show:; $cr$ .
$wr$ iter -end
signal.

$Tr$(Delay forSeconds:

readCount $arrow 0$$r$and next $*10$ ) wait]] newProcess.

.

$mutexarrow Semaphore$ forMutualExclusion.
$warrow$

Semaphore forMutualExclugion.

$randarrow Random$ new.

readerl $re$ sum$e$.

reader2 resume.

writer resume.

Lines 8 to 10 mean that readerl is reading from the shared resource and lines 19 to 21 mean that writeris writing into the shared resource. There are some (Delay...)wait in this program. As in the Producer
Consumer Problem, they simulate the ime to perform reading and writing, and they never appear in thereal program, but are needed to execute the processes concurrently.
The semaphore mutex is used to construct the critical sectio . This kind of guard can be omitted in
the Producer Consumer Problem, but it can not be omitted in the following case. Suppose that lines 4 and
7 are omitted so there is no guard around the critical section. When writer is using the shared resource, if$re$ aderi attempts to use the resource because the value of readCount is 1 (after incremented by readerl),
it is suspended at line 6. At this point, if reader2 becomes active and attempts to use the resource, it is able
to use it because the value of readCount is 2 so reader2 skips wait at line 6. If line 4 exists, $re$ ader2 issuspended at line 4 in this case, so there is no problem. On the other hand, in the critical section guarded
by les 11 and 14, there is no chance to exchange the active process so there is no need to construct thispart as critical section.
Now we will solve this problem based on the object oriented programming concept. In this case,File(shared resource), Reader and Writer are considered as objects. Multiple instances of Reader andWriter can be created. The relation among these is sketched as follows, where, readerl, ..., readerN are
the instances of Reader, writer 1, .. ., writ $erM$ are the instances of Writer and file is the instance of File:
$t$

$n$

$w$

$1\dot{u}$

14

148
This relation has the difference in nuance which the relation in the Producer Consumer Problem has, but
in both cases there is one shared resource and there are two kinds of users. So, the standard form derived
from the Producer Consumer Problem can also be applied to this problem. To perform the information
hiding of File and emphasize the combination of the file itself and its operations, the class for the sharedresource is named as FileIO. The instance of FileIO is assigned to the class variable of adersWriters,
which is the superclass of Reade and $Wr$ iter. The relation among these classes is as follows:${\rm Re}$$r$

A program based on this idea is shown below.
1:class

FileIO

2 : superclasg
3 : inst vars

$mut$

Obj ectex$w$

readCount rand

$4:class$ method
5: instance creation
6:
new
7 :
new initialize$\uparrow super$

8 : instance methods
9: accessing
10:
concurrentRead: $re$ ader11:
self startRead.
$Tr$ anscript show:
12:‘reader‘. reader printString,
start; $cr$ .
13:(Delay forSeconds: and next $*10$ ) wait.
14:
15:
Transcript show: ‘reader‘. reader printString,end ‘ ; $cr$ .
16:17:
self endRead$arrow$

$r$

-

18:
19:
20:
21:
22:
23:
24:
25:
26:

27:
28:
29:
30:
31:

exclusiveWrite: writerself startWrite.
Transcript show: ’writer‘, writ $er$ printString,‘start ‘ ; cr.
(Delay forSeconds: and next $*10$ ) $wa$ it.
Transcript show: ‘writer’, writer printString.
end ‘ ; cr.
se lf $endWr$ ite$r$-privateinitialize
readCount $arrow 0$.

$mutexarrow Semaphore$ forMutualExclusion.
$warrow Semaphore$

forMutualExclusion.

$randarrow Random$

new

32:
33:
34:
35:
36:

startReadmutex wait.
$readCountarrow readCount+1$(readCount $=1$ ) ifTrue: [ wait].
mu ex signal

37:
38:
39:
40:
41:

endReadmutex wait.
readCount $arrow readCount-1$(readCoun $t=0$ ) ifTrue: [ signal].
mut $ex$ signal

42:

$st$

.

$w$

$t$

.

$w$

artwrite

15

145
43:
44:
45:

wait

$w$

endW itesignal$r$$w$$1:class$

ReadersWriters
Obj ect
File Rand

2:superclass$3:class$ vars

4:class methods
5: initialization
initialize
6:File $arrow FileIO$ new.
7 :$Re$ ader initialize.
8:$Wr$
iter initialize.
9:$Randarrow Random$ new
10:

11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:

exampleexample$|rir2r3w1$ w2
$Re$

$|$

adersWriters initialize.

$r1arrow Reader$ new.
$r2arrow Reader$ new.

ader new.
wl $arrow Wr$ iter new.
$r3arrow{\rm Re}$new.

$w2arrow Wr$ iterresume.
wl resume.
$r1$$1:class$$r2$

resume.

resume.

$r3$

w2 resume

ReaderadersWriters
NoOfReaders

2:superclass${\rm Re}$

$3:class$ var

4 : inst $var$

myName5:class methods
6: initialization
7:
initialize$No0f{\rm Re} adersarrow 0$
8 :

9:
10:
11:
12:
13:
14:

15:

instance creation

new
newReader
NoOfReaders $arrow NoOfReaders+1$
newR ader $arrow\sup$ er new.
newReade setName.
$\uparrow newReader$ define
$|$

$|$

.

$e$

$r$

16: instanc me tho $ds$
17: private
18:
setN am$myNamearrow NoOfReaders$
19:
$e$

$e$

20:
21:
22:
23:

definewhileTrue:[(Delay forSeconds: Rand next $*10$ ) wait.
File concurrentRead: myNam ]] newProcess$\uparrow[[true]$$e$

1 : class2 : superclass
3 : class var
4 : inst vars

iter
adersWriters$NoOf$ Writers$Wr$${\rm Re}$

myNam

$e$

5 : class methods
6: initialization
7:
initialize
8 :NoOfWrit $ersarrow 0$
9:instance creation

16

15

$C$

10:
11:
12:
13:
14:
15:

new
} newWriter$|$

NoOfWriters\leftarrow NoOfWriters $+1$

newWriter\leftarrow super new.
newWriter setN am .
$\uparrow newWriter$ define.

$e$16: inst ance methodg
17: private
18:
setName$myNamearrow NoOfWr$ iters
19:
20:
21:
22:
23:

definewhileTrue:[(Delay forSeconds: Rand next $*10$ ) wait.
File exclusiveWrite: myName]] newProcess$\uparrow[[true]$An example of using these classes is shown as a class method example in the class $Re$ adersWriterg,
and three instances of Reader an two instances of Writer are created. One of the execution results of thisproblem is as follows.
$d$reader2$re$ ader3$re$ aderl$re$ ader3
readerl$re$ ader3
readerireader2
readerl
reader3$wr$ iterl

art
art
start

–

$st$

–

$st$

$arrow$$arrow$$arrow$$arrow$–$arrow$$arrow$

-

–

end
end

start
start
end
end
end
$st$ art
end

writeri-writer2
writer2
readeri-st $art$

–

end

-

start

Unlike the monitor procedures of Hoare’s monilor[Hoa], more than one process is able to use the methods
in one class simultaneously (a method even can be used by more than one process at the same time). So theusers of the shared resource have only to use the two methods oncurrentRead: and $exc$ lusiveWrite:, unlike Hoare’s monitor in which we have to use startRead, endRe $ad,$ startWrite and endWrite. Accordingly,
protection of the shared resource is easily accomplished in $SmaUta1k- 80$ , and cannot in Hoare’s monitor. If
monitor is used for this problem, the users must execute st art read or BtartWrite before using the sharedresource and endRead or endWrite after completion of using it. Moreover, accessing the share resource isdone directly by users, the users can use it without executing startRead or startWrite. So it is naturalthat the idea has come up which restrict the execution order of monitor procedure by path express:ons[Cam],but such constructs may not be necessary if SmaUtalk-80 is used.
There are, however, some problems. If the class FileIO is defined as before, the processes which use theinstance of it must know how to access it completely. By this, it is not suitable that the resource is capsuledat which it is scheduled. Moreover, in Smalltalk-80, if several processes execute the methods in the sameclass at the same time, the co$py$ of the text is prepared for each process. So it must be noted about thatand in some cases such methods must be constructed as critical section.
The semaphore mutex in the instance methods st art Read and endRead can not be omitted. The reason
for the case in startRead is the same as in first version, and the reason for the case in endRead is as follows.
Supposed that there are two readers, say rl and $r2$ , and the priority of $r1$ is higher than $r2$ . Now rl is
being suspended at line 22 and r2 has used the shared resource. If the suspending time of $r1$ elapses justbefore r2 executes signal, $r1$ becomes active, executes startRead, uses the shared resource, and comesto suspended at line 14. At this point, if $r2$ becomes active, it executes signal. Consequently, the writercan enter into the critical section even if $r1$ is in the critical section.
$c$

$d$

$w$

$w$

17

151
8. Toward realistic concurrent processeg
As stated before, in principle, once a process of Smalltalk-80 gets the processor, the process keeps it continuously unless the process relinquishes it by itself. If the existing algorithms for concurrent processing are used
to compose $SmaUtalk- 80$ programs, not only may the programs contain useless parts but als the processes
may not be executed concurrently.
In the following sections, we will discuss how to execute the processes concurrently. Three methods aresuggested below. The first two methods impose som burden on the programmers and the last one is toreconstruct the Smalltalk-80 system so that there is no such imposition on the programmers.
$0$

$e$

8.1 The method using Processor yield or (Delay...)wait
This method is tbe easiest one. If Processor yield is inserted at every space among the lines in the
program, the program turns out to be executed as if the original program is executed on the system which
adopts time slicing. Clearly, this method not only imposes an enormous overhead on the system, but it isalso troublesome.
To avoid such annoyances, Processor yield or (Delay...)wait as only to be inserted at the appropriate points. Here, the appropriate points mean the points which must be executed concurrently or the
points at which the active process must be exchanged.
Concrete points are different according to the programs, but the typical patterns can be put in order as
the standard form of the Smalltalk-80 programs argued in chapter 6. Moreover, it is not desirable that thethings which are not related to the algorithms like Processor yield or (Delay...)wait must be used in
the programs and the programmers must do such work. Process scheduling is one of the impor ant things
with which the operating system must deal.
$h$

$t$

8.2 The method making monitors

Let consider the method in which the monitors managing the processes are prepared and nothing is inserted
into the user programs. This monitor is one of the user’s processes managed by Processor and a private
scheduler for the particular program.
The outline of this monitor is as follows. Let $P1p_{2},$$Pn$ be the processes created in the program
and the priorities of these processes be lower than that of the monitor.
$\ldots,$

create processes$p_{1}arrow$. . . newProcess.

$Pnarrow\ldots$$iarrow 1$

ne

$wP$

rocess.

.

repeat the following block[ :$p$resum .
$e$(Delay forMilligeconds:slice)wait.
$Pi$suspend.
$iarrow$$i\backslash \backslash n+1$]

This method has the following $pro$ blems:
1. How to manage processes which are created dynamically,
2. How to detect the process termination, and3. This monitor is private to the program, so the new monitor must be prepared for each program.

18

$15L$

8.3 Reconstructing ProcessorScheduler
Because obje $cts$ , originally, exist independently, the Smalltalk-80 system may be reconstructed to carry out
all objects concurrently. One of the examples based on this idea is Concurrent Smalltalk[Yok]. Concurrent
activities, however, depend on the scheduling algorithms. In Smalltalk-80, this problem may be solved byusing simple time slic $ing$ .
To implement the time slicing, it seems to be enough to prepare the process TimeSlicer as follows. Of
course, Processorscheduler must be reconstructed, and the extent of the effort to reconstruct the system
will depend on future research.
1:
2:
3:
4:
5:

$TimeSlicerarrow$[[true] whileTrue:[ $iarrow Processor$ activeProcess.

ttset the active processeeProcessor yield:on end of the ready queue“‘“put $pr$ ocess(Delay forMilliseconds: slice) wait]].
$i$

.

$i$

Note that activeProcess and Processor yield: are not existing methods in $Sm$ alltalk-80.
Acknowledgment
Authors would like to thank Y. Yamamoto for discussing with them and his helpful comments, and M. Tokoro
for his many comments about the usage of shared resources.

References[Cam] Campbell,R. H. and Habermann,A. N., “The Specification of Process Synchronization by Path Expressions,“ in Lecture Notes in Computer Science, Vo1.16, 8kl02.
[Cou] Courtois,P. J., Heymans,F. an d Parnas,D. J., ”Concurrent Control with Readers and Writers,“ CACM,
Vol.14, No. 10, 667-668 (1971).
[Gol] Goldberg,A. and Robson,D., uSmaUtalk-80: the language and its inplementation,“ Addison-Wesley,
1983.
[Hoa] Hoare,C.A.R., ”Monitors : An Operating System Structuring Concept,“ CACM, Vol.17, No.10, 549557(1974).
[Yok] Yokote,Y. and Tokoro,M., ”Concurrent Smalltalk,“ Computer Software, Vol.2, No.4, $2- 18(1985)(in$Japanese).

19