【免费】(首次提出Capability)ProgramSemantics_DennisvanHorn（CACM66）1资源-CSDN文库

需积分: 0 102 浏览量 2022-08-03 15:37:41 上传评论收藏 1.4MB PDF 举报

资源详情

资源评论

资源推荐

matic problem which will strongly influence coming pro-

gramming languages. Not only will conversational fea-

tures

be essential, there may even be a trend back from all

too sophisticated language systems to the simple pointing

with a light-pen. Pointing has always been one of the

safest ways to convey information.

We come back to Wittgenstein and his principle of

speaking clearly or not speaking at all. Since we know that

it is the computer which we can make speak arbitrarily

clearly, we possibly should try to let the computer speak

more and more and to restrict the human user in the

practical situation to point at YES or NO, or some more

equally simple choices, while the computer talks. This may

sound like science fiction today, but it could really be true

that one day this will become the central application of

pragmatics around the computer.

REFERENCES

1. PEIRCE, C. S. Collected Papers• Harvard Press, Cambridge,

Mass. Vol. 1-6, 1931-1935.

Philosophical Writings. (J. Buchler, Ed.). Routledge

and Kegan Paul, London, 1940; or Dover Publications, New

York, 1955; 368 pp.

2. BOCttENSKI, I. M. A History of Formal Logic. U. of Notre

Dame Press, Notre Dame, Indiana, 1961; pp. 99-100.

3. MORRIS, C. Foundations of the theory of signs. In Interna-

tional Encyclopedia of Unified Science, Vol. 1, No. 2, Uni-

versity of Chicago Press, Chicago, 1938.

4. --. Signs, Language, and Behavior. G. Braziller, New York,

1955.

5. BOLTZMANN, L. Vorlesungen ueber Gastheorie, 1. Theil,

Paragraph 6. Mathematische Bedeutung der Groesse H,

J. A. Barth, Leipzig, 1895, pp. 38-42.

6• SHANNON, C.E. A mathematical theory of communication.

Bell System Tech. J. 27 (1948), 379-433; 623-656.

7. KRAFT, V. Der Wiener Kreis. Springer Verlag, Vienna, 1950.

8• WITTGENSTEIN, L. Tractatus Logico-Philosophicus. First

Print in German, 1921; in English: Routledge and Kegan

Paul, London, 1922.

9. SCHLICK, M. Gesammelte Aufsaetze. Gerold and Co., Vienna,

1938.

10. FEIGI~, H. Logical empirism. InTwentieth Century Philosophy

(D. D. Runes, Ed.), Philosophical Library, New York, 1943,

pp. 373-416.

11. CARNAP, R. The Logical Syntax of Language. First print in

German, 1934; in English: Harcourt Brace and Co., New

York, 1937.

12. --. Introduction to Semantics• Harvard University Press,

Cambridge, Mass., 1942.

13. Formal Language Description Languages (T. B. Steel, Jr., Ed.).

Proc. of the IFIP Working Conf., Vienna, 1964; North Hol-

land, Amsterdam 1966.

14. GORN, S. Some basic terminology connected with mechanical

languages and their processors• Comm. ACM 4 (1961), 336-

339.

15. --. Mechanical pragmatics: a time motion study of a mini-

ature mechanical linguistic system. Comm. ACM 5 (1962),

576-589.

16.--. Semiotic relationships in ambiguously stratified lan-

guage systems. Presented at the Internat. Colloq. for Al-

gebraic Linguistics and Automata Theory, Jerusalem, 1964.

17. MARTIN, R.M. Towards a Systematic Pragmatics--Studies in

Logics. North Holland, Amsterdam, 1959.

Programming Semantics for Multiprogrammed

Computations

Jack B. Dennis and Earl C. Van Horn

Massachusetts Institute of Technology, Cambridge, Massachusetts

The semantics are defined for

a number

of meta-instructions

which perform operations essential to the writing of programs

in multiprogrammed computer systems. These meta-instructions

relate to parallel processing, protection of separate computa-

tions, program debugging, and the sharing among users of

memory segments and other computing objects, the names of

which are hierarchically structured. The language sophistica-

tion contemplated is midway between an assembly language

