# Question
Title: Algorithm for generation of Canonical represented integers
Is there a way to get `canonical representation` of an integer by algorithm? I can get primes, but I don't know how to represent, for example, 1000 as 2^3×5^3. How can I compute the power of each prime number?

# Answer
The simplest algorithm to do this is to divide repeatedly by the prime, until the division no longer yields an integer.
> 4 votes

# Answer
What you're calling the canonical form is a consequence of the fundamental theorem of arithmetic which states that every integer $n\>1$ can be uniquely expressed (up to order) as a product, $$ n = p\_1^{a\_1}\ p\_2^{a\_2}\ \dots \ p\_k^{a\_k} $$ where the $p\_i$ are distinct primes. From a theoretical standpoint, this is particularly interesting since it's currently unknown whether or not there is an efficient algorithm to solve this problem (namely, an algorithm that runs in time polynomial in the number of digits of $n$). Nobody has come up with an efficient algorithm for factorization, but, unlike a lot of known "hard" problems, like the traveling salesman problem, no one has provided a proof that factorization must be hard. While @FrankW's suggested algorithm can be slightly improved, as far as anyone presently knows there's no really efficient solution.
> 3 votes

---
Tags: algorithms, number-theory
---


title: How to reduce bin-packing problems?

text:
# Question
Title: How to reduce bin-packing problems?
This is my first time with reductions and I can't figure out how to do them. I have read the few standard examples that are given in the standard books.

For example, given $n$ numbers $\\{ 0 \< s\_i \<1 , \text{ for }i = 1,..,n \\}$ one wants to minimize the number of number of bins required to pack them if each bin can have at most a sum of $1$.

* How does one show the NP-completeness of the above by reducing it from the SUBSET-SUM problem?
* I also saw this related question here which remains unanswered, Relaxed Bin Packing Problem

Can someone help?

---

Is there some reference (on the web?) which shows a lot of such reductions - I think reading them will help me understand the kind of thinking that is required!

# Answer
To prove that a problem is NP-complete you need to find the decision version of your optimization problem. The answer to the decision problem is yes/no.

Once you state the decision problem, you need to prove that your problem is NP. It means that, given a certificate (an optimal solution) you can verify the feasibility of the solution in polynomial time.

Then you need to prove the NP-hardness, which means that you must reduce an NP-hard problem to your problem. The reduction is in fact, converting every instance of that NP-hard problem, to an instance of your own problem in polynomial time so that, if there is a polynomial algorithm for your problem, it can decide that problem in polynomial time.

In this document, there is the np-completeness proof of bin packing: http://www2.informatik.hu-berlin.de/alcox/lehre/lvws1011/coalg/bin\_packing.pdf

In famous text books you can find the np-completeness proof of: TSP, Hamiltonian path, longest path, set cover, vertex cover, clique and ....

In this document there are a number of good practices: http://www.cs.cornell.edu/courses/CS6820/2012sp/Handouts/111-137.pdf

**Edit.** For the relaxed bin packing, I should say that, sometimes you can relax/ignore some of the conditions in your problem. For example, in bin packing problem, one strict condition is that you should put each item into one bin and you cannot split one item into multiple bins. One may allow each item to be split into multiple bins (now this problem can be solved in polynomial time) which is called the relaxed version of the problem. Sometimes, relaxing one condition (such as integrality of solution) and rounding the obtained solution can give us approximation algorithms. I suggest you to search for relaxation in integer programming for more information.
> 1 votes

---
Tags: complexity-theory, np-complete, reductions
---


# Question
Title: Find pixel mapping matrix with minimum iterations
**The Situation**
I am an electronics engineer and on a volunteer team that have built a prototype eye that has 200\*200 sensors that are mapped to the optic nerve, the connection to the optic nerve is random (organic connection is grown) so I need to have the patient draw what they see, I am trying to limit the number of drawings (difficult for a blind person) the patient has to do to get the relationship between the artificial eye output and the correct perception of the image.

**The Problem**
Given a input image/matrix and an viewable/readable output matrix, **what is an algorithm to automatically identify the encoding with the least number of iterations.**

By changing the input one pixel at a time and then examining the output, the relationship can be discovered, this is, however, very inefficient.

# Answer
> 3 votes
Number the pixels from $0$ to $n^2-1$. Then create $\lceil \log\_2n^2\rceil$ many pictures. In the $i$-th picture all pixels are black, if the $i$-th bit in their number is $1$, white otherwise.

Note: If you have $2^k$ colors available, you can choose the color for each pixel based on $k$ successive bits of the number. This will reduce the number of images by a factor of $k$.

---
Tags: algorithms, machine-learning, pattern-recognition
---


# Question
Title: Searching for an item over a non-uniform query distribution
If I have a static set of $n$ items in a database that are all queried with uniform probability it makes sense to put them in a binary search tree. This way any given search will take, on average, $O(\ln n)$.

What happens now, if the items are not queried uniformly? As a silly example, say that one item is queried 1000 more frequently than any other item. Would it make sense check for that item first and independently, before looking in a search tree of the other items (the so-called LenPEG method)?

For concreteness, let's say the items are queried with a likelyhood that is static, and drawn from a Poisson distribution. What would be the optimal way to structure the data so that the average search time is minimized?

# Answer
The Optimal Binary Search Tree is exactly what you need.

Welcome to the site!
> 3 votes

---
Tags: data-structures, search-algorithms, search-trees
---


title: Top N percent elements in a queue

text:
# Question
Title: Top N percent elements in a queue
I implemented a queue using two stacks which gives me $O(1)$ en-queue time, $O(1)$ amortised time. Now suppose I want to find top $10\\%$ elements in the queue at any time. How am I suppose to implement it.

For example: queue takes the element in this order $$ \\{ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 \\}.$$

Top $10\\%$ elements means $10 \\% $ of $20 = 2$.

Hence the answer will be $19$ and $20$.

The best way I can think of is to sort it and then calculate $N%$ of size of queue and return that many elements. This takes about $O (n \log n + k)$ time.

Is this the most efficient way? I came across this algorithm. It's a linear solution. It seems like an answer, however I would like to know your views.

# Answer
You can implement this in O(klogk + n) time complexity.

Maintain an external min-heap while iterating the queue. The min-heap shall have at most k elements at a time.

Insert the first k elements in the min-heap. Thereafter compare the present queue element with the top of the heap. If the top is less than present value then delete the top element from the heap and insert this new present element.

At the end the heap shall contain top k elements in the queue.
> 2 votes

---
Tags: algorithms, data-structures, time-complexity, sorting
---


title: How to detect repeating random numbers?

text:
# Question
Title: How to detect repeating random numbers?
What is the best way to detect repeating sequences of random numbers?

For example, say I got two random number generators (RNG). One of them has been tampered with and is repeating the sequence of random numbers after every N iterations. The other RNG has not been tampered with and is producing random numbers like it should.

However, one of them is repeating its output every N bytes. N can be small or very large. How to detect this in a reliable and economic way?

Is using rolling hashes (like rsync does) a viable approach?

