Open source Linux has become increasingly popular as a vehicle for incorporating hands-on experience with a real system into both undergraduate and graduate operating systems courses. System virtualization tools, such as VMWare, Xen, VirtualBox, and KVM, allow students to freely experiment with kernel modifications without requiring dedicated hardware and without generating significant concern for the ill-effects of system crashes. Nevertheless, certain kernel projects that are highly desirable from an educational standpoint remain unavailable under standard approaches to virtualization. One such project that is known to carry substantial instructional value is the design and implementation of an SMP-safe driver for a high-performance graphics card. Standard virtualization tools export only a minimally-capable, SVGA graphics adapter, which is an inadequate architecture for such a project. This paper describes an extremely simple, kernel-independent, software tool for use by instructors of operating systems courses. The tool provides a virtual, high-performance graphics card that is suitable for Linux device driver design and implementation. The code for the virtual card, which is relatively short, is easily modified by instructors to present different interfaces each semester. The code for both the virtual card and a sample Linux 3.2.36 driver for it may be freely downloaded from http://people.cs.clemson.edu/~ccorsi/kyouko/.

The TEXNH method is an approach to undergraduate computer science education that is based on cognitive constructivisim, in the sense of Piaget, and which invokes several course design directives that include re-combining art and science, problem-based learning, problem selection from the visual problem domain, and cognitive apprenticeship. The paper describes a new TEXNH course in data structures. It includes a full comparative assessment of the realized improvement in student problem solving capability and, for the first time, cognitive authenticity in problem selection, in that the course problem is a variation on a very recent research result.

The τεΧνη project, which provides an unusual alternative to the standard design of the computing curriculum for the bachelor's degree in computer science, is now entering full-scale implementation at Clemson University. The approach relies extensively on problem-based instruction, computer graphics, and the notion of cognitive apprenticeship. The novelty arises from the magnitude and origin of the problems to be integrated into the curriculum and the breadth of impact across the curriculum. The first three courses in the new curriculum are now being taught. The design of each course is described, and preliminary assessments from earlier trial sessions of the first two courses are offered.

Color images have a gamut that typically spans three dimensions. Nevertheless, several important applications, such as the creation of grayscale images for printing and the re-coloring of images for color-deficient viewers, require a reduction of gamut dimension. This paper describes a technique for preserving visual detail while reducing gamut dimension. The technique is derived by focusing on the problem of converting color images to grayscale. A straightforward extension is then provided that allows re-coloring images for color-deficient viewers. Care is taken so that the resulting images remain within the available gamut and visual artifacts are not introduced. Categories and Subject Descriptors (according to ACM CCS): Enhancement-Filtering I.4.3 [Image Processing and Computer Vision]:

A new approach to the design of the computing curriculum for a Bachelor of Arts degree is described. The approach relies extensively on problem-based instruction and computer graphics to teach key concepts in computer science. The novelty arises from the magnitude and origin of the problems to be integrated into the curriculum and the breadth of the impact across the curriculum. Results from a trial course, the first experiment with the new approach, are described. The course, Tools and Techniques for Software Development, is a sophomore-level course in programming methodology. Construction of a ray-tracing system (for generating synthetic images) was the vehicle chosen for the instruction.

We discuss the role of modeling in the design and validation of life-critical, real-time systems. The basics of Markov, Markov reward, and stochastic reward net models are covered. An example of a nuclear power plant cooling system is developed in detail. Multilevel models, model calibration, and model validation are also discussed.>

A mathematical framework for digital halfloning is proposed.Two models for digital halftoning are provided, one based on maximum-entropy Gibbs measures and one based on reversible Markov chains.The models are seen to be equivalent.This equivalence induces an equivalence between two associated halftoning algorithms, one based on neural networks and one based on simulated annealing.These algorithms are seen to provide halftone images that are preferable to those obtained by standard techniques.