and an advanced algebraic language.

Presented at an ACM Programming Languages and Pragmatics

Conference, San Dimas, California, August 1965.

Work reported herein was supported by Project MAC, an MIT

research program sponsored by the Advanced Research Projects

Agency, Department of Defense, under Office of Naval Research

Contract Number Nonr-4102(01). Reproduction in whole or in

part is permitted for any purpose of the United States Govern-

ment•

Volume

9 / Number 3 / March, 1966

Introduction

An increasing percentage of computation activity will

be carried out by multiprogrammed computer systems.

Such systems are characterized by the application of com-

putation resources (processing capacity, main memory,

file storage, peripheral equipment) to many separate but

concurrently operating computations.

We can cite three quite different examples of multipro-

grammed computer systems to illustrate their diversity of

application. The American Airlines SABRE passenger

record system couples ticketing agents at dispersed offices

to a central data file [1]. The computer support systems of

NASA provide real time control and monitoring of manned

space flights [2]. The Project MAC time-sharing system

permits research workers closer interaction with the powers

of automatic computation [3]. Although these are all on-

line systems, multiprogramming techniques have also been

Communications of the ACM 143

used successfully in systems that perform computations on

an offiine, job-shop basis.

We review some of the distinctive properties of a multi-

programmed computer system (MCS), and then introduce

some concepts and terminology that have proven useful ill

studying the properties of multiprogrammed computa-

tions. As we proceed, we define a number of meta-in-

structions that embody powers mostly absent from con-

temporary programming languages, but essential to the

implementation of computation processes in an MCS.

These powers relate to (1) parallel processing, (2) naming

objects of computation, and (3) protection of computing

entities from unauthorized access. The character of these

meta-instructions is such that they might form part of a

language intermediate in sophistication between an as-

sembly language and an advanced algebraic language for

an MCS. In fact, the semantics of these meta-instructions

could be incorporated in the definition of an intermediate

language that might be employed at some stage in the

translation of a more advanced language.

We do not claim completeness for the set of meta-

instructions to be described. Additional operations will

prove necessary in practice for a specific MCS. In particu-

lar, no means is discussed whereby an object computation

may advise the supervisor of special scheduling or alloca-

tion requirements. Also, conventions for dynamic control

of segment length have been omitted.

Properties of Multiprogrammed Computer Systems

Five properties of multiprogrammed computer systems

are important to the present discussion.

(1) Computation processes are in concurrent operation

for more than one user. A multiprogrammed computer

System is generally the creation of many individuals work-

ing in part toward a common objective and in part for

private goals. A successful MCS must include mechanisms

for preventing undesired interference among computations.

(2) Many computations share pools of resources in a

flexible way. In consequence, the individual planner of a

computation need not be concerned about efficiently using

a certain fixed amount of memory and processing capacity

which would otherwise go to waste. Resources not used by

one computation are available to other concurrent compu-

tations.

(3) Individual computations vary widely in their de-

mands for computing resources in the course of time.

An MCS must have mechanisms (explicit or implicit)

through which a computation may request and release re-

sources according to need. Where many computations are

active, which are not closely coupled in their demands for

resources, the peak demands of some computations will

coincide with the slack demands of others. As the number

of computations in the system is increased, the instan-

taneous total demand for resources will hover closer to

the sum of the individual average demands. Therefore,

the amount of physical resources required in such an MCS

is governed by the average demand over all computations

rather than by the sum of their peak demands.

144 Communications of the ACM

(4) Reference to common information by separate com-

putations is a frequent occurrence.

In an MCS it is advantageous to allow information to

be common among computations proceeding for different

users to avoid needless duplication of procedures and data.

Also, communication among separately planned com-

putations is essential to many MCS objectives. Further-

more, the sharing of a peripheral device by several com-

putations is sometimes required.

(5) An MCS must evolve to meet changing require-

ments.

An MCS does not exist in a static environment. Chang-

ing objectives, increased demand for use, added functions,

improved algorithms and new technologies all call for

flexible evolution of the system, both as a configuration of

equipment and as a collection of programs.

To meet the requirements of flexibility of capacity and

of reliability, the most natural form of an MCS is as a

