Computer-Based Problem Solving Process

The following sections are included:

• Dedication
• Preface
• Contents

System software is a collection of software tools with the goal of making computers convenient and efficient by:

• allowing programmers to develop programs using a human logic;
• allowing hardware to execute programs using a machine logic…

To understand how can one carry out actions that handle software systems (in software) we examine first how can one handle formal systems (in mathematics). We use set theory [Enderton (1977)] to discuss formal systems.

An ad hoc system S is a tuple S = 〈D;r〉 where D is a collection of objects and r is a relationship in D such that:

• Objects (or elements) of D may not be specified by rules of math (not yet). For example, C programs are not specified by the rules of math.
• Rules r of interaction in S may not be defined mathematically. For example, relations between functions making up a C program are not formally defined.
• Behavior of the system may not be specified by mathematical functions. For example, the behavior of a process executing a program is in general not a function.

However, we handle ad hoc systems. For a complete specification, ad hoc systems should be characterized by the rules of math. Unfortunately, ad hoc systems are not constructed from ideal (mathematical) objects. Rather, ad hoc systems are models of behavior (representations) of real and very heterogeneous objects — sometimes expensive…

The most common systems in computer science are probably the state transition systems related to the finite automata theory [Hopcroft and Ullman (1979)]. However, while state transition systems are used as models of computation in general, transition systems are more appropriate as model of computations as performed by a computer. We follow Manna and Pnueli [Manna and Pnueli (1992)] to discuss this concept in the framework of system software.

This part of the book presents the architecture and functionality of the hardware of a computer platform as an ad-hoc system. We do this using the systematic approach for ad-hoc system construction developed in the Chapter 3, which iterates the following actions:

• (1) Define the major behavior of the system;
• (2) Identify system components performing the system behavior;
• (3) Specify the functional behavior of system components;
• (4) Develop an (algorithmic) expression of the system in terms of components at (2) performing the actions specified at (3);

until system performs according to its major behavior specified at (1).

The following sections are included:

• Functional Behavior of Memory
  • Memory control unit
  • Memory simulation
  • Memory hierarchy
  • Sharing memory
  • Fair server for memory simulation
• Functional Behavior of Processor Components
• Functional Behavior of Control Processors
• I/O Devices
  • Implicit TestDevice
  • Explicit TestDevice
  • Automatic TestDevice
• Multi-Programming
  • Efficiency of a hardware system

Step 4 of the systematic approach requires an algorithmic expression for the behavior of the system in terms of its components. The algorithmic expression of a hardware system using SSL is…

We need to emphasize the importance of the algorithmic expression of a computer system, developed previously as an ad hoc system, over and over in this text, thus justifying the computer use as a universal problem solving tool. Therefore, though redundantly, we start the discussion of computer based problem solving methodology by the reproduction of this expression…

System software tools are programs which manipulate processes, software resources, hardware resources, and events. Processes are abstractions that represent computations performed by hardware. Software resources are programs written in various PL-s, data, and documents. Hardware resources are processors, memories, devices. Events, are interrupts, exceptions, and messages that occur during program execution. We dedicate this chapter to the software tools used to manipulate processes.

Various programs existent in memory at a given time require memory to be partitioned among computer users. The two main memory partitions are system memory area, occupied by programs in system software and user memory area, which is the memory available for user programs. While system memory area remains occupied by the same programs over long periods, the user memory area changes continuously…

As in the case of processor and memory, to manipulate I/O devices by program they need to be represented as data. To develop a device data representation we first look at the device functional characterization.

Unlike other computer resources, which are tangible entities and require management tools, computation performed by a computer platform is not tangible. It is a dynamic abstraction observable through the effect the events that occur during a computation task have on the other resources of the system. For example, an interrupt event may result in a switch-context operation (see section 9.8), an exception may result in the increase or decrease of the resources allocated to the currently running program, a message may result in complete change of computation configuration. Therefore, software tools that manage computation activity actually manipulate the events that may occur during computation and have the goal to preserve computation consistency and to maintain the computer busy as long as possible.

CBPSP consist of rules that allow computer users to solve problems using computers. According to the services it provides, CBPSP is implemented by two classes of tools:

• Tools that manage computer resources and the events that arrive during program executions. These tools belong to the Execution Support Environment (ESP). They are organized as libraries of system functions that can be called by program execution process.
• Tools that allow computer user to map problems and problem solving algorithms into computer programs. These tools belongs to the Programming Support Environment (PSE). The execution of these tools is spawned by computer user using commands of a control language.

We examined the development of ESE tools in Part 3 of this book. Here we examine the design and evolution of PSE tools which are called System Programs (SP). More recent computer based problem solving methodology is identified with the process of program development. Therefore the collection of system programs are also called Problem Solving Environment. So here the acronym PSE is dually used. Collectively we refer to the ESE and PSE as software tools.

