Does "True" Computer multi-tasking exist?

Factual Questions
41

That is correct but I was trying to answer the OP’s question using his teacher’s definition. The term was “true multi-tasking”, which (to him) likely meant concurrent asynchronous execution. It is true that’s not what “multi-tasking” really means but the purpose of words is to convey ideas and you sometimes must look beyond the words to perceive the intent of the question. Otherwise it never gets answered in a way the OP can understand.

Part of this is just common sense. Outside of the SMP interpretation, to say no computer can do “true multi-tasking” has no rational meaning. It is very unlikely he meant that no computer can do multi-tasking by the strict industry definition.

It is absolutely an illusion on a uniprocessor, and THAT is the core issue of the OP and his teacher. Acknowledging this is necessary to understand the source of his confusion and possible basis for the question.

That is correct but we must look beyond a rigid dictionary definition and in a sensitive helpful way try to be empathetic and perceive the actual intent of the OP’s question. His teacher’s phrase “true multi-tasking” was likely referring to true concurrent execution. Whether that is the correct dictionary definition or not, to help people we must perceive their actual intent of their question, not take hard stand on terminology as if we were a hostile prosecuting attorney in a court of law.

I did not say or mean to imply that ALL or even MOST IBM mainframes used symmetric multi-processing since the mid-1960s, rather that it was an available technology which existed within their mainframe product line.

It’s my understanding the S/360-67 and multiprocessor option was announced on August 16, 1965.

However the main point is symmetric multiprocessing was a known and implemented technology as early as 1962. Probably the first was the Burroughs D825: https://ubiquity.acm.org/article.cfm?id=2618393

Yes it’s correct that multi-tasking and multi-processing are technically different things, but it is highly likely the OP’s phrase “true multi-tasking” (while technically incorrect) was in fact referring to asynchronous concurrent execution of multiple code paths in a symmetric processing configuration. This technology has existed and been in the marketplace since the early-to-mid 1960s.

By the mid-1970s this was more commonplace. The IBM 3033 was available in a dyadic or dual-processor symmetric configuration in 1978.

In the minicomputer space the Data General MV/20000 Model 2 (which I worked on) was announced in 1985, which was a dual-CPU SMP machine.

As already stated by the mid-1990s true SMP desktop machines were widely available running Windows NT.

In the most likely interpretation of the OP’s teacher, all these SMP machines since the early 1960s could do “true multi-tasking”, in that multiple concurrent tasks or code paths were in true simultaneous execution.

42

The thing is, not only does this question depend on precisely how you define all of the terms in it, but once you’ve precisely defined all of the terms, the answer becomes trivial. If, for instance, you define “multitasking” as a single processor carrying out more than one operation at a time, and define a “processor” as a unit of a computer which is only capable of one operation at a time, then it takes no thought at all to say that, clearly, multitasking is impossible. But you’ll get different answers, also all trivially simple, from other definitions of those terms.

43

Historical note: In 1982 when PC-DOS 1.0 (aka MS-DOS 1.0) was upgraded to PC-DOS 1.1, one of the major changes was to add a background printer manager. Presto! The 1-task OS changed to a 2-task OS. (Of course, interrupt handlers can be viewed as “tasks”, in which view even PC-DOS 1.0 did multi-tasking.)

Of course, long before PC-DOS — at least as early as 1964 — there were operating systems far more sophisticated than PC-DOS that offered a more general approach to multi-tasking.

When a single processor operates in a multi-task mode, the tasks run concurrently, not simultaneously. Is that the distinction OP’s son’s teacher is making?

44

Multi-tasking is about state, and maintaining that state.

It is a broader concept that contains more specific concepts but does not depend on them.

If a computer teacher actually believes “concurrent asynchronous execution” is “true multi-tasking” they do not fully understand the concept or the implementation requirements and details.

To implement “multitasking” you do not need to implement multiple CPUs or simultaneous concurrent execution. In todays world due to technological advances the definition may not seem important and to be honest for almost all computer scientists today it is not critical.

But if you were applying for a job where these concepts are critical, like say you were applying for a job as a a kernel developer, and couldn’t separate these concepts in a job interview it would be considered an area where you lack knowledge and understanding.

