The Experts below are selected from a list of 96 Experts worldwide ranked by ideXlab platform

Zhong Shao - One of the best experts on this subject based on the ideXlab platform.

  • modular verification of Concurrent Thread management
    Asian Symposium on Programming Languages and Systems, 2012
    Co-Authors: Xinyu Feng, Zhong Shao
    Abstract:

    Thread management is an essential functionality in OS kernels. However, verification of Thread management remains a challenge, due to two conflicting requirements: on the one hand, a Thread manager—operating below the Thread abstraction layer–should hide its implementation details and be verified independently from the Threads being managed; on the other hand, the Thread management code in many real-world systems is Concurrent, which might be executed by the Threads being managed, so it seems inappropriate to abstract Threads away in the verification of Thread managers. Previous approaches on kernel verification view Thread managers as sequential code, thus cannot be applied to Thread management in realistic kernels. In this paper, we propose a novel two-layer framework to verify Concurrent Thread management. We choose a lower abstraction level than the previous approaches, where we abstract away the context switch routine only, and allow the rest of the Thread management code to run Concurrently in the upper level. We also treat Thread management data as abstract resources so that Threads in the environment can be specified in assertions and be reasoned about in a proof system similar to Concurrent separation logic.

  • APLAS - Modular Verification of Concurrent Thread Management
    Programming Languages and Systems, 2012
    Co-Authors: Xinyu Feng, Zhong Shao
    Abstract:

    Thread management is an essential functionality in OS kernels. However, verification of Thread management remains a challenge, due to two conflicting requirements: on the one hand, a Thread manager—operating below the Thread abstraction layer–should hide its implementation details and be verified independently from the Threads being managed; on the other hand, the Thread management code in many real-world systems is Concurrent, which might be executed by the Threads being managed, so it seems inappropriate to abstract Threads away in the verification of Thread managers. Previous approaches on kernel verification view Thread managers as sequential code, thus cannot be applied to Thread management in realistic kernels. In this paper, we propose a novel two-layer framework to verify Concurrent Thread management. We choose a lower abstraction level than the previous approaches, where we abstract away the context switch routine only, and allow the rest of the Thread management code to run Concurrently in the upper level. We also treat Thread management data as abstract resources so that Threads in the environment can be specified in assertions and be reasoned about in a proof system similar to Concurrent separation logic.

T. Hironaka - One of the best experts on this subject based on the ideXlab platform.

Xinyu Feng - One of the best experts on this subject based on the ideXlab platform.

  • modular verification of Concurrent Thread management
    Asian Symposium on Programming Languages and Systems, 2012
    Co-Authors: Xinyu Feng, Zhong Shao
    Abstract:

    Thread management is an essential functionality in OS kernels. However, verification of Thread management remains a challenge, due to two conflicting requirements: on the one hand, a Thread manager—operating below the Thread abstraction layer–should hide its implementation details and be verified independently from the Threads being managed; on the other hand, the Thread management code in many real-world systems is Concurrent, which might be executed by the Threads being managed, so it seems inappropriate to abstract Threads away in the verification of Thread managers. Previous approaches on kernel verification view Thread managers as sequential code, thus cannot be applied to Thread management in realistic kernels. In this paper, we propose a novel two-layer framework to verify Concurrent Thread management. We choose a lower abstraction level than the previous approaches, where we abstract away the context switch routine only, and allow the rest of the Thread management code to run Concurrently in the upper level. We also treat Thread management data as abstract resources so that Threads in the environment can be specified in assertions and be reasoned about in a proof system similar to Concurrent separation logic.

  • APLAS - Modular Verification of Concurrent Thread Management
    Programming Languages and Systems, 2012
    Co-Authors: Xinyu Feng, Zhong Shao
    Abstract:

    Thread management is an essential functionality in OS kernels. However, verification of Thread management remains a challenge, due to two conflicting requirements: on the one hand, a Thread manager—operating below the Thread abstraction layer–should hide its implementation details and be verified independently from the Threads being managed; on the other hand, the Thread management code in many real-world systems is Concurrent, which might be executed by the Threads being managed, so it seems inappropriate to abstract Threads away in the verification of Thread managers. Previous approaches on kernel verification view Thread managers as sequential code, thus cannot be applied to Thread management in realistic kernels. In this paper, we propose a novel two-layer framework to verify Concurrent Thread management. We choose a lower abstraction level than the previous approaches, where we abstract away the context switch routine only, and allow the rest of the Thread management code to run Concurrently in the upper level. We also treat Thread management data as abstract resources so that Threads in the environment can be specified in assertions and be reasoned about in a proof system similar to Concurrent separation logic.

