Michael Scott has been a professor of Computer Science at the University of Rochester for 34 years , and has been dean for five years at his Wisconsin – Madison university. He is engaged in research in the field of parallel and distributed programming and language design and teaches students this.

The world knows Michael from the “Programming Language Pragmatics” textbook, and the work “Algorithms for scalable synchronization on shared-memory multiprocessors” won the Dijkstra Award as one of the most well-known in the field of distributed computing. You can also know him as the author of the very algorithm Michael-Scott .

Together with Doug Lee, he developed those non-blocking algorithms and synchronous queues that run Java libraries. The implementation of “dual data structures” in JavaSE 6 enabled a 10-fold improvement in the performance of the ThreadPoolExecutor .

Content:

• Early career, University of Rochester. Project Charlotte, Lynx language;
• IEEE Scalable Coherent Interface, MCS Lock;
• Survival in an ever changing world;
• Are students becoming more stupid? Global trends, internationalization;
• Effective work with students;
• How to keep up with the preparation of new courses and books;
• The relationship between business and academy;
• Practical implementation of ideas. MCS, MS, CLH, JSR 166, working with Doug Lee and more;
• Transaction memory;
• New architectures. Close victory of transactional memory;
• Non-volatile memory, Optane DIMM, ultra-fast devices;
• The next big trend. Dual data structures. Hydra.

Interviews are:

Vitaly Aksenov is currently a post-dock at IST Austria and an employee of the Computer Technologies Department at ITMO University. Engaged in research in the theory and practice of competitive data structures. Before joining IST, he received a PhD at the University of Paris Diderot and at the University ITMO under the guidance of Professor Peter Kuznetsov.

Alexey Fedorov is a producer at the JUG Ru Group, a Russian company that organizes conferences for developers. Alexey participated in the preparation of more than 50 conferences, and in his resume there is anything from the position of a software engineer at Oracle (JCK, Java Platform Group) to the position of a devrela at Odnoklassniki.

Vladimir Sitnikov is an engineer at Netcracker. For ten years, it has been working on the performance and scalability of NetCracker OS — the software used by telecom operators to automate network management processes and network equipment. He is interested in Java and Oracle Database performance issues. Author of over a dozen performance improvements in the official PostgreSQL JDBC driver.

Early career, University of Rochester. Project Charlotte, Lynx language.

Alexey : To begin with, I wanted to tell you that we all in Russia love very much Computer Science, Data Science and algorithms. Right to indecency. We all read the book Cormen, Leiserson and Rivest . Therefore, the upcoming conference, the school and the interview itself should be very popular. We have received many questions for this interview from students, programmers and community members, so we are very grateful for this opportunity. Does Computer Science have the same love in the USA?

Michael : Our region is so diverse, there are so many directions in it, and it affects society in such various ways that it is difficult for me to answer you unequivocally. But the fact is that thanks to her over the past 30 years, there have been tremendous changes in business, industry, art and society as a whole.
')
Vitali : Let's start with something remote. In many universities, there is something like specialization in one particular direction. For Carnegie Mellon University, this is parallel computing; for MIT, cryptography, robots, and multithreading. Is there such a specialization at the University of Rochester?

Michael : To be honest, I would say that CMU and MIT specialize in all areas. Our department has always paid the most attention to artificial intelligence. Half of the people working for us are engaged in AI or human-computer interaction - this proportion is greater than in other departments, and it has always been so. But when I studied at the university, I did not have courses on AI, and I never worked in this area. So my department specializes in a problem that I have nothing to do with. The consolation is that the second most important problem for our department is parallel and multi-threaded programming, that is, my specialty.

Vitaliy : You started to study Computer Science, when the area of ​​multi-threaded programming was just emerging. The list of your publications shows that the first works dealt with a fairly wide range of issues: memory management in multi-threaded systems, distributed file systems, operating systems. Why such versatility? Have you tried to find your place in the research community?

Michael : As a student, I participated in a Charlotte project at the University of Wisconsin, which developed one of the first distributed operating systems. There I worked with Raphael Finkel and Marvin Solomon. My dissertation was devoted to the development of a language for system software for distributed systems - now everyone has already forgotten about it, and thank God. I created the Lynx programming language, which was supposed to simplify the creation of servers for a weakly linked distributed operating system. Since at that time I was mainly engaged in operating systems, I assumed that my career would be mainly related to them. But in Rochester, the university was very small, and because of this, different groups there very closely communicated with each other. There were not a dozen other operating system specialists with whom I could communicate, so all contacts were with people who worked in completely different areas. I really liked it, being a generalist is a big advantage for me. If we talk specifically about multi-stream data structures and synchronization algorithms, then I began to work on them completely by accident.