“multitasking” is a jargon term, with a broad but specific meaning with very real implications. If you look at wolfpup’s cites, this is the critical aspect “Multitasking does not require parallel execution of multiple tasks at exactly the same time”

The mistake many above posters are making is that they are considering details of specific implementations and not the overarching concept.

As a precise term of jargon, “multi-tasking” has specific implementation requirements and those requirements depend on state storage and scheduling but do not care about what specific choices are made on that implementation.

To implement “multi-tasking” maintaining state across interleaved execution is the critical detail, not how the execution exists.

We don’t know from the OP if the teacher just failed to communicate this concept or if their concept was incorrect, but if they insisted that “true multi-tasking” required simultaneous or parallel execution they would fail in a job interview as a kernel developer.

The concept of multi-tasking simply is not dependent on simultaneous or parallel execution and more critically absolutely depends on maintaining state between interrupted, non-contiguous execution.

While it may seem this differentiation is subtle it is not at the implementation level and restoring execution to the same state as before a process was interrupted and scheduling that execution is where most of this complexity exists.

Aspects like the criteria to decide how long to allocate to any one task, how to save and restore state, and other implementation details were very hard to solve and continue to have important implications for specific computing needs. The allocation of compute time and saving and restoring state is what defines “multi-tasking” and not the related or derivative needs of parallel execution or multi-processing.

English isn’t the best method to communicate these ideas, but a venn diagram would convey the information on set membership with ease. But don’t get stuck in the implementation details of a specific solution for this need, the concept is broader than that and if you are looking to dive deep into computer science this will be important for an interview at some point in your life.

Spend some time ruminating on the implications of this statement:

“multi-tasking simply is not dependent on simultaneous or parallel execution”

That statement will explain why most of the responses to this thread are way too product and implementation specific. Maintaining state and scheduling serial operations on a single, non-parallel resource is “true multi-tasking” and even if you have many CPUs the implications for saving and loading state, scheduling time, and providing methods to interrupt execution are what is important.

I would suggest you dump the “true” label altogether as shown above it leads to confusion and in the domain of Computer Science you will have a personal meaning for a term which won’t be useful for you.

Multi-tasking does not require, depend on, or imply simultaneous or parallel execution.

45

TLDR: The concept of multi-tasking does not require, depend on, imply, or exclude simultaneous or parallel execution.

It requires saving/loading state and scheduling execution and making decisions on how you choose to implement it.

46

The statement was conveyed from a high school teacher to his student to the student’s father, who posted a question about it here. So obviously the original statement could have been garbled in that transmission.

The statement about “true multitasking” was allegedly the teacher’s so we have to consider his possible meaning, which means we have to restate that term to try and answer the father’s question.

The word “multitasking” itself does not have a rigorously exact definition. It was apparently first used in a computer context in 1966 in the industry trade journal Datamation. The current definition in the Oxford Dictionary of Computer Science is “…The concurrent execution of a number of tasks, i.e. of a number of jobs or processes”. But concurrent on what time scale?

The term “true multitasking” is not unknown – even in the industry. A search of Google Scholar shows that and similar variants sometimes refer to actual concurrent parallel execution, as contrasted with the illusion of concurrent execution by a multitasking operating system on a uniprocessor. I personally don’t like the term but to answer the father’s question we have to try and deduce the intent of the teacher’s statement.

Over the decades I have heard several engineers and computer science professors say regarding a multitasking operating system “of course, it’s not really running multiple tasks concurrently, but rapid time slicing makes it appear so”. From a single-core uniprocessor perspective that is correct, and maybe that was what the high school teacher was trying to convey.

However he allegedly said “no computers currently do or have ever done true multi-tasking”. If true, that is harder to understand. The discussion about multiprocessors was intended to show that true concurrent execution commonly exists today and has to some degree since the 1960s.

The statement *“processors have become more powerful they can seamlessly switch between processes so fast that it is “virtual” multi-tasking, but they’re still only doing one thing quickly” * further implies it was a general statement about computers as uniprocessors. Things like that were very commonly said (even in academia) 30 years ago, even though a few SMP computers were around then.

From a desktop PC perspective, multiprocessing computers have only been truly ubiquitous since the mid-2000s – not that long ago. Before that “true multitasking” was not concurrent execution but rapid time-slicing between processes or threads.

