分类: OI路程

  • [Asio] 学习笔记1. 初识asio和tcp

    打算基于asio写多种序列化库的测评,在底层用同一个asio构造函数的方式,然后上层测试脚本里切换序列化的实现。
    但是最开始按着demo写逻辑就出现了问题,我想先纯面向过程,就没像demo里写一个connection类,然后就探究到一直会闪退的问题。

    最后定位到时ip::tcp::socket析构的时候会断开连接。

    socket的析构会断开连接

    socket的大概是这样的结构:

    typedef basic_stream_socket<tcp> socket;
    template <typename Protocol, typename Executor>
    class basic_stream_socket
      : public basic_socket<Protocol, Executor>;
    {};
    
    template <typename Protocol, typename Executor>
    class basic_socket: public socket_base
    {
    // ....
      ~basic_socket()
      {
      }
    
    #if defined(BOOST_ASIO_WINDOWS_RUNTIME)
      detail::io_object_impl<
        detail::null_socket_service<Protocol>, Executor> impl_;
    #elif defined(BOOST_ASIO_HAS_IOCP)
      detail::io_object_impl<
        detail::win_iocp_socket_service<Protocol>, Executor> impl_;
    #elif defined(BOOST_ASIO_HAS_IO_URING_AS_DEFAULT)
      detail::io_object_impl<
        detail::io_uring_socket_service<Protocol>, Executor> impl_;
    #else
      detail::io_object_impl<
        detail::reactive_socket_service<Protocol>, Executor> impl_;
    #endif
    };

    大概是这样的关系,虽然basic_socket, basic_stream_socket和tcp都没有在析构函数里做逻辑。但是实际实现操作系统连接句柄的impl_的析构函数里有做逻辑的,而且实现的方式还挺巧妙。
    Windows的io_uring_socket_service和Linux的reactive_socket_service都没有在析构里做逻辑,这一部分是在detail::io_object_impl里做的。

    template <typename IoObjectService,
        typename Executor = io_context::executor_type>
    class io_object_impl
    {
    public:
      typedef IoObjectService service_type;
      // Construct an I/O object using an executor.
      explicit io_object_impl(int, const executor_type& ex)
        : service_(&boost::asio::use_service<IoObjectService>(
              io_object_impl::get_context(ex))),
          executor_(ex)
      {
        service_->construct(implementation_);
      }
    
      // Destructor.
      ~io_object_impl()
      {
        service_->destroy(implementation_);
      }
    
    private:
      // The service associated with the I/O object.
      service_type* service_;
    };

    也就是io_object_impl本身实现的是IoObjectService的生命周期管理,对操作系统的io对象进行统一的封装,给上层提供统一的接口。然后通过模板类可以切换实际实现的方式。

    同时如小标题所示,ip::tcp::socket这类对象在析构的时候会断开连接,所以在asio实际使用过程中,一定要抓住socket的生命周期。

    ip::tcp::socket

    顺便深入看一下tcp的连接实现细节,我们以Linux的视角看一下实现细节。

    socket_base

    我们从最底层看起,basic_socket继承自socket_base,socket_base是一个定义了全双工半双工状态,当前等待状态的抽象类。它的抽象体现在析构函数实现在protetecd里,只有子类对象可以被析构。

    class socket_base
    {
    public:
      /// Different ways a socket may be shutdown.
      enum shutdown_type
      {
    #if defined(GENERATING_DOCUMENTATION)
        /// Shutdown the receive side of the socket.
        shutdown_receive = implementation_defined,
    
        /// Shutdown the send side of the socket.
        shutdown_send = implementation_defined,
    
        /// Shutdown both send and receive on the socket.
        shutdown_both = implementation_defined
    #else
        shutdown_receive = BOOST_ASIO_OS_DEF(SHUT_RD),
        shutdown_send = BOOST_ASIO_OS_DEF(SHUT_WR),
        shutdown_both = BOOST_ASIO_OS_DEF(SHUT_RDWR)
    #endif
      };
      // ....
    protected:
      /// Protected destructor to prevent deletion through this type.
      ~socket_base()
      {
      }
    };

    basic_socket

    template <typename Protocol, typename Executor>
    class basic_socket
      : public socket_base
    {
      detail::io_object_impl<
        detail::reactive_socket_service<Protocol>, Executor> impl_;
    };

    这个对象是对套接字做的一个高级抽象,类似于Linux里万物都是socket,可以read and write,具体的上层协议本身是定义在Protocol里面,Protocol包含协议本身以及endpoint,也就是地址。

    例如TCP的endpoint就是IP和地址,感觉如果未来KCP或者其他协议,可以直接定义一个新的endpoint类,增加多个channel就能实现很多东西,没必要用多个实际上的操作系统套接口?
    这些实际操作系统的实现又落地在impl_里,impl_实际上是一个io_object,不同的系统会是不同的实现,但是保持统一的对外接口,大概如下图:
    file

    我们从最底下向上看,在每个操作系统底层其实有两个部分,service_和implement_,他们互为一组向上和向下的关系抽象,implement_是service_类里的一个struct,主要包含该操作系统API下的资源细节,通常包含套接口句柄,上层协议类型,以及其他的一些数据。
    例如在Linux下,所有的socket都是用int类型的一个句柄,无论是Tcp还是文件还是Udp协议都是同一个句柄。所以implement_里存了套接口以及具体的Tcp还是Udp协议。
    service_则是对操作系统的API提供的一层service抽象,将不同的操作系统的IO接口提供成统一的API,这里实现了创建、连接、收发消息和关闭连接。
    而整个service_会被basic_socket用作操作系统无关的io对象的实现,而基于这些,basic_socket向上层提供了连接和异步的基本能力,创建、管理、异步等待等…
    再进一步basic_stream_socket则是向上层提供了进一步的读写能力。

    本次就先读到这里吧。

    End.

  • 用python理解C++20协程的设计

    C++20拥有一个全新的特性:协程。

    我来从python的角度来解释C++这个特性设计与其他语言的不同,目的以及意义。

    协程是一种可以挂起和恢复执行的函数。C++20协程跟python的生成器是很相似的,如果函数中出现了co_yield, co_return, co_await,那么这个函数就是协程函数。而协程的本质就是将一个函数拆分成多个不能控制执行顺序,但是可以控制执行时机的语言结构。

    对普通函数而言,执行一个函数是开始运行你的逻辑;但是对于协程来说,执行协程函数会先创建一个协程对象,但是是否开始执行还是挂起是视情况而定的。

    例如这个python代码:

    def hello():
        print("Start run")
        ret = yield2
        print("After suspend", ret)
        yield3
        print("After Suspend")
    
    def main():
        generator=hello()
        print(generator)
        ret1 = next(generator)
        print("ret1: ", ret1)
        ret2 = generator.send(23)
        print("ret2: ", ret2)
        generator.send(23)

    在这里hello就是一个协程函数,执行之后会获得一个generator,对generator执行send或者next才会开始真正的执行协程逻辑,从头或者从上次执行的地方一直直行到下一个yield,然后再挂起返回给外面。

    python的生成器跟C++协程很像,都是无栈协程,但是C++的更复杂,因为C++是需要自定义协程对象。
    例如这个简单的C++逻辑:

    TaskCoroutine task_func() {
        std::cout << "task first run" << std::endl;
        co_yield 6;
        std::cout << "---before await task2---" << std::endl;
        co_await task2();
        std::cout << "task resume" << std::endl;
        co_return 3;
    }
    
    int main() {
        std::cout << "Before task_func" << std::endl; 
        TaskCoroutine load_task = task_func();
        std::cout << "After task_func" << std::endl;
        load_task.resume();
        std::cout << "After resume" << std::endl;
        return 0;
    }

    这里因为有co_yield,所以task_func是一个协程函数,但是跟python不同,C++需要定义携程的返回类型,是一个自定义类型,代表的这个携程的Task或者Coroutine。

    这个类型类型必须包含promise_type名字的PromiseType类,例如:

    struct TaskCoroutine
    {
        using promise_type = PromiseType;
    }

    没有这个那编译就会异常,感觉这个是类似于C++20的概念约束做的。

    promise_type又是另外一个约束的类,必须拥有几个必须定义的函数,以及几个可选定义的函数:

    struct PromiseType {
        PromiseType()
        {
            std::cout << "PromiseType" << std::endl;
        }
        TaskCoroutine get_return_object() {
            std::cout << "get_return_object" << std::endl;
            return TaskCoroutine{std::coroutine_handle<PromiseType>::from_promise(*this)};
        }
        std::suspend_never initial_suspend() noexcept {
            std::cout << "initial_suspend" << std::endl;
            return {};
        }
        Awaiter<true> final_suspend() noexcept {
            std::cout << "final_suspend" << std::endl;
            return {};
        }
        void unhandled_exception() {
            std::cout << "unhandled_exception" << std::endl;
        }
        std::suspend_always yield_value(int x) noexcept {
            std::cout << "yield_value" << std::endl;
            return {};
        }
        void return_value(int x) noexcept {
            std::cout << "return_value" << std::endl;
        }
    };

    剩下的内容实在是不想写了,看我的视频吧:
    https://www.bilibili.com/video/BV1H66aYTE84

  • SGU 101 Domino 翻译 题解

    101. 骨牌
    时间限制:0.5s
    内存限制:4096KB

      

  • tyvj 字符串的展开 解题报告

      纯水题,竟然花了我好几天的时间,真是无聊,我写了好久的代码!这个情况应付不了a-b-c,我的会转变成ab-c,唉,不解释不解释。很水,自己做吧,上代码(我的代码分层的思想可以参考一下,可能有点OO性质):

    (代码等下发)

  • RQNOJ 47 [NOIP2003]神经网络

    算法本质:SPFA 算法描述:网上有一些人的代码是错的,只怪NOIP这种破竞赛的难度太低,数据太差,导致他们都可以溜过去了,但是有不少人的代码都是不能够AC的代码,他们利用图的进度来判断是否能够加入SPFA的列队,那么特殊情况,当有一个神经节点无法发送信号时,它后面的所有节点不都死翘翘了,迟迟不能进入列队,你们可以测试一下这一组数据:de> 5 5 1 0 0 1 0 0 0 0 0 0 1 2 1 1 3 1 2 4 1 3 4 1 4 5 1de>   思路其实还是很简单的,就是一层一层的枚举,当入读为0就入列队,如果c[i]<0 ON code lang="C">#include #include #define MAX 200 int n, p; int f[MAX]; int map[MAX][MAX]; int link[MAX][MAX]; int lenth[MAX], in[MAX]; void add(int a, int b, int c) { link[a][lenth[a]] = b; map[a][lenth[a]] = c; lenth[a]++; in[b]++; } int queue[MAX]; int end, head; void enqueue(int i) { queue[end++] = i; } int exqueue(void) { return queue[head++]; } int main(int argc, char *argv[]) { int t, s, l; int i; scanf("%d%d", &n, &p); for(i = 0; i 0){ enqueue(i); }else{ f[i] = -t; } } for(i = 0; i 0){ printf("%d %d\n", i + 1, f[i]); l = 0; } } if(l){ printf("NULL\n"); } return 0; } de>

  • USACO 3.4.4 Raucous Rockers 解题报告

    题目本质:动态规划?枚举?都像 算法描述:用f[i][j][k] 代表第i张碟子装了长度为j的歌, 而且最后一首是k。具体的方程看代码吧 复杂度:时间O(n^4), 空间O(n^3) / LANG: C ID: yylogoo1 PROG: rockers / #include #include #define MAX 21 int num[MAX]; int f[MAX][MAX][MAX]; int ans; int n, t, m; int main(int argc, char *argv[]) { int i, j, k, l; freopen("rockers.in", "r", stdin); freopen("rockers.out", "w", stdout); scanf("%d%d%d", &n, &t, &m); for(i = 1; i f[i][j + num[l]][l]){ f[i][j + num[l]][l] = f[i][j][k] + 1; } }else{ if(f[i][j][k] + 1 < f[i + 1][num[l]][l]){ f[i + 1][num[l]][l] = f[i][j][k] + 1; } } } if(ans

  • SGU 105 Div 3 解题

    算法本质:数学 算法描述:有这么一条数学公式,小学学的,把所有位数上的数加起来,如果能被三整除那么这个数就能被三整除,那么就很方便了,因为题目是相邻的数字相乘,那么题目所描述的数列每隔3个就会有2个能被3整出。 复杂度:时间&空间:O(1) #include #include int num[3] = {0, 0, 1}; int main(int argc, char argv[]) { int n; scanf("%d", &n); printf("%d\n", n / 3 2 + num[n % 3]); return 0; }