Binary optimization models for the design of distributed, fault-tolerant computing systems are considered, with a focus on the task allocation and file assignment modeling schema proposed by J. Bannister and K. Trivedi (Proc. Second Symp. on Reliability in Distributed Software and Database Systems, 1982). It is shown that R. Graham's (1969) partitioning algorithm, S, when applied to this schema can, in the case of finite resources, yield allocations that are arbitrarily poor with respect to the optimum allocation. This contrasts sharply with the case of ample resources, where S provides allocations that are provably close to the optimum. Two alternative allocation algorithms are suggested. Both are seen to deliver allocations preferable to those provided by S, but at some additional computational expense.>

A simulation-based method for obtaining numerical estimates of the reliability of N-version, real-time software is proposed. An extended stochastic Petri net is used to represent the synchronization structure of N versions of the software, where dependencies among versions are modeled through correlated sampling of module execution times. The distributions of execution times are derived from automatically generated test cases that are based on mutation testing. Since these test cases are designed to reveal software faults, the associated execution times and reliability estimates are likely to be conservative. Experimental results using specifications for NASA's planetary lander control software suggest that mutation-based testing could hold greater potential for enhancing reliability than the desirable but perhaps unachievable goal of independence among N versions. Nevertheless, some support for N-version enhancement of high-quality, mutation-tested code is also offered. Mutation analysis could also be valuable in the design of fault-tolerant software systems.>

The foundational structure of a new model of user perception of computer system response time is proposed. It is suggested that the development of such a model is now of central importance to the computer system configuration design effort. The new model is seen to explain the success of an earlier measure, designed for the non-interactive environment, in predicting user estimates of response time for interactive systems. The results of new empirical studies, designed to delineate specific components of the model, are also discussed.

A variety of disk scheduling algorithms, including some newly defined ones, are compared both in simulation and in tests on a real machine running UNIX* System V. In the real system tests, first-come first-served (FCFS), shortest seek time first (SSTF), and the standard System V algorithm (SVS) are all seen to yield relatively poor mean waiting time performance when compared to the VSCAN(0.2) algorithm and modifications thereof suggested by Coffman. Nevertheless, each is seen to excel along a particular performance dimension. The adequacy of open, Poisson arrival simulation models in predicting disk scheduling performance is questioned, and an alternative arrival model is suggested which offers improved predictions in the System V environment.

A continuum of disk scheduling algorithms, V( R ), having endpoints V(0) = SSTF and V(1) = SCAN, is defined. V( R ) maintains a current SCAN direction (in or out) and services next the request with the smallest effective distance. The effective distance of a request that lies in the current direction is its physical distance (in cylinders) from the read/write head. The effective distance of a request in the opposite direction is its physical distance plus R x (total number of cylinders on the disk). By use of simulation methods, it is shown that this definitional continuum also provides a continuum in performance, both with respect to the mean and with respect to the standard deviation of request waiting time. For objective functions that are linear combinations of the two measures, μ w + ko w , intermediate points of the continuum are seen to provide performance uniformly superior to both SSTF and SCAN. A method of implementing V( R ) and the results of its experimental use in a real system are presented.

Provably conservative (and optimistic) reliability models can be systematically derived from more complex models. These derived models incorporate a reduced state space and fewer transitions, and, therefore, have solutions that are more cost- effective than those of the original complex models. The designer can extensively explore the design space without incurring the expense of solving multiple complex models. A conservative- optimistic pair of derived models produces a band that includes the solution to the complex model. Sensitivity analysis can be performed on this pair of models to determine those parameters of the original model that are most sensitive to change (i.e., uncertainty) and hence warrant further expense in obtaining tighter specifications.

A review and a critical evaluation of a representative class of state-of-the-art models for ultrahigh reliability prediction is presented. This evaluation naturally leads us to a new model for ultrahigh reliability prediction now under development. The new model combines the flexibility and accuracy of simulation with the speed of analytic models.

An optimization model is developed for assigning a fixed set of files across an assemblage of storage devices so as to maximize system throughput. Multiple levels of executable memories and distinct record sizes for separate files are allowed. Through the use of this model, a general class of file assignment problems is reduced to the optimization of a convex function over a convex feasible region. A high-speed search procedure specifically tailored to solve this optimization problem is then presented, along with numerical examples from real systems which demonstrate orders of magnitude improvement in execution time over existing routines for solving the file-assignment problem. The optimal device capacity selection problem is then solved by simply calling the file assignment routine for each candidate set of device capacities.