Maybe the teacher’s perspective was a generalized backward-looking overview of “computers” as an idealized uniprocessor construct with a goal of explaining how multi-tasking provides the appearance of concurrent execution. However if he really stated it as conveyed, it’s out of touch with how most computers have worked for many years.

47

Many moons ago when I was taking certification courses, I remember instructors taking pains to explain that a CPU can only do one thing at any given time. The OS is using some clever sleight-of-hand to fool us into think that it’s multi-tasking. This was back before multi-CPU desktops were common, and multi-core CPUs weren’t even a thing.

I think the technical ground has already been well-covered upthread. I just wanted to mention that I too remember instructors being weirdly emphatic about that point, and I could see someone taking it too far.

48

Something I think deserves mention.
Why was the teacher saying this? There is a very important pedagogical point that I’m sure (OK, I hope) was part of the underlying reason.
There is often a confusion about the way the “operating system” works in relation to a user level program. I have seen students (and other people who really should know better) have the ill defined notion that the operating system is executing along with the user program. One of the key things to teach, if you are teaching about the principles of operating systems, and basic computer architecture is the divide between user programs and how you transit to kernel mode (and back), and how this transition is absolutely key for any form of secure operating system. Even ignoring security, the conventional kernel trap/return-from-exception-or-interrupt paradigm dominates ASIs, and is such a basic and important idea that it deserves more attention than it seems to get. Part of describing this, one needs to look at the manner in which a single core can’t do more than one thing at a time.
Whether this was part of the lesson, I have no idea, but it should be.

ETA, HMS Irruncible gets it almost there right before me. This weird emphasis has a reason, although I wonder if the teachers knew why it was needed.

49

That wasn’t true even then. As mentioned above, computers had multiple ALUs. Horizontally microprogrammed machines could execute several microoperations in parallel.
Lockheed SUE microcode (yes Lockheed made minicomputers and the SUE was used for the IMP in the very early Internet by BBN) a jump instruction took two microcycles. You were able to cram another microinstruction between the jump and the next executed instruction, so it was basically doing two instructions at once.

50

I think the basic problem is that many see process execution as a chain of instructions, one after another, and do not have the concept of a process having to wait for a disk access or the like. While you can’t execute two instructions in parallel, you can make use of this dead time by executing two processes in parallel in less total time than they would execute sequentially.
And that’s possible when you can save state, as you say, which is why so much emphasis was put on doing this efficiently, including adding hardware like extra registers.

51

My knee-jerk reaction is that your son’s teacher is an idiot. If we are to define parallelism as simply the ability to execute 2 or more instructions at once, then parallelism exists in computing and it has for many years. I’ve been a software engineer for over 20 years. Trust me on this. Parallelism is a thing.

HOWEVER, I’m going to cut your son’s teacher a tiny bit of slack. When you’re teaching basic computer architecture, you start with a very simple (theoretical) CPU. This CPU is a single core CPU that can only execute one instruction at a time. The lessons start this way because it’s the clearest way to explain the concepts of context switching, scheduling, clocks, etc. without muddying the waters with more advanced concepts such as pre-fetching, pre-processing, multiple pipelines, multiple cores, levels of cache, memory controllers, etc. Trying to teach those basic concepts with a modern, multi-core CPU would be the equivalent of an auto shop teacher rolling his 2017 Prius into the classroom on day 1 and asking the students to repair the Toyota Hybrid Synergy Drive™. So … maybe something got lost in translation there?

52

I think most of us agree that what “multitasking” means has pretty much been well explained at this point. Most of the last half-dozen or so posts have tried to do a sort of philosophical wrapping-up of the subject, so in that spirit, herewith my final thoughts on the matter. This idea that a uniprocessor doesn’t do “true multitasking” because of some vague ill-defined notion that a uniprocessor “can only do one thing at a time” is not just wrong, but to me, infuriatingly wrong. It’s wrong on several levels, because it defies the very clear definition of what multitasking is, and because it confusingly conflates two completely unrelated concepts at completely different levels of logical granularity, CPU hardware architecture and software architecture. I suppose it annoys me because it suggests that the teacher making such claims doesn’t have a very firm grasp of the fundamentals himself.

