Transcript Deadlock

Deadlocks
The dining philosophers problem
Deadlocks
o Modeling deadlocks
o Dealing with deadlocks
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
1
The Dining Philosophers Problem
 Philosophers
o
o
o
o





think
take forks (one at a time)
eat
put forks (one at a time)
Eating requires 2 forks
Pick one fork at a time
How to prevent deadlock?
What about starvation?
What about concurrency?
Slide taken from a presentation by Gadi Taubenfeld, IDC
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
2
Dining philosophers: definition
 Each process needs two resources
 Every pair of processes compete for a specific resource
 A process may proceed only if it is assigned both
resources
 Every process that is waiting for a resource should sleep
(be blocked)
 Every process that releases its two resources must
wake-up the two competing processes for these
resources, if they are interested
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
3
An incorrect naïve solution
(
means “waiting for this fork”)
Slide taken from a presentation by Gadi Taubenfeld, IDC
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
4
Dining philosophers: textbook solution
The solution
o A philosopher first
gets
o only then it tries to
take the 2 forks.
Slide taken from a presentation by Gadi Taubenfeld, IDC
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
5
Dining philosophers: textbook solution code
#define N 5
#define THINKING
#define HUNGRY
#define EATING
0
1
2
int state[N];
semaphore mutex = 1;
semaphore s[N];
// per each philosopher
int left(int i) { return (i-1) % N;}
int right(in it) { return (i+1) % N;}
void philosopher(int i) {
while (TRUE) {
think();
pick_sticks(i);
eat();
put_sticks(i);
}
}
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
6
Dining philosophers: textbook solution code
void pick_sticks(int i) {
down(&mutex);
state[i] = HUNGRY;
test(i);
up(&mutex);
down(&s[i]);
}
void put_sticks(int i) {
down(&mutex);
state[i] = THINKING;
test(left(i));
test(right(i));
up(&mutex);
}
void test(int i) {
if (state[i] == HUNGRY && state[left(i)] != EATING
&& state[right(i)] != EATING) {
state[i] = EATING;
up(&s[i]);
}
}
Is the algorithm deadlock-free? What about starvation?
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
7
Textbook solution code: starvation is possible
Eat
Starvation!
Block
Eat
Slide taken from a presentation by Gadi Taubenfeld, IDC
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
8
Monitor-based implementation
monitor diningPhilosophers
condition self[N];
integer state[N];
procedure pick_sticks(i) {
state[i] := HUNGRY;
test(i);
if state[i] <> EATING
then wait(self[i]);
}
procedure put_sticks(i) {
state[i] := THINKING;
test(LEFT);
test(RIGHT);
}
procedure test(i) {
if (state[LEFT] <> EATING &&
state[RIGHT] <> EATING &&
state[i] = HUNGRY) {
state[i] := EATING;
signal(self[i]);
}
}
for i := 0 to N-1 do state[i] := THINKING;
end monitor
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
9
Java Monitor-based implementation
// Java implementation of the Dining Philosophers Problem
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
class DiningRoom {
private final int NPHIL;
private final int MAXSLEEP = 5000;
enum State {THINKING, HUNGRY, EATING};
private Philosopher[] philosophers;
private final Lock lock = new ReentrantLock();
// Operations that refer to the group of philosophers
DiningRoom(int n) {
NPHIL = n;
philosophers = new Philosopher[NPHIL];
for (int i = 0; i < NPHIL; ++i) {
philosophers[i] = new Philosopher(this, i);
}
}
public int left(int i) {
return (i+NPHIL-1) % NPHIL;
}
public int right(int i) {
return (i+1) % NPHIL;
}
public State getState(int i) {
return philosophers[i].getState();
}
public void setState(int i, State s) {
philosophers[i].setState(s);
}
public void signal(int i) {
philosophers[i].signal();
}
// Each philosopher separately
public class Philosopher implements Runnable {
private DiningRoom diningRoom;
private int myid;
private State myState;
private Condition self;
public Philosopher(DiningRoom dr, int i) {
diningRoom = dr;
myid = i;
myState = State.THINKING;
self = lock.newCondition();
}
public State getState() { return myState; }
public void setState(State s) { myState = s; }
public void signal() { self.signal(); }
public void pauseabit() throws InterruptedException {
Thread.currentThread().sleep((int)(Math.random() *
MAXSLEEP));
}
public void think() throws InterruptedException {
System.out.println("I am " + myid + " and I am
thinking");
pauseabit();
}
public void eat() throws InterruptedException {
System.out.println("I am " + myid + " and I am
eating");
pauseabit();
}
// Invoked while holding the mutex lock
public void test(int k) throws InterruptedException {
if (diningRoom.getState(left(k)) != State.EATING &&
diningRoom.getState(k) == State.HUNGRY &&
diningRoom.getState(right(k)) != State.EATING) {
diningRoom.setState(k, State.EATING);
diningRoom.signal(k);
}
}
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
public void pickup() throws InterruptedException {
lock.lock();
try {
System.out.println("Pickup " + myid);
myState = State.HUNGRY;
test(myid);
while (myState != State.EATING) {
try {
self.await();
}
catch (InterruptedException e) {
myState = State.THINKING;
throw e;
}
}
} finally { lock.unlock(); }
}
public void putdown() throws InterruptedException {
lock.lock();
try {
System.out.println("Putdown " + myid);
myState = State.THINKING;
test(left(myid));
test(right(myid));
} finally { lock.unlock(); }
}
public void run() {
try {
while (true) {
think();
pickup();
eat();
putdown();
}
} catch (InterruptedException e) {
System.out.println("Philosopher " + myid + " just
died");
}
}
}
10
Textbook solution disadvantages
 An inefficient solution
o reduces to mutual exclusion
o not enough concurrency
o Starvation possible
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
11
The LR Solution
 If the philosopher acquires one fork
and the other fork is not immediately
available, she holds the acquired fork
until the other fork is free.
 Two types of philosophers:
o L -- The philosopher first obtains
its left fork and then its right fork.
o R -- The philosopher first obtains
its right fork and then its left fork.
 The LR solution: the philosophers are
assigned acquisition strategies as
follows: philosopher i is R-type if i is
even, L-type if i is odd.
R
L
L
R
R
L
Slide taken from a presentation by Gadi Taubenfeld, IDC
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
12
Theorem: The LR solution is starvation-free
Assumption: “the fork is fair”.
L
6
R
0
3
L
R
2
4
1
L
R
(
means “first fork taken”)
Slide taken from a presentation by Gadi Taubenfeld, IDC
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
13
Dining Philosophers: Simulations
 Code and Simulation results of various strategies:
http://web.eecs.utk.edu/~plank/plank/classes/cs560/560/notes/Dphil/lecture.html
 DPhil_2 is the deadlock risky version / Dphil_4 is the LR solution / Dphil_5 is the
textbook solution (with possible starvation) – 6 is an explicit queue to avoid
starvation – 7 and 8 are Lamport Bakery variants to achieve fairness.
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
14
Deadlocks
The dining philosophers problem
Deadlocks
o Modeling deadlocks
o Dealing with deadlocks
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
15
Synchronization: Deadlocks
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
16
Deadlocks
 Deadlock of Resource Allocation:
o
o
o
o
Process A requests and gets Tape drive
Process B requests and gets Fast Modem
Process A requests Fast Modem and blocks
Process B requests Tape drive and blocks
 Deadlock situation: Neither process can make progress and
no process can release its allocated device (resource)
 Both resources (devices) require exclusive access
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
17
Resources
 Resources - Tapes, Disks, Printers, Database Records,
semaphores, etc.
 Some resources are non-preemptable (i.e., tape drive)
 It is easier to avoid deadlock with preemptable resources (e.g.,
main memory, database records)
 Resource allocation procedure
o Request
o Use
o Release
Iterate
only at the end – and leave
 Block process while waiting for Resources
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
18
Defining Deadlocks
 A set of processes is deadlocked if each process is waiting for
an event that can only be caused by another process in the
set
 Necessary conditions for deadlock:
1. Mutual exclusion: exclusive use of resources
2. Hold and wait: process can request resource while holding another
resource
3. No preemption: only holding process can release resource
4. Circular wait: there is an oriented circle of processes, each of which is
waiting for a resource held by the next in the circle
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
19
Modeling deadlocks
 modeled by a directed graph (resource graph)
o Requests and assignments as directed edges
o Processes and Resources as vertices
 Cycle in graph means deadlock
Process A holds
resource Q
A
Deadlock
Process B
requests
resource P
F
P
S
R
Q
B
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
M
20
Different possible runs: an example
A
Request R
Request S
Release R
Release S
C
B
Request T
Request R
Release T
Release R
Request S
Request T
Release S
Release T
Round-robin
scheduling:
1.
A requests R
2.
B requests S
3.
C requests T
4.
A requests S
5.
B requests T
6.
C requests R
A
B
C
R
S
T
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
21
Different possible runs: an example
A
Request R
Request S
Release R
Release S
C
B
Request T
Request R
Release T
Release R
Request S
Request T
Release S
Release T
An alternative
scheduling:
1.
A requests R
2.
C requests T
3.
A requests S
4.
C requests R
5.
A releases R
6.
A releases S
A
B
C
R
S
T
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
22
Multiple Resources of each Type
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
23
A Directed Cycle But No Deadlock
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
24
Resource Allocation Graph With A Deadlock
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
25
Basic Facts
 If graph contains no cycles  no deadlock
 If graph contains a cycle 
o if only one instance per resource type, then deadlock
o if several instances per resource type, deadlock
possible
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
26
Dealing with Deadlocks
The dining philosophers problem
Deadlocks
o Modeling deadlocks
o Dealing with deadlocks
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
27
Dealing with Deadlocks
 Possible Strategies:
o Prevention
structurally negate one of the four necessary conditions
o Avoidance
allocate resources carefully, so as to avoid deadlocks
o Detection and recovery
o Do nothing (The “ostrich algorithm’’)
deadlocks are rare and hard to tackle... do nothing
Example: Unix - process table with 1000 entries and 100 processes
each requesting 20 FORK calls... Deadlock.
users prefer a rare deadlock over frequent refusal of FORK
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
28
Deadlock prevention
 Attack one of the 4 necessary conditions:
1. Mutual exclusion
o Minimize exclusive allocation of devices
o Use spooling: only spooling process requests access (not good for all
devices - Tapes; Process Tables); may fill up spools (disk space deadlock)...
2. Hold and Wait
o Request all resources immediately (before execution)
Problem: resources not known in advance, inefficient
or
o to get a new resource, free everything, then request everything again
(including new resource)
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
29
Attack one of the 4 necessary conditions (cont'd)
3. No preemption
o Not always possible (e.g., printer)
4. Circular wait condition
o Allow holding only a single resource (too restrictive)
o Number resources, allow requests only in ascending order:
Request only resources numbered higher than anything currently
held
Impractical in general
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
30
Deadlock Avoidance
 System grants resources only if it is safe
 basic assumption: maximum resources required by each
process is known in advance
Safe state:
 Not deadlocked
 There is a scheduling that satisfies all possible future
requests
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
31
Safe states: example
B
l8
l7
Printer
Plotter
Both have printer
l6
l5
Both have plotter
t
r
Both have both
s
Unsafe state
p
q
l1
l2
l3
l4
A
Printer
Plotter
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
32
Safe and Unsafe states (single resource)
 Safe state:
o Not deadlocked
o There is a way to satisfy all possible future requests
(a)
(b)
(c)
Fig. 6-9. Three resource allocation states: (a) Safe. (b) Safe. (c) Unsafe.
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
33
Banker's Algorithm, Dijkstra 1965 (single resource)
 Checks whether a state is safe
1.
2.
3.
4.
5.
6.
Pick a process that can terminate after fulfilling the
rest of its requirements (enough free resources)
Free all its resources (simulation)
Mark process as terminated
If all processes marked, report “safe”, halt
If no process can terminate, report “unsafe”, halt
Go to step 1
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
34
Multiple resources of each kind
 Assume n processes and m resource classes
 Use two matrixes and two vectors:
o Current allocation matrix Cn x m
o Request matrix Rn x m (remaining requests)
o Existing resources vector Em
o Available resources vector Am
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
35
Banker’s Algorithm for multiple resources
1.
Look for a row of R whose unmet resource needs are all smaller
than or equal to A. If no such row exists, the system will
eventually deadlock.
2.
Otherwise, assume the process of the row chosen finishes
(which will eventually occur). Mark that process as terminated
and add the i’th row of C to the A vector
3.
Repeat steps 1 and 2 until either all processes are marked
terminated, which means safe, or until a deadlock occurs,
which means unsafe.
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
36
Deadlock avoidance – an example with
4 resource types, 5 processes
Tape-drives Plotters
E = (6
3
A = (1
0
C=
Scanners CD-ROMs
4
2)
2
0)
T
P S C
T
P S C
A
3
0
1
1
A
1
1
0
0
B
0
1
0
0
B
0
1
1
2
C
1
1
1
0
C
3
1
0
0
D
1
1
0
1
D
0
0
1
0
E
0
0
0
0
E
2
1
1
0
R=
Is the current state safe?
Yes, let’s see why…
We let D run until it finishes
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
37
Deadlock avoidance – an example with
4 resource types, 5 processes
Tape-drives Plotters
E = (6
3
A = (2
1
C=
Scanners CD-ROMs
4
2)
2
1)
T
P S C
T
P S C
A
3
0
1
1
A
1
1
0
0
B
0
1
0
0
B
0
1
1
2
C
1
1
1
0
C
3
1
0
0
D
0
0
0
0
D
0
0
0
0
E
0
0
0
0
E
2
1
1
0
R=
We now let E run until it finishes
Next we let A run until it finishes
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
38
Deadlock avoidance – an example with
4 resource types, 5 processes
Tape-drives Plotters
E = (6
3
A = (5
1
C=
Scanners CD-ROMs
4
2)
3
2)
T
P S C
T
P S C
A
0
0
0
0
A
0
0
0
0
B
0
1
0
0
B
0
1
1
2
C
1
1
1
0
C
3
1
0
0
D
0
0
0
0
D
0
0
0
0
E
0
0
0
0
E
0
0
0
0
R=
Finally we let B and C run.
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
39
Back to original state
Tape-drives Plotters
E = (6
3
A = (1
0
C=
Scanners CD-ROMs
4
2)
2
0)
T
P S C
T
P S C
A
3
0
1
1
A
1
1
0
0
B
0
1
0
0
B
0
1
1
2
C
1
1
1
0
C
3
1
0
0
D
1
1
0
1
D
0
0
1
0
E
0
0
0
0
E
2
1
1
0
R=
If B now requests a Scanner, we can allow it.
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
40
This is still a safe state…
Tape-drives Plotters
E = (6
3
A = (1
0
C=
Scanners CD-ROMs
4
2)
1
0)
T
P S C
T
P S C
A
3
0
1
1
A
1
1
0
0
B
0
1
1
0
B
0
1
0
2
C
1
1
1
0
C
3
1
0
0
D
1
1
0
1
D
0
0
1
0
E
0
0
0
0
E
2
1
1
0
R=
If E now requests a Scanner, granting the
request leads to an unsafe state
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
41
This state is unsafe
Tape-drives Plotters
E = (6
3
A = (1
0
C=
Scanners CD-ROMs
4
2)
0
0)
T
P S C
T
P S C
A
3
0
1
1
A
1
1
0
0
B
0
1
1
0
B
0
1
0
2
C
1
1
1
0
C
3
1
0
0
D
1
1
0
1
D
0
0
1
0
E
0
0
1
0
E
2
1
0
0
R=
We must not grant E’s request
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
42
Deadlock Avoidance is not practical
 Maximum resource request per process is unknown
beforehand
 Resources may disappear
 New processes (or resources) may appear
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
43
Deadlock Detection and Recovery
 Find if a deadlock exists
 if it does, find which processes and resources it involves
 Detection: detect cycles in resource graph
 Algorithm: DFS + node and arc marking
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
44
Find cycles:
For each node, N, in the graph, perform the following
5 steps with N as the starting node
1. Initialize L to the empty list and designate all arcs as unmarked
2. Add the current node to the end of L and check if the node appears twice
in L. If it does, the graph contains a cycle, terminate.
3. If there are any unmarked arcs from the given node, go to 4., if not go to
5.
4. Pick an unmarked outgoing arc and mark it. Follow it to the new current
node and go to 2.
5. We have reached a deadend. Go back to the previous node, make it the
current node and go to 3. If all arcs are marked and the node is the initial
node, there are no cycles in the graph, terminate
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
45
Detection - extract a cycle
1. Process A holds R and requests S
2. Process B holds nothing and requests T
3. Process C holds nothing and requests S
4. Process D holds U and requests S and T
5. Process E holds T and requests V
6. Process F holds W and requests S
7. Process G holds V and requests U
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
46
When should the system check for deadlock ?
 Whenever a request is made - too expensive.
 Every k time units.
 Whenever CPU utilization drops below some threshold
(indication of a possible deadlock).
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
47
Recovery
 Preemption - possible in some rare cases
temporarily take a resource away from its current owner
 Rollback - possible with checkpointing
Keep former states of processes (checkpoints) to
enable release of resources and going back
 Killing a process - easy way out, may cause problems in
some cases, depending on process being re-runable…
 Bottom line: hard to recover from deadlock, avoid it
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
48
Factors Determining Process to “Kill”
1.
2.
3.
4.
5.
6.
What the priority of the process is
How long the process has computed, and how much longer the
program will compute before completing its designated task
How many and what type of resources the process has used
(for example, whether the resources are simple or preempt)
How many more resources the process needs in order to
complete
How many processes will need to be terminated
Whether the process is interactive or batch
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
49
Example - deadlocks in DBMSs
 For database records that need locking first and
then updating (two-phase locking)
 Deadlocks occur frequently because records are
dynamically requested by competing processes
 DBMSs, therefore, need to employ deadlock
detection and recovery procedures
 Recovery is possible - transactions are
“checkpointed” - release everything and restart
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
50
Additional deadlock issues
 Deadlocks may occur with respect to actions of processes,
not resources - waiting for semaphores
 Starvation can result from a bad allocation policy (such as
smallest-file-first, for printing) and for the “starved”
process will be equivalent to a deadlock (cannot finish
running)
 Summary of deadlock treatment:
o Ignore problem
o Detect and recover
o Avoid (be only in safe states)
o Prevent by using an allocation policy or conditions
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
53
The Situation in Practice
 Most OSs in use, and specifically Windows, Solaris, Linux ignore
deadlock or do not detect it
 Tools to kill processes but usually without loss of data
 In Windows NT there is a system call WaitForMultipleObjects
that requests all resources at once
o System provides all resources, if free
o There is no lock of resources if only few are free
o Prevents Hold & Wait, but difficult to implement!
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
54
Linux: the Big Kernel Lock
Linux was first designed with Coarse-Grained Locking
The whole kernel was wrapped in a giant lock around
it to avoid deadlocks (kernel / interrupt handlers /
user threads) introduced in Linux 2.0.
Work began in 2008 to remove the big kernel lock:
http://kerneltrap.org/Linux/Removing_the_Big_Kernel
_Lock
It was carefully replaced with fine-grained locks until it
was removed in Linux 2.6.39 (in 2011!)
https://lwn.net/Articles/424657/
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
55
Xv6 and deadlocks
 Xv6 uses a few coarse data-structure specific locks; for example, xv6 uses a single lock
protecting the process table and its invariants, which are described in Chapter 5.
 A more fine-grained approach would be to have a lock per entry in the process table so
that threads working on different entries in the process table can proceed in parallel.
 However, it complicates operations that have invariants over the whole process table,
since they might have to take out several locks.
 To avoid such deadlocks, all code paths must acquire locks in the same order. Deadlock
avoidance is another example illustrating why locks must be part of a function’s specification:
the caller must invoke functions in a consistent order so that the functions acquire locks in the
same order
 Because xv6 uses coarse-grained locks and xv6 is simple, xv6 has few lock-order chains. The
longest chain is only two deep. For example, ideintr holds the ide lock while calling wakeup,
which acquires the ptable lock. There are a number of other examples involving sleep and
wakeup. These orderings come about because sleep and wakeup have a complicated invariant,
as discussed in Chapter 5.
 In the file system there are a number of examples of chains of two because the file system
must, for example, acquire a lock on a directory and the lock on a file in that directory to unlink
a file from its parent directory correctly. Xv6 always acquires the locks in the order first parent
directory and then the file
Operating Systems, 2013, Meni Adler, Michael Elhadad & Amnon Meisels
56