System for assisting a programmer find errors in concurrent programs

• US 6,067,415 A
• Filed: 12/23/1996
• Issued: 05/23/2000
• Est. Priority Date: 12/26/1995
• Status: Expired due to Fees

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Uchihira, Naoshi
• Primary Examiner(s): Trammell, James P.
• Assistant Examiner(s): Nguyen, Cuong H.
• Application Number:
  US08/772,652
• Time in Patent Office: 1,247 Days
• Field of Search: 395/701, 395/704, 395/183.01, 395/183.13, 395/183.14, 395/702, 395/182.04, 395/706, 707/1, 707/10, 707/103
• US Class Current: 717/131
• CPC Class Codes: G06F 8/30 Creation or generation of source code
• CPC Class Codes: G06F 8/53 Decompilation; Disassembly

Abstract

A designer creates a program with the editor 1. The division means 2 divides each process of the program into a plurality of controllable sections. The detection means 3 finds the dependency relations among the sessions of the program. The generation means 4 represents as a scenario all the possible execution sequences of the sections in each process. When the designer selects the edge of a section to be executed first at each branch in the scenario with the use of the selection means 6, a scenario containing only the combinations of intended execution sequences is generated. Based on this scenario, the conversion means 9 inserts execution timing control instructions into the first program to convert the first program to a second program. The resulting second program does not contain a harmful nondeterminism. Therefore, a hyper sequential programming system or method for developing reliable concurrent programs is provided easily.

Claims

1. A system for assisting a program designer to remove program errors of a concurrent program, said system comprising:

division means for dividing each process of a first concurrent program, consisting of a plurality of processes, into a plurality of sections;

generation means for generating a network structure, consisting of nodes and arrows, which represents a set of possible execution orders of said sections of said first concurrent program, where each arrow indicates a section, and a path of said network structure indicates a possible execution order of said sections;

selection means for selecting sections represented by said arrows at each branch of said network structure; and

conversion means for converting said first concurrent program to a second concurrent program which executes selected execution orders consisting of said selected sections of said first concurrent program selected by said selection means and does not execute sections which are not selected.

2. A method for assisting a program designer to detect program errors, said method comprising:

a division step for dividing each process of a first concurrent program, consisting of a plurality of processes, into a plurality of controllable sections;

a generation step for generating an execution path representing all the possible execution sequences of said sections of each of said processes with the use of branches between said sections;

a selection step for selecting sections at branches in said execution path generated by said generation step; and

a conversion step for converting said first concurrent program to a second concurrent program executing a sequence of said sections according to said execution path consisting of branches of sections selected by said selection step.

3. A system for assisting a program designer to detect program errors, said system comprising:

division means for dividing each process of a first concurrent program, consisting of a plurality of processes, into a plurality of controllable sections;

generation means for generating possible execution paths among all the possible execution sequences of said sections of each of said processes, said possible execution paths including branches in execution sequences of said sections;

selection means for selecting sections at branches in said possible execution paths generated by said generation means; and

conversion means for converting said first concurrent program to a second concurrent program having selected sections at branches being selected by said selection means.

4. A system as claimed in claim 3 wherein said generation means generates an execution path consisting of branches between sections affecting the execution result of said second concurrent program as a result of said selection, said execution path representing the execution sequence of said sections of each process.

5. A system as claimed in claim 4, further comprising an expansion means for expanding said execution path by adding the branches between sections not affecting the execution result of said second concurrent program as a result of said selection.

9. A system as claimed in claim 3 or 6, further comprising execution means for simulating said first concurrent program according to the execution sequence of sections indicated by said execution path created after selection by said selection means.

10. A system as claimed in claim 3 or 6 wherein said conversion is performed by inserting a first instruction for maintaining process synchronization after said section to be executed first with respect to said dependency relation and by inserting a second instruction, corresponding to the first instruction, before said section to be executed next with respect to said dependency relation.

11. A system as claimed in claim 5 or 8 wherein said expansion means comprises:

disassembly means for disassembling said execution path for each process to generate an execution path for each process; and

optimization means for optimizing the execution path of each process by deleting redundant parts,

said conversion means generates said second concurrent program based on each optimized execution path.

12. A system as claimed in claim 5 or 8 wherein said expansion means comprises:

disassembly means for disassembling said execution path for each process to generate an execution path for each process; and

deletion means for deleting redundant parts of the execution path of each process,

said conversion means generates said second concurrent program based on each optimized execution path,

said disassembly means adding synchronization constraints to each execution path to establish synchronization when disassembling said execution path, and

said optimization means removing redundant synchronization constraints from said synchronization constraints.

6. A system for assisting a program designer to detect program errors, said system comprising:

division means for dividing each process of a first concurrent program, consisting of a plurality of processes, into a plurality of controllable sections;

detection means for detecting a dependency relation between said sections;

generation means for generating an execution path representing all the possible execution sequences of said sections of each process with the use of branches between said sections;

selection means for selecting said sections at the branches having a dependency relation; and

conversion means for converting said first concurrent program to a second concurrent program executing a sequence of said sections according to said execution path consisting of branches of sections selected by said selection means.

7. A system as claimed in claim 6 wherein said generation means generates an execution path consisting of branches between sections having said dependency relation, said execution path representing the execution sequence of said sections of each process.

8. A system as claimed in claim 7, further comprising expansion means for expanding said execution path by adding the branches between sections not having said dependency relation.

13. A system for assisting a program designer to detect program errors, said system comprising:

generation means for generating an execution path representing all the possible execution sequences of a plurality of sections, each process of a first concurrent program consisting of said plurality of sections; and

conversion means for converting said first concurrent program to a second concurrent program executing a sequence of said sections according to said execution path generated by said generation means;

expansion means for expanding said execution path by adding branches between sections not having a dependency relation, said expansion means including

disassembly means for disassembling said execution path for each process to generate an execution path for each process; and

deletion means for deleting redundant parts of the execution path of each process,

said conversion means generates said second concurrent program based on each optimized execution path.

14. A system as claimed in claim 13 wherein

said disassembly means adds synchronization constraints to each execution path to establish synchronization when disassembling said execution path, and

said deletion means removes redundant synchronization constraints from said synchronization constraints.

15. A method for assisting a program designer to detect program errors, said method comprising:

a division step for dividing each process of a first concurrent program, consisting of a plurality of processes, into a plurality of controllable sections;

a detection step for detecting a dependency relation between said sections;

a generation step for generating an execution path representing all the possible execution sequences of said sections of each process with the use of branches between said sections;

a selection step for selecting said sections at the branches having a dependency relation; and

a conversion step for converting said first concurrent program to a second concurrent program executing a sequence of said sections according to said execution path, consisting of branches of sections selected by said selection step.

16. A method for assisting a program designer to detect program errors, said method comprising:

a generation step for generating an execution path representing all the possible execution sequences of a plurality of sections, each process of a first concurrent program consisting of said plurality of sections; and

a conversion step for converting said first concurrent program to a second concurrent program executing a sequence of said sections according to said execution path generated by said generation step, wherein said expansion step comprises;

a disassembly step for disassembling said execution path for each process to generate an execution path for each process; and

a deletion step for deleting redundant parts of the execution path of each process, said conversion step generates said second concurrent program based on each optimized execution path.