modular multiprocessor system arranged so that proces-

sors, memory modules and file storage units may be added,

removed or replaced in accordance with changing require-

ments [4].

Concepts and Terminology

Segments. The smallest unit of stored information that

is of interest in the present discussion is called a word. An

ordered set of words grouped together for purposes of

naming is called a segment. A segment is created at some

point in time and has a definite length (which may vary

with time) at any instant of its existence.

Any reference by a computation to data or procedure

information is specified by a word name, w = [i, a], con-

sisting of the index number i of the segment containing the

desired word and a word address a giving the position of the

word within the segment. The index number may be

thought of as an abbreviation for the name of the segment.

The correspondence between an index number and a name

is established by meta-instructions which will be defined

subsequently.

In the programming examples (which are written ill a

pseudo-ALGoL format) variable identifiers, array identifiers

and labels will stand for word names. Word names are

written here as [i, a] only when the index number must be

explicitly mentioned.

The concept of segment has influenced the design of a

commercial computer (the Burroughs B5500), an experi-

mental machine [5] and one military system (the Bur-

roughs D825). The use of segments in software systems is

discussed by Greenfield [6], Holt [7] and others. The design

of addressing mechanisms for MCS's is discussed by

Dennis [8]. A fuller implementation of these concepts in a

machine organization has been discussed by Glaser,

Couleur and Oliver [9], and interesting work in a similar

direction is in progress at the MIT Lincoln Laboratory

[10], IBM [11] and is continuing at Burroughs [12].

Protection. In an MCS, a computation must be denied

access to memory words and other objects of computation

unless access is authorized. In particular, it seems natural

Volume 9 / Number 3 / March, 1966

to implement memory protection on a segment basis. Thus,

we think of a computation as proceeding within some

sphere of protection [13] specified by a list of capabilities or

C-list for short. Each capability in a C-list locates by

means of a pointer 1 some computing object, and indicates

the actions that the computation may perform with re-

spect to that object. Among these capabilities there are

usually several segment capabilities, which designate seg-

ments that may be referenced by the computation and

also give, by means of access indicators, an indication of

the kind of reference permitted:

X executable as procedure including internal read references

for constants.

R readable as data but not executable.

XR executable as procedure and readable as data.

RW readable and writeable as data.

XRW executable as procedure and readable and writeable as

data.

Other types of capability are also permitted in the C-list

of a computation, and are introduced in the discussion as

appropriate. Every capability contains an ownership

indicator (O for owned, 1N for not owned). Computations

have broad powers with respect to owned computing ob-

jects, through mechanisms to be described. In the case of

an owned segment, for example, a computation may

delete the segment, and grant or deny other computations

access to the segment.

During the execution of a computation, capabilities

will frequently be added to and deleted from the C-list

defining its sphere of protection through the use of recta-

instructions to be described in later sections. The linear

subscript of a capability within a C-list is called its index-

number. It is through the use of the index number that the

capability is exercised by processes. For example, a seg-

ment is referenced by giving the index number of the seg-

ment in a word name. We assume that the allocation of

these index numbers is carried out by the system (i.e., the

supervisor program) during the execution of an object

computation.

Processes. We consider that the system hardware com-

prises one or more processors, which we can identify as

being distinct from the main memory, the file storage de-

vices and the input/output devices. Each processor is

capable of executing algorithms that are specified by se-

quences of instructions. A process is a locus of control

within an instruction sequence. That is, a process is that

abstract entity which moves through the instructions of a

procedure as the procedure is executed by a processor.

In a physical computer system a process is represented

by the information that must be loaded into a processor in

The term "pointer" is used here because of its familiarity to

most workers. The permanent representation of a pointer should

not be a hardware address in the machine (main or auxilary

storage), as it is essential that the entire naming structure be

independent of physical device addresses if reallocation of storage

media is to be feasible. The authors suggest the association of a

unique code (called an effective name in [13]) with each computing

entity (segment, directory, etc.), which is assigned at the time the

entity is created.

order to continue execution of the successive instructions

encountered by the process. We call this set of information

the state word of the process, and note that it must not only

contain the accumulator words, index words and the word

name of the next instruction to be executed, but must also