Hironori Kasahara - One of the best experts on this subject based on the ideXlab platform.

  • Multiple-Paths Search with Concurrent Thread Scheduling for Fast AND/OR Tree Search
    2009 International Conference on Complex Intelligent and Software Intensive Systems, 2009
    Co-Authors: Fumiyo Takano, Yoshitaka Maekawa, Hironori Kasahara
    Abstract:

    This paper proposes a fast AND/OR tree search algorithm using a multiple-paths Concurrent search method. Conventional heuristic AND/OR tree search algorithms expand nodes in only a descending order of heuristic evaluation values. However, since the evaluation values are heuristic, a solution node group sometimes includes nodes with lower evaluation values. The tree which has a solution node group including nodes with lower evaluation values requires a long time to be solved by the conventional algorithms. The proposed algorithm allows us to search paths including nodes with lower evaluation values and paths including nodes with higher evaluation values Concurrently. For searching various paths Concurrently, the proposed algorithm uses pseudo-Threads and a pseudo-Thread scheduler managed by a user program with low overhead compared with the OS Thread management. The pseudo-Thread scheduler can weight the amount of search on each path and schedule the pseudo-Threads. The proposed algorithm can solve trees which have solutions including nodes with lower evaluation values also quickly. For performance evaluation, the proposed algorithm was applied to a Tsume-Shogi (Japanese chess problem) solver as a typical AND/OR tree search problem. In tsume-shogi, players can reuse captured pieces. Performance evaluation results on 385 problems show that the proposed algorithm is 1.67 times faster on the average than the previous algorithm df-pn.

  • multiple paths search with Concurrent Thread scheduling for fast and or tree search
    Complex Intelligent and Software Intensive Systems, 2009
    Co-Authors: Fumiyo Takano, Yoshitaka Maekawa, Hironori Kasahara
    Abstract:

    This paper proposes a fast AND/OR tree search algorithm using a multiple-paths Concurrent search method. Conventional heuristic AND/OR tree search algorithms expand nodes in only a descending order of heuristic evaluation values. However, since the evaluation values are heuristic, a solution node group sometimes includes nodes with lower evaluation values.The tree which has a solution node group including nodes with lower evaluation values requires a long time to be solved by the conventional algorithms.The proposed algorithm allows us to search paths including nodes with lower evaluation values and paths including nodes with higher evaluation values Concurrently.For searching various paths Concurrently, the proposed algorithm uses pseudo-Threads and a pseudo-Thread scheduler managed by a user program with low overhead compared with the OS Thread management.The pseudo-Thread scheduler can weight the amount of search on each path and schedule the pseudo-Threads.The proposed algorithm can solve trees which have solutions including nodes with lower evaluation values also quickly.For performance evaluation, the proposed algorithm was applied to a tsume-shogi (Japanese chess problem) solver as a typical AND/OR tree search problem.In tsume-shogi, players can reuse captured pieces.Performance evaluation results on 385 problems show that the proposed algorithm is  1.67 times faster on the average than the previous algorithm df-pn.

  • CISIS - Multiple-Paths Search with Concurrent Thread Scheduling for Fast AND/OR Tree Search
    2009 International Conference on Complex Intelligent and Software Intensive Systems, 2009
    Co-Authors: Fumiyo Takano, Yoshitaka Maekawa, Hironori Kasahara
    Abstract:

    This paper proposes a fast AND/OR tree search algorithm using a multiple-paths Concurrent search method. Conventional heuristic AND/OR tree search algorithms expand nodes in only a descending order of heuristic evaluation values. However, since the evaluation values are heuristic, a solution node group sometimes includes nodes with lower evaluation values.The tree which has a solution node group including nodes with lower evaluation values requires a long time to be solved by the conventional algorithms.The proposed algorithm allows us to search paths including nodes with lower evaluation values and paths including nodes with higher evaluation values Concurrently.For searching various paths Concurrently, the proposed algorithm uses pseudo-Threads and a pseudo-Thread scheduler managed by a user program with low overhead compared with the OS Thread management.The pseudo-Thread scheduler can weight the amount of search on each path and schedule the pseudo-Threads.The proposed algorithm can solve trees which have solutions including nodes with lower evaluation values also quickly.For performance evaluation, the proposed algorithm was applied to a tsume-shogi (Japanese chess problem) solver as a typical AND/OR tree search problem.In tsume-shogi, players can reuse captured pieces.Performance evaluation results on 385 problems show that the proposed algorithm is  1.67 times faster on the average than the previous algorithm df-pn.

N. Nishimura - One of the best experts on this subject based on the ideXlab platform.