Earlier Version

From non-preemptive to preemptive scheduling using synchronization synthesis

Cerny P, Clarke E, Henzinger TA, Radhakrishna A, Ryzhyk L, Samanta R, Tarrach T. 2015. From non-preemptive to preemptive scheduling using synchronization synthesis. 9207, 180–197.

Download
Campus/VPN IST-2015-336-v1+1_long_version.pdf 481.92 KB [Submitted Version]

Conference Paper | Published | English

Scopus indexed
Series Title
LNCS
Abstract
We present a computer-aided programming approach to concurrency. The approach allows programmers to program assuming a friendly, non-preemptive scheduler, and our synthesis procedure inserts synchronization to ensure that the final program works even with a preemptive scheduler. The correctness specification is implicit, inferred from the non-preemptive behavior. Let us consider sequences of calls that the program makes to an external interface. The specification requires that any such sequence produced under a preemptive scheduler should be included in the set of such sequences produced under a non-preemptive scheduler. The solution is based on a finitary abstraction, an algorithm for bounded language inclusion modulo an independence relation, and rules for inserting synchronization. We apply the approach to device-driver programming, where the driver threads call the software interface of the device and the API provided by the operating system. Our experiments demonstrate that our synthesis method is precise and efficient, and, since it does not require explicit specifications, is more practical than the conventional approach based on user-provided assertions.
Publishing Year
Date Published
2015-07-01
Publisher
Springer
Volume
9207
Page
180 - 197
Conference
CAV: Computer Aided Verification
Conference Location
San Francisco, CA, United States
Conference Date
2015-07-18 – 2015-07-24
IST-REx-ID

Cite this

Cerny P, Clarke E, Henzinger TA, et al. From non-preemptive to preemptive scheduling using synchronization synthesis. 2015;9207:180-197. doi:10.1007/978-3-319-21668-3_11
Cerny, P., Clarke, E., Henzinger, T. A., Radhakrishna, A., Ryzhyk, L., Samanta, R., & Tarrach, T. (2015). From non-preemptive to preemptive scheduling using synchronization synthesis. Presented at the CAV: Computer Aided Verification, San Francisco, CA, United States: Springer. https://doi.org/10.1007/978-3-319-21668-3_11
Cerny, Pavol, Edmund Clarke, Thomas A Henzinger, Arjun Radhakrishna, Leonid Ryzhyk, Roopsha Samanta, and Thorsten Tarrach. “From Non-Preemptive to Preemptive Scheduling Using Synchronization Synthesis.” Lecture Notes in Computer Science. Springer, 2015. https://doi.org/10.1007/978-3-319-21668-3_11.
P. Cerny et al., “From non-preemptive to preemptive scheduling using synchronization synthesis,” vol. 9207. Springer, pp. 180–197, 2015.
Cerny P, Clarke E, Henzinger TA, Radhakrishna A, Ryzhyk L, Samanta R, Tarrach T. 2015. From non-preemptive to preemptive scheduling using synchronization synthesis. 9207, 180–197.
Cerny, Pavol, et al. From Non-Preemptive to Preemptive Scheduling Using Synchronization Synthesis. Vol. 9207, Springer, 2015, pp. 180–97, doi:10.1007/978-3-319-21668-3_11.
Main File(s)
File Name
IST-2015-336-v1+1_long_version.pdf 481.92 KB
Access Level
Campus/VPN ISTA Only
Date Uploaded
2018-12-12
MD5 Checksum
6ff58ac220e2f20cb001ba35d4924495


Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar