OS doubt

[aashmohapatra]

Dear Sir

I am confused regarding the memory layout discussed in class (in particular, the 3 diagrams in pages 23, 24, 25 respectively of processes-slides). I've written down whatever I've understood in a page (attached here).

1) Can you please verify if there's any mistake in whatever I've noted down in that page?

2) Are Interrupt Descriptor Table & System Call Table stored in data part of kernel space? Are the corresponding handler routines present in code part of kernel space?

3) Does kernel space comprise of anything other than code and data (that we need to know right now) ?

[Aashirwad Mohapatra]

One more follow-up question:

In my diagram in the previous mail, I had (mistakenly ?) assumed that u-area contains kernel stack. In page 29 of processes-slides about u-area, you've mentioned the line "(Optional) Kernel stack for this process". Also, while listing out the constituents of a process, you've mentioned "kernel stack" and "Admin Info (proc structure & u area)" separately as different constituents. If kernel stack were inside u-area, then it doesn't make sense to list them separately.

So, my question is, according to the convention we will be following in this course, where exactly is kernel stack present? Is it inside the u-area? If not, then where?

Regards,
Aashirwad

[Mandar Mitra]

Apologies for the delayed response.


Q1) Can you please verify if there's any mistake in whatever I've noted down in that page?

Most of what you have written is fine, except that the picture is an oversimplified representation. When we discuss memory management later this sem, we will distinguish between physical memory and virtual memory. Unlike what the picture shows, physical memory for a process will not be a single block of contiguous memory locations.

The first statement in the Warning section is incorrect, however. Multiple processes may be simultaneously present in physical memory. Also, the proc table, containing proc structures of ALL currently existing processes, is stored in kernel data.


Q2) Are Interrupt Descriptor Table & System Call Table stored in data part of kernel space? Are the corresponding handler routines present in code part of kernel space?

Yes for both questions.


Q3) Does kernel space comprise of anything other than code and data (that we need to know right now)?

We haven't really formally defined the term "kernel space". If you define it as memory that can only be accessed by the kernel, then the u area and kernel stack should be regarded as part of kernel space, even though they are per-process entities.


Followup question: In my diagram in the previous mail, I had (mistakenly ?) assumed that u-area contains kernel stack. In page 29 of processes-slides about u-area, you've mentioned the line "(Optional) Kernel stack for this process". Also, while listing out the constituents of a process, you've mentioned "kernel stack" and "Admin Info (proc structure & u area)" separately as different constituents. If kernel stack were inside u-area, then it doesn't make sense to list them separately.

So, my question is, according to the convention we will be following in this course, where exactly is kernel stack present? Is it inside the u-area? If not, then where?

Conceptually, the kernel stack is important enough to be discussed separately. In actual implementations, it may be stored in the u area, or separately. Also, as discussed in class, some implementations (e.g., the Linux kernel) may not even distinguish between the proc structure and u area; everything may be stored within the same structure (called TASK_STRUCT in Linux if I remember correctly).

[Aashirwad Mohapatra]

It's okay.

Understood, thank you!!

[Aashirwad Mohapatra]

One more question, which I asked you after last class on Friday:

I'm confused about where the hardware context is saved during mode switch & context switch respectively. As far as I know, during mode switch, the hardware context of the process is saved in the process' kernel stack. And, during context switch, the hardware context of the process is saved in the process' u-area. My question is, why do we save those in the process' u-area and not it's kernel stack during context switch (like we did, during mode switch)?

[Aashirwad Mohapatra]

A follow-up question (regarding saving context in case of neither mode switch nor context switch):

Suppose a process running in user mode makes a system call. The hardware context is then saved in the kernel stack of the process & mode switch occurs. Now, while the system call routine was being performed by the kernel, suppose a hardware interrupt arrives. Say, the kernel pauses the process & deals with the hardware interrupt. Now, where will the hardware context of the process be saved (before the hardware interrupt gets dealt with)? In it's kernel stack or it's u-area?  (Assume that no context switch occurs. Also, note that no mode switch occurs while going from system call to interrupt and vice-versa). 

[Mandar Mitra]

