Queue-Dispatch Asynchronous Systems

Details Queue-Dispatch Asynchronous Systems Queue-Dispatch Asynchronous Systems

2012-01-23

arxiv.org/abs/1201.4871v2

Computer Science

Logic in Computer Science

29 pages, submitted for publication

Scientific paper

To make the development of efficient multi-core applications easier, libraries, such as Grand Central Dispatch, have been proposed. When using such a library, the programmer writes so-called blocks, which are chunks of codes, and dispatches them, using synchronous or asynchronous calls, to several types of waiting queues. A scheduler is then responsible for dispatching those blocks on the available cores. Blocks can synchronize via a global memory. In this paper, we propose Queue-Dispatch Asynchronous Systems as a mathematical model that faithfully formalizes the synchronization mechanisms and the behavior of the scheduler in those systems. We study in detail their relationships to classical formalisms such as pushdown systems, Petri nets, fifo systems, and counter systems. Our main technical contributions are precise worst-case complexity results for the Parikh coverability problem for several subclasses of our model.

Affiliated with

Also associated with

No associations

Rating

Queue-Dispatch Asynchronous Systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Queue-Dispatch Asynchronous Systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Queue-Dispatch Asynchronous Systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-105282