IEEE Scalable Coherent Interface, MCS lock.

Vitali : Can you tell a little more about this?

Michael : It's a funny story that I don’t get tired of telling everyone. It occurred at the ASPLOS conference in Boston - it was in the late 80s or early 90s. The conference was attended by John Mellor-Crummey, a graduate of our faculty. I was familiar with him, but we had not conducted joint research before. Mary Vernon from Wisconsin made a presentation on the multiprocessor system they developed in Wisconsin: Wisconsin Multicube . In this Multicube, at the iron level, there was a synchronization mechanism called Q on Sync Bit, and later it was renamed Q on Lock Bit, because it could be pronounced like the name of Colby cheese, that is, it was such a pun. If you are interested in multi-threading mechanisms, you probably know that Colby eventually became the synchronization mechanism of the standard Scalable Coherent Interface from IEEE. It was a blocking mechanism that created pointers from one cache to another at the iron level, so that each lock holder knew whose turn it was. When John and I heard about this, we looked at each other and said: why do it at the iron level? Isn't it possible to achieve the same with compare-and-swap? We took one of the notebooks in the audience and sketched the MCS lock on it while Mary continued her report. Later we implemented it, experimented it, the idea was successful, and we published an article. Then, for me, this topic seemed only an amusing distraction, after which I planned to return to the operating systems. But then another problem arose in the same direction, and eventually synchronization, multithreading and data structures became my main specialty. As you can see, it all happened by accident.

Vitaliy : I have long been familiar with the blocking of MCS, but until now I did not know that it was your job, and did not understand that it was an acronym for your surnames.

How to survive in a constantly changing world?

Alexey : I have a question on a related topic. 30 or 40 years ago there was more freedom in different specialties. Do you want to start a career in multithreading or distributed systems - please, you want to deal with operating systems - no problem. In each area there were a lot of open questions and few experts. Now there are narrow specializations: there are no experts on operating systems as a whole, there are specialists in individual systems. The same with multithreading and distributed systems. But the problem is that our lives are not endless, everyone can devote to research only a few decades. How to survive in this new world?

Michael : We are not special in this regard, the same thing happened sometime in other areas. I was lucky that I started working in Computer Science when this sphere was in the “teenage” age. Some of the foundations had already been laid, but everything was still very immature. Such an opportunity appears infrequently. Electrical engineering has existed for a very long time, physics - even longer, mathematics - almost from the beginning of time. But this does not mean that in mathematics no one else makes interesting discoveries. There are still many open problems, but at the same time you need to learn more. You correctly noted that there are now much more specializations than there were before, but this only means that we find ourselves in the same situation as most of the other areas of human activity.

Alexey : I am interested in the more practical aspect of the question. I have a mathematical education, and during my studies I often attended conferences and worked on various scientific topics. I found that no one in the audience understood my reports, and in the same way, the reports of other people were clear only to themselves. In high-level topics this is not the case, but as soon as you begin to delve into something, the audience behind you is no longer in time. How are you fighting this?

Michael : Not always successful. Recently, I prepared a report that went too deep into technical details. In the course of the report, it became clear that most of the audience did not understand me, so I had to adapt to the situation on the go. Slides were no longer to change, so it turned out not too successfully - therefore, generally speaking, I try not to use slides. In general, my advice is this - consider your audience. You need to know who you are applying to, what level of knowledge they have and what they need to hear in order to evaluate your work.

Vitali : Could you hint what this lecture was about?

Michael : To be honest, I would prefer not to dwell on this subject, in order to leave the people in question anonymous. The bottom line is that we often dive too deep into the subtleties of the problem we are working on, so it becomes difficult for us to explain at the beginning of the report why this problem is interesting and important and how it relates to questions that the listeners already know. According to my observations, students this skill is given the hardest. And that was the weakness of my recent report. A properly constructed report should, from the very beginning, find contact with the audience, explain to it exactly what the problem is and how it relates to topics already known to her. How technical this introductory part will be depends on the audience. If it is quite mixed, then the report can be multi-stage. Entry should be available to everyone, and by the end, some may not be able to keep up with you, but people who are relatively familiar with your area will be able to figure everything out.

Are students becoming more stupid? Global trends, internationalization.

Alexey : You have been observing students for several decades. Do students become smarter or smarter from decade to decade or from year to year? In Russia, professors constantly complain that students grow stupid every year, and it’s really not clear what to do with it.