WBPSP is an extension of computer based problem solving process by developing software tools dedicated to problem domain experts. That is, during WBPSP, while solving a problem of the domain D, problem solver can use a Domain Algorithmic Language (DAL(D)), characteristic to the domain, instead of using a programming language. Looking back at the CBPSP, this means that problem solver executes problem solving algorithms using her own brain instead of converting them into programs to be executed by the computer. This can be done because with WBPSP the computer is used by problem solver as a “brain assistant” that perform the operations involved in the problem solving algorithm upon the problem solver requests. In other words, problem solver communicates with her computer using her natural language. But natural language evolves dynamically with problem domain and it is strongly ambiguous. This was the reason to interpose translators from domain language to the computer language, i.e., programming, in the problem solving process in the first place. However, looking carefully at this situation we observe that the problem lies in the requirement that programming languages be Turing complete. That is, programming languages have been developed as universal problem solving tools. On the other hand human oriented problem solving is domain characteristic. For a given problem domain (such as mathematics, physics, chemistry, engineering, business, etc.) problem solving algorithm uses a DAL, which is a fragment of natural language spoken by the problem domain experts. Domain algorithmic languages are learned by domain experts during their domain education process and their ambiguities are removed by the domain context. Therefore if a DAL is formally defined and if every concept employed by a DAL algorithm is associated with a computer artifact representing its computational meaning in the domain, DAL expressions can be evaluated by problem solver using a computer in a similar way in which an arithmetic expression is evaluated using a calculator. Moreover, if the domain concept represented by a DAL algorithm that solves certain problem P is automatically associated with the computer program performing that algorithm as the concept's meaning, then DAL evolves with problem domain. Consequently the computer becomes a cognitive tool used by problem solver as a brain assistant during problem solving process…

Software tool design and implementation may be very complex. The best illustration of a software tool is the design and implementation of a translator. This is because we understand and use translators which are mappings Translator : SL → TL where SL is a languages called the Source Language, and TL is another language called the Target Language. If SL and TL are computer languages, depending upon their level of abstraction, the Translator is called a Compiler, an Interpreter, an Assembler, and/or a Loader/linker. The algorithm performing the mapping depends on our ability to structure SL and TL as mathematical abstractions. Further in this chapter we discuss the compiler implementation as a problem solved during WBPSP where the domain of expertise is Programming Languages. Hence, DAL for us is any programming language one would like to chose to express the compiler implementation algorithm. However, we hope this discussion to be a model for the Web-Based Problem Solving Process carried out for other problem domains.

Programs are programming language expressions developed by people (programmers) who are experts on the syntax and the semantic rules defining the programming language they use. However, since program development is a human activity, according to the Latin proverb “errare humanum est”, which translates in “to err is human”, a program may contain errors. So, the problem faced by software developers becomes the development of tools that allow programmers to create correct programs during computer based problem solving process. For that the software developers need first to define the meaning of the expression “correct program”. Since programs are algorithms expressed using programming languages, the program correctness becomes the correctness of the algorithms they represent. But irrespective whether we talk about the correctness of the algorithm or of the program, we need to remember that programs (or algorithms) are language expressions. And as language expressions they may contain two kind of errors: syntactic errors and semantic errors. Syntactic errors are violations of the language syntax during program development. Since language syntax is usually formally specified, syntax errors can be handled by the compiler. Semantic errors however are more difficult to handle…

The problem solving methodology using a computer is a process that evolves on the following steps:

• Formulate the problem;
• Formalize the problem;
• Develop an algorithm that solves the problem;
• Program the algorithm (i.e., encode the algorithm as a valid program of a programming language available on the computer);
• Compile the program thus obtained;
• Load and link the compiled program;
• Run the program;
• Use the results in the universe of discourse.

The use of the first man-made computer for problem solving was performed by the programmer and is summarized in Figure 17.1…

The computing environment of CP allows two types of programs to coexist in main memory: system programs, that perform actions initiated by CP, and user programs, that perform user computations. They must cooperate while executing a job. However, while performing their functions these programs perform destructive operations, such as read(JobFile) which can replace the contents of a memory area with the information read from the JobFile, thus destroying information stored in computer memory. The destruction of information would be a consequence of user programs and system programs violating their interaction protocol. For example, a user program may input a data record into a buffer that covers a portion of a system program memory area. A system program may input a control record into a buffer that covers a portion of a user program memory area. How can we prevent such situations…

The mode bit and the interrupt mechanism are used to enforce a controlled communication between the BOS and the programs initiated by BOS, (among which the user program is). They cannot provide protection against malicious actions that the agents that share the computer can exercise against each other.

Timing program execution is particularly important to avoid the infinite looping of a program, thus preventing the denial of service aspect of system security. It is of equal interest when computation time becomes a shared resource of the computer platforms as required by real-time applications and time-sharing systems. Timing program execution requires a new architectural change which consists of providing hardware support for clocks and appropriate software support to manipulate these clocks. Hardware support for timing program execution consists of two kind of time measuring gadgets called clocks and timers. Clock registers (CLK) are used to time instruction execution and Timer registers (TMR) are used to time program execution. Clocks and timers behave similarly, they interrupt computation after each time unit they can measure…

BOS has been developed as an automaton that controls the operation of a computing system consisting of: an operator batching jobs at one end of a JobFile, a computer which processes jobs from the other end of the JobFile, and devices that perform I/O operations encoded in the records of that JobFile. BOS evolved by automating the procedure performed by a human operator controlling the system while answering such questions as: is this automaton correct? and is this automaton reliable?. However, since computer is an expensive tool used by humans during problem solving process, questions such as: is this automaton efficient?, is this automaton convenient?, and does this automaton evolve with problem domains?, need also be answered.

Computer based problem solving process evolved the BOS to perform the action…

A real-time system is a computing system that interacts in real-time with its environment. Real-time systems are used as control devices in dedicated applications. Examples such applications are surgical operations, aircraft control, industrial plant control, embedded-devices in house-hold appliances, etc. Software systems which control these applications are real-time systems also called control devices…

The following sections are included:

• Bibliography
• Index