A talk by RU alumni James Robb

An opportunity for current students to ask about masters + PhD studies and see what one RU alumni is doing after graduation

  • 11.9.2019, 12:15 - 13:00

Date and time: 11 September 2019, at 12:15 in room M111
Title: A Fine-Grained Nested Real-Time Locking Protocol for Latency-Sensitive Tasks
Speaker: James Robb

Bio:James Robb, born and raised in Canada, worked as a software developer in Canada, Bosnia, and
Iceland before beginning studies at RU. He graduated from the tölvunarstærðfræði program at RU in
2018 after completing his bachelor's project on enumerating classes of combinatorial objects under the
supervision of Henning Ulfarsson and Christian Bean. Since then, he has started a PhD program in
computer science under the supervision of Björn Brandenburg at the Max Planck Institute for Software
Systems in Kaiserslautern, Germany. Currently, his research focuses on real-time systems.


Abstract: Failure to plan for worst-case scenarios in safety-critical environments such as avionics or healthcare can be catastrophic or even fatal. While many fields of computer science focus primarily on the average-case behaviour of a system, the study of real-time systems focus on producing provably sound analysis of worst-case behaviour in any given scenario, which naturally lends itself to safety-critical applications. Real-time systems are computer systems subject to temporal or “wall-time” constraints: the correctness of a real-time computation does not only depend on the produced value, but also when the value is produced; if a computation exceeds a given deadline, the result is considered to be incorrect.

All but the most trivial of systems will have some shared resources (e.g., network cards, I/O ports,
shared memory, etc.) that tasks will need to access in a mutually-exclusive manner, and a locking
protocol is the mechanism used to arbitrate access to these resources. In this work , we introduce the
first nested locking protocol for real-time systems that is independence-preserving, meaning the
locking protocol isolates real-time tasks with tight timing constraints from delays produced by
contention for shared resources in a system. Independence preservation has been studied previously and
is well understood, but only in the context of non-nested locking. More than one intuitive definition of
independence preservation arises when extending the notion to nested locking. We define and analyze
group independence preservation and outer-lock independence preservation. To realize group
independence preservation, we introduce the Clustered k-exclusion Locking Protocol (CKIP), a novel
asymptotically optimal k-exclusion locking protocol for non-nested resources, that when paired with
the existing Real-Time Nested Locking Protocol (RNLP), produces an optimal fine-grained nested
locking protocol that is group independence-preserving. Conversely, we prove for a large class of
locking protocols, that supporting outer-lock independence preservation results in delays that are lowerbounded in the number of tasks in the system for certain task sets. This lower bound renders a locking
protocol non-optimal, as an optimal real-time locking protocol is upper-bounded linearly in the number
of processors under so-called suspension oblivious analysis.



Vinsamlegast athugið að á viðburðum Háskólans í Reykjavík (HR) eru teknar ljósmyndir og myndbönd sem notuð eru í markaðsstarfi HR. Hægt er að nálgast frekari upplýsingar á ru.is eða með því að senda tölvupóst á netfangið: personuvernd@ru.is

//


Please note that at events hosted at Reykjavik University (RU), photographs and videos are taken which might be used for RU marketing purposes. Read more about this on our ru.is or send an e-mail: personuvernd@ru.is