doubts in OS

[Rahul Bhattacharya]

Sir,

I have few questions in the attached slide. 

Vaguely, How this hash table is made? 

To be precise, 

Q1. Are the linked lists in this table made out of multiple processes?(or only parent-children processes?)

Q2. What is contained in each node of a linked list?

Q3. What is there in the index table(the column under the “hash table” in the figure) of the hash table?

Q4. Where is this hash table stored?(like in the ‘kernel data’ part in the memory?)

Q5. Is this hash table corresponding to the current process running in the ?

[Mandar Mitra]

Rahul Bhattacharya wrote (Mon, Feb 10, 2025 at 01:20:13AM +0530):
> Sir,
> I have few questions in the attached slide.
> Vaguely, How this hash table is made?
> To be precise,
> Q1. Are the linked lists in this table made out of multiple processes?(or
> only parent-children processes?)

ALL existing processes have to be stored in this hash table. A very simple implementation may just use a hash table of size 100 (say), and use f(x) = x mod 100 as the hash function.

> Q2. What is contained in each node of a linked list?

Each node ≡ a single proc structure

> Q3. What is there in the index table(the column under the “hash table” in
> the figure) of the hash table?

A pointer to the head node of the i-th linked list.

> Q4. Where is this hash table stored?(like in the ‘kernel data’ part in the
> memory?)

Yes, as shown in a subsequent diagram.

> Q5. Is this hash table corresponding to the current process running in the ?

I did not understand this last question.

Please email with any other questions that you have.

[Mandar Mitra]

Rahul Bhattacharya wrote (Fri, Feb 14, 2025 at 11:16:20PM -0800):
> Ans of Q3. A pointer to the head node of the i-th linked list.
> > Each node in the linked is a proc structure corresponding to a process.

> And the i-th node is pointing to (i+1)th node in a linked list. But how
> this link is made? Is the ith node represents the parent process of (i+1)th
> node's process? And is pointer in the 'index table' something like "Adam"
> of the following linked list?

In general, no. Assume the following for simplicity.

* hash function: f(x) = x mod 10
* init process with PID 1 (≡ Adam) has spawned processes with PIDs 2, 3, 4.
* All the 4 processes listed above are long running processes, i.e., they will run until someone gives the shutdown command.
* After some time, you login. Your window manager has pid = 100, it spawns a terminal as a child process with pid = 101, which in turn spawns the shell (pid = 102) as a child process.
* After some more time, you start firefox with pid = 342.

Then hash_table[0] will point to proc structure of the window manager.

hash_table[1] will point to init; init will point to terminal.

hash_table[2] will point to PID 2, which will point to shell (102), which will point to firefox (342).

The process hierarchy is maintained via a separate/independent set of <parent, eldest child, next sibling, previous sibling> pointers.

init's eldest child pointer will point to 2, window manager's eldest child pointer will point to terminal, terminal's eldest child pointer will point to shell, and so on.

PIDs 2, 3, 4 will be connected via sibling pointers. The terminal and firefox, both children of the window manager, will also be connected by sibling pointers.


> Q5. Sorry for the incomplete question. Is this hash table storing all the
> proc structures corresponding to processes beginning from the boot till the
> current the current process running in the CPU?

No, only processes that currently exist (i.e., processes that are live or zombie). The proc structure of a process P is freed / cleaned up / deleted if either (i) its original parent (PP, say) does a wait(), and is woken up by P's termination; or (ii) PP terminates without a wait() for P, and P is handed over as a child to init. If P already terminated before the handover, its proc structure is freed during the handover. Otherwise, its proc structure is cleaned up after it terminates.

Does all of this make sense?