Michael : From us, old people, you can really hear a lot of negativity. Subconsciously, we have a tendency to expect students to learn all that 30 years of experience that we already have. If I have a deeper understanding than in 1985, then why do students not have it? Probably because they are 20 years old, how are you? I think the most significant changes in recent decades are related to the demographic composition: we now have significantly more international students, with the exception of Canadians. Previously, there were many Canadians, because we are very close to the border with Canada, and students from there can go home on weekends. But now there are many good universities in Canada, and Canadians prefer to study with themselves, in the US they began to travel significantly less.

Alexey : Do you think this is a local trend or global?

Michael : I don’t remember exactly who, but someone said that the world is flat. Our area has become much more international. ACM conferences used to be held exclusively within the USA, then they decided to hold them in other countries once every 4 years, and now they are taking place around the world. Even more, these changes affected the IEEE , since it has always been a more international organization than ACM. And there are program managers from China, India, Russia, Germany and many other countries, because there is a lot going on everywhere now.

Alexey : But, probably, there are some negative sides of such internationalization?

Michael : I would say that all the negative aspects relate not to technology, but to politics. At one time, the main problem was the fact that the United States stole the most intelligent and talented people from countries all over the world. And now the main problem is political games between different countries around visas and immigration.

Alexey : That is, barriers and similar things. Clear.

Vladimir : Personally, I wonder what approach you take when you teach a new subject to students. There are different options: you can try first to inspire them to try something new, and you can pay more attention to the details of how a certain technology works. What do you prefer?

Effective work with students

Alexey : And how to find the damn balance between the first and second?

Michael : The problem is that classes do not always take place as I would like. Usually, I give students reading material in advance so that they get into it, understand as much as they can and formulate questions about the places that could not be understood. Then you can focus on the most difficult moments in the classroom and explore them all together. This is how I like to teach the most. But taking into account the load that now lies on the students, I do not always manage to get them prepared in advance. As a result, we have to devote much more time to the general retelling of the material than we would like. Despite this, I try to make our classes interactive. Otherwise, it is easier to record a video once, which students can then watch at home. The meaning of living activities is in human interaction. In class, I prefer not to use slides, but chalk and blackboard, except in some cases when a diagram is too complicated to be drawn on a blackboard. Because of this, I do not need to adhere to a rigid lesson plan. Since there is no strictly defined order in which I give material, this allows you to adapt to the audience depending on the questions I receive. In general, I try to make the classes as interactive as possible, so that the material I present depends on the questions that are being asked.

Vladimir : This is very cool. In my experience it is quite difficult to get questions from the listeners. Even if you ask in advance to ask any questions, no matter whether stupid or clever, they are still silent. How do you handle it?

Michael : You will laugh, but if you stand silently for a long time, then sooner or later everyone will become uncomfortable, and somebody will ask a question. Or you can ask a simple technical question with the answer “yes” or “no” to determine whether people understood what was just mentioned. For example, is there a data race in the given example? Who thinks so? Who thinks not? Who does not understand anything at all, because in total only half of the hands have risen?

Vitaliy : And if you answered incorrectly, you take off from the class :-)

Michael : If you haven't answered anything, then you have to ask a question. I have to understand what a student needs to know in order to answer the question I just asked. I need them to help me help them. I am ready to adjust to them so that they understand the problem. But if I do not know what is going on in their heads, I cannot do it. And if you don’t give students peace of mind for a long time, in the end, sometimes they ask the right questions, that is, through which I see what is happening in the minds of the students.

Alexey : Do these questions sometimes push on ideas that you haven’t thought of before? Are they unexpected? Do they allow to look at some problem in a new light?

Michael : There are questions that open up a new way of presenting material. Often there are questions that lead to interesting problems that I did not plan to talk about. Students often tell me that I have a tendency to move away from the topic of an occupation when this happens. And, according to them, very often this is the most interesting part of the lesson. Quite rarely, literally several times, students asked questions that pushed on a new direction in research and grew into an article. This happens much more often in conversations with students, and not during class, but occasionally it was during class.

Alexey : That is, the students asked you questions, on the basis of which you could then publish an article?

Michael : Yes.

Vitaliy : How often do you have such conversations with students? , ?

: — . - 5 6 , - . , — . , . , . , . , , . , , , .

: ? , — .

: , — , . . , , . , , 9 17 . , , — .

.

: - , ? - Computer Science.

: , — .

: , 10, 20, 30 ? , , .

: , . 1980-, , ( Doug Baldwin ). , , . , . ( : «Programming Language Pragmatics» ) 200 . , , . , : , , , . , , . , Pascal, . Swift, Go, Rust, , . , , , . Python, Ruby Perl, , , , .

: . ? , — , . ?

: , 100% . , — . Rust, Google, Mozilla . , . , .

: . (cache coherence). , ? . ?