On Monday, February 10, 2025 at 1:14:19 PM UTC+5:30 Aashirwad Mohapatra
wrote:
> One more question, which I asked you after last class on Friday:
>
> I'm confused about where the hardware context is saved during mode switch
> & context switch respectively. As far as I know, during mode switch, the
> hardware context of the process is saved in the process' kernel stack.

Yes, this is correct.

> during context switch, the hardware context of the process is saved in the
> process' u-area. My question is, why do we save those in the process'
> u-area and not it's kernel stack during context switch (like we did, during
> mode switch)?

I think this is doable in principle, but would be (significantly?) more complicated in some situations. For example, suppose P_old is actually in user mode when the interrupt (that leads to the context switch) arrives. Then, P_old does not even have a kernel stack. The interrupt will normally be handled on a common kernel stack (recall that interrupts are handled in "system context", not "process context"). The kernel will resume P_new soon, and will restore P_old later. The common kernel stack is likely to be modified during this time, so it is not a good place to store P_old's hardware context.

One alternative would be to CREATE a kernel stack for P_old, just to store the hardware context, but that seems more complicated than simply saving P_old's hardware context in a dedicated block inside the u area.

Does this make sense? Note that this is just guesswork. I haven't actually looked at the kernel code that does this; nor have I tried to implement the alternative that you suggest.

I'll need to do some homework to answer your follow-up question (interrupt handling during a system call) with surety. Please remind me if you do not get a response by the end of this week.

[Aashirwad Mohapatra]

I'm having trouble understanding these 2 lines: "Then, P_old does not even have a kernel stack. The interrupt will normally be handled on a common kernel stack".

1) I'm confused regarding the wording in the line "P_old does not even have a kernel stack": Did you mean to say that P_old's kernel stack is empty? [Asking because, I had assumed that every process initially gets allocated a separate kernel stack. In user mode, it is empty & during kernel mode it is non-empty. But, a process always has a kernel stack during it's lifespan. Please correct me if I'm wrong]

2) Previously, we agreed that, during mode switch, the hardware context of a process is saved in the process' kernel stack. Suppose a process is in user mode and suppose then, mode switch occurs due to a hardware interrupt (in which case the process "doesn't have" a kernel stack). Then, where will the process' hardware context be saved during this mode switch? (I had assumed that it will be saved on the process' kernel stack [which was empty previously, in user mode], but seems like I'm wrong. Will it be on the "common kernel stack"?)

3) I had assumed that kernel stack is a per-process entity. So, my question is: What is common kernel stack? I probably missed this term during class (also, couldn't find this term in the slides). Could you please elaborate a bit more on this? (for example, it's location in memory & it's uses)

[Mandar Mitra]

Apologies for adding to the confusion! Instead of guessing, let me check more carefully what actually happens in practice. I hope to present a clearer picture over email or in class today.

Aashirwad Mohapatra wrote (Tue, Feb 11, 2025 at 04:27:58AM -0800):
> I'm having trouble understanding these 2 lines: "Then, P_old does not even
> have a kernel stack. The interrupt will normally be handled on a common
> kernel stack".
>
> 1) I'm confused regarding the wording in the line "P_old does not even have
> a kernel stack": Did you mean to say that P_old's kernel stack is empty?
> [Asking because, I had assumed that every process initially gets allocated
> a separate kernel stack. In user mode, it is empty & during kernel mode it
> is non-empty. But, a process always has a kernel stack during it's
> lifespan. Please correct me if I'm wrong]
>
> 2) Previously, we agreed that, during mode switch, the hardware context of
> a process is saved in the process' kernel stack. Suppose a process is in
> user mode and suppose then, mode switch occurs due to a hardware interrupt
> (in which case the process "doesn't have" a kernel stack). Then, where will
> the process' hardware context be saved during this mode switch? (I had
> assumed that it will be saved on the process' kernel stack [which was empty
> previously, in user mode], but seems like I'm wrong. Will it be on the
> "common kernel stack"?)
>
> 3) I had assumed that kernel stack is a per-process entity. So, my question

> is: What is *common kernel stack*? I probably missed this term during class

[Aashirwad Mohapatra]

Okay, sure

[Aashirwad Mohapatra]

Can the same process correspond to multiple programs / executable files (not necessarily at the same time) ?

