BABYL OPTIONS: Version: 5 Labels: Note: This is the header of an rmail file. Note: If you are seeing it in rmail, Note: it means the file has no messages in it.  1, answered,, Received: from ATHENA-AS-WELL.MIT.EDU by po7.MIT.EDU (5.61/4.7) id AA09319; Wed, 14 Apr 93 17:17:33 EDT Received: from THOR.LCS.MIT.EDU by Athena.MIT.EDU with SMTP id AA09465; Wed, 14 Apr 93 17:17:27 EDT Received: by thor.lcs.mit.edu (5.57/Ultrix3.0-C) id AA22880; Wed, 14 Apr 93 17:17:17 -0400 Message-Id: <9304142117.AA22880@thor.lcs.mit.edu> To: derek@cambridge.apple.com, kkkken@Athena.MIT.EDU, segawa@lcs.mit.edu, tlee@Athena.MIT.EDU, umesh@thor.lcs.mit.edu Subject: 6.853 Problem set 3 Date: Wed, 14 Apr 93 17:17:16 -0400 From: Umesh Maheshwari X-Mts: smtp *** EOOH *** To: derek@cambridge.apple.com, kkkken@Athena.MIT.EDU, segawa@lcs.mit.edu, tlee@Athena.MIT.EDU, umesh@thor.lcs.mit.edu Subject: 6.853 Problem set 3 Date: Wed, 14 Apr 93 17:17:16 -0400 From: Umesh Maheshwari X-Mts: smtp Hi, There are 6 of us, as of now, who will be working in the Operating Systems and Distributed Systems area: Chee Chow web@athena.mit.edu Derek White derek@cambridge.apple.com Hideo Segawa segawa@lcs.mit.edu Kenneth Duda kkkken@athena.mit.edu Thomas Lee tlee@athena.mit.edu Umesh Maheshwari umesh@thor.lcs.mit.edu I think each of us should select a subtopic to focus on. Gifford listed these: Process mgmt Multi-processor support Protection Naming in a distributed sys Overall system structure Low-level transaction support Fault-tolerant operating Programming languages issues We don't need to cover all of them (I think), and we can devise topics of our own. Also, if two people are interested in the same topic (or similar topics, like the first two in the list) they could form a subgroup. If we select 5-6 topics, each of us could independently write a page on it for the position paper (which has to be <= 5 pages). Each would then get a 4 minute slot to summarize the issues in front of the class. (Thomas suggested that we could make 3 subgroups of 2; each subgroup will then tackle two topics from the list. This would provide more continuity in the presentation.) A good way to start would be to indicate your preferences for the topics. This is only tentative -- we could resolve overlaps when we next meet. I am interested in these two: Programming languages issues Low-level transaction support Thomas said he is interested in these: Protection Fault-tolerant operating Hideo: Process Mgmt Multi-processor support keep in touch! umesh  1,, Received: from ATHENA-AS-WELL.MIT.EDU by po7.MIT.EDU (5.61/4.7) id AA13960; Wed, 14 Apr 93 18:41:14 EDT Received: from brazil.cambridge.apple.com by Athena.MIT.EDU with SMTP id AA15935; Wed, 14 Apr 93 18:41:12 EDT Received: from ministry.cambridge.apple.com by brazil.cambridge.apple.com with SMTP (5.64/25-eef) id AA20355; Wed, 14 Apr 93 18:44:37 -0400 for kkkken@athena.mit.edu Received: from derek.cambridge.apple.com by cambridge.apple.com with SMTP (5.64/25-eef) id AA05637; Wed, 14 Apr 93 18:34:04 -0400 Message-Id: <9304142234.AA05637@cambridge.apple.com> Date: Wed, 14 Apr 1993 18:41:15 -0400 To: derek@cambridge.apple.com, kkkken@Athena.MIT.EDU, segawa@lcs.mit.edu, tlee@Athena.MIT.EDU, umesh@thor.lcs.mit.edu, Umesh Maheshwari From: derek@cambridge.apple.com Subject: Re: 6.853 Problem set 3 *** EOOH *** Date: Wed, 14 Apr 1993 18:41:15 -0400 To: derek@cambridge.apple.com, kkkken@Athena.MIT.EDU, segawa@lcs.mit.edu, tlee@Athena.MIT.EDU, umesh@thor.lcs.mit.edu, Umesh Maheshwari From: derek@cambridge.apple.com Subject: Re: 6.853 Problem set 3 At 5:17 PM 04/14/93 -0400, Umesh Maheshwari wrote: >Hi, ... >I think each of us should select a subtopic to focus on. >Gifford listed these: > >Process mgmt >Multi-processor support >Protection >Naming in a distributed sys >Overall system structure >Low-level transaction support >Fault-tolerant operating >Programming languages issues > ... >A good way to start would be to indicate your preferences for the topics. >This is only tentative -- we could resolve overlaps when we next meet. I'm interested in: Programming languages issues Overall system structure ---------------------------------------- Derek White (-ex Mr. Pascal) ATG/East (AppleLink: DEREK)  1,, Received: from ATHENA-AS-WELL.MIT.EDU by po7.MIT.EDU (5.61/4.7) id AA19031; Wed, 14 Apr 93 20:32:57 EDT Received: from W20-575-109.MIT.EDU by Athena.MIT.EDU with SMTP id AA22704; Wed, 14 Apr 93 20:32:42 EDT From: kkkken@Athena.MIT.EDU Received: by w20-575-109.MIT.EDU (5.61/4.7) id AA15430; Wed, 14 Apr 93 20:32:39 -0400 Date: Wed, 14 Apr 93 20:32:39 -0400 Message-Id: <9304150032.AA15430@w20-575-109.MIT.EDU> To: umesh@thor.lcs.mit.edu Cc: derek@cambridge.apple.com, segawa@lcs.mit.edu, tlee@Athena.MIT.EDU, umesh@thor.lcs.mit.edu, kkkken@Athena.MIT.EDU In-Reply-To: Umesh Maheshwari's message of Wed, 14 Apr 93 17:17:16 -0400 <9304142117.AA22880@thor.lcs.mit.edu> Subject: 6.853 Problem set 3 *** EOOH *** From: kkkken@Athena.MIT.EDU Date: Wed, 14 Apr 93 20:32:39 -0400 To: umesh@thor.lcs.mit.edu Cc: derek@cambridge.apple.com, segawa@lcs.mit.edu, tlee@Athena.MIT.EDU, umesh@thor.lcs.mit.edu, kkkken@Athena.MIT.EDU In-Reply-To: Umesh Maheshwari's message of Wed, 14 Apr 93 17:17:16 -0400 <9304142117.AA22880@thor.lcs.mit.edu> Subject: 6.853 Problem set 3 I think two people per topic is a good idea. Sort of a way of hedging your bets; less likely we'll leave big holes. I'm interested in programming language issues and naming in a distributed system. -Ken  1,, Received: from ATHENA-AS-WELL.MIT.EDU by po7.MIT.EDU (5.61/4.7) id AA03087; Sun, 25 Apr 93 20:13:23 EDT Received: from THOR.LCS.MIT.EDU by Athena.MIT.EDU with SMTP id AA08401; Sun, 25 Apr 93 20:13:20 EDT Received: by thor.lcs.mit.edu (5.57/Ultrix3.0-C) id AA23012; Sun, 25 Apr 93 20:13:18 -0400 Message-Id: <9304260013.AA23012@thor.lcs.mit.edu> To: tlee@Athena.MIT.EDU Cc: derek@cambridge.apple.com, kkkken@Athena.MIT.EDU, segawa@charm.lcs.mit.edu, umesh@thor.lcs.mit.edu, web@Athena.MIT.EDU Subject: 6853 Date: Sun, 25 Apr 93 20:13:18 -0400 From: Umesh Maheshwari X-Mts: smtp *** EOOH *** To: tlee@Athena.MIT.EDU Cc: derek@cambridge.apple.com, kkkken@Athena.MIT.EDU, segawa@charm.lcs.mit.edu, umesh@thor.lcs.mit.edu, web@Athena.MIT.EDU Subject: 6853 Date: Sun, 25 Apr 93 20:13:18 -0400 From: Umesh Maheshwari X-Mts: smtp Hi Thomas, I am finding it difficult to muster interesting material on low-level OS support for transactions. So I have been thinking about what else I could do. Since you have two topics to cover all by yourself, I could join you in one. I could do "protection" -- I am reading the paper on "single address space operating systems" and find it quite interesting. Or I could do fault-tolerant computing -- I've read some papers on "reliable multicast" by Birman and on "replication for higher availability" by Liskov. Or we could do the two topics together. Let me know how you find the idea. umesh  1,, Received: from ATHENA-AS-WELL.MIT.EDU by po7.MIT.EDU (5.61/4.7) id AA08673; Sun, 25 Apr 93 23:17:41 EDT Received: from SNOW-GOON.MIT.EDU by Athena.MIT.EDU with SMTP id AA04983; Sun, 25 Apr 93 23:17:35 EDT From: web@Athena.MIT.EDU Received: by snow-goon.MIT.EDU (5.61/4.7) id AA06848; Sun, 25 Apr 93 23:17:32 -0400 Message-Id: <9304260317.AA06848@snow-goon.MIT.EDU> To: Umesh Maheshwari Cc: tlee@Athena.MIT.EDU Cc: derek@cambridge.apple.com, kkkken@Athena.MIT.EDU, segawa@charm.lcs.mit.edu, umesh@thor.lcs.mit.edu, web@Athena.MIT.EDU Subject: Re: 6853 In-Reply-To: Your message of Sun, 25 Apr 93 20:13:18 -0400. <9304260013.AA23012@thor.lcs.mit.edu> Date: Sun, 25 Apr 93 23:17:28 EDT *** EOOH *** From: web@Athena.MIT.EDU To: Umesh Maheshwari Cc: tlee@Athena.MIT.EDU Cc: derek@cambridge.apple.com, kkkken@Athena.MIT.EDU, segawa@charm.lcs.mit.edu, umesh@thor.lcs.mit.edu, web@Athena.MIT.EDU Subject: Re: 6853 In-Reply-To: Your message of Sun, 25 Apr 93 20:13:18 -0400. <9304260013.AA23012@thor.lcs.mit.edu> Date: Sun, 25 Apr 93 23:17:28 EDT personally, I like the "write something about something you find intersting that sorta fits into the topic" idea, so I say choose either topic, or both, and do it. -Chee  1,, Received: from ATHENA-AS-WELL.MIT.EDU by po7.MIT.EDU (5.61/4.7) id AA08875; Mon, 26 Apr 93 13:44:27 EDT Received: from GAMBA.LCS.MIT.EDU by Athena.MIT.EDU with SMTP id AA14505; Mon, 26 Apr 93 13:44:25 EDT Received: by gamba.lcs.mit.edu (5.57/Ultrix3.0-C) id AA00225; Mon, 26 Apr 93 13:44:17 -0400 Date: Mon, 26 Apr 93 13:44:17 -0400 From: segawa@gamba.lcs.mit.edu (Hideo Segawa) Message-Id: <9304261744.AA00225@gamba.lcs.mit.edu> To: umesh@thor.lcs.mit.edu Cc: derek@cambridge.apple.com, kkkken@Athena.MIT.EDU, web@Athena.MIT.EDU, tlee@Athena.MIT.EDU Subject: direction *** EOOH *** Date: Mon, 26 Apr 93 13:44:17 -0400 From: segawa@gamba.lcs.mit.edu (Hideo Segawa) To: umesh@thor.lcs.mit.edu Cc: derek@cambridge.apple.com, kkkken@Athena.MIT.EDU, web@Athena.MIT.EDU, tlee@Athena.MIT.EDU Subject: direction Umesh, Following is a rough draft I am now thinking of to discuss and reference. Please give me any comment or sugestion or reforming direction. Hideo -- Hideo Segawa segawa@charm.lcs.mit.edu ------------- \documentstyle[12pt]{article} \begin{document} \title{Multi Processor Support} \author{Hideo Segawa} \maketitle \section{Thread Support} For concurrent programming it is difficult to surpass the idea of scheduler activation (Anderson et al.[]) at this moment, beca use it achieves the high-peformance of user thread switching, and removes the hanging-up problem during I/O wait. One of the interesting features is NUMA( Non-Uniform Memory Access ). Massive Parallel Machines, which have been based on messa ge passing scheme, are trying to support single address space like KSR-1. Some ad-hoc scheduling algorizms are proposed to remove a thrashing problem. \section{Parallel Processing Support} The establishment in parallel programing style has brought change in parallel computer architecture. Hardware is now designed t o avoid unnecessary efforts to keep consistent view from every processor. Various kinds of consistency model have been proposed from strict Sequent's snoop cache model to DASH's release consistency mod el. A new and the least strict consistency model called entry consistency is proposed(Bershad et al.[]). Midway supports this new m odel which runs from a network of workstations connected by Ethernet, distiributed memory system to real bus connected shared m emory system. It provedes programming language support, compiler support and language support. I believe this is a very intersting movement, because Midway tries to achieve an architecture independent programing interface. Considering current progress of netwrok and its controllers, a network of workstations can be an alternative of parallel machi nes. Portability of program is a big issue. \end{document}  1,, Received: from ATHENA-AS-WELL.MIT.EDU by po7.MIT.EDU (5.61/4.7) id AA00122; Fri, 23 Apr 93 15:43:06 EDT Received: from THOR.LCS.MIT.EDU by Athena.MIT.EDU with SMTP id AA03877; Fri, 23 Apr 93 15:43:02 EDT Received: by thor.lcs.mit.edu (5.57/Ultrix3.0-C) id AA08025; Fri, 23 Apr 93 15:42:57 -0400 Message-Id: <9304231942.AA08025@thor.lcs.mit.edu> To: derek@cambridge.apple.com, kkkken@Athena.MIT.EDU, segawa@charm.lcs.mit.edu, tlee@Athena.MIT.EDU, umesh@thor.lcs.mit.edu, web@Athena.MIT.EDU Subject: 6853 Date: Fri, 23 Apr 93 15:42:55 -0400 From: Umesh Maheshwari X-Mts: smtp *** EOOH *** To: derek@cambridge.apple.com, kkkken@Athena.MIT.EDU, segawa@charm.lcs.mit.edu, tlee@Athena.MIT.EDU, umesh@thor.lcs.mit.edu, web@Athena.MIT.EDU Subject: 6853 Date: Fri, 23 Apr 93 15:42:55 -0400 From: Umesh Maheshwari X-Mts: smtp Some issues about the top-level design: * should it be micro-kernel based? how to reduce the cost of context-switches? * single 64-bit address space for all processes on the same machine? * How transparent should it be? * multiprocessor support: shared-memory / msg passing? We decided to meet at 1:45pm on Wednesday -- that gives only 45 min before the class. Given that we took nearly an hour and a half today, I think we should make it 1:30pm. Write up something and post it to the group! umesh  1,, Received: from ATHENA-AS-WELL.MIT.EDU by po7.MIT.EDU (5.61/4.7) id AA27876; Tue, 27 Apr 93 09:55:37 EDT Received: from SNOW-GOON.MIT.EDU by Athena.MIT.EDU with SMTP id AA00333; Tue, 27 Apr 93 09:55:31 EDT From: web@Athena.MIT.EDU Received: by snow-goon.MIT.EDU (5.61/4.7) id AA10552; Tue, 27 Apr 93 09:55:28 -0400 Message-Id: <9304271355.AA10552@snow-goon.MIT.EDU> To: segawa@gamba.lcs.mit.edu (Hideo Segawa) Cc: umesh@thor.lcs.mit.edu Cc: derek@cambridge.apple.com, kkkken@Athena.MIT.EDU, web@Athena.MIT.EDU, tlee@Athena.MIT.EDU Subject: Re: direction In-Reply-To: Your message of Mon, 26 Apr 93 13:44:17 -0400. <9304261744.AA00225@gamba.lcs.mit.edu> Date: Tue, 27 Apr 93 09:55:25 EDT *** EOOH *** From: web@Athena.MIT.EDU To: segawa@gamba.lcs.mit.edu (Hideo Segawa) Cc: umesh@thor.lcs.mit.edu Cc: derek@cambridge.apple.com, kkkken@Athena.MIT.EDU, web@Athena.MIT.EDU, tlee@Athena.MIT.EDU Subject: Re: direction In-Reply-To: Your message of Mon, 26 Apr 93 13:44:17 -0400. <9304261744.AA00225@gamba.lcs.mit.edu> Date: Tue, 27 Apr 93 09:55:25 EDT More blurbs for tomorrow's meeting... -Chee ---------------------------------------------------------------------- Multiprocessing on Parallel Processor Machines (I agree with Hideo that the issues in here are tightly coupled and maybe there's really little value in working to separate them apart) Although a lot of work has been done to reduce the cost of a context switch, we can also achieve the same (or similar) effect by having reasonably cheap context switches, and simply switching less frequently. With multiprocessor MIMD machines, this becomes a viable option. The In the APRIL project, context switches occur on cache misses and network requests, instead of by a scheduler. Another simple idea is to not automatically schedule new threads with different processors. Programmers, in the programming language can request that a new thread be spawned, but the new thread is actually scheduled on the same processor as the parent. Surrounding processors will, when they are idle, look around for tasks to take from other processors. This gives the advantage that parallel programs on this system will not run significantly slower than serial programs. This also results in course-grain parallelism, which is important for MIMD machines. I'm lookin at an older Thor paper by Prof. Liskov. I don't see too much that's interesting with programming language ideas for distributed computing. I guess I'll read more in the paper for wednesday.  1,, Received: from ATHENA-AS-WELL.MIT.EDU by po7.MIT.EDU (5.61/4.7) id AA19340; Tue, 27 Apr 93 22:38:43 EDT Received: from FARNSWORTH.MIT.EDU by Athena.MIT.EDU with SMTP id AA24011; Tue, 27 Apr 93 22:38:40 EDT Received: by farnsworth.mit.edu (5.57/Ultrix3.0-C) id AA09145; Tue, 27 Apr 93 22:39:47 -0400 Date: Tue, 27 Apr 93 22:39:47 -0400 From: tlee@farnsworth.mit.edu (Thomas Lee) Message-Id: <9304280239.AA09145@farnsworth.mit.edu> To: segawa@charm.lcs.mit.edu, umesh@thor.lcs.mit.edu Subject: draft write-up Cc: derek@cambridge.apple.com, kkkken@Athena.MIT.EDU, web@Athena.MIT.EDU *** EOOH *** Date: Tue, 27 Apr 93 22:39:47 -0400 From: tlee@farnsworth.mit.edu (Thomas Lee) To: segawa@charm.lcs.mit.edu, umesh@thor.lcs.mit.edu Subject: draft write-up Cc: derek@cambridge.apple.com, kkkken@Athena.MIT.EDU, web@Athena.MIT.EDU The principal goals of fault tolerance research are two-fold: to ensure that computer systems "do the right thing" or else they do nothing at all, (atomicity) and that they do so sooner, rather than later (availability). Because systems can fail for any number of reasons, efforts to provide fault tolerant performance may be broadly divided into: hardware, software, and end-to-end or system level research. Hardware strategies for fault tolerance revolve around redundancy. Pair-and-spare architectures and TMR (triple modular redundancy) are the two most common techniques. Although both of these strategies tolerate only single failures, extensions to provide for multiple failure are well understood. Moreover, "software faults are the dominant source of system failures. All other faults can be masked with a combination of redundancy, geographic diversity, and software to automate tasks." [Gray, 119] Consequently, future research in fault tolerance is likely to focus on software. Software fault tolerance research is likely to focus on storage, processes, and message passing. Assuming that the underlying storage, process, and message passing substructure is reliable, then applications built using these tools, should be able to tolerate most software faults. While reliable storage and message passing are addressed extensively within the literature, fault tolerant processes - in particular, the strategy of process pairs, are not. Process pairs emulate the hardware strategy of a "spare" to continue service should the primary fail. Areas for further research involve detection - knowing when the "spare" must assume control and continuation - recognizing the most recent state of the primary. As fault tolerant hardware and software are increasingly well understood, however, research will turn towards broader, system level concerns. Design diversity and human factors are two such issues. Design diversity refers to minimizing interdependencies between modules. For instance, reliable message handling may depend, at least to some degree, upon reliable processes. Interdependencies violate the single-fault assumption used in the standard Mean Time To Failure statistical analyses. Human factors research attempts to account for human error, recognizing that a fault tolerant system must include its operators as well. Therefore, reducing human error (replacing the wrong board or entering an incorrect transaction) is also a crucial element of fault tolerant research. Pair-and-spare employs two sets of duplexe hardware modules. If the first pair of modules do not agree at least one of the modules must be in error, and the pair is replaced by its "spare". TMR assumes that the majority is always correct. If the output of one module disagrees with that of the other two, the deviating module is removed from service for repair.  1,, Received: from ATHENA-AS-WELL.MIT.EDU by po7.MIT.EDU (5.61/4.7) id AA21925; Tue, 27 Apr 93 23:45:25 EDT Received: from M16-034-11.MIT.EDU by Athena.MIT.EDU with SMTP id AA27474; Tue, 27 Apr 93 23:45:17 EDT From: kkkken@Athena.MIT.EDU Received: by m16-034-11.MIT.EDU (5.61/4.7) id AA26658; Tue, 27 Apr 93 23:45:13 -0400 Date: Tue, 27 Apr 93 23:45:13 -0400 Message-Id: <9304280345.AA26658@m16-034-11.MIT.EDU> To: derek@cambridge.apple.com, kkkken@Athena.MIT.EDU, segawa@charm.lcs.mit.edu, tlee@Athena.MIT.EDU, umesh@thor.lcs.mit.edu, web@Athena.MIT.EDU Subject: ok folks here it is *** EOOH *** From: kkkken@Athena.MIT.EDU Date: Tue, 27 Apr 93 23:45:13 -0400 To: derek@cambridge.apple.com, kkkken@Athena.MIT.EDU, segawa@charm.lcs.mit.edu, tlee@Athena.MIT.EDU, umesh@thor.lcs.mit.edu, web@Athena.MIT.EDU Subject: ok folks here it is I'm actually vaguely proud of it, so go ahead, shoot it all down! { \catcode`\ =\active \catcode`\^^M=\active \gdef\beginverbatim{\begingroup% \def\\{\char92}% \catcode`\ =\active% \catcode`\^^M=\active% \catcode`\$=12% \catcode`\&=12% \catcode`\^=12% \catcode`\#=12% \def {\ }% \def {\hfil\break\noindent\strut}% \tt}} \let\endverbatim\endgroup \catcode`\@=\active\def@{\beginverbatim\let@\endverbatim} \centerline{NAMING IN A DISTRIBUTED SYSTEM} Recent development in naming in distributed systems makes it clear that names should transcend machine boundaries, and that files are not the only thing that we want to name. Sprite introduces a machine-independent naming scheme, but only for files. Windows NT introduces a heirarchical structure that includes many kinds of ``objects'', but they are limited to being of classes predefined by the NT ``micro''-kernel, and names are only meaningful on a given machine. The operating system of the future will have a namespace organized in a heirarchy. Like Sprite, a fully-qualified name will have a meaning independent of the machine interpreting the name. However, names will be allowed to contain enviornment variable references whose meaning is host- (in fact process-) specific (such names are not fully-qualified; performing the variable substitution results in a fully-qualified name). This way it is possible to deal with things such as different binary types, multiple sources of system software, or the desire to store a temporary file on a local disk. For example, the object name @/edu/mit/athena/local/$localhost/fs/tmp/foo@ would name a temporary file on the current host, and the object name @/edu/mit/lcs/system/$cluster/$hosttype/bin/ls@ might name the @ls@ program. I could access a file stored locally on a nearby host with the pathname @/edu/mit/athena/local/w20-575-13/fs/tmp/bar@. Administration of a global namespace would be accomplished as follows. The first several levels of the heirarchy indicate the name of the administrative domain in which the object exists; objects must live in exactly one administrative domain. The objects at this high level are {\it container} objects; their only purpose is to contain other objects, and the only operations that most users perform on them are {\it list} and {\it search}. These top-level objects are read-only, and can thus be highly replicated and cheaply cached. This mechanism distributes the task of administration in the same way that the Internet host namespace does. The fundamental operations performed on a name are {\it substitute} and {\it resolve.} Substitute, as mentioned above, turns a name with variable references into a fully-qualified name. Resolve converts a name into an {\it object identifier}. This identifier is enough information for the process with the name to call methods of the object. A {\it name-resolution server} will run on each node for this purpose, much in the way a @named@ process runs on every host using Internet name service. The name-resolution server keeps track of where objects are located, and also keeps track of which objects exist on the current machine. However, it is the responsibility of a container object to be able to locate its children. Specifically, if a container object receives a {\it search} request for a name it contains, it must be able to provide that name's object identifier. For example, consider a distributed file system. The object @/edu/mit/athena@ is a replicated, read-only container object with an entry @home@, which is itself a replicated read-only object with an entry for each username. Each workstation at MIT is permanently configured with the locations of the @/edu/mit/athena@ object (this is how Internet DNS works). Now say I access a file in my home directory, @/edu/mit/athena/user/kkkken/sounds/burp@. This is the first file access I make on this workstation, so its local name-resolution server asks one of the @/edu/mit/athena@ replicants where to find @home@; an object identifier is returned. It then asks this object for @kkkken@, and so on down the chain, much like NFS. Things other than files can be stored in this system. For example, to kill a process on my machine, I could call the {\it kill} method on @/edu/mit/athena/local/m16-034-11/proc/kkkken/134@, perhaps. Of course, variables could be set up so I would merely need to type @$domain/local/$host/proc/$user/134@ or even @$myprocs/134@. One nice thing about the system is that if I accidentally left a process running on another machine, I could easly find it and kill it without remotely logging in. I would expect all user-visible operating system data structures to be accessible via object names, including machine performance statistics, access to local daemons, and objects such as semaphores, message queues, and named pipes. Issues I haven't addressed are access control and caching of read/write objects. Kerberos works pretty well for access control; objects can maintain access control lists and use kerberos to establish the identities of principals making RPC requests. Maybe the Sprite system works well for caching, I don't really know. \bye  1,, Received: from ATHENA-AS-WELL.MIT.EDU by po7.MIT.EDU (5.61/4.7) id AA00849; Fri, 30 Apr 93 14:15:04 EDT Received: from THOR.LCS.MIT.EDU by Athena.MIT.EDU with SMTP id AA04910; Fri, 30 Apr 93 14:14:56 EDT Received: by thor.lcs.mit.edu (5.57/Ultrix3.0-C) id AA17333; Fri, 30 Apr 93 14:14:49 -0400 Message-Id: <9304301814.AA17333@thor.lcs.mit.edu> To: derek@cambridge.apple.com, kkkken@Athena.MIT.EDU, segawa@charm.lcs.mit.edu, tlee@Athena.MIT.EDU, umesh@thor.lcs.mit.edu, web@Athena.MIT.EDU Subject: 6853: A page on protection Date: Fri, 30 Apr 93 14:14:45 -0400 From: Umesh Maheshwari X-Mts: smtp *** EOOH *** To: derek@cambridge.apple.com, kkkken@Athena.MIT.EDU, segawa@charm.lcs.mit.edu, tlee@Athena.MIT.EDU, umesh@thor.lcs.mit.edu, web@Athena.MIT.EDU Subject: 6853: A page on protection Date: Fri, 30 Apr 93 14:14:45 -0400 From: Umesh Maheshwari X-Mts: smtp Here's me providing input at the last minute. I will bring copies to the meeting. umesh -------- \documentstyle[]{article} \begin{document} This section focuses on mechanisms for access-control, as opposed to the related but distinct issues of security, authentication, and authorization. Access-control information can be viewed as a relation between the set of principals (or protection domains) and the set of objects. More specifically, the relation specifies exactly which operations of an object can a principal invoke. Traditionally, two different ways of organizing this information are used: {\em access control lists} (ACLs) and {\em capabilities}. In the first scheme, each object stores an ACL that specifies the principals and the operations they can invoke. Typically, the owner of the object has the right to modify the ACL. The Unix file system uses a coarse form of ACLs where the principals are grouped into 3 categories. Capabilities, on the other hand, put the burden of access-control information with the principals. A capability is a ticket that allows the principal possessing it to invoke certain operations on the indicated object. As used in the Amoeba system, capabilities are a ``unified mechanism for naming, accessing, and protecting objects'' [MT86]. In order that the principals may not generate (forge) capabilities by themselves or enhance the ones given to them, two techniques can be used. First, the capabilities can be protected by the OS while the application has only indirect access to them (akin to file descriptors in Unix). Alternatively, an {\em encrypted checksum} can be added to each capability so that tampering it makes it void. It is desirable to disallow certain kinds of capabilities to be even copied between principals; this can be achieved by encoding the principal identity within the capabilities. In scalable, wide-spread distributed systems with a large number of principals, the use of ACLs may create a bottleneck at the servers: each access must be validated by searching in a long list of principals. Further, it is difficult to garbage collect the ACL entries for principals that have ceased to exist, resulting in waste of space by ever-increasing ACLs. Capabilities appear to be better suited for scalability and distribution. An access here requires validating the presented capability, which is a constant time operation independent of the number of principals. Similarly, the storage overhead per object is reduced. Admittedly, the principals must now store capabilities for various objects, but this results in a better distribution of storage space in a client-server setting. Further, capabilities can be hierarchically handed-off by the owner server to other trusted servers for distribution, which in turn authenticate the client principals before providing the capability. Copying of capabilities between clients, if deemed illegal, can be prevented by encoding a client-specific ID into the capabilities. Capabilities do lack certain desirable features of ACLs. ACLs allows a tight centralized control over the object since the ACL can be modified without contacting the principals; but with capabilities, it is impossible to {\em selectively revoke} a capability from certain principals while still honoring others. A recent project, {\em CACL} [RSC92], provides the semantics of ACLs while employing a capability-like implementation (``CACL'' is a combination of Capabilities and ACLs). (I am going to say more about CACL and add a paragraph on protection of the virtual address space. If you think that some piece above can be shrunk to make space, pl let me know.) % References: \begin{description} \item[MT86] S. J. Mullender, and A. S. Tanenbaum. The Design of a Capability-Based Distributed Operating System. {\em The Computer Journal}, 29(4), 1986. \item[RSC92] J. Richardson, P. Schwartz, and L-F Cabrera. CACL: Efficient Fine-Grained Protection for Objects. {\em OOPSLA'92}, pp 263--275, 1992. \end{description} \end{document}  1,, Received: from ATHENA-AS-WELL.MIT.EDU by po7.MIT.EDU (5.61/4.7) id AA19891; Fri, 30 Apr 93 19:08:10 EDT Received: from THOR.LCS.MIT.EDU by Athena.MIT.EDU with SMTP id AA00285; Fri, 30 Apr 93 19:08:05 EDT Received: by thor.lcs.mit.edu (5.57/Ultrix3.0-C) id AA01633; Fri, 30 Apr 93 19:07:58 -0400 Message-Id: <9304302307.AA01633@thor.lcs.mit.edu> To: derek@cambridge.apple.com, kkkken@Athena.MIT.EDU, segawa@charm.lcs.mit.edu, tlee@Athena.MIT.EDU, umesh@thor.lcs.mit.edu, web@Athena.MIT.EDU Subject: 6853 Date: Fri, 30 Apr 93 19:07:57 -0400 From: Umesh Maheshwari X-Mts: smtp *** EOOH *** To: derek@cambridge.apple.com, kkkken@Athena.MIT.EDU, segawa@charm.lcs.mit.edu, tlee@Athena.MIT.EDU, umesh@thor.lcs.mit.edu, web@Athena.MIT.EDU Subject: 6853 Date: Fri, 30 Apr 93 19:07:57 -0400 From: Umesh Maheshwari X-Mts: smtp This is to remind you to send me the latest copy of your writeup. I will put them together, remove as many wrinkles as I can and send the result to Ken, who will remove more wrinkles and send it to Chee, and so on. Before sending me your writeup, see if it has any references that you have not filled in (the "[]"s ). Add a bibliography at the end. umesh  1,, Received: from ATHENA-AS-WELL.MIT.EDU by po7.MIT.EDU (5.61/4.7) id AA22554; Fri, 30 Apr 93 20:43:48 EDT Received: from GAMBA.LCS.MIT.EDU by Athena.MIT.EDU with SMTP id AA03719; Fri, 30 Apr 93 20:43:46 EDT Received: by gamba.lcs.mit.edu (5.57/Ultrix3.0-C) id AA26898; Fri, 30 Apr 93 20:43:44 -0400 Date: Fri, 30 Apr 93 20:43:44 -0400 From: segawa@gamba.lcs.mit.edu (Hideo Segawa) Message-Id: <9305010043.AA26898@gamba.lcs.mit.edu> To: umesh@thor.lcs.mit.edu, derek@cambridge.apple.com, kkkken@Athena.MIT.EDU, tlee@Athena.MIT.EDU, web@Athena.MIT.EDU Subject: 6853 *** EOOH *** Date: Fri, 30 Apr 93 20:43:44 -0400 From: segawa@gamba.lcs.mit.edu (Hideo Segawa) To: umesh@thor.lcs.mit.edu, derek@cambridge.apple.com, kkkken@Athena.MIT.EDU, tlee@Athena.MIT.EDU, web@Athena.MIT.EDU Subject: 6853 Attached is a preliminary draft of mine, which lacks the referencs of Anderson's paper. I will come to the lab. tommorow afternoon in order to be ready for refinement. Any comment is appreciated. Have a good weekend! Hideo -------------------------- \documentstyle[12pt]{article} \begin{document} \title{Multi Processor Support} \author{Hideo Segawa} \maketitle \section{Multi-processor support} Researches on multi-processor architecture has been focused on achieving two contradictive issues. \begin{itemize} \item Scalabilty to achieve high performance. \item Sharing of resources for ease of programing. \end{itemize} Shared memory machines are generally recognized as being convenient to program because hardware provides processors with a cons istent view of global memory. Unfortunately, providing this consistency limits their scalability. Physically distributed memory, where each processor has its own local memory, providing logically shared memory is the goal of this research. \section{Scalability} The establishment in parallel programing style has brought change in parallel computer architecture. Hardware is now designed t o avoid unnecessary efforts to keep consistent view from every processor. Release consistency model proposed in DASH(Gharachorloo et al.[]) reduced the hardware overhead to provide consistent view comp ared with Sequent's snoop cache model. It ensures that all previous shared data updates are consistent before a release of a synchronization variable is observed by a ny processor, where an explicit synchronization operation is assumed. A new and the least strict consistency model called entry consistency is proposed(Bershad et al.[]). In an entry consistent sys tem, a processor's view of memory becomes consistent only when it enters critical section. When an acquire for a synchronization variable is pending, a thread will be switched to another. Stated in another way, entry consistency model requires that synchronization accesses be thread consistent; a thread's acquire and release accesses must be performed in the order that they were issued by the thread. In contrast, release consistency requires that synchronization accesses be thread consistent. Midway supports this new model which runs from a network of workstations connected by Ethernet, distributed memory system to re al bus connected shared memory system. It provides programming language support, compiler support and language support. For further efficient remote memory access, multiphase memory operations has been investigated. To avoid thrashing where data c an be invalidated before it is used, transaction buffers which keep track of memory requests are proposed(Kubiatowicz et al.[])  1,, \section{Sharing} For concurrent programming it is difficult to surpass the idea of scheduler activation (Anderson et al.[]) at this moment, beca use it achieves the high-performance of user thread switching, and removes the hanging-up problem during I/O wait. In scheduler activation, threads share an virtual address space, and a thread will give up the processor and return it to kerne l when it waits for an I/O completion. *** EOOH *** \section{Sharing} For concurrent programming it is difficult to surpass the idea of scheduler activation (Anderson et al.[]) at this moment, beca use it achieves the high-performance of user thread switching, and removes the hanging-up problem during I/O wait. In scheduler activation, threads share an virtual address space, and a thread will give up the processor and return it to kerne l when it waits for an I/O completion. Sharing of a virtual address space by massive processors is one of the intersting features. Massive Parallel Machines, which have been based on message passing scheme, are trying to support single address space like KSR 1 from Kendall Square Research(Glen Zorpette[]). The KSR1's memory are physically distributed but by attaching a special main m emory controller managed as if they were pieces of a single virtual large virtual memory. When a processor needs the data at a certain address, the processor's own local memory is searched first. If the address is not there, a high speed search engine finds the address and its data in another memory. Briefly saying, KSR1 achieved hardware oriented data-shipping mechanism among distributed memories, and it may cause serious pe rformance drawback for certain applications(Patterson[]). On the other hand, operating system-level NUMA( Non-Uniform Memory Access ) memory management is also an active research area a nd the effectiveness of various page placement polies were tested(LaRowe et al.[]). \section{References} Gharachorloo et al.,''Memory Consistency and Event Ordering in Scalable Shared Memory Multiprocessor,''Proceedings of the 16th Annual Symposium on Computer Architecture, May 1989. Brian Bershad et al.,''Midway: Shared Memory Parallel Programing with Entry Consistency for Distributed Memory Multiprocessors, '' CMU-CS-91-170, September, 1991. John Kubiatowicz et al.,''Closing the Window of Vulnerability in Multiphase Memory Transactions,'' ASPLOS V, October, 1992. Glen Zorpette,''The power of parallelism,''IEEE Spectrum, September, 1992. David Patterson,''Massive Parallelism and Massive Storage,''Second International Conference on Parallel and Distributed Informa tion Systems, 1993. LaRowe et al.,''The robustness of NUMA Memory Management,''Operating Systems Review, Vol.25, No.5, October, 1991. \end{document}  1,, Received: from ATHENA-AS-WELL.MIT.EDU by po7.MIT.EDU (5.61/4.7) id AA19570; Sat, 1 May 93 20:40:45 EDT Received: from guardian.apple.com by Athena.MIT.EDU with SMTP id AA03423; Sat, 1 May 93 20:40:34 EDT Received: from [90.1.0.8] by guardian.apple.com with SMTP (5.65/7-Aug-1992-eef) id AA02144; Sat, 1 May 93 14:05:41 -0700 for Received: by alink-gw.apple.com (921113.SGI.UNSUPPORTED_PROTOTYPE/15-Mar-1993-eef) id AA10443; Sat, 1 May 93 14:03:03 -0700 for WEB@ATHENA.MIT.EDU Date: 01 May 93 20:43 GMT From: DEREK@AppleLink.Apple.COM (White, Derek) Subject: 64 bit OS To: UMESH@THOR.LCS.MIT.EDU, DEREK@CAMBRIDGE.APPLE.COM Cc: KKKKEN@Athena.MIT.EDU, SEGAWA@CHARM.LCS.MIT.EDU, TLEE@Athena.MIT.EDU, WEB@Athena.MIT.EDU, DEREK@AppleLink.Apple.COM (White, Derek) Message-Id: <736290182.1856700@AppleLink.Apple.COM> *** EOOH *** Date: 01 May 93 20:43 GMT From: DEREK@AppleLink.Apple.COM (White, Derek) Subject: 64 bit OS To: UMESH@THOR.LCS.MIT.EDU, DEREK@CAMBRIDGE.APPLE.COM Cc: KKKKEN@Athena.MIT.EDU, SEGAWA@CHARM.LCS.MIT.EDU, TLEE@Athena.MIT.EDU, WEB@Athena.MIT.EDU, DEREK@AppleLink.Apple.COM (White, Derek) Sorry for taking so long. It took a while before I saw that this system has any merit. It won't scale up to global-area networks, but it may still be useful. This is too long though. I can be reached at derek@applelink.apple.com over the weekend (I think). ----------------------------------------------------- Introduction We believe that that there are several important directions in operating systems and distributed systems over the next several years. Future research will involve improving micro-kernel based operating systems, support for scalable and sharing problems in multi-processor systems, location independent naming of objects, capability based protection, and fault tolerance. ----------------------------------------------------- Overall System Structure There will be ongoing research into operating systems that take advantage of 64 bit addressing. 64 bit addressing can provide a single virtual address space that allows efficient message passing, data persistence and sharing over local area networks. A single virtual address space separates the concepts of address translation and memory protection. Protection Processes gain access to segments of virtual memory by requesting the kernel to "attach" a segment to the process. The kernel may allow or deny access to the segment based on higher-level access control list or capability based techniques. Access to unattached segments can be detected at a very low level as shown in [1]. Persistence Data persistence can be implemented by simply paging segments of virtual memory to disk. When the data is accessed again, it will be paged to the same virtual address, so saving or restoring a complex network of data does not involve modifying pointers. Distribution Data can be distributed across nodes on the network by dynamically partitioning the virtual address space among the nodes. The operating system may move the physical location of pages by sending the data across the network and changing the virtual-to-physical address translations of the pages. The management of the address space over the network is a variant of the distributed naming problem that all distributed systems must handle. Data sharing Two processes can communicate by requesting a segment of shared virtual memory from the OS. Since virtual addresses are constant among the processes, pointers are meaningful unique identifiers for objects. Complex networks of objects can be passed through the shared memory without "flattening" pointers or doing other address translation. A server may return a pointer to a client that the client can't dereference, but the client may use that pointer is subsequent remote procedure calls (RPC). RPC can be enhanced by these techniques and by more direct transfer of control: A server can export the virtual addresses of certain entry points to clients, and the clients can call the server routines through a kernel routine, as described in [2]. A single virtual address space allows the efficient LRPC scheme of [3] to be implemented without pointer translation, and allows for complex data structures to be passed between processes. Furthermore, it allows the same technique to be used transparently across machine boundaries. Summary A large single address space allows an operating system to provide efficient message passing on a machine, which can enable truly mirco-kernel based operating systems. It also allows RPC with the same semantics as LRPC, which promotes the construction of distributed systems. Further research needs to be done in the areas of managing the virtual address space, and maintaining consistent distributed and persistent data. Techniques also need to be developed to integrate data that comes from persistent storage or networks that are not managed by the system (getting the latest copy of Microsoft Word 23.5, or some hyper-mail document from Japan for instance). [1]E. J. Koldinger, J. S. Chase, and S. J. Eggers. Architectural Support for Single Address Space Operating Systems. In ASPLOS, pages 175-186, October 1992. [2]J. S. Chase, H. M. Levy, E. D. Lazowska, and M. Baker-Harvey. Lightweight shared objects in a 64-bit operating system. In Proc. of the Conference on Object-Oriented Programming Systems, Languages, and Applications, October 1992. [3]B.N Bershard, T.E. Anderson, E. D. Lazowska, and H. M. Levy. Lightweight remote procedure call. ACM Transactions on Computer Systems, 8,1 pages 37-55, February 1990.