Resource Identifiers

User programs need to deal with a variety of “things” outside of themselves, including

• Files
• Devices (such as the console)
• Other processes
• Network connections
• Users (and groups of users)
• Access rights

In particular, a program may wish to say things like

• “Write this string to this file I opened earlier.”
• “Read the next character from the terminal.”
• “Wait for this other process to finish.”
• “Check whether my userid is in the administrative-access group.”

Each of these actions involves some kind of resource that the operating system manages. The question is: How does a program refer to these resources?

In the Past: “Operating System” as a Library

In the earliest days of computing, the operating system was just a set of subroutines linked into a program (and only one program ran at a time, with full control of the machine). In this model, the program could refer to resources directly.

Thus, we might have a struct openfile that represents an open file, and a program might refer to a file by passing around a pointer to an openfile structure. This style corresponds to how we'd code anything else—using pointers to objects to refer to them. But when we get to the point where multiple programs are running at once, with some level of isolation between them, this approach breaks down—we need another way to refer to resources.

struct openfile* open(const char* filename, int flags);
int write(struct openfile* file, const void* buf, size_t len);
int read(struct openfile* file, void* buf, size_t len);
int close(struct openfile* file);

User Space vs. Kernel Space

The operating system is responsible for managing the resources of the computer, and it needs to do so in a way that is secure and efficient. One of the key principles of operating system design is the separation of user space and kernel space.

In essence, there is a wall between user space and kernel space. User programs run in user space, and cannot directly access anything in kernel space. In contrast, the operating system runs in kernel space, and has full access to the entire computer, but it cannot necessarily trust any information it receives from user space.

Thus, we need to be very careful about how we allow data to cross the boundary between user space and kernel space. The operating system needs to ensure that the data it receives from user programs is valid and safe to use. As we've seen, we can't safely store struct openfile objects in user space, or trust that struct openfile pointers are valid. We need a different way to refer to resources.

Numeric Identifiers

One straightforward way to refer to resources is to use a number. The most obvious number to use is an index into an array of resource structures. For example, we might have an array of struct process objects, and refer to a process by its index in the array.

Tagged Indexes

In some systems, we want to be even more sure that the index is valid. For example, we might want to ensure that the index refers to a process that the user program is allowed to access. In this case, we might use a tagged index.

A tagged index is a pair of a number and a tag (sometime called a uniqifier). The tag is a value that is associated with the resource, and it is used to ensure that the index is valid. So, for example, our process table could instead look like

Now the resource identifier is a pair of a number and a tag, but those identifiers can usually be combined into a single number. For example, we might use the formula tag << 16 | index to combine the tag and index into a single number.

To ensure that we have unique tags, we might use consecutive numbers (sometimes called generation numbers) or we might use completely random numbers. Those approaches guarantee that will have a different tag when reusing a slot in the table, which makes it harder for a program to accidentally refer to the wrong resource.

Hash Tables

A very similar approach is to use a hash table with the resource identifier as the key. If we keep the key as an number, a hash table with linear probing is remarkably similar to our tagged-index approach

Unix-like systems often feel like they're always using plain indexes, because they often produce relatively small numbers, and some resources, like file descriptors, clearly are just plain indexes. We'll revisit Unix's choices when we talk about process IDs.

Windows, on the other hand, has a HANDLE type that is explicitly a tagged index for various resources.

Fixed-Size Tables for Numeric Identifiers

OS designers have a choice to make. If they impose fixed limits on parameters such as the number of possible processes, number of possible open files, and so on, they can use fixed-size tables, which are simpler to implement and also typically just a little bit faster than dynamic data structures.

What (Else) Do We Call These Numeric Identifiers?

Although we've used the term “numeric identifiers” here, various terms are used in practice, including

• Handle: Windows uses the term “handle” for (tagged) numeric identifiers.
• Descriptor: Unix-like systems often use the term “descriptor” for resource identifiers (e.g., file descriptors).
• Identifier: The term “identifier” is also used, as it's more general (e.g., PID means “process identifier”).

Despite the plethora of terms, the basic idea is the same: a number that refers to a resource.

Other Options

There are also other ways to refer to resources, including

• Hierarchical Numbering — IP addresses, for example, are numerical but also hierarchical, where the sequence of numbers captures the hierarchy of the network itself.
• System-Generated Strings — In principle, the operating system could name resources with strings, but this approach is less efficient and harder to check for validity.
• User-Provided Strings — In some cases, the operating system might allow user programs to name resources themselves. The most obvious example is file names, but POSIX also provides named semaphores and named message queues.

Scope and Lifetime

Two other important aspects of a resource identifier are its scope and lifetime.

Scope is where the identifier is valid. For example, file descriptors are usually only valid within specific processes; process IDs are only valid within a single system; but an IP address is valid across the entire Internet.

Lifetime is how long the identifier is valid. For example, a file descriptor is only valid as long as the file is open, while a process ID is valid as long as the process is running.

Reference Counting

Sometimes we can have multiple identifiers that refer to the same resource. For example, POSIX provides the dup system call, which duplicates a file descriptor. In this case, we need to ensure that the resource is only freed when all the identifiers have been closed. We can handle this case by using reference counting, where we keep track of how many identifiers refer to a particular resource, and only free that resource when the count drops to zero.

(When logged in, completion status appears here.)