indicate the C-list applicable to the computation to which

the process belongs.

A process is said to be running if its state word is con-

tained in a processor which is running. A process is called

ready if it could be placed in execution by a processor if one

were free. Running and ready processes are said to be

active. A process that is not active is suspended and is

awaiting activation by an external event, such as the com-

pletion of an i/o function.

Computations. Loosely speaking, a computation may

be thought of as a set of processes that are working to-

gether harmoniously on the same problem or job. More

precisely, we define a computation to be a set of processes

having a common C-list such that all processes using that

same C-list are members of the same computation.

Notice that two processes having separate C-lists are

always members of separate computations, even though

these C-lists might describe the same set of capabilities.

Notice also that there exist one-to-one correspondences

among computations, spheres of protection and C-lists;

each computation operates within the restrictions of a

unique sphere of protection that is specified by a unique

C-list. The relationship among these entities is shown

schematically in Figure 1.

C-LIST

,••....

SEGMENT

CAPABILITY

•

.~.-----'---"-,SEGMENT

CAPABILITY

: Z

CESS\~

\ PROCESS

\ /

, \ /

COMPUTATION

F~G. 1. A computation

Principals. The ordinary notion of a user of an MCS is

of an individual who requests computing service from an

MCS, or who interacts with a time-shared MCS from a

console. We generalize this notion by defining the term

principal to mean an individual or group of individuals to

whom charges are made for the expenditure of system

resources. In particular a principal is charged for resources

consumed by computations running on his behalf. A prim

eipal is also charged for retention in the system of a set of

computing entities called retained objects, which may be

program and data segments, for example. The structure

and identification of these retained objects is discussed in

a later paragraph.

We can clarify our notion of a principal by giving some

examples. Each individual user of the MAC time-sharing

system acts as a principal, since he is able to utilize system

resources to achieve any personal goal--restricted only by

Volume 9 / Number 3 / March, 1966 Communications of the ACM 145

剩余12页未读，继续阅读

评论收藏

内容反馈

woo静

粉丝: 23
资源: 347

(首次提出Capability)ProgramSemantics_DennisvanHorn（CACM 66）1

评论0

最新资源

(首次提出Capability)ProgramSemantics_DennisvanHorn（CACM 66）1

评论0

DFIG Capability.rar_DFIG Capability_capability curve_dfig

capability_vrf-lite的作用

Business Capability Modeling_ Capability mapping best practices.pdf

How_Linux_Capability_Works

信息安全_数据安全_ast1-r02-cybersecurity_capability_read.pdf

Power-Handling-Capability.rar_The Power_capability curve

Process_Capability_and_Performance

the_art_of_capability_planning

acquire-deduction-capability.rar_made_party9cg_silence3ya_进程与线程

irods_capability_automated_ingest

一个win32下的ARM开源编译器

UECapabilityInformation.pdf

People Capability Maturity Model

The Cooperative Engagement Capability.pdf

1.Capability配置简介1

CMMI(Capability Maturity Model Integration)培训资料

Improving the load-following capability of a solid oxide fuel cell system

face3（Future Airborne Capability Environment）规范

SCP1:SCP v1

VM-Pro通用化视觉系统框架V1.6

net framework4.0和4.5开发包（用于visual studio 2022 安装net旧版本）

串口侦听 串口监听 不占用串口 不占用串口的监听

【C#源码】TCP+串口通信的调试工具 （源码+教学视频）

用c# 自己封装的Modbus工具类库源码

C#含有ModbusRtu通讯库，通讯示例 硬件设备测试例程

基于C#与Sql Server的智慧星学生选课管理系统.rar

C#40000字全套精华教程！！！从入门到精通，一篇就够了！！！

HslCommunication.dll 7.0.1 免费版本 全部源代码和测试工程

C# .Net使用第三方库PacketDotNet，开发的抓包软件示例

最新资源

串口侦听串口监听不占用串口不占用串口的监听

【C#源码】TCP+串口通信的调试工具（源码+教学视频）

C#含有ModbusRtu通讯库，通讯示例硬件设备测试例程

HslCommunication.dll 7.0.1 免费版本全部源代码和测试工程