At first glance, it seemed to me that exec( ) does just that. But, if a process' user address space gets changed, is it now the same process? Asking because you've mentioned that process = process context & user address space is a constituent of a process' context.

[Aashirwad Mohapatra]

I was trying to modify the program of question 4 (Lab 1) to solve question 6 (Lab 1). To track the creation and free up orders, my attempt was: The order of fork() calls corresponds to the creation order [i.e, the i-th fork() call creates the i-th child process] and the return value [PID] of wait() to parent tells me about the free up order of the zombies. Could you please verify if this is correct ?

Also, how do I track the termination order of the child processes?

[Mandar Mitra]

Aashirwad Mohapatra wrote (Sat, Feb 22, 2025 at 12:04:29AM -0800):
> Can the same process correspond to multiple programs / executable files
> (not necessarily at the same time) ?
>
> At first glance, it seemed to me that exec( ) does just that.

Yes, that was the answer that I was looking for.

> But, if a
> process' user address space gets changed, is it now the same process?
> Asking because you've mentioned that process = process context & user
> address space is a constituent of a process' context.

Yes, I think it is fair to say that the process is the same, since a process is identified by its PID. The process' proc structure + u area remain unchanged, and in some sense, those components constitute the "soul" of the process.

[Mandar Mitra]

Aashirwad Mohapatra wrote (Sat, Feb 22, 2025 at 04:31:19AM -0800):
> I was trying to modify the program of question 4 (Lab 1) to solve question
> 6 (Lab 1). To track the creation and free up orders, my attempt was: The
> order of fork() calls corresponds to the creation order [i.e, the i-th
> fork() call creates the i-th child process]

Yes, this part is correct.

> and the return value [PID] of
> wait() to parent tells me about the free up order of the zombies. Could you
> please verify if this is correct ?

Yes, this is fine too, but the question is intended to determine whether the "free up order of the zombies" is the same as the order in which the child processes terminate, or something else, i.e., if Child 1 (older sibling) terminates AFTER Child 2 (younger sibling), and the parent THEN calls wait, in what order will it get back the exit statuses of the two children?

> Also, how do I track the termination order of the child processes?

A rigorous way to control the termination order would involve process synchronisation, which we have not covered yet. For now, the method that we are using makes processes sleep for different amounts of time, e.g., to make P1 terminate after P2, you could make P1 sleep for 10 seconds, and P2 not sleep at all. This is not foolproof, of course, but will generally work in practice.

[Aashirwad Mohapatra]

I'm still not able to solve that question (Q6 of Lab1). To convey you where exactly I'm getting stuck, I'll post the 2 programs, which I wrote for Q4 & Q6 respectively (with help from ChatGPT) below:

#include "common.h"    // to output in order of creation, use wait() inside 1st for loop  [experiment with lines 17 & 22]

int main() {
    int pid, status;
   
    for (int i=0; i<10; i++) {  // Loop to create 10 children
        if ((pid = fork()) < 0) {
            perror("fork failed");
            exit(1);
        }

        if (pid == 0) {  // Child process
            printf("Child %d: PID = %d\n", i+1, getpid());
            exit(0);  // Child exits
        }
       
        // wait(&status);
    }
   
    // parent process
   
    for (int i=0; i<10; i++){
        if((pid = wait(&status)) < 0){
            perror("wait failed");
            exit(1);    
        }
       
        printf("parent freed child with PID %d \n", pid);
    }  

    printf("All children freed. Parent exiting.\n");  

    return 0;
}

********************************************************************
The above is the program for Q4. Can you please verify if it's correct?

**********************************************************************

#include "common.h"    

int main() {
    int pid, status;
   
    srand(time(NULL));  // Seed random number generator
   
    for (int i=0; i<10; i++) {  // Loop to create 10 children
        if ((pid = fork()) < 0) {
            perror("fork failed");
            exit(1);
        }

        if (pid == 0) {  // Child process
            sleep(rand() % 20);
            printf("Child %d: PID = %d\n", i+1, getpid());   // Child i is the i-th child created
            exit(0);  // Child exits
        }
    }
   
    // parent process
   
    for (int i=0; i<10; i++){
        if((pid = wait(&status)) < 0){
            perror("wait failed");
            exit(1);    
        }
       
        printf("parent freed child with PID %d \n", pid);
    }  

    printf("All children freed. Parent exiting.\n");  

    return 0;
}

