Responsive Parallelism with Synchronization
Responsive Parallelism with Synchronization
复制标题
响应式并行与同步
DOI：
10.1145/3591249
复制
发表时间：
2023
影响因子：
--
通讯作者：
Acar, Umut A.
中科院分区：
文献类型：
--
作者：
Muller, Stefan K.;Singer, Kyle;Keeney, Devyn Terra;Neth, Andrew;Agrawal, Kunal;Lee, I-Ting Angelina;Acar, Umut A.
许多并发程序为线程分配优先级以提高响应能力。但是，当与互斥锁和条件变量等同步机制结合使用时，优先级可能导致优先级反转，即高优先级线程被低优先级线程延迟。在使用互斥锁的优先级反转很容易使用动态技术，如优先级继承处理，但在使用条件变量的优先级反转没有得到很好的研究和动态技术是不合适的。在这项工作中，我们使用静态和动态技术相结合，以防止在代码中使用互斥锁和条件变量的优先级反转。类型系统确保安全地使用条件变量，即使动态技术在运行时更改线程优先级以消除使用互斥时的优先级反转。我们证明了我们的系统的合理性，使用一个模型的优先级反转的基础上成本模型的并行程序。为了证明类型系统是实用的实现，我们在Rust和C++的类型系统中对其进行编码，并通过使用这些编码编写相当大的案例研究来证明限制并不过分繁重，包括将Memcached对象服务器移植到使用我们的C++实现。
Many concurrent programs assign priorities to threads to improve responsiveness. When used in conjunction with synchronization mechanisms such as mutexes and condition variables, however, priorities can lead to priority inversions, in which high-priority threads are delayed by low-priority ones. Priority inversions in the use of mutexes are easily handled using dynamic techniques such as priority inheritance, but priority inversions in the use of condition variables are not well-studied and dynamic techniques are not suitable.In this work, we use a combination of static and dynamic techniques to prevent priority inversion in code that uses mutexes and condition variables. A type system ensures that condition variables are used safely, even while dynamic techniques change thread priorities at runtime to eliminate priority inversions in the use of mutexes. We prove the soundness of our system, using a model of priority inversions based on cost models for parallel programs. To show that the type system is practical to implement, we encode it within the type systems of Rust and C++, and show that the restrictions are not overly burdensome by writing sizeable case studies using these encodings, including porting the Memcached object server to use our C++ implementation.
登录
查看更多内容
响应式并行计算：桥接竞争线程和协作线程
DOI：
10.1145/3062341.3062370
发表时间：
2017
期刊：
Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation
影响因子：
--
作者：
Stefan K. Muller;Umut A. Acar;R. Harper
通讯作者：
R. Harper
能力演算中的类型化内存管理
DOI：
--
发表时间：
1999
期刊：
ACM-SIGACT Symposium on Principles of Programming Languages
影响因子：
--
作者：
Karl Crary;D. Walker;G. Morrisett
通讯作者：
G. Morrisett
与 future 和 state 的响应式并行
DOI：
10.1145/3385412.3386013
发表时间：
2020
期刊：
Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation
影响因子：
--
作者：
Muller, Stefan K.;Singer, Kyle;Goldstein, Noah;Acar, Umut A.;Agrawal, Kunal;Lee, I-Ting Angelina
通讯作者：
Lee, I-Ting Angelina
NESL 的可证明时间和空间高效的实现
DOI：
10.1145/232627.232650
发表时间：
1996
期刊：
Proceedings of the 19th International Symposium on Principles and Practice of Declarative Programming
影响因子：
--
作者：
G. Blelloch;John Greiner
通讯作者：
John Greiner
顺序函数语言中的并行性
DOI：
10.1145/224164.224210
发表时间：
1995
期刊：
Proceedings 16th Annual IEEE Symposium on Logic in Computer Science
影响因子：
--
作者：
G. Blelloch;John Greiner
通讯作者：
John Greiner