It might be useful, for starters, to have a clearer description of CPU instruction processing. Simplistically but essentially correctly, a uniprocessor has a single program counter (PC) and at any point in time the PC points to one and only one memory address containing one and only one instruction. But if someone is going to go on about the minutiae of CPU operation, they should also mention another feature that has existed in even the most primitive uniprocessors for more than half a century: the program interrupt system.

And here’s why this is important. For the sake of simplicity let’s for the moment forget all about operating systems and just consider a primitive uniprocessor computer in which the user program has direct control of everything. Suppose you need to write a realtime program for a science lab which regularly samples a data stream, does a bunch of processing on the data, and actively displays the processed results and statistics on a monitor that is constantly refreshed. As well, the program needs to accept command inputs at any time, which changes various things that it does.

The most realistic and efficient way to structure such a program is around the interrupt system. Thus, you have a “main loop” of code that handles the ongoing computation and display. For data acquisition, you have the clock programmed to generate interrupts, say, every 100 milliseconds. This interrupts the main loop at exactly the right time when a data sample is needed, saves context and transfers control to an interrupt service routine which performs the necessary data acquisition, then restores context and returns control to the main loop. For command input, each keystroke at the keyboard generates an interrupt which enters an interrupt service routine that buffers the character and returns control, and if it detects a line break, executes the command and returns control to the main loop. And in a priority interrupt system, even interrupt service routines can be interrupted by higher priority interrupts, so you get nested interrupts from which you return in reverse order (often literally by popping saved context off a pushdown stack).

You might have dozens or even hundreds of event-driven threads like this. The beauty of it is that the main loop of ongoing computation and display can be written as if it was simple sequential instructions that the computer executes as if it was doing nothing else. Likewise, each of the interrupt-driven threads can be written to do its job as if there was nothing else going on. Yet when it all comes together, the interrupt system allows these conceptually simple sequential code units to execute asynchronously and responsively to perform the needed tasks in a way that might not be possible at all otherwise, and creating an event-driven code execution path that, if you traced it out, would be unpredictable and appear staggeringly complex. It would be hard to argue that such a system only provides the “illusion” of concurrency. It is multi-threaded in a real, true, important and extremely useful sense.

One might also consider a bug that sometimes arises in these types of multi-threaded or collaborative multitasking systems – the closely related problems of race conditions and deadlocks. These issues can lurk undetected for a long time under the surface of many complex multi-threaded/multitasking software systems. They can manifest seemingly at random, depending on the flow and timing of events. I would love to hear the “multitasking is only an illusion” crowd explain how race conditions and deadlocks can randomly occur on a uniprocessor computer that “can only do one thing at a time”. A race condition is the very definition of multiple concurrent activities interfering with each other. There may not be concurrency at the instruction level in a uniprocessor, but there certainly is at the task or process level.

53

While technically correct, CPU engineers generally consider that to be hardware parallelism, not multitasking multiple streams of machine instructions.

It is correct that on many machines, each machine instruction is decomposed to a group of microinstructions. The micro-sequencer fetches each microinstruction from the control store. On horizonally-microprogrammed machines each microinstruction is composed of multiple fields which do not require further decoding. The bits of each field are routed in parallel to separate hardware logic separate from the other fields. So a single microinstruction could be concurrently doing an add, multiply, shift, overflow check and register load using separate hardware blocks.

However the lowest generally-accessible interface was the machine instruction (or macro-instruction) level. Only microprogrammers on machines with writable control store could access and perform microprogramming, which was essentially the hardware realm. This was during the mainframe and minicomputer era and by programmers of bit slice processors. Microcode on modern integrated CPUs is not accessible even to system programmers.

Despite a uniprocessor internally using horizontal microcode to implement each machine instruction, it is not considered a multitasking CPU capable of running multiple code paths concurrently. A complex microprogram which implements a high level machine instruction such as “enqueue to a linked list” is generally running in a purely serial fashion, even though each microinstruction may be activating various hardware components in parallel.

54

The Central Processing Unit was only one element of a computer. A shared resource. When the CPU runs much faster than the rest of the computer, that shared resource can be shared between multiple threads / users / processes without contention.

A lot of computing used to be I/O bound, and the main things you would wait for were the printer and the tape deck.

55