***************************************************************

The above is the program for Q6, where I just added a sleep() to that of Q4, as you suggested earlier. I can clearly see from the output of this program that the free up order and the creation order are not same. But, how do I know if the free up order and the termination order are the same? In particular, how do I keep track of the termination order in my above program? [If this is outside our midsem syllabus, then please don't bother answering. I'll skip it for now & retry when we cover those concepts later]

[Aashirwad Mohapatra]

Understood, thank you!

[Mandar Mitra]

Aashirwad Mohapatra wrote (Sun, Feb 23, 2025 at 12:24:23PM -0800):
> I'm still not able to solve that question (Q6 of Lab1). To convey you where
> exactly I'm getting stuck, I'll post the 2 programs, which I wrote for Q4 &
> Q6 respectively (with help from ChatGPT) below:

Question 4:

> if (pid == 0) { // Child process
> printf("Child %d: PID = %d\n", i+1, getpid());
> exit(0); // Child exits

As discussed in class, the main point of this exercise is to ensure that the child processes themselves do not continue the for loop, and the above code does this correctly.

Unimportant pedantic point: as far as I can tell, in your program, the parent does not print its PID (which it should have, according to the question).


Question 6:

> The above is the program for Q6, where I just added a sleep() to that of
> Q4, as you suggested earlier. I can clearly see from the output of this
> program that the free up order and the creation order are not same. But,
> how do I know if the free up order and the termination order are the same?
> In particular, how do I keep track of the termination order in my above
> program?

One possible way would be to make the children sleep for 20, 18, 16, ... seconds before they terminate. In practice, this will almost always ensure that the children terminate in the opposite order of their creation. (You don't have to worry right now that the method is not foolproof.)

Make the parent sleep for a longer duration, say 30 seconds, before the for loop with the wait calls. This will "ensure" that all children have terminated by the time the parent calls wait for the first time. The pids returned by wait will tell you the cleanup order.

Does this make sense?

[Aashirwad Mohapatra]

I did what you said above, here's my program:

#include "common.h"    

int main() {
    int pid, status;
   

    printf("Parent: PID = %d\n", getpid());

   
    for (int i=0; i<10; i++) {  // Loop to create 10 children
        if ((pid = fork()) < 0) {
            perror("fork failed");
            exit(1);
        }

        if (pid == 0) {  // Child process

            printf("Child %d: PID = %d\n", i+1, getpid());   // Child i is the i-th child created

            sleep(20-2*i);

            exit(0);  // Child exits
        }
    }
   
    // parent process
   

    sleep(30);

   
    for (int i=0; i<10; i++){
        if((pid = wait(&status)) < 0){
            perror("wait failed");
            exit(1);    
        }
       
        printf("parent freed child with PID %d \n", pid);
    }  

    printf("All children freed. Parent exiting.\n");  

    return 0;
}

***************************************************************

But, every time I run the above program, the output tells me that the cleanup order & the creation order are the same (which shouldn't be the case, right ?). Interestingly, if I comment out the "sleep(30)" line for the parent, I get that the cleanup order & the termination order are the same (& different from the creation order). I even tried this out using a compiler other than gcc (an online one: "programiz"), I get the same observations. Could you please explain these?

[Mandar Mitra]

Aashirwad Mohapatra wrote (Mon, Feb 24, 2025 at 05:25:12AM -0800):
> But, every time I run the above program, the output tells me that the
> cleanup order & the creation order are the same (which shouldn't be the
> case, right ?). Interestingly, if I comment out the "sleep(30)" line for
> the parent, I get that the cleanup order & the termination order are the
> same (& different from the creation order). I even tried this out using a
> compiler other than gcc (an online one: "programiz"), I get the same
> observations. Could you please explain these?

The main point of the problem was to empirically answer the following question. If multiple child processes have terminated before the parent process P calls wait(), in what order are the child processes cleaned up: (A) in the order of their termination, or (B) in the order of their creation?

The sleep() calls in the children ensure that the order of termination is (almost certainly) the opposite of the order in which they were created. The long sleep() in the parent ensures that all children have terminated by the time the parent calls wait(). Thus, your program above shows that, for the platform that you are using, the answer is (B).

Without the long sleep in the parent, only 1 child is dead every time the parent calls wait(), so there's no choice involved, and we don't get the answer that we are looking for.

[Aashirwad Mohapatra]

Understood, thank you !!

[Aashirwad Mohapatra]

I've few questions from page 14 (avg. sleep time & dynamic priority) and page 16 (data structures) of the Scheduling in Linux slides:

In page 16, if I understand correctly, each static priority value 0-139 corresponds to a ready queue of processes with that static priority value. The Linux 2.6 scheduler picks (some ?) process from the first non-empty ready queue. In page 14, you've mentioned that dynamic priority value is used by the scheduler when selecting a process to run.

1) How does the scheduler pick a process (from the first non-empty ready queue) using dynamic priority values, ensuring that the whole procedure takes O(1) time ?

2) How good is the "picking (some ?) process from the first non-empty queue" strategy? In particular, can't a process having lesser static priority have greater dynamic priority (compared to another process) ? Then, this strategy may not be very good.

[Mandar Mitra]

Aashirwad Mohapatra wrote (Tue, Mar 11, 2025 at 05:21:07AM -0700):
> In page 16, if I understand correctly, each *static priority *value 0-139

> corresponds to a ready queue of processes with that static priority value.

Sorry for the confusion: these queues actually correspond to dynamic priority values (the "prio" field of the proc structure), not static priority.

> The Linux 2.6 scheduler picks (some ?) process from the first non-empty

> ready queue. In page 14, you've mentioned that *dynamic priority* value is

> used by the scheduler when selecting a process to run.

I hope this is now consistent with the above.

> 1) How does the scheduler pick a process (from the first non-empty ready
> queue) using dynamic priority values, ensuring that the whole procedure
> takes O(1) time ?
>