# Answer
> 1 votes
does not yet seem to be a duplicate on this very site:
cycle detection, see also where hares catch up with turtles
(would-be comment: the question first states repetition `every N iterations`, next `every N bytes`.)
(If it didn't carry over: for each PRNG to check, have a clone. For each change in state of the original one, trigger two in the clone. If the states get identical, you detected a cycle. No deterministic PRNG with limited state can avoid it. The states need not be as small as the results; they rarely are, nowadays, and the cycle lengths are *huge*.)

---
Tags: algorithms, randomness, random-number-generator
---


title: Relaxed Bin Packing Problem

text:
# Question
Title: Relaxed Bin Packing Problem
The problem I have is like this bin packing problem, but instead I have $n$ bins and a collection of items with discrete masses. I need to put at least $m$ kg of stuff in each bin.

Is there an efficient way of doing this? Is there a way that will assure there is approximately the same amount in each bin? Does having a good guess at the probability distribution of the masses help?

**More explicitly:**

I have $q$ objects $\\{o\_1...o\_q\\}$, each has a size $w(o\_i) \in \mathbb{N}$.

I need to find a collection of $n$ disjoint bins $B = \\{b\_1...b\_n\\}$ containing the objects such that

$$\forall b\_i \in B: \sum\_{o \in b\_i}w(o) \> m$$

for some $m$. When it is possible that is.

# Answer
> 4 votes
The problem is NP-complete because it is in NP and captures the partition problem with $n = 2$ and $m = \frac12 \sum\_{i = 1}^q{w(o\_i)} - \frac12 \min\_{i}w(o\_i)$. If an equal weight partition exists, then the items can be packed in two bins each of weight $\frac12 \sum\_{i = 1}^q{w(o\_i)}\>m$. If it doesn't, then one of the two bins would have weight at most $m$.

---
Tags: algorithms, efficiency, packing
---


# Question
Title: Function whose implementation is difficult (computationaly) to work out
Let's say I've got a function $f$ that takes a single number and returns a number. And I have another function $\mathrm{verify}f$ which takes the input I gave to $f$ and the number returned by $f$ which returns true if the output is the same as $f$ would have returned given the input.

If you know the input and output to $f$ and the function to verify then it is possible to work out what the implementation of $f$ is.

What I'd like to know, is if there exist some function that even if you know the output and the input and the verification function it's impossible to work out what $f$ does.

It feels like these functions must not exist – but I don't know that for sure.

# Answer
> 2 votes
If the function $f$ is computable, then $\mathrm{verify}f$ is computable too: to work out if $y=f(x)$ for some given $x$ and $y$, just compute $f(x)$ and see if it's equal to $y$. That tells you nothing about the implementation of $f$.

The relationship between the difficulty of computing $f$ and $\mathrm{verify}f$ is the essence of the **P**-vs-**NP** problem.

# Answer
> 2 votes
It's impossible to have a VerifyF function that will tell you anything about the implementaion of F -- take the simplest function of all; return 0.

Externally, you can not tell difference between:

```
   return 0;
   return input*0;
   return (randomMemoryLocation!=pi) ? 0 : -1;

```

In practical terms, this is why some people are dismissive of test driven development. A test does NOT verify that function returns the correct result, it verifies that it did NOT return the INCORRECT result when the test was run.

Whether that is sufficient for your needs is a practical (not theoretical) question. Theoretically, you just can't tell without out being able to examine the function F.

**Edit:** In fact, it is often the case that different algorithms can be used to produce identical results. This can be used to brute force test the correctness of an **implementation**, by examining the full range of inputs. This of course is not sufficient if you are concerned about security -- because in that case the algorithm may be sensitive to external factors that do not show up during your testing, even though you covered the entire (visible) input range.

# Answer
> 2 votes
There are examples that are vaguely of this sort in cryptography, if you are willing to allow $f$ to also depend upon a key that is kept secret.

If you choose $f$ right, here is what can be achieved. Given many pairs $(x\_i,y\_i)$ where $y\_i=f(k,x\_i)$, it can potentially be hard (computationally infeasible) to recover $k$, for someone who has no prior information on $k$. Depending upon your situation, this might or might not be a suitable solution.

Note: This does not contradict the impossibility results in the other answers.

You might also be interested in software obfuscation. Do some reading on the topic, and you'll probably be able to learn more. More detailed questions about obfuscation are probably more likely to reach a knowledgeable audience on Security.SE or Crypto.SE.

# Answer
> 1 votes
Surprisingly, such functions do exist and are used in public-key digital signatures.

We assume only Bob knows Bob's private key. Bob derives a public key from it, and publishes the public key -- we assume everyone knows Bob's public key.

> Let's say I've got a function f that takes a single number and returns a number.

Yes, Bob has a signing function that knows Bob's private key. That signing function takes a single number -- typically the hash of some plaintext message -- and returns a number called a public-key digital signature.

> And I have another function verifyf which takes the input I gave to f and the number returned by f which returns true if the output is the same as f would have returned given the input.

Yes, since everyone knows Bob's public key, anyone one the world can use the signature verifying algorithm, which takes the input Bob gave to f -- the hash of some plaintext message; and the number returned by f -- the public-key digital signature -- and also Bob's public key, which everyone knows. The signature verifying algorithm either accepts or rejects the message as an authentic message from Bob.

> If you know the input and output to f and the function to verify then it is possible to work out what the implementation of f is.

A signed message from Bob typically contains the plaintext message used as input to Bob's signing function, and also that function's output -- the digital signature.

Most of the details of a signing algorithm are already public, but even if the adversary gets a signed message from Bob, it is widely considered practically impossible to work out exactly what Bob's public key is, or to forge some other message that tricks someone into thinking that other forged message came from Bob.

https://crypto.stackexchange.com/ and https://security.stackexchange.com/ may be better places for asking more detailed questions about such functions.

(I see that D.W. already gave basically the same answer, except without rambling on quite so long :-).

# Answer
> 0 votes
I am a bit uncertain about what you are asking, but I suspect you are looking for zero-knowledge proofs. Here's the basic idea.

Suppose I want to convince you that I know where Elmo is (I hope you know the game) without telling you where Elmo is. I take a big sheet of paper, cut an Elmo-shaped hole in it, cover the puzzle so that the hole is directly above Elmo. You can now verify that I know where Elmo is, but you yourself do not know how to find him.

Translating this to your question we have a function $f$ which finds Elmo, and a verifier $v$ which checks that Elmo can be seen through the hole. There is no way for the verifier to figure out how I found Elmo.

Zero-knowledge proofs are a grown-up form of the same idea. They can be used for security, read the Wikipedia page.

---
Tags: computability
---


# Question
Title: What kind of order is binary tree ancestry?
Let `isAncestor` be a relation on binary tree nodes such that `isAncestor x y` means `y` can be reached from `x` in `n` steps from parent to child, where `n` may be zero. It is clear from this definition that `isAncestor` is a partial order. (Two nodes are mutual ancestors if and only if they are identical, and ancestors of ancestors are also ancestors.)

But on a second reflection, `isAncestor` is not just a partial order. For instance, it has the property `forall x y z, isAncestor x z -> isAncestor y z -> ( isAncestor x y \/ isAncestor y x )`, which I don't think is common to all partial orders.

Is there a kind of order that precisely designates `isAncestor`? Since binary trees are extensively studied in CS, I'm guessing there must be a name and a well known set of properties for this kind of relation.

# Answer
Your condition is almost equivalent to the statement that the partial order is a tree.

Consider the following two conditions on a partial order $\ge$:

C1: There exists a top element $r$ (also called "the root") such that $\forall x . r \ge x$.

C2: For all $x,y,z$, $x \ge z \land y \ge z$ implies $x \ge y \lor y \ge x$ (this is your condition).

Notice that every tree satisfies both conditions (i.e., its `isAncestor` partial order satisfies both of these conditions).

Moreover, I claim that every partial order that satisfies both of these conditions has a Hasse diagram that is a tree.

Why? Well, if C1 is true, then C2 is equivalent to

C3: For all $v$, there is a single unique path from $v$ to the root $r$ in the Hasse diagram of $\ge$.

This is easy to prove by looking at the contrapositive: if there were two incomparable paths from $v$ to the root, then we could find a violation of C2 (let $x,y$ be two incomparable elements, each on one of the paths).

And if C1 and C3 is true, then the Hasse diagram is a tree.

---

Bottom line: there's no particular reason to expect any special name for your property. Your property almost characterizes trees, once we take into account the correspondence between a partial order and its Hasse diagram (which is a DAG).
> 1 votes

---
Tags: binary-trees, partial-order
---


# Question
Title: How do I solve interdependent recurrence relations?
I have three functions with values given as

$$\begin{align\*} P(0) &= 0 \quad & P(i+1) &= 5M(i)\\ M(0) &= 1 \quad & M(i+1) &= R(i) + 2P(i)\\ R(0) &= 3 \quad & R(i+1) &= R(i) + 3P(i)\\,. \end{align\*}$$

If it was a linear recurrence with one function I could solve it using matrices. But here I cannot bring it to a single relationship. Each one is interrelated with the others.

How do I approach this problem?

# Answer
> 4 votes
Eliminate one recurrence at a time, by plugging in.

For instance, you can use the equation $P(i)=5 M(i-1)$ to eliminate every instance of $P(\cdot)$ in each of the other recurrences. Plugging in, we get

$$M(i) = R(i-1) + 10 M(i-2)$$ $$R(i) = R(i-1) + 15 M(i-2).$$

Now you have two inter-related recurrence relations, instead of three; you've eliminated one.

Do it one more time, say to remove each instance of $M(\cdot)$. You get something like

$$R(i) = R(i-1) + 15 R(i-3) + 150 M(i-4).$$

Do it again, to remove the $M(\cdot)$:

$$R(i) = R(i-1) + 15 R(i-3) + 150 R(i-5) + 1500 M(i-7).$$

Keep doing this, and you'll get a summation, say something like:

$$R(i) = R(i-1) + 15 R(i-3) + 150 R(i-5) + \cdots + 15 \times 10^{(i-3)/2} \times M(0)$$

(if $i$ is odd.)

Now you're down to a single recurrence relation. Solve it. Then, use the equations above to derive the solutions for $P(\cdot)$ and $M(\cdot)$.

---
Tags: proof-techniques, recurrence-relation
---


# Question
Title: How many ways to find a sum totalling n using only certain Integers?
Using an infinite supply of integers of a set S, how many ways are there to reach a sum of n?

Clarification: The Integers are arbitrary, positive, and may not include 1.

At first I thought it was the coin changing problem without pennies, but it's not because the order is important so coin changing will always be less.

It's also like Leonardo's Leaps but with arbitrary leap sizes, and again possibly without a leap of 1.

# Answer
This is NP-hard, by reduction from the partition problem.

Consider the decision problem version of your problem: given $S,n$, is there at least one way to reach a sum of $n$ using the integers from $S$ (possibly multiple times).

Suppose I have a partition instance, a set $T$ where I want to know whether it can be partitioned into $T\_1,T\_2$ such that the sum of $T\_1$ equals the sum of $T\_2$. Let $c$ be a very large constant, and define $S=\\{t+c : t \in T\\}$ and $n=(m+|T|c)/2$ where $m$ is the sum of all of the numbers in $T$.

Then the answer to the decision problem is yes if and only if the answer to the original partition problem was yes.

You should be able to fill in the details from here (including, in particular, how to choose the constant $c$, based upon $T$).

See also https://cstheory.stackexchange.com/q/19758/5038.

Of course, the problem may still be easy for many $S$; there may even be infinite easy subclasses. See also Dealing with intractability: NP-complete problems for more on strategies for what to do, when you have a problem that is NP-hard but you still have to solve it.
> 1 votes

---
Tags: algorithms, combinatorics, recursion, integers
---


title: Using base 80 for compressing files

text:
# Question
Title: Using base 80 for compressing files
I want to compress file size through making my own numbering system which is 80-based number, I do really want to know whether this even possible ? I learnt that Hexadecimal uses symbols like A, B, C, D, E, F to represent 10,11,12,13,14,15 -- and that's what i want to do to my own numbering system but in a bigger scale . Please correct me if i'm missing something .

Is it possible ?

# Answer
While you will need fewer 80-based numbers than 2-based numbers (bits) to encode the same file, the only way to store these 80-based numbers on a computer is to encode them as bits. So you do not gain anything.

In fact you actually lose space, since 80 is not a power of 2: You will need 7 bits for each 80-based number, but in these 7 bits you could instead encoed 128 different states, if you used them directly.
> 30 votes

# Answer
There are several ways to interpret the question. What I *think* you might be asking is that you have a sequence of $n$ letters in an alphabet $\Sigma$ where $\left| \Sigma \right| = 80$. You want to store this in as few as possible bits. We will assume that the letters in the alphabet are uniformly distributed.

The information-theoretic amount of space required to store this is $n \log\_2 \left| \Sigma \right|$ bits. Using arithmetic coding, you can do this in linear time, using $O(\log n)$ bits of intermediate space. (Remember, that's the logarithm of the number of symbols, in bits! If the size of the sequence fits in a machine word, the intermediate storage required is a constant number of machine words at the most.)

So that's pretty good. But what about if we want random access?

It turns out that it can be done. The first technique to do it was only discovered about four years ago. We can store the sequence in $n \log\_2 \left| \Sigma \right|$ bits, such that *reading or writing* any entry takes $O(1)$ time. If you think about it, this is a remarkable result, because it means that a computer which works with any radix is, in a sense, equivalent to a binary one.

Here's the paper: Yevgeniy Dodis, Mihai Pătraşcu, and Mikkel Thorup, An Alternative to Arithmetic Coding with Local Decodability, STOC 2010.

By the way, remember the name Mihai Pătraşcu. He was and is the closest thing we have to a modern-day Évariste Galois. He died very young, of a brain tumor at the age of 29. But in his short career as a computer scientist, his work revolutionised the field of analysis of algorithms in ways that will take decades to fully understand.
> 10 votes

# Answer
If you have a number (eg. 123456789⏨) as text you can write it in a different base (such as 21i3v9 in base 36), so you *compress* it **written as text** (from 9 characters to 6).

If you go further you end up storing it in binary (4 bytes¹).

Now, this works because you started with a reduced set \[0-9\] and moved to a bigger one \[0-9a-z\] **and** many bits of data were unused in the initial representation.

Similarly, if we know that a file only contains letters, we can easily compress it by changing the base. However, if you were to *compress* from arbitrary content, that won't (always) work. You may compress (get smaller outputs) for some files, but others will become larger **just as any lossless compression method**, this is unavoidable.

It can still useful though, for instance a method that compresses English texts well but makes Chinese texts larger may be good enough if you write a lot more English than Chinese.

¹ Actually you only need 2²⁷ bits, although nowadays computer storage uses multiples of 8 bits (but perhaps you wanted to store a serie of numbers of 2²⁷ bits? ☺).
> 3 votes

# Answer
Base 80?? Why 80? It doesn't make sense, however base 85 does. It's quite convenient as you can represent 4 bytes using 5 characters (because 85^5 = 4,437,053,125 which is slightly more than 2^32 = 4,294,967,296)

Here's my code for writing a single 32-bit `word`:

```
for (i=0; i<5; i++)
{
    c = (word % 85) + 37;
    word /= 85;
    fwrite(&c, sizeof(uint8_t), 1, file);
}

```

and here's for reading it back:

```
    word = 0;
    for (i=4; i>=0; i--)
        fread(&c[i], sizeof(uint8_t), 1, file);

    for (i=0; i<5; i++)
        word = word*85 + c[i]-37;

```

If you really want to use base 80 you can use the same approach and replace the instances of 85 with 80 and you'll need 6 characters for every 4 bytes instead of 5.

How is it going to compress anything though? You do realise that files are written in base 256, right? This being said if you zip a file written in base 85 it will be about the same size as the zipped original base 256 file, which makes base 85 (or base 64) a nice choice if you want to represent binary data using printable characters.
> 2 votes

# Answer
Different bases are used for different purposes, although as the other answers explain you won't gain anything in terms of compression.

See wikipedia for an explanation of base64 encoding. Base 64 is often used, not for compression, but to encode binary data that would normally result in non-printable characters and control codes into a printable ASCII character space. This will result in a *larger* file size, but is useful for transferring binary data that can be embedded in other ASCII files, e.g. inside XML, emails, CSS, web pages, etc.
> 0 votes

---
Tags: data-compression, number-formats
---


title: Can an interrupt handler be preempted?

text:
# Question
Title: Can an interrupt handler be preempted?
Can a running interrupt handler be pre-empted by another interrupt handler? If this is possible, in which scenarios is this safe, and in which scenarios is it not? If this is not possible, why?

# Answer
This depends on both the processor architecture and the kernel architecture.

Generally speaking, interrupt handlers start with interrupts disabled. This is necessary so that the interrupt handler has room for storage — at a minimum, the interrupt handler needs the exclusive use of a few registers, including the program counter, which the processor must save somewhere (in a set of banked registers).

On some processors, it's possible for an interrupt to be interrupted by another higher-priority interrupt. To give one example that I'm familiar with, on ARM processors, there are two interrupt levels: IRQ (normal interrupts) and FIQ (fast interrupts). Each has their own register bank for the program counter and stack pointer, and their own interrupt vector. An IRQ handler starts with IRQ disabled but FIQ enabled; an FIQ handler starts with both IRQ and FIQ disabled. Thus an FIQ can be triggered in the middle of handling an IRQ.

It's up to the operating system to decide when an interrupt handler will reenable interrupts of the same priority, or interrupts of a different type with the same priority. The longer interrupts are blocked, the longer the latency to handle an interrupt that comes soon after another. In particular, a real-time OS typically needs to reenable interrupts very fast. To give a couple of examples:

* FreeBSD's interrupt handlers can be preempted when they are performing a blocking operation (waiting for a lock).
* Linux encourages splitting the task of an interrupt handler into two parts: the *top half* is the actual interrupt handler, and runs with interrupts disabled; the *bottom half* runs with normal preemption for as long as it needs. Typically the top half exchanges data between hardware peripherals and a preallocated memory buffer, then the bottom half handles all the rest such as communicating with other kernel and userland threads, initiating new hardware I/O, etc.

At the point where an interrupt handler unmasks interrupts, it must be ready to cope: it must not be using any resource that another interrupt handler would thrash. Furthermore, since the interrupt handler hasn't finished its job, there must be some mechanism for the program counter to be saved somewhere; the mechanics of this depends a lot on both the processor and the kernel architecture.
> 27 votes

---
Tags: operating-systems, os-kernel
---


# Question
Title: What are potential pitfalls with having a minimal kernel that runs managed code?
Suppose I want to build an operating system based on a very small native lower kernel that acts as a managed code interpreter/runtime and a larger upper kernel compiled to a non-native machine language (Java bytecode, CIL, etc.). Examples of similar operating systems would be Singularity and Cosmos.

What pitfalls and development challenges exist writing an OS with this sort of infrastructure in contrast to a purely-native solution?

# Answer
Depending on the language, there can be many development challenges:

1. **Pointers:** If a language doesn't have pointers, it will be a challenge to do relatively-easy tasks. For example, you can use pointers to write to VGA memory for printing to the screen. However, in a managed language, you will need some kind of "plug" (from C/C++) to do the same.
2. **Assembly:** An OS always needs some assembly. Languages like C#, Java, etc. don't work so well with it, unlike C/C++. In C or C++ you can also have inline assembly which is very, very useful for many tasks. There are MANY cases where this is needed (examples in x86): loading a GDT, loading an IDT, enabling paging, setting up IRQs, etc.
3. **Control:** If you are using something like Cosmos, you aren't having full control. Cosmos is a micro-kernel and essentially "bootstraps" your "kernel". You can implement something like Cosmos from scratch if you really wanted to, however, that can take a long, long time.
4. **Overhead:** With managed languages, there is A LOT of overhead compared to C or even C++. Things like Cosmos need to implement a lot of things before even a C# hello world kernel can be run. In C, you are ready to go, no real setup needed. In C++, there are just a few things that need to be implemented to use some of C++'s features.
5. **Structures:** In C/C++ there are structs which many managed languages do not have, and so, you would need to implement some way of having something like a struct. For example, if you want to load a IDT (Interrupt Descriptor Table), in C/C++, you can create a struct (with a packed attribute), and load it using the x86 ASM instruction *lidt*. In a managed language, this is much harder to do...

Managed languages, syntax-wise, are easier, however, for many OS related things are many times not very-well suited. That doesn't mean they can't be used, however, something like C/C++ are often recommended.
> 8 votes

# Answer
I have heard it claimed (by a researcher working on a competing microkernel technique) that very little is known about how to evaluate security of systems that are extensible through managed code.

The problem is that the kinds of bugs that might cause a security hole are very different than security researchers are used to. In a traditional microkernel all the drivers and other subparts of the kernel are isolated from one another by running them in different address spaces. In a microkernel where the isolation is implemented through type checking managed code you avoid the enormous overheads of switching address spaces every time you need to use a sub-service, but the tradeoff is that now evaluating the isolation mechanism is more difficult.

Any particular part of the kernel (say a device driver) written in the managed language is safe if and only if the type checker says the driver is safe *and* the type checker has no bugs. So the type checker is part of the kernel core. In practice it seems that type checkers are considerably larger and more complicated than are traditional microkernel cores. That means that the *attack surface* is potentially larger.

I don't know whether traditional micro-kernel isolation techniques or managed-code based isolation techniques are really more or less reliable. There's a bootstrapping problem here: until managed-code isolation techniques are widely used, we're not going to know how often they are insecure. But without knowing how insecure they are, it is difficult to deploy them in situations that are security critical.
> 5 votes

---
Tags: operating-systems, type-checking, interpreters, os-kernel
---


# Question
Title: Writing a multitasking operating system for a processor without MMU
I've been thinking of writing a hobby operating system for some of the ARM processors. There are many popular single-board computers with ARM MPU, so I simply wanted to purchase one of those (choosing one with more open documentation). I was surprised when I found out, that even boards with really enough memory do not have MPUs with Memory Management Unit.

As I've always been working with i386+ processors and never anything else (except for some Microchip PICs), I'm now confused and not sure if one can write a working operating system whose functionality wouldn't be limited when comparing to OSes written for MPUs with MMU.

I could think of few solutions for "replacing" or "simulating" MMU and I've got few questions:

* On Intel processors in 16 and 32-bit modes there is a way of using segments and segment selectors to use different blocks of memory by different tasks. That means that I could change memory space by changing contents of segment registers when doing a task switch when on x86. Are there any general concepts for memory segmentation that could be used on ARM architecture?
* By loading a linked object file instead of executable I could use relocations (fix-ups) or position independent code to point tasks on pieces of memory in the same way as if I mapped the memory using paging structures. Would this be effective enough?
* I have also read something about Memory Protection Units on ARM processors. Could these be helpful?

Are there any "usual" ways of managing tasks on systems without MMU?

# Answer
It's actually not that hard to design an operating system that doesn't require an MMU. There are a few conveniences you'll have to do without, but nothing insurmountable.

* Since different tasks will have to be loaded at different addresses, all your code (except for the kernel, the standard library, and any other code that's part of your base runtime environment) has to be compiled as position-independent. This means relative jumps and a base address for heap access stored in a register. Spending one register as a base address might seem costly if you're used to x86-32's four general registers, but most modern architectures have more, and even 8088 has the segment registers precisely for that.
* A Unix-like architecture has to be revised, because you can't implement `fork`. That's ok, most operating systems don't have `fork`. (You can have `vfork`.)
* You can't preallocate large gobs of space without also allocating the corresponding memory. This means no growing of the stack or heap on the fly by allocating one more page at a time.

If you have an MPU, then your tasks can still be separated from each other as usual in multitasking operating systems. Without an MPU, memory separation can only be cooperative if you allow tasks to execute arbitrary code. One way to achieve memory separation without an MPU is to restrict tasks to use only verified code on a virtual machine and implement memory protection in software as part of the VM engine.

uClinux is a project based on the Linux kernel that runs on processors (including ARM Cortex-M) without an MMU. Its restrictions on multitasking are essentially what I outlined above.
> 18 votes

---
Tags: operating-systems, memory-management, memory-hardware, os-kernel
---


# Question
Title: Are Time-sharing and multi-tasking operating systems same or different
My question is regarding time-sharing and multi-tasking systems.

Time-sharing operating system assigns time slot to each task while multi-tasking OS runs various jobs in parallel.

But as I get it, on a single processor system, time-sharing is the only way to achieve multi-tasking. (I don't know if I am correct on this premise.)

So, are time-sharing and multi-tasking system same or different.
And if they are different, then what are the key differences (particularly on a single-processor/single-core system with no hyper-threading support etc) ?

Thanks

# Answer
> Just as multiprogramming allows the processor to handle multiple batch jobs at a time, multiprogramming can also be used to handle multiple interactive jobs. In this latter case, the technique is reffered to as **time sharing**, because processor time is shared among multiple users. In a time-sharing system, multiple users simultaneously access the system through terminals, with the OS interleaving the execution of each user program in a short burst or quantum of computation.

William Stallings, Operating Systems Internals and Design Principles, 7th Edition

You should keep in mind that the principal objective of a time sharing system is not to maximize processor use, but to minimize response time.

I think it would be correct however to assert that on a single processor system, multi-tasking is achieved through time sharing. Remember that a processor can execute only one task at a time at any given time.
> 5 votes

---
Tags: operating-systems, os-kernel
---


# Question
Title: Why using Hyper-threading can lead to performance degradation
I have read it at various places like this, that Hyper-threading leads to performance degradation.

I am unable to get why or how hyper-threading leads to degradation.

Why it is so that even when Hyper-threading allows the OS to utilize free resources does the degradation happens.

Though benchmarks does indicate hyper-threading as the culprit but can someone explain me the reason for this.

Thanks

# Answer
It would seem that the answer, as per usual, has something to do with caches. Since hyper-threads utilize the same L1 and L2 caches, one hyper-thread can trash another's caches. In the worst case the threads take turns trashing the other's cache and performance degrades as the caches are re-filled only to be trashed again.

Of course, this is likely very workload specific, which would explain why the problem is mostly seen on servers.

It is also worth noting that the answer depends in part on what you mean by "performance." For example, in real-time systems your performance metric is predictability instead of throughput, which hyper-threading negatively impacts by introducing unpredictable stalls.
> 8 votes

---
Tags: computer-architecture, performance, threads
---


title: Relation between Signals and Events

text:
# Question
Title: Relation between Signals and Events
There are POSIX signals (linux man), and various event-based operating systems (such as TinyOS, most seem to be targeted at embedded systems). But the mechanisms seem very similar.

Are the terms 'signal' and 'event' interchangeable? Or are signals a sub-set of events? Or are they two fundamentally different for some reason that I am completely missing?

# Answer
> 4 votes
As general concepts, the words *signal*, *notification* and *event* are mostly interchangeable, though they carry different connotations and some words wouldn't be used to denote some specific mechanisms. A particular operating system or other concurrency framework may use these terms for different mechanisms.

Some differences to watch for (with signals, events or whatever they're called) include:

* Synchronous vs asynchronous: does the sender block until the recipient receives the signal?
* Stacking: if multiple identical signals are generated before the recipient acknowledges any of them, will the recipient receive that many signals, or can they be merged?
* Associated information: is the signal just “hey, wake up”, or does it have an associated tag, or does it have a payload (which could be a pointer to a larger data structure)?
* Destinations: does the signal target a specific task (unicast), or a set of recipients (multicast), or all tasks that care (broadcast)? In the multicast case, will all the specified targets receive the signal, or is the signal cleared as soon as one task acknowledges it (this may be termed unicast rather than multicast)?

For example, POSIX signals are asynchronous, unicast (multicast if sent to a process group), they stack, and have a tag which is a small integer. I'm not familiar with TinyOS; from a quick read of the tutorial I think they are asynchronous, unicast (perhaps with other possibilities), non-stacking, and have a payload (and, incidentally, sending an event is called *signalling* it; receiption is called *triggering*, because the *event* in TinyOS terminology is the handler instance rather than not the message).

I think the word *event* wouldn't be used if there is no associated information at all. The word *signal* wouldn't be used if there's a rich payload: with a rich payload, it's a *message*, possibly an *event* or a *notification*. GUI frameworks often call notifications of user input *events*; GUI events have a payload (e.g. to identify which key was pressed) and don't stack.

The use of the word *event* tends to promote event-driven architectures, where programs are structured as event callbacks rather than as a thread that checks for notifications periodically, but it isn't limited to this use.

---
Tags: operating-systems, os-kernel
---


title: Handling TOCTTOU with system calls

text:
# Question
Title: Handling TOCTTOU with system calls
What are some of the best practices when implementing system call functionality for handling/avoiding "Time of check to time of use" (TOCTTOU) security issues?

# Answer
One of the simplest ways to avoid TOCTTOU issues is for your system calls to perform the check at time of use (within the system call) instead of trusting a prior check. If you can gracefully fail a check upon use, the caller can instead rely upon exception handling to avoid a check race or a vulnerability. This methodology will help with both long-running and short-running scenarios.

To further assist with short-running scenarios, you could implement transactions for your security-related system calls. Of course, this would require being architected in early on, and would influence the design of the system call APIs, but it would provide concurrent consistency across the system.
> 1 votes

# Answer
In a kernel like anywhere else, the basic principle to avoid TOCTTOU bugs is to ensure that the time of check is the same as the time of use. That is, the check and the use must be part of the same atomic operation.

At the lowest level, kernel code can ensure that an operation is atomic by entering a critical section during which all interrupts are disabled. A critical section has a high cost (especially on a multiprocessor system), and so is only used when absolutely necessary and only for very short lengths of time.

Most system calls invoke a specific object, e.g. a file or device or process or other concept represented in the kernel by some data structure. A typical architecture associates a lock with each object. For example, a system call to open a device might do the following:

1. take the lock associated with the process
2. take the lock associated with the device
3. match the calling process's privileges with the file permissions
4. if the caller has the appropriate privilege, open the device
5. release the device lock
6. release the process lock

On a single-processor machine, many system calls can be atomic by the simple expedient of not relinquishing control from the kernel back to user land processes. Care must be taken that interrupts do not modify any object used by a system call; locks are useful for that. On multi-processor machines, locks must ensure that kernel code executing on different processors will not take conflicting actions.

One important piece of data that a system call manipulates is the arguments. On a multiprocessor machine, or on a single-processor machine with a preemptible kernel, the calling process may continue executing during the system call, so the kernel must take care to first copy the arguments into kernel memory, then validate its copy and use its copy.
> 1 votes

---
Tags: operating-systems, security, os-kernel
---


# Question
Title: Why is the OS design able to reduce power consumption?
I have read that OSes like Android and iOS are somehow optimised to improve battery life.

My understanding is that a CPU executes a certain number of operations in a certain time, so I would think that you can speed up applications by reducing number of operations required, but since the CPU will still do *x* operations in *y* time, that should not affect power?

Also, if a process occupies more RAM, does it consume more power?

# Answer
> 16 votes
Common CPUs that go into smartphones, laptops and even desktop PCs have a variable clock rate. When the scheduler detects that it has idle time, it can reduce the clock rate, and increase it again if there are more processes competing for CPU time.

CPUs optimized for battery-powered devices tend to be composed of many functional components that each have their own clock (example: ARM Cortex A8). When one component is idle, the operating system can turn it off (or reduce its clock), which saves power. For example, on many multicore CPUs (such as the ones in high-end mobile devices), each core can be turned on or off separately. ARM is particularly good at this game, which is one of the reasons why most smartphones have ARM CPUs.

Varying the clock rate or turning off the clock of electronic components is known as **power management**. It tends to be a complex part of writing and optimizing an operating system for a battery-powered device, with many dependencies on the exact hardware model.

What goes for the CPU goes for peripherals too. The backlit display is a major consumer of power on a smartphone, for example, followed by the radio. The CPU operating system may play a role in power management of peripherals; secondary chips also runs their own firmware which performs power management as well.

Applications have their part to play in keeping power consumption down: they must allow the operating system to do its thing. The worst thing an application can do is polling — running a loop like `while (not_ready()) {}`. Even introducing a small delay as in `while (not_ready()) {usleep(100);}` doesn't help as it doesn't allow enough time for the processor to go into low-power mode, or if it does, each unfruitful wake up means wasted energy. Thus the operating system APIs must be designed so that applications never need to poll, but can instead subscribe to some kind of event mechanism and remain idle until they are notified of a relevant event. Applications in turn need to take advantage of such mechanisms, so the design of the whole software stack has an impact on power consumption.

You can get some information about what's responsible for your PC's power consumption with Intel's Powertop utility. Smartphones typically have a way to see how much power applications have been consuming as well. Accounting for power consumption by application precisely is difficult: if a component wakes up for two applications, the wake-up time may be accounted to one of them somewhat arbitrarily or to neither; peripherals' power consumption are also not always be easily tracked to the application responsible.

A RAM chip doesn't know which of its bits store data of an active process, so it can't be turned off selectively in this manner. A process's power consumption isn't related to the amount of memory that it uses (except inasmuch as the RAM accesses consume power, but re-using the same memory or using different RAM areas makes no difference with respect to power consumption).

# Answer
> 4 votes
In terms of processor power the main thing the OS can do is to provide APIs that discourage applications from polling. (And also eliminate all polling inside the kernel and device drivers if there was any.) Then the processor can be put into a low power sleep state whenever there is nothing to do.

For every device there needs to be a way for the user apps to go to sleep after a request and then get woken up again only when the result is ready.

Obviously tight polling loops are a disaster (because they keep the processor fully awake and executing useless noops and jumps.) But there are more subtle, but nearly as bad cases where the user app is setting timers, waking up on the timer alarm, checking some condition, resetting the timer and going back to sleep.

I know less about this part but I think there may also be creative ways of using DMA (direct memory access) controllers to handle long strings of repeat interrupts without waking the processor core itself.

# Answer
> 3 votes
The OS main role is to provide a runtime environment as independent from the hardware as possible. It knows who is using what hardware, when and how someone is using hardware. This allow the OS to reduce the hardware power consumption when it is not used.

Modern hardwares provide many ways to reduce power consumption, such as

* shutting down unused peripherals and part of the processor (floating point arithmetic units, processor cores, ...)
* down-clocking of less used parts (including processor core)
* power-supply adjustment to fit with current clock frequency (you may modify a processor working voltage on the fly, sometimes by hundreds of mA)

> if a process occupies more RAM, does it consume more power?

Not really. Nevertheless, if your system has 1GB of DRAM, but you only uses 512MB, with some memory controllers, it is possible to stop refreshing part of the DRAM, thus reducing power consumption. LPDDR supports Partial Area Self Refresh to do the same while in self-refresh (while the processor is stopped, which is true most of time on mobile devices).

As you may see, there are many ways to reduce power consumption on modern architectures, but it requires the OS to handle it. Some features, such as PASR, are very tricky to use, this requires much work on the OS to adapt memory management, to implement suspend/resume procedures, ...

# Answer
> 3 votes
As you are no doubt aware, the OS maintains a variety of lists. Two of these lists are the ready list and the timer list. The ready list identifies which tasks/threads are ready to run. The timer list identifies the tasks/threads that are in a blocked state with a timeout.

Imagine that the OS has an empty ready list. That is, it has run out of tasks that are ready to run (it is in the idle state). Some processors (such as the x86) have a halt instruction that the OS can invoke to cause the processor to stop until it is awoken by an external interrupt (such as a tick interrupt). During this period of time, it is consuming less power. This technique can be further improved by peeking at the timer list. If you are idle and you know that soonest a task can wake up from a timer tick is 100 ticks away, the tick rate may be temporarily modified to be say 100 times slower. This way, the processor can expend even less energy for a longer period of time because it will not have to service up to 100 tick interrupts.

Once the external interrupt arrives, the tick rate will have to be recalculated. If the external interrupt made a task ready, the tick rate goes back to normal. If not, the number of ticks to sleep must be recalculated along with the new (slowed) tick rate.

Hope this helps.

# Answer
> 2 votes
To add to the other answers:
Your question regards iOS and Android as operating systems but the "Operating System" is only part of them.
Both Android and iOS are frameworks and include many parts that are not considered part of the actual OS but are active in reducing power consumption.
For example, Android by design allows the application developers to save their state when hidden, so processes can be terminated when not actively in use and thus reduce the amount of ready threads and allow for core shutdown and clock rate reductions.
There are features in the "OS" that set adaptive brightness, wi-fi sleep state, cleanup threads, schedule pooling, LED indicators, cellular standby behavior, and other aspects that affect power consumption drastically.
In addition, some mobile platforms have been working hard on optimizing their CPU/GPU usage ratio, since the GPU is more adapted at graphics and it's a relatively new addition to the mobile landscape, more and more graphic related parts of the OS are moving to the GPU, which clears work from the CPU, and allowing for the usage of CPU power optimizations to be used (and in many cases, also speed up the system as a whole).

---
Tags: computer-architecture, operating-systems, performance, program-optimization
---


title: Memory ballooning in the OS

text:
# Question
Title: Memory ballooning in the OS
Some hypervisors optimize memory usage using a method that is called ballooning (at least that's what KVM calls it), this method deduplicates memory between VMs and sets common pages to read-only with copy on write.
This is sort of the opposite of a fork call.

Is it feasible to implement on an OS level for processes (I was mainly thinking of for the duplication of memory when browsing with Chromium with multiple tabs on the same site), has it been implemented already?

# Answer
Actually, what you've described confuses ballooning and 'same-page-merging'. I'll try to elaborate on the two to make the distinction apparent.

**Memory ballooning**

This is a trick to make sure that some of the memory allocated to the *guest* virtual machine remains usable by another *guest* or the *host* itself (caches, etc). It's done in the following way:

The guest kernel is injected with a driver, that monitors guest memory usage, and 'steals' some of the unused memory (allocating it for itself in the guest memory space, thus making sure nothing on this guest can touch that range).

Then it informs the host kernel, that it can in fact remove these memory pages from the core, that they are not going to be used in the guest (until the guest experiences some memory pressure, at which point the balloon will deflate, and use these ranges again).

Ultimately, the kernel can allocate the exact same memory to another guest, and make the entire memory usage a lot more efficient **if** the guests are running with a lot of free memory.

**Same Page Merging**

This technique identifies identical memory pages, that for some reason are not already marked 'quasi-read-only' with copy-on-write, and marks them as such.

Now, on the OS level, there is limited need for these kinds of tricks. Simply enough, most time when you have identical memory pages, they are already read-only (sometimes even without CoW), since these are mostly applications code, libraries etc. They are natively opened through a Memory Map, and thus the kernel can keep only one copy of them in core (if any at all, it can also completely page it out, and allow it to be paged in from primary store as needed).

On the virtualized OS level, the same principle is properly applied within each guest subsystem. However, the host kernel, has no idea if two of the guests are running mostly the same code, and thus are sharing the same memory - the guests don't communicate to coordinate that.

Which is why it can occasionally scan the entire system for identical memory pages - most of the time, they will be identical **across** the guest OS's, not within each one - the guest kernel makes a decent job keeping the memory neat within it's range. Thus, in the typical VM environment, where one host kernel handles 50+ guests, the memory savings can be pretty substantial.

**Both at once**

Ballooning and Same-Page-Merging can co-exist very well, achieving pretty substantial memory overcommit for identical systems.

---

To answer your question - the Same-Page-Merging can and sometimes is enabled at an OS level. It has to do with page sharing that are interpreted, and thus could end up being identical without having the same backing file.

In your Chromium example - the process binaries themselves are already deduplicated through read-only startup map - they share the exact same memory space. The page caches (contents of the tabs) are usually also shared between processes (read-only copy-on-write) due to the way disk cache is managed - the same on-disk file can be opened simulatenously between different processes in the VM-optimal sense.

The advantage would be most evident with the shared state of different Javascript engines - but I'm not sure if they are allocated in the exact same memory layout, ensuring that the entire memory page is identical.

This is different on mobile systems. Android, for instance, extensively employs KSM to deduplicate identical code between different applications.

In either case, you can enable it yourself on Linux (Kernel SamePage Merging). The driver exports various statistics that, after reading this answer, you should be able to interpret, and make your own decision whether it's a good match for your purpose.

https://www.kernel.org/doc/Documentation/vm/ksm.txt
> 14 votes

---
Tags: operating-systems, memory-management, virtual-memory
---


# Question
Title: How are system calls handled in a virtual machine?
Quoting wikipedia, a *system call* is:

> In computing, a system call is how a program requests a service from an operating system's kernel. This may include hardware related services (e.g. accessing the hard disk), creating and executing new processes, and communicating with integral kernel services (like scheduling). System calls provide an essential interface between a process and the operating system.

In ordinary operating systems, when a system call is made the operating system enters kernel mode and performs the requested operation.

**What happens to a system call made by a process in a virtual machine?** Is it handled by the virtual machine only, or is it delegated to the outer kernel to be operated by the hardware-facing kernel?

# Answer
> 7 votes
There are 3 common strategies to handle this:
**1. Hypervisor traps system calls from guest**: The hypervisor checks whether the privileged instruction(effectively system call) came from the guest OS itself, or from a user-space program within the guest OS. If it's the former case, then the hypervisor will actually forward the call to the hardware, although through the virtualization instructions. If it's the latter, the hypervisor will redirect the call to the guest OS, and then proceed.
**2. Binary translation**: Here the hypervisor checks the code from the guest OS in what are called as "basic blocks", scanning for privileged instructions. Wherever it finds them, it replaces them with calls to it's own procedures to system calls. It then proceeds to cache these blocks & eventually builds a whole set of such blocks.
**3. Paravirtualization**: Here the guest OS itself is modified so that instead of making calls to the hardware, it has APIs to invoke the hypervisor to get its hardware I/O done.

Source: Modern Operating Systems by Andrew Tanenbaum

---
Tags: computer-architecture, operating-systems, process-scheduling, virtual-memory
---


# Question
Title: How does an operating system create entropy for random seeds?
On Linux, the files `/dev/random` and `/dev/urandom` files are the blocking and non-blocking (respectively) sources of pseudo-random bytes.

They can be read as normal files:

```
$ hexdump /dev/random
0000000 28eb d9e7 44bb 1ac9 d06f b943 f904 8ffa
0000010 5652 1f08 ccb8 9ee2 d85c 7c6b ddb2 bcbe
0000020 f841 bd90 9e7c 5be2 eecc e395 5971 ab7f
0000030 864f d402 74dd 1aa8 925d 8a80 de75 a0e3
0000040 cb64 4422 02f7 0c50 6174 f725 0653 2444
...

```

Many other unix variants provide `/dev/random` and `/dev/urandom` as well, without the blocking/non-blocking distinction.

The Windows equivalent is the `CryptGenRandom()` function.

How does the operating system generate pseudo-randomness?

# Answer
The title and the body of your question ask two different questions: how the OS creates entropy (this should really be *obtains* entropy), and how it generates pseudo-randomness from this entropy. I'll start by explaining the difference.

## Where does randomness come from?

Random number generators (RNG) come in two types:

* Pseudo-random number generators (PRNG), also called *deterministic random bit generators* (DRBG) or combinations thereof, are deterministic algorithms which maintain a fixed-size variable internal state and compute their output from that state.
* Hardware random number generator (HRNG), also called “true” random number generators, are based on physical phenomena. “True” is a bit of a misnomer, because there are no sources of information that are known to be truly random, only sources of information that are not known to be predictable.

Some applications, such as simulations of physical phenomena, can be content with random numbers that pass statistical tests. Other applications, such as the generation of cryptographic keys, require a stronger property: **unpredictability**. Unpredictability is a security property, not (only) a statistical property: it means that an adversary cannot guess the output of the random number generator. (More precisely, you can measure the quality of the RNG by measuring the probability for an adversary to guess each bit of RNG output. If the probability is measurably different from 1/2, the RNG is bad.)

There are physical phenomena that produce random data with good statistical properties — for example, radioactive decay, or some astronomical observations of background noise, or stock market fluctuations. Such physical measurements need **conditioning** (whitening), to turn biased probability distributions into a uniform probability distribution. A physical measurement that is known to everyone isn't good for cryptography: stock market fluctuations might be good for geohashing, but you can't use them to generate secret keys.

Cryptography requires **secrecy**: an adversary must not be able to find out the data that went into conditioning. There are cryptographically secure pseudo-random number generators (CSPRNG): PRNG algorithms whose output is suitable for use in cryptographic applications, in addition to having good statistical properties. One of the properties that make a CSPRNG *cryptographically secure* is that its output does not allow an adversary to reconstruct the internal state (knowing all the bits but one produced by a CSPRNG does not help to find the missing bit). I won't go into how to make a CSPRNG because that's the easy bit — you can follow recipes given by professional cryptographers (use a standard algorithm, such as Hash\_DRBG, HMAC\_DRBG or CTR\_DRBG from NIST SP 800-90A) or the ANSI X9.31 PRNG. The CSPRNG requires two properties of its state in order to be secure:

* The state must be kept secret from the start and at all times (though exposure of the state will not reveal past outputs).
* The state must be linear: the RNG must never be started twice from the same state.

## Architecture of a random number generator

In practice, almost all good random number generators combine a CSPRNG with one or more **entropy sources**. To put it succintly, entropy is a measure of the unpredictability of a source of data. Basing a random number generator purely on a hardware RNG is difficult:

* The raw physical data is likely to need conditioning anyway, to turn probabilistic data into a uniform distribution.
* The output from the source of randomness must be kept secret.
* Entropy sources are often slow compared with the demand.

Thus the RNG in an operating system almost always works like this:

1. **Accumulate sufficient entropy** to build an unpredictable internal state.
2. **Run a CSPRNG**, using the accumulated entropy as the seed, i.e. as the initial value of the internal state.
3. Optionally, periodically mix additional entropy into the internal state. (This is not strictly necessary, since entropy is not “consumed” at any measurable rate. It helps against certain threats that leak the RNG state without compromising the whole system.)

A random number generation service is part of the job of an operating system, because entropy gathering requires access to hardware, and entropy sources constitute a shared resource: the operating system must assemble them and derive output from them that will suit applications. Pseudo-random conditioning of the entropy sources is required in the operating system; it might as well be cryptographically secure, because this isn't fundamentally harder (and it is required on operating systems where applications do not trust each other; on fully cooperative systems, each application would have to run its own CSPRNG internally if the operating system didn't provide one anyway).

Most systems with persistent storage will load an RNG seed from disk (I'll use “disk” as an abbreviation for any kind of persistent storage) when they boot, and overwrite the seed with some fresh pseudo-random data generated from that seed, or if available with random data generated from that seed plus another entropy source. This way, even if entropy is not available after a reboot, the entropy from a previous session is reused.

Some care must be taken about the saved state. Remember how I said the state must be linear? If you boot twice from the same disk state, you'll get the same RNG outputs. If this is a possibility in your environment, you need another source of entropy. Take care when restoring from backups, or when cloning a virtual machine. One technique for cloning is to mix the stored entropy with some environmental data that is predictable but unique (e.g. time and MAC address); beware that if the environmental data is predictable, anyone in possession of the stored VM state can reconstruct the seed of a forked VM instance.

## Entropy sources

Finding (and correctly using) entropy sources is the most challenging part of random number generation in an operating system. The available entropy sources will necessarily be dependent on the hardware and on which environment the hardware runs in.

If you're lucky, your hardware provides a peripheral which can be used as an entropy source: a hardware random number generator, either dedicated or side-purposed. For example:

NIST SP800-90B provides design guidelines for hardware RNG. Evaluating a hardware RNG is difficult. Hardware RNG are typically delicate beasts, which need to be used with care: many types require some time after boot and some time between reads in order to destabilize, they are often sensitive to environmental conditions such as the temperature, etc.

Intel x86-64 processors based on the Ivy Bridge architecture provide the `RdRand` instruction which provides the output from a CSPRNG seeded by thermal noise. Most smartphone processors include a hardware entropy source, though Android doesn't always use it.

Systems that lack a strong entropy source have to make do with combining weak entropy sources and hoping (*ensuring* would be too strong a word) that they will suffice. Random mouse movements are popular for client machines, and you might have seen the security show by certain cryptography programs that ask you to move the mouse (even though on any 21st century PC operating system the OS will have accumulated entropy without the application needing to bother).

If you want to look at an example, you can look at Linux, though beware that it isn't perfect. In particular, `/dev/random` blocks too often (because it blocks until enough entropy is available, with an overly conservative notion of entropy), whereas `/dev/urandom` is almost always good except on first boot but gives no indication when it doesn't have enough entropy. Linux has drivers for many HRNG devices, and in accumulates entropy from various devices (including input devices) and disk timings.

If you have (confidential) persistent storage, you can use it to save entropy from one boot to the next, as indicated above. The first boot is a delicate time: the system may be in a fairly predictable state at that point, especially on mass-produced devices that essentially operate out of the factory in the same way. Some embedded devices that have persistent storage are provisioned with an initial seed in the factory (produced by a RNG running on a computer in the factory). In virtualized server environments, initial entropy can be provisioned when instantiating a virtual machine from the host or from an entropy server.

Badly-seeded devices are a widespread problem in practice — a study of public RSA keys found that many servers and devices had keys that were generated with a poor RNG, most likely a good PRNG that was insufficiently seeded. As an OS designer, you cannot solve this problem on your own: it is the job of the entity in control of the deployment chain to ensure that the RNG will be properly seeded at first boot. Your task as an OS designer is to provide a proper RNG, including an interface to provide that first seed, and to ensure proper error signaling if the RNG is used before it is properly seeded.
> 34 votes

# Answer
In addition to Gilles answer, interrupts can also be used to establish entropy. In Linux for example, when adding an interrupt handler you can define whether the occurrence of this interrupt should be used as a contribution to the kernel's entropy pool.

Of course this should never be the case with interrupts that an attacker might be able to determine. For example, at first glance network traffic (i.e. their resulting interrupts) seems to be a good source of randomness. However, an attacker might be able to manipulate your traffic in a way that he then can predict the randomness you're needing for some operation.
> 3 votes

---
Tags: operating-systems, cryptography, randomness, security, entropy
---


# Question
Title: Can multiple tasks in an RTOS share one stack to save memory?
Many small embedded systems have a limited amount of RAM, 10k or less. I know you can run an RTOS on such systems, however, a realistic number of tasks in such a system is very low, mainly because every task needs its own stack area.
Is it possible to share the space needed for the stack of some of these tasks?
I understand that this is possible in a cooperative environment, such that a task can report its willingness to relinquish the processor (and refrain from using its stack). But in an RTOS you don't normally use cooperative multitasking.
But then, maybe it is sufficient to use non-preemptive tasks when sharing stack space, in a certain way that's also "cooperative" in my opinion.

Can it be done in an RTOS? How?

# Answer
> 4 votes
As long as they do not overlap in execution, the tasks can re-use the same stack space. That is, they can not safely execute in parallel or else one task will corrupt another's stack space.

This corruption may occur due to local variables or parameters stored on the stack, or even due to the occurrence of an ISR.

Hope this helps

---
Tags: operating-systems, memory-management, real-time
---


# Question
Title: Where is the OS when a process is running?
> We know that operating system is responsible for handling memory allocation, process management etc. CPU can perform only one task at a time(assuming it to be single core). Suppose an operating system has allocated a CPU cycle to some user initiated process and CPU is executing that. Now where is operating system running? If some other process is using the CPU, then, is operating system not running for that moment? as OS itself must need CPU to run. If in case OS is not running, then who is handling process management, device management etc for that period?

This question was previously asked on Stack Overflow by vish. I answered it, and so did Martin James, and our answers feel partly contradictory.

# Answer
The question is mixing up who's in control of the memory and who's in control of the CPU. The wording “running” is imprecise: on a single CPU, a single task is running at any given time in the sense that the processor is executing its instructions; but many tasks are executing in the sense that their state is stored in memory and their execution can resume at any time.

While a process is executing on the CPU, the kernel is not executing. Its state is saved in memory. The execution of the kernel can resume:

* if the process code makes a jump into kernel code — this is called a system call.
* if an interrupt occurs.

If the operating system provides preemptive multitasking, it will schedule an interrupt to happen after an interval of time (called a time slice). On a non-preemptive operating system, the process will run forever if it doesn't yield the CPU. See How do modern operating systems like linux handle multitasking? for an explanation of how preemption works.

Tasks such as process management and device management are triggered by some event. If the event is a request by the process, the request will take the form of a system call, which executes kernel code. If the event is triggered from hardware, it will take the form of an interrupt, which executes kernel code.

(Note: in this answer, I use “CPU” and “processor” synonymously, to mean a single execution thread: a single core, or whatever the hardware architecture is.)
> 8 votes

# Answer
I think OP was asking whether the OS needs to run all the time on the CPU (to manage processes and other things). Therefore, I think the second answer fits best: The OS *doesn't* need to run all the time. Eventually it will run again due to the timer interrupt.

Your answer seems a bit more complicated because you're mostly referring to main memory (which OP didn't ask for imo).
> 1 votes

---
Tags: operating-systems, multi-tasking
---


# Question
Title: Bare Metal Operating Systems in High Performance Computing
Few years back, I stumbled across Return Infinity \- the OS framework designed around flat, 64bit memory model, with minimal MMU / VM overhead, etc.

I'm wondering if there are any public benchmarks or success stories of that approach - I'm eyeing it as something to practice doing low latency / high performance computing systems.

The theoretical advantages are substantial, if you're aiming to build a specific-purpose computer system (think bare redis / memcache, fft, transcoding, scientific computing etc).

# Answer
The Return Infinity site you linked claims that BareMetal is an ***Exokernel***.

Exokernel was an MIT research project from the mid to late 1990s which is still widely studied. The philosophy behind Exokernels was that they would provide just *mechanism* and all *policy* would move to user-level libraries. In later papers they more specifically said that the kernel provides *protection* and the libraries provide *management*. The idea was to avoid expensive abstraction layers that are actually unneeded by certain applications.

In hindsight, it is probably not unfair to claim that the main achievement of the Exokernel research project was to invent a number of very clever techniques to make a microkernel OS perform better than a monolithic OS in some cases. The key, I think, was finding ways to avoid kernel-boundary crossing costs. One way they did this was through judicious and careful mapping of kernel data structures into an application's memory space. This allows large amount of data to be transferred across the kernel/user boundary with fewer system calls and address space changes. They also came up with several techniques for describing network and file system policies with tiny languages that could be easily checked and safely checked inside the kernel. (So the core filesystem and network handling in Exokernel is actually done inside the kernel, rather than from a user-level service across an isolation boundary like it might be in a naive microkernel.)

The canonical paper on Exokernels is (IMHO) one of the best systems experience papers I've ever read. It's been quite a while since I read it, but I recall it as being quite honest about both strengths and weaknesses of the approach.

Kaashoek, M. Frans; Engler, Dawson R.; Ganger, Gregory R.; Briceño, Héctor M.; Hunt, Russell; Mazières, David; Pinckney, Thomas; Grimm, Robert; Jannotti, John; Mackenzie, Kenneth: Application Performance and Flexibility on Exokernel Systems, *Proceedings ACM Symposium on Operating Systems Principles*, (SOSP-15):251-266, 1995. (That's a Citeseer link and the Citeseer server is often down, so here also is the ACM link (paywalled).

The wikipedia article on Exokernels is not terrible, and gives a reference to at least one other (later) research project, Nemesis from Cambridge University. Another efficient microkernel project that was being worked on around the same time as Exokernel was the L4 microkernel by Jochen Liedtke.
> 7 votes

---
Tags: operating-systems, performance
---


title: How are userland programs executed?

text:
# Question
Title: How are userland programs executed?
Say we have a simple OS with a filesystem, and some programs on that filesystem. How then does a program get executed by the OS?

My understanding is that the executable file gets loaded into memory, but after that I'm a little fuzzy. I understand the OS creates a process, but I'm not sure exactly how it works. How does the OS tell the machine code to run, and how does the scheduler interact with the program to start, pause and resume execution per scheduling policy?

# Answer
Obviously, with the various forms of operating systems out there, this process can vary (and in some cases, be completely different) but this outlines a general overview.

### Step 1: Load the program into memory.

This is pretty basic; grab the contents of the program and load it into memory. Depending on how memory is managed by the operating system and the platform, additional steps might be required. These could include configuring the memory page where the program is loaded to permit code execution as well as mapping page(s) to the application's initial stack.

Also, many operating systems won't load the entire program into memory immediately; they'll often allocate physical pages and load parts of the program into memory on-demand. This is generally an implementation detail that's transparent to the process, though.

### Step 2: Begin executing the program.

Once the program is loaded into memory, the operating system will create whatever internal structures are required to manage the process (such as a `struct task_struct` in Linux) and do any other necessary bookkeeping. When that's through, the operating system will locate the program's entry point (often a `main` function or similar) and direct the processor to start executing the program at that location.

An operating system will usually start a new process in response to an interrupt (generally a system call of some sort) so in order to return to user mode, where the process will execute, a "return from interrupt" instruction (such as `iret` in x86 assembly) is typically used to restore the system state prior to the interrupt.

### Step 3: Give control to another process.

This part depends heavily upon the multitasking architecture of the operating system, if it even supports multitasking. (If it doesn't, skip ahead to **Step 5**.)

### Step 3a: (Preemptive Multitasking) Suspend the process after a short while.

In a preemptive system, a scheduler allocates a small timeslice for each running process. This timeslice is enforced by a system timer, which will fire an interrupt once a process's time is up. The interrupt will transfer control back to the kernel.

### Step 3a: (Cooperative Multitasking) Wait for the process to give up control.

Cooperative systems depend on individual processes to manually give control back to the operating system on a regular basis. Of course, if a process misbehaves and doesn't return control, it would hang the operating system.

### Step 3b: Save the relevant state of the process.

Once the operating system has control back from the previously executing process, it saves whatever state is necessary to return to the process at a later time. This includes the address of the next instruction the process would have executed, as well as some or all of the processor registers.

### Step 4: Return control to the process.

When it's time to resume the process, the operating system will do the reverse process of the previous step; it will restore the processor registers and start executing code where the process previously left off. Like when a process is started, this is often done with a "return from interrupt" instruction. In a preemptive system, the operating system will also start the timeslice clock again.

### Step 5: Handle a process's exit.

Once the process has completed its task, it will return control to the operating system for the last time by exiting. Often, the process will provide the operating system with some exit data; the operating system can do whatever it wants with this exit data. That could include notifying the process's parent of the exit, logging the completion of the process, or any number of other things. Once that's all said and done, the operating system will remove its record of the no-longer-running process and (generally) free the memory and resources the program had allocated during its execution.

Again, your mileage may vary depending on what operating system and platform you're working with. They come in all shapes and sizes, and they *all* work differently.
> 12 votes

---
Tags: operating-systems, multi-tasking
---


# Question
Title: Which process states exist a multi-processor machine?
In a single-processor architecture, A process might be `New`, `Ready`, `Running`, `Blocked` and `Terminated`.

Are there any additional states in a multi-processor architecture?

# Answer
> 3 votes
More states aren't technically needed, depending on an operating system's implementation.

A kernel can have a task scheduler running on each processor. This allows for the use of the same process states, since each scheduler is running independent of each other. The kernel can have "load balancing" between the processors so that not too many processes are queued-up on one processor

xv6 (UNIX V6 port for x86 architecture) is a bare-bones kernel that does just this, and so, it has the same process states like in a single-processor environment.

---
Tags: operating-systems, process-scheduling
---


# Question
Title: Showing that tournament sort requrires O(n log n) comparisons
I wish I could think of a better way to word my question. Maybe some one here could offer s suggestion for that, as well.

On to my question. Before I do, this is a class question that has been asked, answer, and considered to be over; however, I'm struggle accepting the answer. For this reason, I'm here hoping someone can word it in a way that I understand it.

The problem is as follows:

```
Show that if n is a power of 2, tournament sort requires O(n lg n) comparisons.

```

I refer to a rooted tree graph of six levels (0-5) with the vertices doubling at each level: i.e 1, 2, 4, 8, 16, 32. I see a pattern very similar to binary. I'm not implying the problem is binary related, but it is powers of 2 and I'm very comfortable with binary.

Using that 2^5 = 32, n=32; therefore, n is a power of 2. No argument here. Now I read the problem to say that 32log32 (nlogn) will result in the number of comparisons. The aide answering my question said, "the calculated results of the nlogn were immaterial. I just needed to know there were 5 levels down, and therefore 5 levels up." Additionally, he kept referring to 5log5 which I still don't see a result that makes any sense to me.

As I study the question, I read it to say that the nlogn should provide me with a number of comparisons, based on n. I cannot make that happen with a known values.

Can someone please help me to follow this better?

# Answer
Initially you place the elements you want to sort in the leaves of the tournament tree. Then you fill all the internal nodes with the bigger of the two elements in their respective children. This takes $n-1$ comparisons.

After that, you have the largest element in the root. So you can remove it and place it in the output. Now all the comparisons where this element was involved have to be redone. This is one comparison per level of the tree, making $(\log n) -1$ comparisons (-1, since on the lowest level, there is only one candidate element left, so you don't need to compare.)

Now the second largest element is at the top and you can repeat the procedure. And so on. In the end you will have made up to $\log n$, i.e. $O(\log n)$ comparisons for each of the $n$ elements.

Summing up, we have $n-1 + n\cdot O(\log n)$ comparisons. By the rules of $O$-notation, that is in $O(n\log n)$.
> 2 votes

---
Tags: algorithm-analysis, asymptotics, sorting
---


# Question
Title: No compression algorithm can compress all input messages?
I just started reading a book called Introduction to Data Compression, by Guy E. Blelloch. On page one, he states:

> The truth is that if any one message is shortened by an algorithm, then some other message needs to be lengthened. You can verify this in practice by running GZIP on a GIF file. It is, in fact, possible to go further and show that for a set of input messages of fixed length, if one message is compressed, then the average length of the compressed messages over all possible inputs is always going to be longer than the original input messages.
>
> **Consider, for example, the 8 possible 3 bit messages. If one is compressed to two bits, it is not hard to convince yourself that two messages will have to expand to 4 bits, giving an average of 3 1/8 bits.**

Really? I find it very hard to convince myself of that. In fact, here's a counter example. Consider the algorithm which accepts as input any 3-bit string, and maps to the following outputs:

```
000 -> 0
001 -> 001
010 -> 010
011 -> 011
100 -> 100
101 -> 101
110 -> 110
111 -> 111

```

So there you are - no input is mapped to a longer output. There are certainly no "two messages" that have expanded to 4 bits.

So what exactly is the author talking about? I suspect either there's some implicit caveat that just isn't obvious to me, or he's using language that's far too sweeping.

*Disclaimer:* I realize that if my algorithm is applied iteratively, you do indeed lose data. Try applying it twice to the input 110: 110 -\> 000 -\> 0, and now you don't know which of 110 and 000 was the original input. However, if you apply it only once, it seems lossless to me. Is that related to what the author's talking about?

# Answer
> 17 votes
What you are missing is that you need to consider all bits of size **3 or less**. That is: if in a compression scheme for bits of size 3 or less we compress one of the 3-bit strings to a 2-bit string, then some string **of size 3 or less** will have to expand to 3 bits or more.

A losless compression scheme is a function $C$ from finite bit strings to finite bit strings which is injective, i.e., if $C(x) = C(y)$ then $x = y$, i.e., $C(x)$ uniquely determines $x$.

Consider an arbitrary compression scheme $C$ and let $S$ be a set of binary strings. We can express how well $C$ works on $S$ by computing the ratio $$\text{CompressionRatio}(C,S) = \frac{\sum\_{x \in S} \mathrm{length}(C(x))}{\sum\_{x \in S} \mathrm{length}(x)}.$$ A small compression ratio is good. For example, if it is $1/2$ that means we can on average compress strings in $S$ by 50% using $C$.

If we try to compress *all* strings of length at most $n$ then we are in trouble:

> **Theorem:** Let $S$ be the set of *all* strings of length at most $n$ and $C$ any compression scheme. Then $\text{CompressionRatio}(C,S) \geq 1$.

So, the best compression scheme in the world is the identity function! Well, only if we want to compress *random* strings of bits. The bit strings which occur in practice are far from random and exhibit a lot of regularity. This is why it makes sense to compress data despite the above theorem.

# Answer
> 9 votes
Just an additional note to Andrej's good answer:

You can also take a look to to Kolmogorov complexity:

**Definition**: Given a string $s$, its Kolmogorov complexity $C(s)$ relative to a fixed model of computation is the length of the shortes program (e.g. Turing machine) that outputs $s$.

Informally $C(s)$ measures its *information content* or its *degree of redundancy*; a string $s$ is *incompressible* if $C(s) \geq |s|$

Two fundamental theorems are:

1) independently from the model of computation there is a constant $c$ such that for every string $s$: $C(s) \leq |s| + c$ (informally, given a string $s$ you can hard encode it in a program that simply outputs it without any processing or compression)

2) for all $n$ there exist a string $s$ of length $n$ that is incompressible: $C(s) \geq |s|$ (analogous to the theorem described in Andrej's answer).

The proof is simple: there are $2^n$ binary strings of length $n$, but fewer descriptions (programs) of length $\< n$:

$\sum\_{i=0}^{n-1} 2^i = 2^n - 1 \< 2^n$.

# Answer
> 4 votes
Your counterexample is wrong.

Your list of compressed values has some hidden information which indeed makes the average length longer than 3 bits. The extra information is the length of the output string.

With our eyes we can see from your table that the first output string is only 1 bit long, and the others are 3 bits, but you're cheating if you don't explicitly encode that fact. Let's encode that by prepending one more bit; 0 will mean "length = 1", and 1 will mean "length = 3".

So your table really becomes:

```
000 -> 00
001 -> 1001
010 -> 1010
011 -> 1011
100 -> 1100
101 -> 1101
110 -> 1110
111 -> 1111

```

...which averages to 3.75 bits.

EDIT

Here's an afterthought, which illustrates the same point. It's a nice quiz question:

Morse code is made up of just dots and dashes. Let's call dot 0, and dash 1. All the uppercase letters are encoded as no more than four bits.

```
E = . = 0
Q = --.- = 1101

```

There are 26 uppercase letters. But four bits should only be able to encode 16 distinct values. What's going on?

# Answer
> 0 votes
Counting the trivial zero-length case, there are $2^{n+1}-1$ bit strings whose length is at most n (if lengths are known to be exact multiples of eight, the number is smaller but harder to compute). Thus, all strings of length $n$ or less could be represented using strings of fixed length $n+1$. If many strings will be much shorter than the maximum length, however, it may be helpful to use alternative coding schemes which add more than one to the length of maximal strings, but less to the length of shorter strings. Consequently, the amount of information conveyed by knowing a string's exact length depends upon how long one would assume that the string could be, and how willing one would be to pad shorter strings.

Because such factors are very much application dependent, it's helpful to assume a computation model in which input strings are assumed to contain information that would be sufficient to let a reader know where they end (even if they were padded with arbitrary quantities of arbitrary data), and output strings are required to do likewise. Such a computation model will allow any operations which would work on individual data records to just work as well on any concatenated sequence of data records \[code which would know when to stop reading entire uncompressed records can be presumed to know just as well when to stop reading entire compressed ones\].

---
Tags: data-compression, coding-theory
---


# Question
Title: What do complexity classes look like, if we use Turing reductions?
For reasoning about things like NP-completeness, we typically use many-one reductions (i.e., Karp reductions). This leads to pictures like this:

(under standard conjectures). I'm sure we're all familiar with this sort of thing.

What picture do we get, if we work with Turing reductions (i.e., Cook reductions)? How does the picture change?

In particular, what are the most important complexity classes, and how do they relate? I am guessing that $P^{NP}$ plays the role that used to be taken up by $NP$ and $coNP$ (because $P^{NP}$ is closed under Turing reductions in the same way that $NP$ is closed under Karp reductions); is that about right?

So should the picture look like $P \subset P^{NP} \subset PH \subset PSPACE$ now, i.e., something like the following?

Is there some new sequence that plays a role that corresponds to the polynomial hierarchy? Is there a natural sequence of complexity classes $C\_0=P$, $C\_1=P^{NP}$, $C\_2=?$, ..., such that each complexity class is closed under Turing reductions? What is the "limit" of this sequence: is it $PH$? Is it expected that each class in the sequence is different from the previous one? (By "expected", I mean under plausible conjectures, similar to the sense in which it is expected that $P \ne NP$.)

---

Related: Many-one reductions vs. Turing reductions to define NPC. That article explains that the reason we work with Karp reductions is that it gives us a finer-grained, richer, more precise hierarchy. Essentially, I am wondering what the hierarchy would look like if we worked with Turing reductions: what the coarser, less rich, less precise hierarchy would look like.

# Answer
> 4 votes
You can use $\mathsf{P}^{\Sigma^\mathsf{P}\_i}$. Some authors denote them by $\square^\mathsf{P}\_i$ (similar to $\Delta^\mathsf{P}\_i$ and $\nabla^\mathsf{P}\_i$ notations). It's essentially the Turing closure of the polynomial hierarchy. We have $$\mathsf{P}^{\Sigma^\mathsf{P}\_i}\subseteq \mathsf{NP}^{\Sigma^\mathsf{P}\_i}= \Sigma^\mathsf{P}\_{i+1}\subseteq \mathsf{P}^{\Sigma^\mathsf{P}\_{i+1}}$$ Therefore $\mathsf{P^{PH}} = \sum\_{i\geq 0}\mathsf{P}^{\Sigma^\mathsf{P}\_i} = \sum\_{i\geq 0}\Sigma^\mathsf{P}\_{i} = \mathsf{PH}$.

If the polynomial hierarchy does not collapse all inclusions are strict.

---
Tags: complexity-theory, reductions, complexity-classes
---


# Question
Title: Enumerate All Possible Strings Over Alphabet
I am given the following decision problem:

A program $ \Pi $ takes as input a pair of strings and outputs either $true$ or $false$. It is guaranteed that $\Pi$ terminates on any input. Does there exist a pair ($I\_1,I\_2$) of strings such that $\Pi$ terminates on ($I\_1,I\_2$) with output value $true$?

It is clear that $\Pi$ is semi-decidable and to proof this, I am asked to give a semi-decision procedure. However, how do I enumerate *all* possible pairs strings? Or how do I enumerate all possbile (single) strings in general? Of course, such a program may never terminate, but that is no problem because I am only asking for semi-decidability.

EDIT2: Solution (Java)

# Answer
> 2 votes
Consider a string over $\Sigma$ to be a number written in base $|\Sigma|$ and implement a counter. Remember to include leading "zeroes": first generate all the length-1 strings, then all the length-2 ones, and so on.

# Answer
> 2 votes
The principle of the counter implementation suggested by David Richerby's answer to enumerate the integers is very simple and nice. However I would amend it differently to answer Hendrik Jan's comment regarding leading zeros.

One way is to enumerate all positive integers in base $|\Sigma|$, using $\Sigma$ as an ordered set of digits, which we assume for simplicity to begin with $0$ and $1$. However, one must ignore all integers numbers that do not begin by the digit $1$ on the left, and for the numbers that are kept, one must remove the leading $1$ on the left. So, for example,$"100617"$ becomes $"00617"$. This will take care of including strings with leading $0$'s. It will also take care of including the empty string in the enumeration, since $"1"$ becomes the empty string $""$.

Alternatively, to avoid generating numbers that are skipped, you can more directly change the successor function of the counter. You make it work as usual, except when the number is of the form $1\\,z^n$ for $n\geq 0$, in which case the next number is $1\\,0^{n+1}$, assuming the last symbol is $z$ in $\Sigma$ used as an ordered set of digits. For example $successor("1zzz")="10000"$. Thus all the numbers enumerated begin with a $1$, which you remove, so that it becomes an **enumeration of all strings, including the empty string**.

Then, when you get a string of size n, cut it in two substrings in the n+1 ways possible (since the empty string is also a string), and that will give you an **enumeration of pairs of strings**.

---
Tags: algorithms, strings, enumeration
---


# Question
Title: Which hazards are solved by instruction reordering?
I am not clear on whether it's data and control hazards, or control hazards only. Also, the "solved" word confuses me - technically, instruction reordering is used to solve dependences and thus prevent hazards from happening in the first place. Once they do happen, though, it's stalls and forwarding. Would that make the answer "None"?

Is my thinking wrong?

# Answer
> 3 votes
Instruction reordering in cpu-pipelines doesn't solve any hazards problem.

Register renaming eliminates write-after-write data hazards on registers and write-after-read data hazards on registers.

Speculative execution tries to find some useful work to do in the presence of control hazards.

Instruction reordering only works between instructions that are already completely independent of one another (either because they work with completely different registers or because after register renaming they don't need any of the same registers). At best I would say that instruction reordering solves a "bookkeeping hazard" (I just made that term up). The reason you would *not* do instruction reordering dynamically in the pipeline is if the bookkeeping hardware to do instruction reordering is too expensive for one reason or another. Issuing instructions in-order is cheaper (in terms of hardware) than implementing the queues and logic to do out-of-order issue.

---
Tags: compilers, cpu-pipelines
---