Tencent interview: On a 32-bit 4GB system, accessing 2GB of data, what will happen to the virtual memory?

Hello everyone, I am Xiaolin.

Today a reader sent me his interview experience with Tencent in August, in which he was asked quite a lot of questions.

The operating system and network interviews account for 60% of the entire interview, and the remaining 40% is Java + project content (the reader's technology stack is Java-oriented).

This time, I will mainly analyze the issues related to the operating system and the network for everyone.

Tencent Interview Questions

operating system

Can a single core be multithreaded?

OK.

A single core creates multiple threads, and the CPU quickly switches from one process to another, during which each process runs for tens or hundreds of milliseconds. Although a single-core CPU can only run one process at a certain moment, it may run multiple processes during 1 second, thus creating an illusion of parallelism, which is actually concurrency.

Concurrency and Parallelism

How does a virtual address find the corresponding content?

There are two main ways to manage operating system memory. Different management methods have different addressing implementations:

• Memory segmentation: The virtual address space of a process is divided into multiple segments of different sizes, each of which corresponds to a logical unit, such as code segment, data segment, heap segment, and stack segment. The size of each segment can be adjusted as needed, so that different segments can allocate and release memory as needed. The advantage of virtual memory segmentation is that it can better manage different types of data, but due to the inconsistent size of the segments, external fragmentation is prone to occur.
• Memory paging: The virtual address space of a process is divided into pages of fixed size, and the physical memory is also divided into page frames of the same size. Virtual addresses are mapped to physical addresses through page tables, and pages can be loaded and released on demand. The advantage of virtual memory paging is that it can better utilize physical memory space, but it may cause internal fragmentation.

Segmented addressing mode

The virtual address under the segmentation mechanism consists of two parts, the segment selection factor and the offset within the segment.

picture

Segment selection factor and offset within segment:

• The segment selector is stored in the segment register. The most important part of the segment selector is the segment number, which is used as an index into the segment table. The segment table stores the base address of the segment, the segment boundaries, and the privilege level.
• The segment offset in the virtual address should be between 0 and the segment boundary. If the segment offset is legal, the segment base address plus the segment offset is used to obtain the physical memory address.

In the above, we know that the virtual address is mapped to the physical address through the segment table. The segmentation mechanism divides the virtual address of the program into 4 segments. Each segment has an entry in the segment table. The base address of the segment is found in this entry, and then the offset is added, so the address in the physical memory can be found, as shown in the following figure:

picture

If we want to access the virtual address at offset 500 in segment 3, we can calculate the physical address as segment 3 base address 7000 + offset 500 = 7500.

The segmentation method is very good, which solves the problem that the program itself does not need to care about the specific physical memory address, but it also has some shortcomings:

• The first is the problem of memory fragmentation.
• The second is the problem of low efficiency of memory swapping.

Paging addressing mode

The virtual address and the physical address are mapped through the page table, as shown below:

picture

The page table is stored in the memory, and the memory management unit (MMU) is responsible for converting the virtual memory address into the physical address.

When the virtual address accessed by the process cannot be found in the page table, the system will generate a page fault exception, enter the system kernel space to allocate physical memory, update the process page table, and finally return to the user space to resume the process.

Under the paging mechanism, the virtual address is divided into two parts, the page number and the page offset. The page number is used as the index of the page table, which contains the base address of the physical memory where each physical page is located. The combination of this base address and the page offset forms the physical memory address, as shown in the figure below.

picture

To sum up, for a memory address translation, there are actually three steps:

• Divide the virtual memory address into page number and offset;
• According to the page number, query the corresponding physical page number from the page table;
• Just take the physical page number and add the previous offset to get the physical memory address.

Here is an example where a page in virtual memory is mapped to a page in physical memory through a page table, as shown below:

picture

If 32-bit 4G executes 2G stuff, what changes will there be in virtual memory?

When an application requests memory through the malloc function, it actually requests virtual memory, and no physical memory is allocated at this time.

When the application reads and writes this virtual memory, the CPU will access this virtual memory. At this time, it will find that this virtual memory is not mapped to the physical memory. The CPU will generate a page fault interrupt, the process will switch from user mode to kernel mode, and the page fault interrupt will be handed over to the kernel's Page Fault Handler (page fault interrupt function) for processing.

The page fault interrupt handler will check whether there is free physical memory:

• If so, physical memory is allocated directly and a mapping relationship between virtual memory and physical memory is established.
• If there is no free physical memory, the kernel will start to reclaim memory, such as using the swap mechanism.

What is the Swap mechanism?

When the system's physical memory is insufficient, it is necessary to release some of the space in the physical memory for use by currently running programs. The released space may come from programs that have not been operated for a long time. The released space will be temporarily saved to the disk, and when those programs are to be run, the saved data will be restored from the disk to the memory.

In addition, when there is pressure on memory usage, memory recycling will be triggered, and the infrequently accessed memory will be written to the disk first, and then released to other processes that need it more. When the memory is accessed again, it can be read from the disk again.

This process of swapping memory data out of disk and restoring data from disk to memory is what the Swap mechanism is responsible for.

Swap is to use a disk space or local file as memory, which includes two processes: swap out and swap in:

• Swap Out is to store the memory data that is not used by the process temporarily to the disk and release the memory occupied by this data;
• Swap In means reading the memory from disk to memory when the process accesses it again.

The process of swapping in and out is as follows:

picture

The advantage of using the Swap mechanism is that the memory space that the application can actually use will far exceed the system's physical memory. Since the price of hard disk space is much lower than that of memory, this method is undoubtedly economical. Of course, frequent reading and writing of the hard disk will significantly reduce the operating speed of the operating system, which is also the disadvantage of Swap.

What is the difference between kernel mode and user mode?

Kernel mode and user mode are two different execution modes in an operating system.

• Kernel state is the state in which the operating system runs in the highest privilege level mode, which has full control over system resources. In kernel state, the operating system can execute privileged instructions, access all memory and devices, and perform critical system operations. The code running in kernel state is usually the operating system kernel or driver.
• User mode is a mode in which applications run at a lower privilege level. In user mode, applications can only access limited system resources and cannot directly execute privileged instructions or access kernel-level data. Code running in user mode is usually an application or user process.

The difference between kernel state and user state lies in the restrictions on permissions and resource access. Kernel state has higher permissions and wider resource access capabilities, while user state is restricted and can only access limited resources. The operating system ensures the security and stability of the system by protecting key operations and resources in kernel state. User programs request services or resources from the operating system through system calls and execute in user state to provide higher isolation and security.

Network Protocol

What are the common http response codes?

HTTP status codes are divided into five categories: 1XX: message status code; 2XX: success status code; 3XX: redirect status code; 4XX: client error status code; 5XX: server error status code.

picture

Five major categories of HTTP status codes

The common specific status codes are: 200: successful request; 301: permanent redirection; 302: temporary redirection; 404: the page cannot be found; 405: the requested method type is not supported; 500: internal server error.

What are the characteristics of each version of http?

HTTP/1.1 performance improvements over HTTP/1.0:

• Using long connections improves the performance overhead caused by short HTTP/1.0 connections.
• It supports pipeline network transmission. As long as the first request is sent, the second request can be sent without waiting for it to come back, which can reduce the overall response time.

But HTTP/1.1 still has performance bottlenecks:

• The request/response header is sent without compression. The more header information there is, the greater the delay. Only the body part can be compressed.
• Sending a lengthy header. Sending the same header to each other each time causes a lot of waste;
• The server responds in the order of requests. If the server responds slowly, the client will not be able to request data, which is head-of-line blocking.
• No request priority control;
• Requests can only be initiated by the client, and the server can only respond passively.

HTTP/1 ~ HTTP/2

HTTP/2 performance improvements over HTTP/1.1:

• Header Compression
• Binary format
• Concurrent transmission
• The server actively pushes resources

1. Header compression

HTTP/2 will compress the header. If you send multiple requests at the same time and their headers are the same or similar, the protocol will help you eliminate the duplicate parts.

This is the so-called HPACK algorithm: a header information table is maintained on both the client and the server, all fields are stored in this table, an index number is generated, and the same field will not be sent in the future, only the index number will be sent, thus increasing the speed.

2. Binary format

HTTP/2 is no longer a plain text message like HTTP/1.1, but adopts a binary format. Both the header information and the data body are binary and are collectively referred to as frames: Headers Frame and Data Frame.

HTTP/1 vs HTTP/2

Although this is not user-friendly, it is very computer-friendly, because computers only understand binary. Therefore, after receiving the message, there is no need to convert the plaintext message into binary, but to directly parse the binary message, which increases the efficiency of data transmission.

3. Concurrent transmission

We all know that the implementation of HTTP/1.1 is based on the request-response model. In the same connection, HTTP completes a transaction (request and response) before processing the next transaction. In other words, in the process of sending a request and waiting for a response, you cannot do other things. If the response is delayed, the subsequent request cannot be sent, which also causes the problem of head-of-line blocking.

HTTP/2 is really cool, introducing the concept of Stream, where multiple Streams are multiplexed in one TCP connection.

picture

As can be seen from the figure above, a TCP connection contains multiple streams, and a stream can contain one or more messages. A message corresponds to a request or response in HTTP/1 and consists of an HTTP header and a body. A message contains one or more frames, which are the smallest unit of HTTP/2 and store the content (header and body) in HTTP/1 in a binary compressed format.

A unique Stream ID is used to distinguish different HTTP requests. The receiving end can assemble HTTP messages in order according to the Stream ID. Frames of different Streams can be sent out of order, so different Streams can be sent concurrently, that is, HTTP/2 can send requests and responses in parallel and interleaved.

For example, in the figure below, the server sends two responses in parallel: Stream 1 and Stream 3. Both streams run on a TCP connection. After receiving them, the client will assemble them into HTTP messages in order according to the same Stream ID.

picture

4. Server Push

HTTP/2 also improves the traditional "request-response" working mode to a certain extent. The server is no longer a passive responder, but can actively send messages to the client.

Both the client and the server can establish a Stream, and the Stream ID is also different. The Stream established by the client must be an odd number, while the Stream established by the server must be an even number.

For example, in the figure below, Stream 1 is the resource requested by the client from the server. It is a stream established by the client, so the ID of the stream is an odd number (number 1); Streams 2 and 4 are resources actively pushed by the server to the client. They are streams established by the server, so the IDs of these two streams are even numbers (numbers 2 and 4).

picture

For example, the client obtains an HTML file from the server through an HTTP/1.1 request, and HTML may also need to rely on CSS to render the page. At this time, the client must initiate another request to obtain the CSS file, which requires two message round trips, as shown in the left part of the following figure:

picture

As shown in the right part of the above figure, in HTTP/2, when the client accesses HTML, the server can directly and actively push the CSS file, reducing the number of message transmissions.

Introduction to TCP congestion control

When the network is congested, if a large number of data packets continue to be sent, it may cause data packet delays and losses. At this time, TCP will retransmit the data, but retransmission will cause a heavier burden on the network, resulting in greater delays and more packet losses. This situation will enter a vicious cycle and be continuously amplified....

Therefore, TCP cannot ignore what happens on the network. It is designed as a selfless protocol. When the network is congested, TCP will sacrifice itself and reduce the amount of data sent.

So, there is congestion control, the purpose of which is to prevent the "sender"'s data from filling up the entire network.

In order to regulate the amount of data to be sent on the "sender side", a concept called "congestion window" is defined.

Congestion control mainly consists of four algorithms:

• Slow Start
• Congestion Avoidance
• Congestion occurs
• Fast recovery

Slow Start

After TCP has just established a connection, it first has a slow start process. This slow start means increasing the number of data packets sent little by little. If a large amount of data is sent right away, wouldn't this cause congestion to the network?

The slow start algorithm only requires one rule to be remembered: each time the sender receives an ACK, the size of the congestion window cwnd increases by 1.

Here it is assumed that the congestion window cwnd and the send window swnd are equal. Here is an example:

• After the connection is established, cwnd = 1 is initialized at the beginning, indicating that data of an MSS size can be transmitted.
• When an ACK is received, cwnd is increased by 1, so 2 packets can be sent at a time.
• After receiving 2 ACKs, cwnd increases by 2, so 2 more packets can be sent than before, so 4 packets can be sent this time.
• When these 4 ACK confirmations arrive, the cwnd of each confirmation increases by 1, and the cwnd of the 4 confirmations increases by 4, so 4 more can be sent than before, so 8 can be sent this time.

The change process of the slow start algorithm is as follows:

Slow start algorithm

It can be seen that with the slow start algorithm, the number of packets sent increases exponentially.

So when will the slow start price stop?

There is a state variable called slow start threshold ssthresh (slow start threshold).

• When cwnd < ssthresh, the slow start algorithm is used.
• When cwnd >= ssthresh, the "congestion avoidance algorithm" will be used.

Congestion Avoidance

When the congestion window cwnd "exceeds" the slow start threshold ssthresh, the congestion avoidance algorithm will be entered.

Generally speaking, the size of ssthresh is 65535 bytes.

Then after entering the congestion avoidance algorithm, its rule is: every time an ACK is received, cwnd increases by 1/cwnd.

Continuing with the previous slow start example, let's assume that ssthresh is 8:

• When 8 ACK confirmations arrive, each confirmation increases by 1/8, and the cwnd of 8 ACK confirmations increases by 1 in total, so 9 MSS of data can be sent this time, which becomes a linear growth.

The change process of the congestion avoidance algorithm is as follows:

Congestion Avoidance

Therefore, we can find that the congestion avoidance algorithm changes the exponential growth of the original slow start algorithm into linear growth. It is still in the growth stage, but the growth rate is slower.

As the traffic keeps growing, the network will gradually become congested, causing packet loss. At this time, the lost data packets will need to be retransmitted.

When the retransmission mechanism is triggered, the "congestion occurrence algorithm" is entered.

Congestion occurs

When the network is congested, data packets will be retransmitted. There are two main retransmission mechanisms:

• Timeout retransmission
• Fast Retransmit

When a "timeout retransmission" occurs, the congestion occurrence algorithm will be used.

At this time, the values ​​of ssthresh and cwnd will change:

• ssthresh is set to cwnd/2,
• cwnd is reset to 1 (it is restored to the initialization value of cwnd, I assume here that the initialization value of cwnd is 1)

The changes in the congestion occurrence algorithm are shown in the following figure:

picture

Congested sending - timeout retransmission

Then, we restart the slow start, which will suddenly reduce the data flow. This is really like returning to the pre-liberation era once the "timeout retransmission" occurs. However, this method is too radical and the reaction is too strong, which will cause network lag.

There is a better way. We have talked about the "fast retransmit algorithm" before. When the receiver finds that an intermediate packet is lost, it sends the ACK of the previous packet three times, so the sender will retransmit quickly without waiting for a timeout.

TCP considers this situation not serious because most of the packets are not lost, only a small part is lost. Then the changes of ssthresh and cwnd are as follows:

• cwnd = cwnd/2, which means it is set to half of the original value;
• ssthresh = cwnd;
• Enter the fast recovery algorithm

Fast recovery

Fast retransmit and fast recovery algorithms are generally used at the same time. The fast recovery algorithm believes that if you can still receive 3 duplicate ACKs, it means that the network is not that bad, so there is no need to be as strong as RTO timeout.

As mentioned before, before entering fast recovery, cwnd and ssthresh are updated:

• cwnd = cwnd/2, which means it is set to half of the original value;
• ssthresh = cwnd;

Then, enter the fast recovery algorithm as follows:

• Congestion window cwnd = ssthresh + 3 (3 means that 3 data packets are confirmed to have been received);
• Retransmit lost packets;
• If a duplicate ACK is received, cwnd increases by 1;
• If an ACK for new data is received, cwnd is set to the value of ssthresh in the first step. This is because the ACK confirms the new data, indicating that all data from the duplicated ACK has been received, and the recovery process is over. The state before recovery can be returned, that is, the congestion avoidance state is entered again.

The change process of the fast recovery algorithm is as follows:

Fast retransmit and fast recovery

In other words, the situation did not return to the pre-liberation era overnight like "timeout retransmission", but it remained at a relatively high value and subsequently increased linearly.

What affects the window size?

The TCP window size is affected by several factors, including the following:

• Receiver Window Size: The receiver's window size determines the amount of data the sender can send. If the receiver's window is small, the sender needs to wait for confirmation before continuing to send data, thus limiting the sending rate.
• Bandwidth and latency: The bandwidth and latency of the network will have an impact on the TCP window size. Higher bandwidth and lower latency can usually support larger window sizes, thereby achieving higher data transfer rates.
• Congestion control: TCP's congestion control mechanism adjusts the window size according to the degree of network congestion. When network congestion occurs, TCP will reduce the window size to reduce the sending rate to avoid further deterioration of congestion.
• Routers and network devices: The buffer size of routers and other network devices also has an impact on the TCP window size. If the buffer is small, it may cause packet loss or increased latency, thus limiting the window size.
• Operating system and application: The operating system and application can also configure and adjust the TCP window size. By adjusting the parameters of the operating system or the settings of the application, the default value and dynamic adjustment behavior of the TCP window size can be affected.

Therefore, the TCP window size is affected by multiple factors such as the receiver's window size, bandwidth and delay, congestion control, network equipment, operating system, and application.