> 2) How good is the "picking (some ?) process from the *first *non-empty

> queue" strategy? In particular, can't a process having lesser static
> priority have greater dynamic priority (compared to another process) ?
> Then, this strategy may not be very good.

These questions should now be moot.

Please let me know if anything is still confusing.

-mandar

[Aashirwad Mohapatra]

No, it makes sense now. Thank you !!

[Aashirwad Mohapatra]

In the blocking version of semaphores, the behaviour of signal(S) is mentioned differently in class notes & slides:

Signal(S){     // slides
  S.value++;
  if (S.value <= 0){
    P = dequeue(S.L);
    wakeup(P);
  }
}

Signal(S){    // class notes
  P = dequeue(S.L);
  if (P != NULL) wakeup(P);
  else S.value++; 
}

Are the two versions equivalent ? (asking because: in the slide one, S.value is always being incremented, whereas in the class-notes version it is not)
Also, which version should I follow ?

[Mandar Mitra]

Aashirwad Mohapatra wrote (Wed, Mar 26, 2025 at 06:24:37PM -0700):
> In the blocking version of semaphores, the behaviour of signal(S) is
> mentioned differently in class notes & slides:
>
> Signal(S){ // slides
> S.value++;
> if (S.value <= 0){
> P = dequeue(S.L);
> wakeup(P);
> }
> }
>
> Signal(S){ // class notes
> P = dequeue(S.L);
> if (P != NULL) wakeup(P);
> else S.value++;
> }
>
> Are the two versions equivalent ? (asking because: in the slide one,
> S.value is always being incremented, whereas in the class-notes version it
> is not)
> Also, which version should I follow ?

They are equivalent only for binary semaphores (I think). Since we have not had time to discuss binary semaphores in class (or how to implement general/counting semaphores using binary semaphores), please ignore the version I wrote on the board, and follow the version given in the slides.

I'm reasonably sure I announced this correction in class, but as a general rule, whenever there is an inconsistency between the slides and what I say in class, please just follow whatever's in the slides. Of course, it would help if you could point out the discrepancy, as you have above.

Thanks,
Mandar.

[Aashirwad Mohapatra]

Got it, thank you!