The contention I was addressing was that a CPU could only do one thing at a time. That’s incorrect. If the contention was that a CPU could execute only one instruction at a time, then there is more support, though even single core single thread machines with long pipelines can be said to be kind of executing more than one instruction at a time.
I did my PhD and additional research on microprogramming, and was back then was an officially certified world leading authority - or at least that was what the North Holland ad for a book with a paper of mine in it said.
Of course horizontal machines have microoperation parallelism, as I said, not instruction set level parallelism.
Microprogramming is still done at Intel, but it is not done for RISC machines, and the old idea of language directed architectures never panned out. I can direct you to a nice paper about that in a book that I reviewed. There is some connection between RISC and vertical microprogramming. Dave Patterson did his dissertation on microprogramming - I heard his talk on it, and it was very good - and the IBM people who really invented RISC were very familiar with microcode thanks to its use in the cheaper System 360 machines.
Most people who aren’t involved in chip design or microprocessor architectures don’t understand how much parallel stuff is going on, even if it doesn’t look like it at the ISA level. The post after the one you responded to covers what one might consider instruction level parallelism.

56

That’s a great point. Of course when I taught computer architecture 40 years ago that’s what we had. And this teacher is in a high school, so I’d wonder if he/she ever even took architecture.
Things are a lot more complicated than they used to be. I proposed in my column that people stop teaching about logic gates with 1 and 0 inputs, since the real waveforms you see at gates in an 8 nm process node don’t look anything like 1s and 0s, and you anchor on a simple input model and not one with crosstalk, power droop and all the other wonderful things you see these days in the real world.

57

Thanks, I have read Patterson’s papers for years. He was against the high-level-language machines, probably a good idea since they didn’t work out. However some effective HLL machines were in production, including the Burroughs B1700. The IBM Future Systems Project was HLL, which resulted in the AS/400. In the Pulitzer Prize-winning book Soul of a New Machine, the competing computer was an HLL design modeled after the Burroughs systems.

Ironically I think the new RISC-V that Patterson is involved with uses a type of vertical microcode, but they call it “millicode”.

As you said, in general microcoded execution is considered instruction-level-parallelism, not multitasking.

It would be interesting to get a response from the OP; there is probably more thoughtful analysis in this thread than he’d get on any other forum.

58

I mean, eh. The program I attended just stuck to logical logic gates - NAND, NOR, etc, with one topic being that if you had only a limited subset of gates, how would you optimize a given circuit.

To me this seems like the layer below this is a quite tractable problem for automated optimizers. Since you can translate a given truth table into many separate combinations of “base” gates, you could build an automated tool that would use the actual real world tradoff matrix to choose which base gates to use, optimizing for a heuristic, for a given subsection of a chip.

Sprinkle a little machine learning in (so the tool doesn’t have to search the almost infinitely large space of permutations) and you should be able to build a chip design tool that beats every human alive. Umm, in fact given that chip topology is a 2 dimension grid problem similar to Go, just the grid is bigger and the goal isn’t to win, it’s to get the best score on a heuristic, it should be very tractable to machine learning…

I would assume that state of the art chip design firms use it heavily, then, especially Nvidia…

But I got off topic, the main thing is, these real world electrical issues mean that you may not be able to cleanly abstract them away. For instance, if the noise you mention means a particular component is statistically a little unreliable, you may want to use error correction strategies that bundle several operations together or work at a higher level of abstraction because your base gates are unreliable, but not so unreliable that you can afford to use ternary logic and majority gates.

59

Done and done. It’s called logic synthesis, and a company called Synopsys has a near monopoly on it. It definitely does it better than people can, driven by RTL languages like Verilog.
The stuff I did required mucking around at the gate level. But that is like mucking around in assembly language. In fact, in just the way I’d say most programmers have never seen assembly code, one of the designers on a chip I was helping with asked me to show him how to trace signals at gate level. It was something he had never needed to do before. This guy was a good designer also.

But my point on gates is not the gates themselves (what you see in a schematic or netlist is gates from the cell library you are using) but the electrical signals driving the gates. They get taught as simple 1s and 0s, but in reality they are a lot more messy.

60

Well yeah of course they are messy, but the only information that comes out of that fuzz on your scope is : 1, 0, and some nonzero chance of error.