Victor R. Volkman received a B.S. in computer science from Michigan Technological University in 1986. His areas of interest include database internals, compiler semantics, and graphics applications. He is currently employed as software engineer at Cimage, Inc. of Ann Arbor, Michigan. He can be reached at the HAL 9000 BBS, 313-663-4173, 1200/2400 baud.
Since its introduction in 1985, DESQview has become one of the most popular multitasking environments available for the PC. It provides many of the advanced features of OS/2 without requiring expensive hardware and software, and without forsaking your existing PC-DOS development tools and environment. Environments which fully support multitasking must provide an operating system interface for the application developer. Quarterdeck Office Systems's DESQview Application Program Interface (API) allows C programmers to access its entire set of operating system functions for multitasking, event queues, mailboxes, windows, dialog boxes, and more. C compilers currently supported include Microsoft, Borland, Lattice, Metaware, and Watcom. DESQview APIs are also available for BASIC, Pascal, and database languages.
The DESQview API is especially useful for developing networking and parallel processing simulations. Simulating a network or parallel processing problem helps solidify the algorithms used without tying up expensive resources during development. One problem which I have previously investigated with parallel processing simulators is that of approximating the roots of a function. This problem was first suggested to me in 1986 by Prof. Dave Poplawski of the Michigan Technological University. The roots of the function f(x) are those values of x where f(x) = 0. The most efficient solution is to evenly partition the possible range of the root between competing CPUs. In a simulator, each CPU is modeled by a single task running concurrently with many others. I first implemented my model using the Intel HyperCube simulator on a VAX-11/750 under BSD UNIX 4.2. The ease with which the DESQview API implements the parallel root finder demonstrates the power of DESQview's task management and intertask communication abilities. This article will detail the multitasking features available in the DESQview Application Programming Interface (API) C Library and present a small application in C.
The DESQview Environment
Before delving into the parallel root application, I will explain how DESQview interacts with MS-DOS and your application programs. DESQview is a preemptive multitasker which provides a fixed time-slice to every program running on your computer. When one program uses up its time-slice, DESQview intervenes and switches the context to the next available program waiting in line. In a non-preemptive system such as MS-Windows, the program running in the foreground must explicity relinquish control before others can execute. Each program loaded by DESQview can have its own window with up to 640K available for its MS-DOS session. These windows are mapped into EEMS or EMS 4.0 memory or else swapped to disk when not in use. Although DESQview will run on any PC compatible, it is most effective when teamed up with the built-in memory management capabilities of an 80386 processor.DESQview supports a multitasking interface in three different models: tasks, applications, and processes. The task model allows you to run more than one function in a program simultaneously. These tasks are also referred to as execution threads. To start a new task, call tsk_new() with a pointer to the function for the thread to execute. The only limit to the number of simultaneously executing tasks is the size of your program stack, since the stack for each child task must be allocated only from the parent's stack. DESQview tasks share the same program space, but not the same stack space. Since the parallel root finder requires little stack and heap space, the task model was chosen for multitasking.
The application model is only slightly more sophisticated than the task model. An application can consist of several tasks, each with its own screen window. One window is designated as the foreground window and receives a larger time-slice than the remaining windows by default. Although the windows are all logically related to the same process, they can be physically resized and moved as if they were separate processes. Applications are like tasks in that they are executing within the same program space. An application could be considered to be midway between a task and a process.
The process model allows for the greatest degree of multitasking independence. Each process is allocated its own window with up to 640K for its MS-DOS session. Processes have totally separate program, stack, and heap spaces. Additionally, processes need not even be executing the same program at all, making them ideal for client/server applications such as database servers and print servers. This also implies that processes cannot communicate with global variables. Fortunately, DESQview provides a mailbox facility for communicating between tasks and processes in the system.
Critical Sections And Semaphores
Whenever programs share data in any network or multitasking system, they must use an arbitration system to determine who is allowed to read or write the data. Otherwise, data may be lost or corrupted when two programs attempt to write data to the same place. In a networking scenario, record locking of data files is often sufficient to control access. However, when two tasks want to access the same global variable no such simple metaphor exists. The problem of controlling access to shared program data can be effectively solved using the semaphore control model.Any part of a program which reads or writes shared data could potentially be a critical section. A critical section is a part of a task which must be completed without interruption by the scheduler. If two or more tasks are executing their critical sections simultaneously, then a data collision is an immediate hazard. For example, a bank teller initiates both Task #1 and Task #2 to update my account balance, which is initially $500. Task #1 is supposed to deposit $100 and Task #2 should withdraw $200. Each task will read the balance, modify the balance, and then write back the balance. The two tasks are asynchronous with respect to each other. In Figure 1a, Task #2 overwrites the balance and causes the deposit made by Task #1 to be lost. Figure 1b shows the correct answer when the critical sections which read and write the account balance are respected.
A semaphore is a counter indicating the number of processes attempting to execute a critical section. A software semaphore is like a railroad semaphore that prevents more than one train from entering the same section of track. DESQview provides support for semaphores through the mailbox API calls. The mal_lock() function allows a mailbox to be used as a semaphore. The first task that calls mal_lock() against a mailbox becomes its owner. When other tasks call mal_lock() they are automatically suspended until the owner relinquishes control with a mal_unlock() call. Protecting critical sections is now as simple as surrounding them with calls to mal_lock() and mal_unlock(). The sendv() function in MONITOR.C (Listing 1) is such an example.
The Monitor
A monitor is a set of functions which integrates data structures and functions to control the synchronization of concurrent tasks. A monitor may be implemented with semaphores, events, and messages. Just as a program is an abstract concept for a set of functions, a monitor is an abstraction for interprocess communication. The monitor can hide the low-level implementation details sufficiently so the programmer can safely ignore them.The monitor becomes the central repository for critical sections and shared variables. Since the monitor contains all references to the data structures, they can be reduced to static local variables. Consequently, the tasks access the data only through the monitor and therefore will have no critical sections of their own. The monitor is passive and executes only when called from a task. Figure 2 shows a monitor controlling access from N processes to the shared data.
Hwang and Briggs (1984) considered monitors such a powerful paradigm that they presented a special Pascal-like syntax for describing them. In practice, these constructions require awkward macros that are difficult for the novice to debug. Instead, moving the monitor's global variables and functions into a separate source file is sufficient to hide its implementation. The monitor for the parallel root finder is encapsulated in MONITOR.C and MONITOR.H (see Listing 1 and Listing 2) .
Hwang and Briggs also asserted that any complex system can be decomposed into a set of processes and monitors allowing them to communicate. This decomposition can greatly simplify program maintenance and verification of correctness. When data structures must be changed, it is easy to determine whether the monitor will be affected. New processes and monitors can also be added without upsetting the entire system.
Root Finder: Main Program
A monitor simplifies the job of the parallel root finder. The file FINDROOT.C (Listing 3) contains just three functions: main(), task_findroot(), and f(). Table 1 lists all the DESQview API functions used in the root finder application. The main() function initializes the API, opens a window, starts the tasks, waits for completion, and then displays the results. The first step of initialization is to determine if DESQview is running or not. The api_init() call returns the current DESQview version or zero if DESQview is not active. The api_level() call asserts the version of the API interface you will be using. Setting api_level() ensures upward compatibility with future DESQview versions.After intializing DESQview, the main() function opens a new window for itself which reports status messages on the root finding process. The win_new() function creates a new window based on the window title, height, and width. Next, the win_move() function moves the window into place. The win_logattr() and win_attr() calls ensure the text color is readable. The win_frame() and win_unhide() calls set flags to disable the window border and mark it as displayable. Finally, win_top() redraws the window using all of the attributes and flags set by the previous window calls.
Before starting the tasks, the monitor must be initialized. The open_monitor() function first creates a mailbox to be used strictly as a semaphore, then allocates memory for a MONITOR structure which will track messages passed between tasks. After opening the monitor, a priming MASTER message must be sent through the monitor. This message will be claimed by the first task to find the root in its interval.
Once everything has been initialized, starting the tasks is easy. A call to tsk_new() starts a new task:
task_han = tsk_new(task_findroot, stacks[i], STACKSIZE, " ", 0, 0, 0);The tsk_new() function returns a task handle which can be used to suspend, resume, or abort the task. The first parameter is a pointer to a function returning an integer. More precisely, the parameter should be a pointer to a void function since the return value cannot be accessed. The second parameter is a pointer to the stack for the new task. The child task's stack must be allocated from the parent task's stack. Otherwise, the C compiler's assumptions about the stack segment will be invalid. In FINDROOT.C, a two-dimensional array variable called stacks is declared locally. (An alternative would be to call the MSC function alloca() to allocate a block directly from the stack.) The third parameter specifies the size of the stack available to the child task. The remaining four parameters allow a window to be automatically created when the child task starts up.A task receives its parameters in a mail message. Unlike the C standard library spawn() functions, the DESQview tsk_new function cannot directly pass parameters to the spawned process. Fortunately, you can find a task's mailbox by calling mal_of(), passing the task handle. Calling mal_write() sends a copy of the string to the child:
sprintf(node_str, "%d", i ); mal_write(mal_of(task_han), node_str, sizeof(node_str));Once the tasks are up and running, the main program has nothing to do but wait for the final answer and display the results. The MASTER task is responsible for notifying the main program with the TERMINATE message.
Root Finder: Child Tasks
The real work of root finding takes place in task_findroot(). The only parameter which task_findroot() needs to know is its node number assigned by its parent. Each task computes one value for f(x) and then communicates with its neighbors to find the interval where the root is. Before a task can begin searching for a root, it must know its node number. The node numbers run from zero to NUMPRC-1, where NUMPRC is the number of processes being simulated. The parent task sends the node number to the mailbox of each child task. The child task must first call mal_me() to learn its mailbox handle, then call mal_read() with the mailbox handle to obtain a pointer to the message. Since mal_write() wrote the message, the call to mal_read() returns a pointer to a copy of the message rather than a pointer to the parent's message buffer.After finding its node number, each task opens its own window by calling the API function win_new(). The node number is used to size and position each window so that they don't overlap on the screen. If there are more than four tasks, the windows will be only half the width of the screen. Figure 3 shows a screen dump from a program run with four tasks.
When the child task's window is set up, it enters the main DO loop and computes its f(x) value. Each task is assigned an interval whose size is determined by the global interval of interest divided by the number of nodes:
interv = (global_x1-global_x0)/(NUMPRC);The variables global_x0 and global_x1 are the left and right boundaries respectively of the global interval. The MASTER task will adjust the global interval once during each iteration to narrow the search boundaries. Figures 4a through 4c show how the interval decreases over three iterations. Each task can compute its f(x) value as follows when it knows the left-hand boundary, its node number, and the size of the interval:
y1 = f(global_x0+interv* (node+1));After computation, two asynchronous communications allow a given node to find the function results of its neighbor node. First, all even nodes send their values to their right neighboring node. Second, all odd nodes send their values to their neighbor on the right. Node 0 only has a neighbor to the right and node NUMPRC-1 only has a neighbor on the left. Figure 5 illustrates both stages of the communications. This message passing pattern fits well with hypercube architectures, which require communications to be between adjacent nodes.Finally, each child task must determine if the root lies within its assigned interval. If f(x0) * f(x1) is negative, then f(x) must have crossed the X-axis in that interval. In other words, the root was below the X-axis at one end of the interval and above the X-axis at the other end. This test is unreliable if more than one root appears in any interval. Figure 6 shows that if the line crosses the axis an even number of times in the interval, the test fails. A more advanced root finder would be able to handle multiple roots.
The node that discovers the root computes the new boundary conditions. Note that all other processes must synchronize against this controller node. This synchronization ensures a correctly placed interval for the following iteration. If the MASTER task finds that current interval to be less than EPSILON, then it sends the TERMINATE message instead of relinquishing the MASTER status. These TERMINATE and MASTER messages are not addressed to a specific node but to dummy nodes which can be received from any task. When the main program receives the TERMINATE notification, the child tasks finish and are deallocated.
Root Finder: Inside The Monitor
As mentioned earlier, MONITOR.C and MONITOR.H contain the monitor used for the parallel root finder. This monitor consists only of the functions open_monitor(), close_monitor(), sendv(), and recvl(). You must first call the open_monitor() function to initialize the monitor's data structure. open_monitor() opens a new mailbox, assigns the name requested by the user, and then allocates a monitor structure.The close_monitor() function disables the monitor by closing the mailbox, freeing the monitor structure, and setting the monitor pointer to NULL.
The sendv() and recvl() entry points are the only functions to actually use a semaphore. Both functions attempt to lock the semaphore handle before accessing the variables within their critical sections. The first task to call mal_lock() becomes the owner of the semaphore. Other tasks that attempt to call mal_lock() before the owner calls mal_unlock() are suspended. Tasks in a suspended state must forfeit their timeslices until the expected condition occurs. After taking the semaphore, the sendv() entry point simply records the message value and its destination in the monitor. Finally, sendv() releases the semaphore.
The recvl() function blocks the calling task until a message from the requested node is received. After obtaining the semaphore, recvl() checks whether the message has arrived. If it has not arrived, recvl() releases the semaphore and forfeits the rest of its timeslice via api_pause() in order to avoid a busywait in the task awaiting a message. The recvl() entry point continues its strategy of lock, test, and unlock as long as necessary. When the message finally arrives, the value is copied to the address specified in the val_p parameter. recvl() then unlocks the semaphore so the process can begin again.
Implementation Notes
The DESQview-specific version of the parallel root finder was implemented on a 16MHz 80286 computer running MS-DOS 3.30. The program was developed and tested in conjuction with DESQview version 2.25, but should work fine with any version 2.01 or later. The root finder was compiled with Microsoft C 5.1 and linked with the DESQview API C Library version 1.2.Although the API C Library claims to be reconfigurable to any memory model, I used only the large model (code > 64K, data > 64K) as recommended by Davis (1989). The root finder executable is about 42K excluding stack requirements. Unlike many other windowing and menu packages which could add up to 100K to your application, the DESQview API typically adds less than 10K of overhead, since most API functions are stubs that pass the parameters along to the DESQview kernel. This stub approach is similar in concept to the Dynamic Link Library (DLL) of OS/2, but requires that DESQview be resident in memory before a program can call API functions.
Conclusion
With the recent introduction of multiple-CPU 80386 computers by Zenith, Compaq and others, the development of parallel programs has jumped from the theoretical to the practical. Since the cost of parallel computers will always exceed the cost of single-CPU computers, simulating parallel algorithms with a multitasking system remains an attractive development alternative.The parallel root finder demonstrates the ease with which multitasking programs can be developed using the DESQview API C library. The root finder also takes advantage of the intertask communication and windowing capabilites of the API. The DESQview API can also manage many other aspects of your application environment including event queues, dialog boxes, keyboards, mice, timers, and scheduling. You can be certain the DESQview API will continue to play a role in extending the capabilities of MS-DOS programs in the 1990s.
Annotated Bibliography
Davis, Stephen R., DESQview: A Guide to Programming the DESQview Multitasking Environment, Redwood City, CA: M&T Publishing Inc., 1989.The definitive tutorial for those interested in writing applications to use the full power of DESQview. Davis covers windowing, multitasking, interprocess communication, generalized message input, memory management, critical sections, and semaphores. Unfortunately, it does not include a complete catalog of the function library.
DESQview API C Library, Santa Monica, CA, Quarterdeck Office Systems, 1988.
Covers the Applications Programming Interface (API) for C. A complete alphabetical listing of all API functions, parameters, descriptions, and return values is provided. Several DESQview-specific programs demonstrate intertask communication, process creation, timers, menus and event handling.
Hitt, Frederick J. "Drawing Out DESQview Power", PC Tech Journal, April 1989, pp. 47-61.
Covers the entire set of API functions in a relatively short space. Hitt covers many of the low-level details of multitasking and how it is enhanced with the 80386. There is also a practical list of do's and don'ts for controlling multitasking programs. No source programs are provided.
Hwang, Kai and Briggs, Fay, Computer Architecture and Parallel Processing, New York, NY, McGraw-Hill Inc., 1984. pp. 570-577.
A textbook that includes many dissections of parallel computer and supercomputer architectures. It provides a thorough survey of memory, I/O, pipelining, vector processing, array processors, multiprocessor systems, and data flow computers. Software techniques, such as semaphores and monitors, for effectively utilizing parallel processing are emphasized at each step.
Parker, Tim. "Software Review: DESQview 2.2, API Toolkit", Computer Language, Vol. 6, No. 4, April 1989, pp. 115-118.
A user report divided between the DESQview 2.2 environment and the DESQview API Toolkits for C and Pascal. Parker gives an accurate account of the major features of DESQview 2.2 and how they work. Additionally, he presents a very simple overview of the API functions, API Debugger, and API Panel Design Tool.