jss@sjuvax.UUCP (J. Shapiro) (02/28/85)
[Pacman's revenge...?] I agree that this conversation has run overlong, but one thing that I am sure all of us have noticed by now is the fact that neither the UNIX file system nor the RMS services is perfect for everything. There are other regards in which UNIX is better than VMS or vice versa. (E.g. pipes in favor of UNIX, file and record locking in favor of VMS). One poster (regrettably I forget who) suggested that an operating system should be built using a bottom level file model with libraries to manipulate that bottom level at successively higher levels of abstraction. This seems on initial consideration to be a good idea - it avoids always paying for things you don't really want. The problem lies in picking an underlying model sufficiently robust to do all of the things you want to do with record and file locking, and in noting which level of abstraction a file shuold be evaluated under. Has anyone out there given some thought to what might make a sufficiently robust underlying system?? There are things UNIX can't provide under its current incarnation even with library routines.... Jon Shapiro Haverford College
guy@rlgvax.UUCP (Guy Harris) (03/02/85)
> The problem lies in picking an underlying model sufficiently robust > to do all of the things you want to do with record and file locking, ... Well, several UNIX versions *do* have record and file locking - System V Release 2 Version 2, for one. They are based on John Bass' byte-stream locking mechanism; you lock a given range of bytes in the file. VMS, on the other hand, has a locking mechanism that locks magic cookies; cooperating applications agree on a name for a resource and they lock that name when they want to lock that resource. This goes all the way back to OS/360's ENQ/DEQ locking primitive, which locked names made of an 8-character "qname" and an 8-character "rname" - queue and resource names, probably, giving a two-level hierarchy. I believe VMS supports N-level name hierarchies, for N reasonably large. This means you can lock things other than files; perhaps locking should have nothing to do with the file system. Guy Harris {seismo,ihnp4,allegra}!rlgvax!guy
chuck@dartvax.UUCP (Chuck Simmons) (03/04/85)
> VMS, on the other hand, has a locking mechanism that locks magic cookies; > cooperating applications agree on a name for a resource and they lock > that name when they want to lock that resource. > ... > This means you can lock things other than files; perhaps locking should > have nothing to do with the file system. > > Guy Harris (in my opinion) Locking should have a lot to do with the file system. As a miniumum, by default if one process has a file open with write permission no other process should be able to read or write that file. (This is just one example.) This protects naive users (like myself) from trashing themself or being trashed by others. Interestingly (?), this default locking mechanism implemented by the operating system which the user/programmer does not need to worry about provides a simple-minded "magic cookie" locking mechanism. The cooperating applications simply agree on the name of a file. To lock the magic cookie, a process opens the file with all permissions. To unlock the magic cookie, the process closes the file. No doubt, it would be nice to have some sort of queuing mechanism as well, however. Naturally, two processes should be able to override the default locking mechanism. For example when you have a database that needs to be accessed by many users at the same time. But it is important that a programmer not need to put any thought into having exclusive access to a file when he is expecting only one process to access that file. It is alright if a programmer needs to think a little more when she wants to use a shared file. You mentioned "N-level heirarchies". What are these? Where would you use them? Could you describe some sample applications that use nifty and easy to use locking mechanisms? Our system is pretty simple-minded (but much better than Unix), and so my education is lacking. Thanks, chuck_simmons%dcts1@dartvax
henry@utzoo.UUCP (Henry Spencer) (03/06/85)
> As a miniumum, by default if one process has a file open with write > permission no other process should be able to read or write that file. Of course, this means that (for example) you can't read a log file as it is being produced to watch what's happening. -- Henry Spencer @ U of Toronto Zoology {allegra,ihnp4,linus,decvax}!utzoo!henry
haapanen@watdcsu.UUCP (Tom Haapanen [DCS]) (03/07/85)
In article <5178@utzoo.UUCP> henry@utzoo.UUCP (Henry Spencer) writes: >> As a miniumum, by default if one process has a file open with write >> permission no other process should be able to read or write that file. >Of course, this means that (for example) you can't read a log file as >it is being produced to watch what's happening. Probably a much better 'minimum' idea would be to disallow two people writing at once to avoid data corruption, but to allow simultaneous reads and one write. This type of thing is implemented on CMS as well, where one can access a minidisk as READ, WRITE or MULTIWRITE. It's always possible to access a file as READ, but WRITE is only available if no one else is writing it. If you want to write simultaneously, you must use MULTIWRITE, which is potentially very dangerous. \tom haapanen watmath!watdcsu!haapanen Don't cry, don't do anything No lies, back in the government No tears, party time is here again President Gas is up for president (c) Psychedelic Furs, 1982
chuck@dartvax.UUCP (Chuck Simmons) (03/08/85)
> > As a miniumum, by default if one process has a file open with write > > permission no other process should be able to read or write that file. > > Of course, this means that (for example) you can't read a log file as > it is being produced to watch what's happening. > -- > Henry Spencer @ U of Toronto Zoology Actually... I guess I never mentioned 'append' permission. 'write' permission let's you modify the contents of a file, but not make it longer. 'append' permission allows you to make a file longer, but not change the contents of the file. There is no reason why one process could not have a file open with 'read' while another process has the file open with 'append' since the processes will not be conflicting. This is just one answer. The other answer is that we make the log file a 'sharable' file. Then the logging process can periodically lock the file, write out (er, append) a buffer's worth of information to the file, and then unlock the file. The reading process well do similar things, but it will read instead of append. Of course, this means you have to have a lock-queuing mechanism implemented. And you have to know in advance that the file is sharable. A more interesting problem is: how will the reading process know when information has been appended to the logfile? Naturally it could 'poll', but it would be much nicer if it could get an interrupt whenever the logging process had made the file longer. chuck_simmons%d1@dartvax
jeff@rtech.ARPA (Jeff Lichtman) (03/08/85)
> > VMS, on the other hand, has a locking mechanism that locks magic cookies; > > ... > > This means you can lock things other than files; perhaps locking should > > have nothing to do with the file system. > > (in my opinion) Locking should have a lot to do with the file system. > ... > The > cooperating applications simply agree on the name of a file. To lock > the magic cookie, a process opens the file with all permissions. To > unlock the magic cookie, the process closes the file. > > Thanks, chuck_simmons%dcts1@dartvax Why should one have to pay the overhead of opening a file in order to obtain a lock? Opening a file is expensive on every operating system I know about. Also, you would be forced to have a file for every (non-file) object you wanted to lock. If you couldn't predict in advance the number of locks your program was likely to get, you would either have to create a enough files in advance to handle the worst case, or you would have to create the files on the fly (more overhead!). I feel that the file system should call the lock manager, and that one should have the option when opening a file to speciify the type of locking to use. Using the file system to do locking requires too much overhead and/or advance allocation of resources. -- Jeff Lichtman at rtech (Relational Technology, Inc.) aka Swazoo Koolak
jlg@lanl.ARPA (03/09/85)
> As a miniumum, by default if one process has a file open with write > permission no other process should be able to read or write that file. The restriction should be that any process can read ANY shared file. The only constraint is that two processes shouldn't be writing to the same file at the same time. Read locks are only present in some systems because some people like to use them as process synchronisation flags. For example, suppose I am trying to read a file that some other process is writing. If my process is ahead of the producer process, I will simply be reading old data (until the end of file, then I will be forced to wait until the producer catches up anyway). But I should EXPECT to read old data if I'm ahead of the producer (if the processes are really asynchronous I may be unaware that the producer is presently running). So a read lock would only serve to synchronize the two processes - which should be done directly anyway. In the above argument I assume that record transfers are atomic operations in the O/S (that is, the contents of a partially written record cannot be read). If this is not the case, problems will develop with or without read locks. Remember, people will ask for the specific ability to override any automatically applied locks. Someone made the claim that there are some issues pertaining to locks that UNIX could not do at all even with libraries. This is clearly not true since VAX-UNIX can simulate a general Turing machine and can therefore perform ANY computable function. Clearly all that's required is for processes that share file resources to do all I/O through a third 'monitor' process which envokes your locking scheme. In fact, each shared resource could have its own monitor process associated with it. This means more overhead for those who wish to share file resources, but it means less overhead for those who don't (as compared to a system which implements locks at a lower level). J. Giles
cliff@unmvax.UUCP (03/09/85)
> Someone made the claim that there are some issues pertaining to locks that > UNIX could not do at all even with libraries. This is clearly not true > since VAX-UNIX can simulate a general Turing machine and can therefore > perform ANY computable function. Clear as mud...VAX-UNIX can't even simulate all finite automata, much less a turing machine. Does anyone out there have a machine that *can* simulate a turing machine? I want to put one next to my perpetual motion machine :-). --Cliff [Matthews] {purdue, cmcl2, ihnp4}!lanl!unmvax!cliff {csu-cs, pur-ee, convex, gatech, ucbvax}!unmvax!cliff 4744 Trumbull S.E. - Albuquerque NM 87108 - (505) 265-9143
jeff@rtech.ARPA (Jeff Lichtman) (03/11/85)
> > As a miniumum, by default if one process has a file open with write > > permission no other process should be able to read or write that file. > > > The restriction should be that any process can read ANY shared file. The > only constraint is that two processes shouldn't be writing to the same file > at the same time. Read locks are only present in some systems because some > people like to use them as process synchronisation flags. > > J. Giles Read locks are very important in transaction systems. If a process is allowed to read a write-locked object, then it's possible for it to read data that will later be backed out. This could happen if the writer terminates abnormally, or it deliberately orders a roll-back. For example, suppose that one program was performing an audit, and another was updating accounts. If the updater updated an account and then later rolled back this update, the reader could get an invalid view of the update. Also, if the writer has to make multiple updates to make the data consistent (e.g. deducting from one account and crediting another), a reader could get an inconsistent view of the data by reading only part of the updates. My feeling is that the default should always be to prevent disaster. If the user wants to take the chance of inconsistency, or knows how to write programs and schedule jobs to prevent inconsistency, then he or she should have the option of relaxing the default. A user shouldn't have to make a concious decision to prevent disaster. -- Jeff Lichtman at rtech (Relational Technology, Inc.) aka Swazoo Koolak
jlg@lanl.ARPA (03/11/85)
> > Someone made the claim that there are some issues pertaining to locks that > > UNIX could not do at all even with libraries. This is clearly not true > > since VAX-UNIX can simulate a general Turing machine and can therefore > > perform ANY computable function. > > Clear as mud...VAX-UNIX can't even simulate all finite automata, much less > a turing machine. Does anyone out there have a machine that *can* simulate > a turing machine? I want to put one next to my perpetual motion machine :-). MOST computers can SIMULATE a Turing machine. The only thing that prevents them from being computationally equivalent to a Turing machine is the lack of an infinite store. But even an infinite store can be SIMULATED by simply changing the disk packs as they fill. Theorems of computational equivalence can (and frequently are) applied to finite systems as well as infinite ones. Obviously, Turing machine simulation can only proceed as far as your budget for mass storage allows, but it really IS a simulation of the real thing. There is a difference between simulation and reality. J. Giles
honey@down.FUN (code 101) (03/12/85)
cliff, intending to impress us all with his wit and his intelligence, notes that vax/unix is not a turing machine, for it "can't even simulate all finite automata." tell us, cliff, what would you call a machine that can simulate all finite automata? peter
jqj@cornell.UUCP (J Q Johnson) (03/12/85)
>...VAX-UNIX can't even simulate all finite automata, much less >a turing machine. Does anyone out there have a machine that *can* simulate >a turing machine? I want to put one next to my perpetual motion machine :-). As with most things, it depends on your precise definitions. I consider my VAX/UNIX machine to be a Turing machine since it has a tape drive and the possibility of adding more modern mass storage devices as they are developed. I figure that I can always hang another tape if necessary (perhaps waiting while the manufacturer makes more tapes for me), thereby giving me an infinite-tape Turing machine. Note that a very simple program for a Turing machine (one that reads n positions on the tape then rewinds) may for large n take quite a while to complete since I might need a large piece of the mass of the Universe as the raw material for the MANY tapes required. Assumptions: 1/ I have good field service technicians who can keep my VAX running for an arbitrarily long time, and 2/ either the mass of the Universe is infinite or there is no limit on inventable recording densities (since I need to be able to store a finite but unbounded amount of information). Now that I've given you a Turing machine, would you consider a satellite as a candidate for a perpetual motion device (not a machine since getting useful work out of it would make it non-perpetual)?
johnl@ima.UUCP (03/13/85)
> My feeling is that the default should always be to prevent disaster.
(The writer was advocating very stringent default locking to avoid letting
programs read partly updated or inconsistent data by mistake.)
It depends what you mean by disaster. In your system, it's evidently
disastrous for people to see an inconsistent view of a data base. In my
system, it's disastrous for some gonzo to read lock /etc/passwd so that
nobody can log in. Both are real problems, but different environments
require different approaches.
I've argued this with a lot of people, and it has become evident to me that
no simple locking scheme can do the right thing, whatever that is, in more
than a minority of circumstances. As a result, I've become firmly attached
to the idea of locking magic cookies so that a group of programs that want
to synchronize their reading and writing can do so, while other programs
that don't understand locking do not get "file locked" errors that they
cannot deal with.
Oh, and lest you get the wrong idea, the magic cookies should be named in
the file system name space, which on a Unix system is the only real name
space there is, and is certainly the only one rich enough to deal with
private groups of locks, local groups of locks, and such.
John Levine, ima!johnl
PS: I promise not to write any more on this topic for at least a month.
cliff@unmvax.UUCP (03/18/85)
Here is the original claim that prompted my retort: **************************************************************************** Someone made the claim that there are some issues pertaining to locks that UNIX could not do at all even with libraries. This is clearly not true since VAX-UNIX can simulate a general Turing machine and can therefore perform ANY computable function. **************************************************************************** Many articles/letters have been written concerning my reply: **************************************************************************** Clear as mud...VAX-UNIX can't even simulate all finite automata, much less a turing machine. Does anyone out there have a machine that *can* simulate a turing machine? I want to put one next to my perpetual motion machine :-). **************************************************************************** TM are useful abstractions for many proofs, but the VAX-UNIX simulation paragraph is a crock. Not only can't VAX-UNIX simulate TM, it is irrelevant to "issues pertaining to locks." Here are a few answers/comments: 1. >do you have an example of a finite automata that >VAX/UNIX can't simulate There is only a fixed number of states that any VAX-UNIX configuration can be in (although this number is quite large), call this number N. It is impossible to simulate a FA that reads a "tape" and only accepts if the "tape" contains exactly N+1 1's on it. 2. >As with most things, it depends on your precise definitions. I >consider my VAX/UNIX machine to be a Turing machine since it has a tape >drive and the possibility of adding more modern mass storage devices as >they are developed. The tape is not infinite, nor is the control arbitrarily large. The article was about real VAX-UNIX machines (which is why the theoretical TM doesn't apply) ... you can claim that you can continually put new tape on it, but that does not make it so, the fact is you can't and that should be obvious. 3. >cliff, intending to impress us all with his wit and his intelligence, >notes that vax/unix is not a turing machine, for it "can't even >simulate all finite automata." tell us, cliff, what would you call a >machine that can simulate all finite automata? > peter Peter, you are almost correct. I was hoping my wit and intelligence would impress *you!* Why should I worry about the other schmucks...after all, you are the man, eh? Of course the answer to your question is either a Turing machine, or Wendy, depending on the zone (look at zee map). The point I was making is that since VAX-UNIX can't simulate all FA, it obviously can't simulate all TM (the redundancy is beside the point...look at how many people got stuck elsewhere). I am glad that I was less than explicit, otherwise I might not have had the chance to clarify my intent to impress you. I was so excited to see that not only did you read my article and find it worth replying to, but you actually knew my name! 4. >MOST computers can SIMULATE a Turing machine. The only thing that prevents >them from being computationally equivalent to a Turing machine is the lack >of an infinite store. But even an infinite store can be SIMULATED by simply >changing the disk packs as they fill. I think you are confusing *very large* with infinite. 5. >Theorems of computational equivalence >can (and frequently are) applied to finite systems as well as infinite ones. That is true, but your application was way off base. First there is your claim "since VAX-UNIX can simulate a general Turing machine and can therefore perform ANY computable function." which is not even remotely true. Then there is the fact that TM are models of computation, which does not always directly concern "issues pertaining to locks." An example is the locking protocol of an Ethernet where there are real-time concerns ... "time" from a TM perspective is quite different from real-time. Just how do you model an ethernet with a TM? --Cliff [Matthews] {purdue, cmcl2, ihnp4}!lanl!unmvax!cliff {csu-cs, pur-ee, convex, gatech, ucbvax}!unmvax!cliff 4744 Trumbull S.E. - Albuquerque NM 87108 - (505) 265-9143
jlg@lanl.ARPA (03/19/85)
> 4. >MOST computers can SIMULATE a Turing machine. The only thing that prevents > >them from being computationally equivalent to a Turing machine is the lack > >of an infinite store. But even an infinite store can be SIMULATED by simply > >changing the disk packs as they fill. > > I think you are confusing *very large* with infinite. I think YOU are confusing 'simulation' with 'computational equivalence'. The two are not synonymous. 'Infinite' can be simulated by 'very large', it's fairly easy and I gave an example of how to do it. > 5. >Theorems of computational equivalence > >can (and frequently are) applied to finite systems as well as infinite ones. > > That is true, but your application was way off base. First there is your claim > "since VAX-UNIX can simulate a general Turing machine and can therefore > perform ANY computable function." > which is not even remotely true. Then there is the fact that TM are models of > computation, which does not always directly concern "issues pertaining to > locks." An example is the locking protocol of an Ethernet where there are > real-time concerns ... "time" from a TM perspective is quite different from > real-time. Just how do you model an ethernet with a TM? Real easy to model an ethernet with a Turing Machine - keep time as a variable within the code. This is how modeling is done. A lot of physical phenomena occur in time-frames of 10^(-10) seconds or less, no computer (yet) can run this fast, but the phenomena CAN be modeled (we do it all the time). As for locks in VAX/UNIX vs. VAX/VMS - both systems fail to be computationally equivalent to Turing Machines in the same way: lack of infinite store. Therefore, any proceedure which works on a VAX/VMS system can also be made to work on a VAX/UNIX system with, at most, an addition of storage. The VMS locking protocol supposedly works on VAX/VMS systems, so it can also be implemented on a VAX/UNIX system. If nothing else you can simulate a bare VAX under UNIX and run VMS on that virtual machine. J. Giles
phil@osiris.UUCP (Philip Kos) (03/20/85)
> . . . Therefore, any proceedure which works on a VAX/VMS system > can also be made to work on a VAX/UNIX system with, at most, an addition of > storage. The VMS locking protocol supposedly works on VAX/VMS systems, so > it can also be implemented on a VAX/UNIX system. If nothing else you can > simulate a bare VAX under UNIX and run VMS on that virtual machine. > > J. Giles Perhaps somebody from Relational Technology would be interested in discussing the problem of locking on UNIX, since they had to deal with it in porting Ingres to UNIX machines. Phil Kos The Johns Hopkins Hospital