: , . ( William Bolosky ) ( Leonidas Kontothanassis ) 1990- . , : , , , . . , NUMA, page placement . , , — . , (hardware transactional memory). , , . , , . , .

: : , ? ?

: , , . , . , , . , , - . , - - , . . - , , . — .

: . , . , , Intel. , ?

: , , , - . , : , , . , , , . , , , , . , , . , . , . - 15 . , , «How to evaluate systems research» - , . , , , , . , .

: , , . , , TDP, . ? , ?

: , . , . , , . , Linux. , AWS. .

: ? ?

: . - 1980- , . , (National Science Foundation ) (Coordinated Experimental Research, CER). Computer Science, . 1984 128- BBN Butterfly, . . 128 , , . , 128 . MCS.

: , ?

: — . : -, , , . - 10 , - . Intel. , , , . , ( Steven Swanson ) . , . , . , , , .

. MCS, MS, CLH, JSR 166, .

: , . MCS - (MS) , Java. ( : ). CLH , . .

: , 10 .

: Java?

: . , ? ?

: , MS Java 5. (Mark Moyers) Sun Microsystems . , , , . (Doug Lea). , - 25 Sun JSR 166 , java.util.concurrent. , MS, . , , . , . , « », . , . Java.

: , .size() , O(1)?

: , .

: .size() Java, , , . , .

: (dual data structures) (Bill Scherer) — , Hydra . , Java Executor Framework. , (fair and unfair queues). , . executors .

: ? , . , , , , , - . ?

: , « » — , . , . , K42 IBM MCS , acquire release. , , . , , , . , .

, . , MS , , CAS. CAS . Intel , - 30 , . , MS, . , O(n) , O(1). , . - , . , . , , , , . . (Dave Dice) Oracle. , , , . NUMA-aware .

: , . - , , , . .

: , . , , . , . , 10, 20, 25 . , . , , , , . , . , . , , 10 . — 20. , . . , . (Joe Izraelevitz) DISC, , . , , . , . , , .

: - , ? , ? , , , .

: , , . -, , Google Scholar , , . , . , , , — . . , , , . , , .

: , ?

: , , . , , . , , . , (M. Herlihy, JEB Moss) . 1990- , , , . , JSR 166. , . 2000-, . . . . , , .

: . , , . , . , , , . ( : — , Disruptor Aeron . Joker 2015, YouTube . , ). , , . . What do you think of it?

: : , .

: , .

: — . , . (Butler Lampson), « ». . , , 10 — . ISA , , . . , . — GPU, , , , FPGA. , ? , .

: , . , . : — , , — , , , .

: — - .

: C++.

: - (Hans Boehm). , , . , . , , , 30 . ( : ).

: : ?

: . , , API. API, . , . . , , , , .

: , , , , , ? , , . , . ?

: . , , , - . , , . MNS . (Adam Morrison) (Yehuda Afek) LCRQ . , , fetch-and-increment. . , fetch-and-increment . (Eric Freudenthal) Ultracomputer c (Allan Gottlieb) 1980-, . fetch-and-increment .

. ?

: , ?

: , , , .

: , ?

: — Intel IBM. , - load store . happens-before, . , , , . , , .

— . , . . , , 100 , , . , , . , - .

: , . ?

: . — . , — . , . , , , . , . , , . . , CAS , , . , , .

, Optane DIMM, .

: , — : . ? , - ?

: , , . , Intel Optane DIMM , - 3 10 , RAM. . , RAM. , 10 , DRAM — . . , - . , - , — . , , . . , , . , , , «» .

, — . . - , , 5 , TCP-IP , . . , , . , . USENIX ATC . , , , I/O, . , .

: — , — . , .

: .

: , ?

: , - . , , . , , - . , .

: . , RAM CPU. - RAM .

: . , . .

: , . .

: . .

: .

. Dual data structures. Hydra.

: , . , , . , ? , , ?

: , . , , - . - , , , . , .

: Hydra . , , . ?

: . , . , , Java. , , . , , , , . , . , — , , . . , 10 , - , . - , . «» , , , -. - , . . , , , . , .

: ? , ?

: , , -, , , -, , , . , , . . , . , .

: : , ?

: , . , , , . , . , . , - MS.

: ?

: , . Hydra. , Java, LCRQ, .

: , Hydra — , - ?

: , , Hydra , Java, , .

: , .

: , .

: , : .

: , ? ?

: , , . , . , . , SPTDC; - Java, -, Java. Java, .

: , Hydra - , , - . , . , , . , . Thank you very much!

: .

: -.

: , . - ?

: , . - , , , .

: , . , !

Hydra 2019, 11-12 2019 -. «Dual data structures» . .